Clojurians Log v2

Another practical downside shows up when you use a lot of higher order functions in real-world development: bugs get harder to track. When you’re data-oriented, you can see incorrect data as it flows through, but when your data is hidden inside functions definitions it’s much harder. That’s not an argument to completely avoid higher order functions. But it does make me cautious of taking them too far

SICP?

Sicp is the first place I saw something like it, but it is a general technique that can be used to emulate (or as a target for compilation) pattern matching over algebraic data types https://crypto.stanford.edu/~blynn/compiler/scott.html

Fascinating. Is there a practical scenario where something like this gives an elegant solution, or is it more just a mathematical thought exercise to see how far the abstraction can take you (which looks to be pretty far indeed, based on that link)?

Hard to say. There are downsides with recursive functions when you don't have proper tail call optimization into loops (like clojure). In that series of blog posts the author compiles a subset of Haskell to the lamba calculus, then compiles the lambda terms to SKI combinator terms and writes a vm for those. The vm allows for compiling to webassembly, and I think the vm for it won or got an honorable mention one year in the international obfuscated c code contest

Oh, actually there is a haskell library parsec, where at one point the maintainer removed a lot of pattern matching on results and replaced it with what he called continuation passing, which looked very similar and resulted in performance improvements

if anyone's interested this talk is a really great intro to combinator calculus (not just SKI but a whole flock of birds) https://www.youtube.com/watch?v=6BnVo7EHO_8

https://panicsonic.blogspot.com/2009/12/adventures-in-parsec.html?m=1 not exactly the same, but if you squint there is a through line

and a little exploratory code I wrote along with it:

(defn uncurry [f]
  (if-not (fn? f)
    f
    (fn*
      ([a] (uncurry (f a)))
      ([a b] (uncurry ((f a) b)))
      ([a b c] (uncurry (((f a) b) c)))
      ([a b c d] (uncurry ((((f a) b) c) d)))
      ([a b c d & more]
       (uncurry (reduce #(%1 %2) ((((f a) b) c) d) more))))))

(defmacro bird [params & body]
  {:pre [(vector? params) (<= 1 (count params))]}
  (let [[p & ps] (rseq params)]
    `(uncurry ~(reduce #(list 'fn* [%2] %1)
                 (list* 'fn* [p] body)
                 ps))))

(comment
  (let [f (uncurry (fn [x] (fn [y] (fn [z] (+ x y z)))))]
    [(f 1 2 3)
     ((f 1) 2 3)
     ((f 1 2) 3)
     (((f 1) 2) 3)])
  ;; => [6 6 6 6]
  
  (macroexpand '(bird [a b c] a))
  ;; => ( (fn* [a] (fn* [b] (fn* [c] a))))
  ,)

(defmacro defbird
  {:clj-kondo/lint-as 'clojure.core/fn}
  [bird-name doc & bird-tail]
  `(def ~bird-name ~doc (bird ~@bird-tail)))

;; 
(defbird S "Starling" [a b c] (a c (b c)))
(defbird K "Kestrel" [a b] a)
(defbird KI "Kite" [a b] b)
(defbird I "Ibis" [a] a)
(defbird B "Bluebird" [a b c] (a (c b)))
(defbird C "Cardinal" [a b c] (a c b))
(defbird W "Warbler" [a b] (a b b))
(def B₁ "Blackbird" (B B B))
(def B₂ "Bunting" (B B₁ B))
(defbird O "Owl" [a b] (b (a b)))

(K :yes :no) ;; => :yes
(KI :yes :no) ;; => :no
((K I) :yes :no) ;; => :no

squinting a bit at the tables it seems that Cons above is really the "Vireo" combinator λabc.cab - a bit of a puzzle what car and cdr correspond to though, they're sort of like wrapped versions of K and KI aha:

(defbird T "Thrush" [x f] (f x))
(defbird V "Vireo" [a b f] (f a b))

(let [Cons V
      car (T K)
      cdr (T KI)]
  [(car (Cons 1 2))
   (cdr (Cons 1 2))])
;; => [1 2]

https://git.sr.ht/~hiredman/lions/tree/master/item/src/com/manigfeald/comb.clj#L32 rewrites lambda terms into ski

=> 25

user=> (def Cons (fn [a b] (fn [f] (f a b))))
#'user/Cons
user=> (def car (fn [cell] (cell (fn [a b] a))))
#'user/car
user=> (def cdr (fn [cell] (cell (fn [a b] b))))
#'user/cdr
user=> (car (Cons 1 2))
1
user=> (cdr (Cons 1 2))
2
user=>