Eval Apply Example

The particular problem I would like to look at is

Its the evaluation of

eval quote (((lambda(x) (lambda(y) (+ x y))) applied to 3) applied to 4) in some global environment which I will call e0. 

What we have is a procedure of one argument x which produces as its value a procedure of one argument y which adds x to y. We are applying the procedure of one argument x to 3 so that x should become 3, and the result of that will be a procedure of one argument y, which we will then apply to 4.

To do this we need a global environment,which I’ll call e0, and it will have definitions of +, *, -, /, car, cdr, cons, eq? and everything else. Something the machine is born with.

What does it mean to do this evaluation? First, we will go through all the special forms, this is not a number, this is not a symbol, its not a quoted expression, its not a thing that begins with lambda, its not a thing that begins with cond, therefore its an application of an operator to operands, its a combination.  The combination has an operator and operands.

We transform this to apply of (eval of (quote ((lambda(x) (lambda(y) (+ x y))) 3) in the environment, also e0, (Note here I have evaluated the operator) with the arguments being the result of (evlist the list containing 4 ine0).  e0 is the quoted expression for the data structure which will be the environment goes there. (What this basically does is, when you get a combination, evaluate the operator, evaluate the operand and apply the operator to operand. The evaluation of operands or arguments is done in steps, through evlist. If you see the body of evlist its just the consing of the evaluation of each argument.)

To do this, I have to do first and the second. Lets do the second first. This is first part followed by, the evlist turns into cons of eval of 4 in e0, followed by evlist ‘() in e0.

This is apply of eval of …. eval of 4 is 4, it meets the number criterion, evlist of empty list is the empty list, so what I get is the list 4 (4).

Lets look at the next intersting thing, what do I do to evaluate that expression? Evaluating this is nothing but an application of the operator applied to this operands,its that combination. So its just apply of eval of the operator, and evlist of the operands.

Note that next thing will be a special case because its a lambda expression, why weren’t those earlier things considered lambda expressions, because they were lambda expressions applied to some arguments (operators applied to operands), now its just pure operator that we have settled down to.

Eval of a lambda expression produces a procedure object. (Think of this as an abstract procedure object, with the two circles, and the 2nd circle pointing to the environment.) This abstract object we denote by closure, and environment e0 gets captured in it. Now we have to apply that procedure to the arguments.

However, that procedure is not primitive, its got the tag closure. Therefore, we have to do a bind. A new environment is made, which has as its parent environment, e0, and we’ll call this e1, and x is bound to 3 in e1.

So what our expression transforms into is the eval of the body of the procedure, in the environment e1. Apply (eval (lambda(y) (+ x y) e1) (4)).

I know how to evaluate a lambda. That means I apply the abstract procedure closure (x) (+ x y) with e1 captured in it. Apply that to 4.

That’s easy. That means I have to make a new environment which points to the environment pointed by the procedure, and which binds y to 4. This environment we will call e2. 

Our expression then is evaluate the body in e2. i.e. (eval (+ x y) e2)

But this is an application, therefore it becomes, apply of eval of + in e2, (apply (eval + e2) (evlist ‘(x y) e2)

That is (apply some primitive operator + to the result of evaluating x and y in e2), which is (apply some primitive operator + to 3 and 4) which gives me a 7 magically (since we don’t know +)

See one important ingredient – what’s being passed around, and who owns what and what his job is. eval produces procedure and arguments for apply. Some things eval can do by itself, those are little self things that are not interesting. Eval also evaluates all arguments one after the other, that’s not very interesting. Apply can do certain things by itself, such as +, not very interesting.But if apply can’t apply a procedure, it produces an expression, and an environment, for eval. The procedure and arguments wrap up the state of a computation, and so do expressions and environment.

eval-apply-example-board-1

eval-apply-example-board-2

eval-apply-example-env-diagram

eval-apply-example-board-3

eval-apply-loop

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: