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

*To*: address@hidden, address@hidden, address@hidden*Subject*: Re: So, what the heck is a continuation anyway?*From*: Guy Steele - Sun Microsystems Labs <address@hidden>*Date*: Mon, 10 Dec 2001 18:16:48 -0500 (EST)*Cc*: address@hidden*Reply-to*: Guy Steele - Sun Microsystems Labs <address@hidden>*Sender*: address@hidden

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)))

- Prev by Date:
**data structure in LL** - Next by Date:
**Re: So, what the heck is a continuation anyway?** - Previous by thread:
**Re: So, what the heck is a continuation anyway?** - Next by thread:
**Re: So, what the heck is a continuation anyway?** - Index(es):