Wednesday, February 04, 2004
There are some problems with evaluating the parse tree on its own. The problems come in when trying to deal with call/cc. In order to handle them I decided to have the S-Expressions in the parse tree operate on external stacks, rather than calling each other recursively. Here'r are my thoughts which I wrote up earlier on the topic:
Evaluation of (call/cc f) needs to pass to f something that represents the current state of execution -- i.e. whatever the interpreter was planning to do with the return value of (call/cc f). With the other versions of the interpreter the evaluation of an SExpression is handled entirely by recursive double dispatch between an expression, its subexpressions, and the vm. Knowning what the interpreter is going to do with an expression involves knowing the stack of calling SExpression.evaluate() functions that has led up to the call to evalute the current expression. And then, knowing the call-stack isn't quite enough because several evaluations can happen in a single evaluate() method, and so t's not clear where in the method to return to.
Idea: explicitly keep track of the stack of expressions to evaluate. That is, have the VM evaluate expressions on a stack, and have each SExpression.evaluate() not be allowed to evaluate any other SExpressions, but only push and pop SExpressions from the stack.
Example: 1
Example: (if T 'true 'false)
Example: ((lambda (x) (+ 2 x)) 1)
A: Yes, we are.
Q: Do you have a good reason for doing it here, and not above with apply-function?
A: Hrm.. well, what's the alternative:
Moving on.
Expression Evaluation
Evaluation of (call/cc f) needs to pass to f something that represents the current state of execution -- i.e. whatever the interpreter was planning to do with the return value of (call/cc f). With the other versions of the interpreter the evaluation of an SExpression is handled entirely by recursive double dispatch between an expression, its subexpressions, and the vm. Knowning what the interpreter is going to do with an expression involves knowing the stack of calling SExpression.evaluate() functions that has led up to the call to evalute the current expression. And then, knowing the call-stack isn't quite enough because several evaluations can happen in a single evaluate() method, and so t's not clear where in the method to return to.
Idea: explicitly keep track of the stack of expressions to evaluate. That is, have the VM evaluate expressions on a stack, and have each SExpression.evaluate() not be allowed to evaluate any other SExpressions, but only push and pop SExpressions from the stack.
Example: 1
EXP STACK: [ 1 ] ; push the expression to evaluate on the stack
RTN STACK: [ ]
pop the top and inspect it. It's a number. How do we evaluate numbers? Well, they just evaluate to themselves. So, push the result of evaluating the number onto the return-value stack.
EXP STACK: [ ]
RTN STACK: [ 1 ]
Example: (+ 2 3)
EXP STACK: [ (+ 2 3) ] ; push expression to evaluate
RTN STACK: [ ]
pop it off and inspect it. It's a list. How do we evalute lists? Well, we first evaluate the 'car' of the list, and then apply the return value as a function, to the rest of the list.
EXP STACK: [ + ] ; the 'car' of the list
[ << apply-function >> ] ; a function application
RTN STACK: [ (2 3) ]
So now we evaluate the top of the stack, '+', which is a symbol. How do we evaluate symbols? We look them up.
EXP STACK: [ << apply-function >> ]
RTN STACK: [ << addition-function >> ]
[ (2 3) ]
Now we evaluate a function, the apply-function function. This pops an SExpression from the RTN STACK, verifies that it is a Function, and then applies it to list of the arguments on the RTN stack. Well, what does 'applying' the addition-function do first? Well, it first has to set itself up for evaluation. So it checks that it has the appropriate number arguments (which it does) and then evalutes each of its arguments. Only after all of this does the function actually get evaluated. So, first things first:
EXP STACK: [ 3 ] ; push argument 2
[ 2 ] ; push argument 1
[ << addition-function>> ] ; push myself.
RTN STACK: [ ]
So now we evaluate the arguments, both numbers:
EXP STACK: [ << addition-function>> ]
RTN STACK: [ 2 ]
[ 3 ]
Now we evalute the addition-function. It pops its arguments off the return stack, checks that they are both numbers, and adds them up.
EXP STACK: []
RTN STACK: [ 5 ]
Nothing's left on the EXP STACK, so we're done evaluating the expression. The return value is on the RTN STACK.
Example: (if T 'true 'false)
EXP STACK: [ (if T 'true 'false) ]
RTN STACK: [ ]
EXP STACK: [ if ]
[ << apply-function >> ]
RTN STACK: [ (T 'true 'false) ]
EXP STACK: [ << apply-function >> ]
RTN STACK: [ << if-function >> ]
[ (T 'true 'false) ]
EXP STACK: [ T ]
[ << if-function >> ]
RTN STACK: [ 'true ]
[ 'false ]
EXP STACK: [ << if-function >> ]
RTN STACK: [ T ]
[ 'true ]
[ 'false ]
EXP STACK: [ 'true ]
RTN STACL: [ ]
...
EXP STACK: [ ]
RTN STACK: [ true ]
Q1: What about functions with an arbitrary number of arguments?
A1.1: The function could push a sentinel on the RTN stack, so that the function just consumes expressions from the return stack until it reaches the sentinel.
A1.2: The function could push the number of things to read as the first thing on the RTN stack.
A1.3: The function instance could hold state as to the number of expressions it should read.
A1.3 means having to create a new instance of the function each time it's evaluated (so as to keep states distinct). Boo.
A1.1 means having to create a new SExpression that's just has the job of being a sentinel. Boo.
A1.2 No internal state, no new SExpressions, just good, clean fun. Way to go!
Closures
So a closure is a function and an environment in which to evaluate the function. When a closure is evaluated it swaps in its environment frame stack for the current stack, executes it's function, and swaps back in the old environment.Example: ((lambda (x) (+ 2 x)) 1)
EXP STACK: [ ((lambda (x) (+ 2 x)) 1) ]
RTN STACK: [ ]
ENV STACK: [ p1: { } ]
...
EXP STACK: [ << (lambda (x) (+ 2 x)), p1: {} >> ]
RTN STACK: [ 1 ]
ENV STACK: [ p1: {} ]
So at this point we have the closure on the top of the expression stack, it's argument on the RTN stack, and the current environment (labelled 'p1') on the environment stack. Evaluating the closure does a few things:
- replaces the environment stack with its own. Since it's the same, there's no difference.
- creates a new environment frame on the stack to hold the bindings to its formal parameters (p2).
- puts a function on stack to return the environment stack to what it was.
- puts it's body on the stack to be executed.
EXP STACK: [ (+ 2 x) ]
[ << replace-env-stack p1 >> ]
RTN STACK: [ ]
ENV STACK: [ p2: { x = 1 } ]
[ p1: {} ]
Q: Aren't we storing state in the 'replace-env-stack' function? A: Yes, we are.
Q: Do you have a good reason for doing it here, and not above with apply-function?
A: Hrm.. well, what's the alternative:
EXP STACK: [ (+ 2 x) ]
[ << replace-env-stack >> ]
RTN STACK: [ p1 ]
ENV STACK: [ p2: { x = 1 } ]
[ p1: {} ]
So that means that we'd treat environments as SExpressions. I don't like that. I can't even make sense of what that would me. So forget it.
Moving on.
...
EXP STACK: [ << replace-env-stack p1 >> ]
RTN STACK: [ 3 ]
ENV STACK: [ p2: { x = 1 } ]
[ p1: {} ]
EXP STACK: [ ]
RTN STACK: [ 3 ]
ENV STACK: [ p1: {} ]
Example: (set add (lambda (x) (lambda (y) (+ x y))))
EXP STACK: [ (set add (lambda (x) (lambda (y) (+ x y)))) ]
RTN STACK: [ 3 ]
ENV STACK: [ p1: {} ]
...
EXP STACK: [ (lambda (x) (lambda (y) (+ x y))) ]
[ << set-function >> ]
RTN STACK: [ add ]
ENV STACK: [ p1: {} ]
...
EXP STACK: [ << set-function >> ]
RTN STACK: [ << (lambda (x) (lambda (y) (+ x y))), p1 >> ]
[ add ]
ENV STACK: [ p1: {} ]
EXP STACK: [ ]
RTN STACK: [ ]
ENV STACK: [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ]
Example: continuing from above, (set add6 (add 6))
EXP STACK: [ (set add6 (add 6)) ]
RTN STACK: [ ]
ENV STACK: [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ]
...
EXP STACK: [ (add 6) ]
[ << set-function >> ]
RTN STACK: [ add6 ]
ENV STACK: [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ]
...
EXP STACK: [ << apply-function >> ]
[ << set-function >> ]
RTN STACK: [ << (lambda (x) (lambda (y) (+ x y))), p1 >> ]
[ 6 ]
[ add6 ]
ENV STACK: [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ]
...
EXP STACK: [ (lambda (y) (+ x y)) ]
[ << replace-env-stack p1 >> ]
[ << set-function >> ]
RTN STACK: [ add6 ]
ENV STACK: [ p2: { x = 6 } ]
[ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ]
...
EXP STACK: [ << replace-env-stack p1 >> ]
[ << set-function >> ]
RTN STACK: [ << (lambda (y) (+ x y)), p2 >> ]
[ add6 ]
ENV STACK: [ p2: { x = 6 } ]
[ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ]
EXP STACK: [ << set-function >> ]
RTN STACK: [ << (lambda (y) (+ x y)), p2 : { x = 6 } >> ]
[ add6 ]
ENV STACK: [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >> } ]
EXP STACK: [ ]
RTN STACK: [ ]
ENV STACK: [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >> } ]
Example: continuing from above, (add6 1)
EXP STACK: [ (add6 1) ]
RTN STACK: [ ]
ENV STACK: [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >> } ]
...
EXP STACK: [ << apply-function >> ]
RTN STACK: [ << (lambda (y) (+ x y)), p2: { x = 6 } >> ]
[ 1 ]
ENV STACK: [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >> } ]
EXP STACK: [ (+ x y) ]
[ << replace-env-stack p1 >> ]
RTN STACK: [ ]
ENV STACK: [ p3: { y = 1 } ]
[ p2: { x = 6 } ]
[ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >> } ]
...
EXP STACK: [ << replace-env-stack p1 >> ]
RTN STACK: [ 7 ]
ENV STACK: [ p3: { y = 1 } ]
[ p2: { x = 6 } ]
[ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >> } ]
EXP STACK: [ ]
RTN STACK: [ 7 ]
ENV STACK: [ p1: { add = << (lambda (x) (lambda (y) (+ x y))), p1 >>,
add6 = << (lambda (y) (+ x y)), p2: { x = 6 } >> } ]
Continuations
Let's get some terminology going. Let the 'state' of the interpreter at any given moment consist of the EXP, RTN, and ENV stacks.
A continuation is a 1-ary function which *replaces* the current state of the interpreter with its own, and pushes its argument on the RTN stack.
Example:
Assume we have the current state:
EXP STACK: [ ]
RTN STACK: [ ]
ENV STACK: [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
In other words, we have a 1-ary function 'f' which just applies it's parameter to the number 1. So (f number?) returns T.
Now evaluate (call/cc f)
EXP STACK: [ (call/cc f) ]
RTN STACK: [ ]
ENV STACK: [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
EXP STACK: [ call/cc ]
[ << apply-function >> ]
RTN STACK: [ (f) ]
ENV STACK: [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
EXP STACK: [ << apply-function >> ]
RTN STACK: [ << call/cc >> ]
[ (f) ]
ENV STACK: [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
So call/cc is a function which which creates a continuation and passes that to its argument. Let's label the current state when call/cc is executing 's1'. s1 looks like this:
EXP STACK: [ ]
RTN STACK: [ ]
ENV STACK: [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
So the next step is to apply 'f' to the continuation.
EXP STACK: [ f ]
[ << apply-function >> ]
RTN STACK: [ << continuation-function, s1 >> ]
ENV STACK: [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
...
EXP STACK: [ << apply-function >> ]
RTN STACK: [ << (lambda (cc) (cc 1)), p1 >> ]
[ << continuation-function, s1 >> ]
ENV STACK: [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
EXP STACK: [ (cc 1) ]
RTN STACK: [ << replace-env-stack, p1 >> ]
ENV STACK: [ p2: { cc = << continuation-function, s1 >> ]
[ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
...
EXP STACK: [ <> ]
RTN STACK: [ << continuation-function, s1 >> ]
[ (1) ]
[ << replace-env-stack, p1 >> ]
ENV STACK: [ p2: { cc = << continuation-function, s1 >> ]
[ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
So now, applying the continuation to 1, we replace the current state with s1, and push 1 onto the return stack.
EXP STACK: [ ]
RTN STACK: [ 1 ]
ENV STACK: [ p1: { f = << (lambda (cc) (cc 1)), p1 >> } ]
And we're done.0 Comments:
