[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: So, what the heck is a continuation anyway?



If you speak Common Lisp, you might find the following
bit of code illuminating.  (If you speak Scheme but
not Common Lisp, then just delete or ignore all occurrences
of the strings "funcall " and "#'").

This is an interpreter for a tiny Scheme-like language
(I'll call it FOO) with just the following constructs:

	numeric literals
	variable names
	LAMBDA expressions
	IF
	function calls

and three built-in functions:

	+
	*
	CALL/CC

(I took the cheesy way out on defining the functions:
I just made undefined variables evaluate to themselves
and have the @apply function check for those names.
That's okay because the data domain of this language
is just numbers---there aren't any operations on symbols.)

I spelled the name of each functino with a leading "@" purely
to avoid conflict with the Common Lisp functions of the
same name.

You can evaluate an expression by typing at the Common Lisp
top level:

	(@eval '<expression> '() #'(lambda (x) x))

Note two things about this piece of code:

(1) Every call from one Common Lisp function to another is
a tail-call.  In other words, in effect I am not using the
Common Lisp stack at all to keep information about the state
of the FOO program being interpreted.

(2) Every LAMBDA expression in the code of the interpreter
is a continuation: it says what to do next when the call to
any given @-routine is "finished".

(3) Every @-routine takes a continuation "cont" and always
finishes either by calling cont (as a tail-call) or by
calling another @-routine (as a tail-call).

If you keep in mind that "#'" means roughly "allocate  (in the heap)
a closure for the following LAMBDA expression" and that a closure can
refer to lexical variables visible to the LAMBDA expression, you can see
that one continuation can know about another, which knows about another,
and so on; this chain is sometimes called the "control stack", but in
this implementation it's all in the heap.

Does this help?

--Guy

(defun @eval (exp env cont)
  (cond ((numberp exp) (funcall cont exp))
	((symbolp exp) (@lookup exp env cont))
	((eq (first exp) 'LAMBDA)
	 (funcall cont (list 'CLOSURE (second exp) (third exp) env)))
	((eq (first exp) 'IF)
	 (@eval (second exp) env
		#'(lambda (test)
		    (@eval (cond (test (second exp)) (t (third exp))) env 
cont))))
	(t (@eval (first exp) env
		  #'(lambda (fn)
		      (@evlis (rest exp) env
			      #'(lambda (args) (@apply fn args cont))))))))

(defun @lookup (name env cont)
  (cond ((null env) (funcall cont name))
	((eq (car (first env)) name) (funcall cont (cdr (first env))))
	(t (@lookup name (rest env) cont))))

(defun @evlis (exps env cont)
  (cond ((null exps) (funcall cont '()))
	(t (@eval (first exps) env
		  #'(lambda (arg)
		      (@evlis (rest exps) env
			      #'(lambda (args) (funcall cont (cons arg 
args)))))))))

(defun @apply (fn args cont)
  (cond ((eq fn '+) (+ (first args) (second args)))
	((eq fn '*) (* (first args) (second args)))
	((eq fn 'call/cc)
	 (@apply (first args) (list (list 'CONTINUATION cont)) cont))
	((atom fn) 'UNDEFINED-FUNCTION)
	((eq (first fn) 'CLOSURE)
	 (@eval (third fn) (pairlis (second fn) args (fourth fn)) cont))
	((eq (first fn) 'CONTINUATION)
	 (funcall (second fn) (first args)))
	(t 'UNDEFINED-FUNCTION)))