Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Building SICMUtils, the Atelier of Abstractions

Building SICMUtils, the Atelier of Abstractions

These slides are from my second talk at the 2022 European Lisp Symposium in Porto, Portugal: https://european-lisp-symposium.org/2022/index.html

The source code for these slides and the demos in the talk live at https://github.com/sritchie/programming-2022.

Abstract:
SICMUtils is a Clojure library designed for interactive exploration of mathematical physics. It is simultaneously a work of persuasive writing, a collection of essays on functional pearls and computational ideas, a stable of workhorse functional abstractions, and a practical place to work and visualize algorithms and physical systems, on a server or in the browser.

How do you build a library like this? This talk will go through the architecture of SICMUtils, based on many of the ideas of "additive programming" from Gerald Sussman and Chris Hanson's latest book, Software Design for Flexibility. We'll look at surprising examples of the system becoming easier to extend over time. Clojure's embrace of its host platform lets us use the best modern work in Javascript for visualization, while keeping the horsepower of our servers for real work. Lisp's particular elegance will shine throughout.

Sam Ritchie

March 23, 2022
Tweet

More Decks by Sam Ritchie

Other Decks in Programming

Transcript

  1. 9

  2. 12

  3. MANY ENVIRONMENTS REPL Nextjournal org-mode, these slides Clojure, Clojurescript Zeugma,

    any Java environment Roam Research or Obsidian, etc TexMacs 13
  4. 16

  5. 17

  6. NUMERICS full numeric tower in JavaScript, up to Complex dual

    numbers modular arithmetic types Quaternions, beyond 18
  7. EXAMPLES OF GENERICS [sicmutils.generic * + - / divide negate

    negative? infinite? invert abs sqrt quotient remainder modulo floor ceiling integer-part fractional-part 1 2 3 4 5 6 7 8 9 10 expt 11 exp exp2 exp10 12 log log2 log10 13 gcd lcm 14 exact-divide 15 square cube 16 20
  8. EXAMPLES OF GENERICS [sicmutils.generic * + - / divide negate

    negative? infinite? invert abs sqrt quotient remainder modulo floor ceiling integer-part fractional-part 1 2 3 4 5 6 7 8 9 10 expt 11 exp exp2 exp10 12 log log2 log10 13 gcd lcm 14 exact-divide 15 square cube 16 make-rectangular make-polar real-part imag-part magnitude angle conjugate transpose trace determinant dimension dot-product inner-product outer-product cross-product partial-derivative Lie-derivative solve-linear solve-linear-left solve-linear-right simplify] square cube 16 cos sin tan 17 cot sec csc 18 atan 19 acos asin acot asec acsc 20 cosh sinh tanh coth sech csch 21 acosh asinh atanh acoth asech acsch 22 sinc tanc sinhc tanhc 23 24 25 26 27 28 29 30 31 20
  9. SYMBOLIC COMPUTATION (+ (square (sin 'x)) (square (cos 'x))) (+

    (expt (sin x) 2) (expt (cos x) 2)) (simplify (+ (square (sin 'x)) (square (cos 'x)))) 1 21
  10. "LITERALS", IE, SYMBOLIC-LIKE THINGS: literal numbers literal functions symbols, or

    literal-number literal vectors, matrices quantum states, bra, ket 23
  11. PATTERN MATCHING DSL (rule (/ (* ??u ?x ??v) (sqrt

    ?x)) => (* ??u (sqrt ?x) ??v)) 24
  12. PATTERN COMBINATORS (let [r (while (fn [l _] (< l

    100)) (rule ?x => (? #(inc (% '?x)))))] (= 101 (r 12))) 25
  13. PATTERN COMBINATORS (let [r (while (fn [l _] (< l

    100)) (rule ?x => (? #(inc (% '?x)))))] (= 101 (r 12))) Literal Derivative: (choice (rule (D ?f) => ((expt D 2) ?f)) (rule ((expt D ?n) ?f) => ((expt D (? #(inc (% '?n)))) ?f)) (rule ?f => (D ?f))) 25
  14. RENDERERS Infix: TeX: (->infix (+ (square (sin 'eta)) (cube (tan

    'phi_2)))) sin²(η) + (tan(φ₂))³ (->TeX (+ (square (sin 'eta)) (cube (tan 'phi_2)))) {\sin}^{2}\left(\eta\right) + {\left(\tan\left({\phi}_2\right)\right)}^ 26
  15. RENDERERS JavaScript Source Renderer (println (->JavaScript (+ (square (sin 'eta))

    (cube (tan 'phi-2))))) function(eta, phi_2) { return Math.pow(Math.sin(eta), 2) + Math.pow(Math.tan(phi_2), 3); } 27
  16. FUNCTION COMPILATION (defn my-fn [x y] (+ x (sin y)

    (square (cos 'x)) (square (sin 'x)) (cube (sin y)))) (binding [*mode* :source] (compile-fn my-fn)) (clojure.core/fn [x45929 x45930] (clojure.core/let [G0000000000000000 (Math/sin x45930)] (clojure.core/+ (clojure.core/* -1.0 G0000000000000000 (Math/pow (Math/cos x45930) 2.0)) x45929 (clojure.core/* 2.0 G0000000000000000) 1.0))) 28
  17. FUNCTIONAL NUMERICAL METHODS Univariate and multivariate minimization Polynomial and RF

    interpolation Richardson Extrapolation (FUNCTIONAL!) Numerical quadrature numeric derivatives Native ODE solvers … 29
  18. TYPE VS KIND (map kind [(make-rectangular 1 2) 10 {:k

    "v"}]) (:sicmutils.complex/complex java.lang.Long clojure.lang.PersistentArrayMap) 35
  19. CONSTRAINED EXTENSIBILITY (derive ::square-matrix ::matrix) (derive ::column-matrix ::matrix) (derive ::row-matrix

    ::matrix) (derive ::matrix ::f/cofunction) (defmethod g/mul [::matrix ::matrix] [a b] (mul a b)) (defmethod g/mul [::v/scalar ::matrix] [n a] (scalar*matrix n a)) (defmethod g/mul [::matrix ::v/scalar] [a n] (matrix*scalar a n)) 36
  20. STICK WITH CLOJURE Different Environments, CLJS Small # of core

    data structures ~Everything is Immutable 37
  21. DSL, PATTERN MATCHING: (defn unary-elimination [& ops] (let [op-set (into

    #{} ops)] (ruleset ((? _ op-set) ?x) => ?x))) (require '[pattern.rule :as r :refer [ruleset =>]]) 1 2 3 4 5 6 7 (defn constant-elimination [op constant] 8 (letfn [(filter-constants [{xs '??xs}] 9 (remove #{constant} xs))] 10 (ruleset 11 (~op ??xs) => (~op (?? ~filter-constants))))) 12 13 (defn constant-promotion [op constant] 14 (ruleset 15 (~op ~constant) => ~constant 16 40
  22. DSL, PATTERN MATCHING: (defn unary-elimination [& ops] (let [op-set (into

    #{} ops)] (ruleset ((? _ op-set) ?x) => ?x))) (require '[pattern.rule :as r :refer [ruleset =>]]) 1 2 3 4 5 6 7 (defn constant-elimination [op constant] 8 (letfn [(filter-constants [{xs '??xs}] 9 (remove #{constant} xs))] 10 (ruleset 11 (~op ??xs) => (~op (?? ~filter-constants))))) 12 13 (defn constant-promotion [op constant] 14 (ruleset 15 (~op ~constant) => ~constant 16 (defn constant-elimination [op constant] (letfn [(filter-constants [{xs '??xs}] (remove #{constant} xs))] (ruleset (~op ??xs) => (~op (?? ~filter-constants))))) (let [op set (into #{} ops)] 4 (ruleset 5 ((? _ op-set) ?x) => ?x))) 6 7 8 9 10 11 12 13 (defn constant-promotion [op constant] 14 (ruleset 15 (~op _ ~constant) => ~constant 16 (~op ~constant _) => ~constant)) 17 18 (def my-simplify 19 (r/rule-simplifier 20 40
  23. DSL, PATTERN MATCHING: (defn unary-elimination [& ops] (let [op-set (into

    #{} ops)] (ruleset ((? _ op-set) ?x) => ?x))) (require '[pattern.rule :as r :refer [ruleset =>]]) 1 2 3 4 5 6 7 (defn constant-elimination [op constant] 8 (letfn [(filter-constants [{xs '??xs}] 9 (remove #{constant} xs))] 10 (ruleset 11 (~op ??xs) => (~op (?? ~filter-constants))))) 12 13 (defn constant-promotion [op constant] 14 (ruleset 15 (~op ~constant) => ~constant 16 (defn constant-elimination [op constant] (letfn [(filter-constants [{xs '??xs}] (remove #{constant} xs))] (ruleset (~op ??xs) => (~op (?? ~filter-constants))))) (require '[pattern.rule :as r :refer [ruleset =>]]) 1 2 (defn unary-elimination [& ops] 3 (let [op-set (into #{} ops)] 4 (ruleset 5 ((? _ op-set) ?x) => ?x))) 6 7 8 9 10 11 12 13 (defn constant-promotion [op constant] 14 (ruleset 15 (~op ~constant) => ~constant 16 (defn constant-promotion [op constant] (ruleset (~op _ ~constant) => ~constant (~op ~constant _) => ~constant)) (letfn [(filter constants [{xs ??xs}] 9 (remove #{constant} xs))] 10 (ruleset 11 (~op ??xs) => (~op (?? ~filter-constants))))) 12 13 14 15 16 17 18 (def my-simplify 19 (r/rule-simplifier 20 (unary-elimination '+ '*) 21 (constant-elimination '+ 0) 22 (constant-elimination '* 1) 23 (constant-promotion '* 0))) 24 40
  24. DSL, PATTERN MATCHING: (defn unary-elimination [& ops] (let [op-set (into

    #{} ops)] (ruleset ((? _ op-set) ?x) => ?x))) (require '[pattern.rule :as r :refer [ruleset =>]]) 1 2 3 4 5 6 7 (defn constant-elimination [op constant] 8 (letfn [(filter-constants [{xs '??xs}] 9 (remove #{constant} xs))] 10 (ruleset 11 (~op ??xs) => (~op (?? ~filter-constants))))) 12 13 (defn constant-promotion [op constant] 14 (ruleset 15 (~op ~constant) => ~constant 16 (defn constant-elimination [op constant] (letfn [(filter-constants [{xs '??xs}] (remove #{constant} xs))] (ruleset (~op ??xs) => (~op (?? ~filter-constants))))) (require '[pattern.rule :as r :refer [ruleset =>]]) 1 2 (defn unary-elimination [& ops] 3 (let [op-set (into #{} ops)] 4 (ruleset 5 ((? _ op-set) ?x) => ?x))) 6 7 8 9 10 11 12 13 (defn constant-promotion [op constant] 14 (ruleset 15 (~op ~constant) => ~constant 16 (defn constant-promotion [op constant] (ruleset (~op ~constant) => ~constant (require '[pattern.rule :as r :refer [ruleset =>]]) 1 2 (defn unary-elimination [& ops] 3 (let [op-set (into #{} ops)] 4 (ruleset 5 ((? _ op-set) ?x) => ?x))) 6 7 (defn constant-elimination [op constant] 8 (letfn [(filter-constants [{xs '??xs}] 9 (remove #{constant} xs))] 10 (ruleset 11 (~op ??xs) => (~op (?? ~filter-constants))))) 12 13 14 15 16 (def my-simplify (r/rule-simplifier (unary-elimination '+ '*) (constant-elimination '+ 0) (constant-elimination '* 1) (constant-promotion '* 0))) (letfn [(filter constants [{xs ??xs}] 9 (remove #{constant} xs))] 10 (ruleset 11 (~op ??xs) => (~op (?? ~filter-constants))))) 12 13 (defn constant-promotion [op constant] 14 (ruleset 15 (~op _ ~constant) => ~constant 16 (~op ~constant _) => ~constant)) 17 18 19 20 21 22 23 24 40
  25. (my-simplify '(cos (+ 0 (+ 0 12 0) (* 1

    x)))) (cos (+ 12 x)) 41
  26. MULTI-STAGE PROGRAMMING (defn my-fn [x y] (+ x (sin y)

    (square (cos 'x)) (square (sin 'x)) (cube (sin y)))) (binding [*mode* :source] (compile-fn my-fn)) (clojure.core/fn [x45929 x45930] (clojure.core/let [G0000000000000000 (Math/sin x45930)] (clojure.core/+ (clojure.core/* -1.0 G0000000000000000 (Math/pow (Math/cos x45930) 2.0)) x45929 (clojure.core/* 2.0 G0000000000000000) 1.0))) 43
  27. CLOJURE COMMUNITY Sussman et. al. Colin Smith Clerk: Martin Kavalar,

    Jack Rusher, Nextjournal team maria.cloud SCI, CLJ-Kondo: Michiel Borkent (@borkdude) 44
  28. HARD? No types so far what's the right way to

    introspect the library? Context 46
  29. THANKS! Sam Ritchie, Mentat Collective Slides, Demos live at @sritchie

    https://github.com/sritchie/programming-2022 50