Continuation passing macros in Lisp from scratch (Part 2)
In last part, we started building the intuition towards Python-like yield function. We wrote a yield function which basically appends given value to a global list. Finally the surrounding function returned a lambda to get values from this global list.
There are 3 problems in this approach:
- We need to know implementation details and add code to retrieve values from implementation. i.e. it is not abstracted.
- Expressions are evaluated when adding the value to global list, not at the time of retrieval
- All yield calls are evaluated before returning value extractor lambda. So, we cannot have an infinite generator with this approach.
Let’s iterate to solve these problems.
Step 4: add values to global list one by one
In Step 3, call to fun2 evaluated all yields before returning. So by the time fun2 returned, all values were ready in global *state*. We want a lazy approach where values are evaluated only when required.
Again, let’s try a manual approach first before writing a function to do so. Let’s say we have functions f1, f2, f3, f4 and f5 that we want to evaluate one after other, lazily. Since functions are first class objects, we can simply append function instead of value to the global *state*. Here is the code to do that:
(defvar *state* '())
; using named functions
(defun f1 ()
(setf *state* (append *state* (list #'f2)))
1)
(defun f2 ()
(setf *state* (append *state* (list #'f3)))
3)
(defun f3 ()
(setf *state* (append *state* (list #'f4)))
5)
(defun f4 ()
(setf *state* (append *state* (list #'f5)))
7)
(defun f5 ()
11)
(defun fun1 ()
(setf *state* '())
(setf *state* (append *state* (list #'f1)))
(lambda ()
(let ((f (pop *state*)))
(funcall f))))
(setq var1 (fun1))
(funcall var1)
(funcall var1)
(funcall var1)
(funcall var1)
(funcall var1)
Here, f1 appends f2 to *state*, f2 appends f3 and so on. fun1 appends f1 and returns a lambda to pop from *state* and execute function.
Problem with this approach is hard coding the next function call within current function. i.e. f1 explicityly adds f2. To avoid this, we can simply pass the next function to execute as argument.
Passing body to yield
Here is the code to do this:
(defun yield (ret &rest body)
(push (lambda () (quote body)
(1+ ret))
*state*))
(defun feval ()
(let ((fun (pop *state*)))
(funcall fun)))
(defun main ()
(setf *state* '())
(yield 0
(yield 1
(yield 3
(yield 5
(yield 7
(yield 11 0))))))
#'feval)
(funcall out) ; => 1
(funcall out) ; => 2
(funcall out) ; => 4
(funcall out) ; => 5
(funcall out) ; => 6
(funcall out) ; => 12
yield takes 2 args, a return value and function body to execute next. It packages this function body in a lambda and appends to *state*. feval pops function from *state* and executes it. Note, since we are adding lambda in-to-out but want to execute out-to-in, we must push to reverse the order.
Step 5: Convert to macro
Let’s convert above yield function a macro.
(defvar *state* '())
(defmacro yield2 (&body body)
`(setq *state* (append *state* (list (lambda () ,@body)))))
(defun test-yield2 ()
(setq *state* '())
(print "before")
(yield2 (print "yield 1") 1)
(yield2 (print "yield 2") 2)
(yield2 (yield2 "nested yield") "outer yield")
(print "yld complete")
(print *state*)
(print (funcall (pop *state*)))
(print (funcall (pop *state*)))
(print (funcall (pop *state*)))
(print (funcall (pop *state*))))
(test-yield2)
Output:
"before"
"yld complete"
(#<FUNCTION (LAMBDA () :IN TEST-YIELD2) {5367FA4B}>
#<FUNCTION (LAMBDA () :IN TEST-YIELD2) {5367F9EB}>
#<FUNCTION (LAMBDA () :IN TEST-YIELD2) {5367F8DB}>)
"yield 1"
1
"yield 2"
2
"outer yield"
"nested yield"
"nested yield"
Explanation:
yield2 macro is straightforward. We have *state* list, we are appending lambda to it.
Content of this lambda is ,@body which is basically all body expanded from list (*list in Python).
test-yield2 calls macro. Note that actual print call in macro is executed during funcall. Which means that yield2 will simply expand and append lambda to *state*. When we execute this lambda then print is executed.
This also explains why we are using append instead of push. For nested yield2, lambda append expression is expanded but not executed. It will be executed during execution of outer lambda. This fine distinction is important to understand difference between macros and functions.
Step 6: Save context to global variable instead of list
This is a simpler step, but takes us much closer to Paul’s macros as well as original Scheme’s call-cc system.
(defvar *cont* 0)
(defmacro yield (expr &body body)
`(let ((*cont* #'(lambda () ,@body)))
,expr))
(defvar *fun-stack*)
(defun test-yield ()
(print "before")
(yield (funcall *cont*) (print "yield 1") 1)
(yield (setq a1 *cont*) (print "yield 2") 2)
(print "before a1 funcall")
(funcall a1)
(print "after a1 funcall")
(setq *fun-stack* '())
(yield (push *cont* *fun-stack*)
(yield (push *cont* *fun-stack*) "nested yield")
"outer yield")
(print (funcall (pop *fun-stack*)))
(print (funcall (pop *fun-stack*)))
(print "yld complete"))
Output:
"before"
"yield 1"
"before a1 funcall"
"yield 2"
"after a1 funcall"
"outer yield"
"nested yield"
"yld complete"
"yld complete"
Explanation
This one is actually easy to understand based on Step 5. Instead of pushing to a global list, we are simply setting value of a global variable *cont* with context-capture (yield function body). And we are passing expr which tells us how to use this *cont*.
In first call (yield (funcall *cont*) (print "yield 1") 1) we simply call lambda immediately after yield. In second call (yield (setq a1 *cont*) (print "yield 2") 2) we save this context into another variable, which can be called anytime later.
What is interesting, is now our code resembles On Lisp lambdas. Here are lambdas mentioned in the book:
(defmacro =bind (parms expr &body body)
‘(let ((*cont* #’(lambda ,parms ,@body))) ,expr))
(defmacro =values (&rest retvals)
‘(funcall *cont* ,@retvals))
Notice how =bind resembles our yield and how =values resembles (funcall *cont*) expression passed in first call.
In Part 3 we’ll implement lazy Tree DFS using our yield macro.