Re: Continuation examples (was Re: So, what the heck is a continuation anyway?)

[Guy Steele - Sun Microsystems Labs <address@hidden>]

   From: Luke Gorrie <luke@bluetail.com>
   Date: 11 Dec 2001 17:20:26 +0100
   
   Guy Steele - Sun Microsystems Labs <gls@labean.East.Sun.COM> writes:
   
   > Okay, just for fun, I upgraded the toy "FOO interpreter" of my
   > previous messages:
   
   Hello Guy, nice program :-)

Thanks.

   > 	((eq (first exp) 'LETREC)
   > 	 (let ((newenv (pairlis (mapcar #'first (second exp))
   > 				(make-list (length (second exp)))
   > 				env)))
   > 	   (@evletrec (second exp) newenv (third exp) newenv cont)))
   
   [...]
   
   > (defun @evletrec (bindings slots body env cont)
   >   (cond ((null bindings) (@eval body env cont))
   > 	(t (@eval (second (first bindings)) env
   > 		  #'(lambda (fn)
   > 		      (rplacd (first slots) fn)  ;the side effect that "ties the 
knot"
   > 		      (@evletrec (rest bindings) (rest slots) body env 
cont))))))
   
   There's a bug here: evletrec assumes `slots' will be in the same order
   as `bindings', but `pairlis' can muck that up. On my computer with
   CLISP, the slots get reversed and the "evil" program becomes
   _diabolical_ (`last' is invoked first).
   
   Can be fixed by changing the `pairlis' in @eval to `pairlis-forward':
   
     (defun pairlis-forward (keys values alist)
       (append (mapcar #'cons keys values) alist))

Yes, good catch!  My face is red.

   > The lessons here are:
   > (1) LETREC is not that difficult to add.
   > (2) Even toy, throwaway interpreters are vulnerable to feature creep.
   
   (3) Even toy, throwaway interpreters have to be ported.

(4) I should read the manual!  I foolishly relied on my memory of pairlis;
but CLTL clearly states that "The new pairs may appear in the resulting
a-list in any order".

Another fix is to use name lookup rather than relying on order:

(defun @evletrec (bindings body env cont)
  (cond ((null bindings) (@eval body env cont))
	(t (@eval (second (first bindings)) env
		  #'(lambda (fn)
		      (rplacd (assoc (first (first bindings)) env) fn)
		      (@evletrec (rest bindings) body env cont))))))

and the code in @eval is now simply:

        ...
	((eq (first exp) 'LETREC)
	 (@evletrec (second exp)
		    (third exp)
		    (pairlis (mapcar #'first (second exp))
			     (make-list (length (second exp)))
			     env)
		    cont))
	...

--Guy