;;; LISP and Scheme pioneered the concept of _closures_: packaging the memory state of a ;;; function at the point of its dynamic creation, as a first-class programming ;;; language construct. ;;; So not only are LISP functions first-class values that can be passed around as ;;; arguments to other functions (most commonly, MAP, REDUCE, or other kinds of folds, ;;; as we'll see below, but so is the relevant state of the environment in which they ;;; are created. ;;; There was a great question in class: isn't the goal of functional programming to ;;; eliminate all state and side effects? To which the practical answer is, a lot ;;; of our mental modeling of real systems does include state. So we'd like a way ;;; to contain state and side effects on it in a tractable way: have only as much ;;; as needed, and represent it so that our compilers can reason about it. ;;; _Closures were a great step down this road._ ;; Let's see how lambdas and closures are implemented in eLisp. ;; These implementations are somewhat idiosyncratic, but they show what (lambda (x y) (+ x y)) (closure (t) (x y) (+ x y)) ; a "closure" appears. What is it? (type-of (lambda (x y) (+ x y))) cons ; unsurprisingly, a list ;; I'll define a convenience macro for seeing disassembly in this buffer ;; This came from reading "M-x find-function" of 'disassemble (defmacro disas (f) `(disassemble-internal ,f 2 nil)) disas (disas (lambda (x y) (+ x y))) doc: ... args: (arg1 arg2) 0 stack-ref 1 1 stack-ref 1 2 plus 3 return nil ;; This disassembly comes from interpreting the byte-compiled representation of ;; this lambda. This representation is described in https://nullprogram.com/blog/2014/01/04/ ;; ;; We can see this representation with BYTE-COMPILE. The constants vector, empty [] here, ;; is going to be the key to closures. It will represent the environment that is matched ;; up the the bytecode, making different closures have their private data. (byte-compile (lambda (x y) (+ x y))) #[514 "\\\207" [] 4 "(fn X Y)"] ;; The funny-looking string is the actual bytecode sequence DISAS shows. We can cross- ;; reference them against the bytecode manual, https://rocky.github.io/elisp-bytecode.pdf, ;; Section 5 "Opcode table". ;; The string shows a mix of ASCII code where printable, and \xxx in octal where xxx are ;; octal digits. ^A depicts \001, (opcode stack-ref 1), \\ depicts \134 (plus), \207 is return. ;; The above code referenced only the arguments passed to it (and pushed at the bottom ;; of the stack when the lambda is called). What if the lambda code referenced some other ;; values, like those local symbols created by LET? Then magic happens: (defun make-counter () (let ((count 0)) ;; referenced by lambda's body (lambda () (setq count (1+ count))))) make-counter (setq a (make-counter)) (closure ((count . 0)) nil (setq count (1+ count))) ; ^^^^^^^^^^-- the closure expression now includes a variable (funcall a) 1 (funcall a) 2 (funcall a) 3 a (closure ((count . 3)) nil (setq count (1+ count))) ; note the change in the bound variable ;; Making another counter will create a different memory cell entirely: (setq b (make-counter)) (closure ((count . 0)) nil (setq count (1+ count))) (funcall b) 1 (funcall a) 4 ;; Disassembly helps a little: the count value is the CAR of a CONS cell referenced ;; from the constants vector of the bytecode vector created by BYTE-COMPILE (disas a) args: nil 0 constant (4) ;; this is a reference on the stack. Disassembler shows its current value 1 dup 2 car-safe 3 add1 4 setcar 5 return nil (disas b) args: nil 0 constant (1) ;; this is exactly the same bytecode as for A, the only difference is in the constants vector 1 dup 2 car-safe 3 add1 4 setcar 5 return nil ;; Note that the bytecode is exactly the same. It's only the constants vector that's different. (byte-compile a) #[0 "\300\211\242T\240\207" [(4)] 2] (byte-compile b) #[0 "\300\211\242T\240\207" [(1)] 2] (byte-compile (setq c (make-counter))) #[0 "\300\211\242T\240\207" [(0)] 2] (boundp 'a) t (boundp 'count) ; Count is elided from any compilation. It's just a position in the constants vector. nil ;;; Now let's see what MAKE-COUNTER is like: (defun make-counter () (let ((count 0)) (lambda () (setq count (1+ count))))) (byte-compile 'make-counter) #[0 "\300C\301\302\"\207" [0 make-closure #[0 "\300\211\242T\240\207" [V0] 2]] 4] ; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^-- internal LAMBDA; (byte-compile a) #[0 "\300\211\242T\240\207" [(4)] 2] (disas 'make-counter) args: nil 0 constant 0 1 list1 ; a CONS cell with the CAR pointing to 0 2 constant make-closure ; does most of the work! Check out its description. 3 constant args: nil 0 constant V0 1 dup 2 car-safe 3 add1 4 setcar 5 return 4 stack-ref 2 ; that's (0) 5 call 2 6 return nil ;;; See https://cosc59.gitlab.io/lisp/make-closure-log.txt for a detailed bytecode walkthrough. ;;; ---------- Let's see what the right kind of lambdas can do ----------------- ;;; Read the first half of https://www.cs.cornell.edu/courses/cs3110/2014sp/lectures/5/map-fold-map-reduce.html about Map and Reduce ;;; Read Structure and Evaluation of Computer Programs (SICP, https://web.mit.edu/6.001/6.037/sicp.pdf) ;;; Section 2.2 through p. 165 (p. 194 of the PDF). ;; We'll use Common Lisp style REDUCE. (require 'cl-lib) ; Common Lisp's REDUCE and other functions are available in eLisp as a library cl-lib ;; Some people say MAP is all you need for programming with collections (mapcar (lambda (x) (* x x)) (number-sequence 1 10)) (1 4 9 16 25 36 49 64 81 100) ; This is known as a left fold: (cl-reduce (lambda (x y) (print (list "+" x y)) ; this trace print will show us the order of applying LAMBDA (+ x y)) '(1 4 9 16 25 36 49 64 81 100)) ("+" 1 4) ("+" 5 9) ("+" 14 16) ("+" 30 25) ("+" 55 36) ("+" 91 49) ("+" 140 64) ("+" 204 81) ("+" 285 100) 385 ; This is known as the right fold: (cl-reduce (lambda (x y) (print (list "+" x y)) (+ x y)) '(1 4 9 16 25 36 49 64 81 100) :from-end t) ; start from the right ("+" 81 100) ("+" 64 181) ("+" 49 245) ("+" 36 294) ("+" 25 330) ("+" 16 355) ("+" 9 371) ("+" 4 380) ("+" 1 384) 385 ;; It turns out that REDUCE can be MAP, FILTER, MEMBER, and REVERSE with the right lambda ;; and direction. All it takes is supplying an initial value that the pairwise ;; lambda starts from. ;; Let's try with the initial value of an empty list, folding from the left: (cl-reduce (lambda (x xs) (print (list "step" xs x)) (cons x xs)) '(a b c d e f) :initial-value nil) ("step" a nil) ("step" b (nil . a)) ("step" c ((nil . a) . b)) ("step" d (((nil . a) . b) . c)) ("step" e ((((nil . a) . b) . c) . d)) ("step" f (((((nil . a) . b) . c) . d) . e)) ((((... . c) . d) . e) . f) ;; oops, this didn't go well. ;; The order of LAMBDA's arguments needs reversing. With it--- (cl-reduce (lambda (xs x) (print (list "step" xs x)) (cons x xs)) '(a b c d e f) :initial-value nil) ("step" nil a) ("step" (a) b) ("step" (b a) c) ("step" (c b a) d) ("step" (d c b a) e) ("step" (e d c b a) f) (f e d c b a) ; <--- we accidentally got the REVERSE via REDUCE! ;; Observe the pattern: one of the 2-arity LAMBDA's arguments is a list, starts with ;; the () empty list as initial value, the other iterates over the original list ;; What if we fold from the right using the same pattern? We got the identity! (cl-reduce (lambda (x xs) (print (list "step" xs x)) (cons x xs)) '(a b c d e f) :initial-value nil :from-end t) ("step" nil f) ("step" (f) e) ("step" (e f) d) ("step" (d e f) c) ("step" (c d e f) b) ("step" (b c d e f) a) (a b c d e f) ;; So now we can write a MAP function as a right fold: (defun mpcar (f ll) (cl-reduce (lambda (x xs) (cons (funcall f x) xs)) ll :initial-value nil :from-end t)) mpcar (mpcar (lambda (x) (* x x)) nil) nil (mpcar (lambda (x) (* x x)) (number-sequence 1 10)) (1 4 9 16 25 36 49 64 81 100) ;; We can write a filter function, too. There's just one small trick compared to ;; MAP: MAP always adds a CONS cell, FILTER only does so for elements that pass ;; the test, otherwise passes on the already accumulated list or the initial () ;; if none matched so far. (defun filt (f ll) (cl-reduce (lambda (x xs) (if (funcall f x) (cons x xs) ; CONS xs)) ; ..or previous list ll :initial-value nil :from-end t)) filt (filt #'evenp nil) nil (filt t nil) ;; even this works although it won't with any non-empty list nil (filt #'evenp (number-sequence 1 10)) (2 4 6 8 10) (filt #'oddp (number-sequence 1 10)) (1 3 5 7 9) (filt (lambda (x) (> x 5)) (number-sequence 1 10)) (6 7 8 9 10) ;; And so we have FILTER via fold. ;; MEMBER is an interesting function to implement with a fold. Note that ;; it returns not the matching element but rather the CONS cell of ;; the original list that has the first occurrence of the matching element, ;; _not_ the element itself: (member 64 '(1 4 9 16 25 36 49 64 81 100)) (64 81 100) (member 2 '(1 4 9 16 25 36 49 64 81 100)) ; it's nil otherwise nil ;;; Suggested exercise: implement MEMBER via REDUCE! ;;; Suggested exercise: make all of the above these tail-recursive. ;;; NOTE: Tail-recursion will be natural with left folds, right folds will be tricky. ;;; Look for more examples in https://cosc59.gitlab.io/lisp/everything-is-a-fold.el