Section Notes 10--Lambda the Ultimate

CS51--Spring, 2008

Week of May 4, 2008

Scheme procedures

There is more to calling a procedure than evaluating its body. Procedures are interesting because they change the way symbols are evaluated; references to names of arguments within the procedure need to be resolved within the correct local environment rather than from the global symbol table.

It simplifies matters a bit to see that there does not need to be a distinction between arguments and ``local variables'' (let-bound variables); let is just a rearranged lambda. So you only need to worry about arguments.

Binding arguments

eval takes an argument specifying the current local environment. To call a procedure, you'll need to allocate a new environment to pass to eval. Arguments will be bound to their values within this environment.

The most difficult part of binding arguments is handling improper argument lists. Scheme allows a user-defined function to take a variable number of arguments when its formal argument list is improper:

    (define (varargs a b c . d)
        ....

Let's say this function is called on the arguments (1 2 3 4 5 6). Corresponding parts of the formal and actual arguments are matched up:

Formal arg	value
a	1
b	2
c	3
d	(4 5 6)

The way to understand this is that a, b, and c are in the cars of their respective cons cells, so they are assigned to cars of the argument list. d is in the cdr of the third cons, so it gets assigned the cdr of the third cons in the actual arguments.

Nested functions

As long as each function invocation allocates its own environment, functions can call themselves or each other freely in any combination. However, this is not sufficient to handle the case of nested functions, where one function (often a lambda) occurs lexically within the body of another.

Scheme uses lexical scope, a scoping rule which stipulates that nested functions must be able to see the local variables of any enclosing functions. Be sure you understand that this has nothing to do with functions called from other functions; it only affects functions whose code occurs physically inside that of other functions.

The function find-gt below contains a lambda that has its own local variable a and also uses variable x from its enclosing function:

    (define (find-gt l x)
        (filter (lambda (a) (> a x)) l))

What happens if a nested function has arguments with the same names as its enclosing function?

To deal with nested functions, we need to evaluate symbols using a chain of environments. If a symbol is not found in the closest lexical environment, we step out to the next enclosing environment and try that next. The cool part is that the function invocation that created this enclosing environment might have terminated--its environment lives on! Recall that when a function returns a function, the returned function can still use its entire lexical environment when invoked later.

For this to be possible, you need to save a pointer to the current local environment whenever a new procedure is created. This saved environment will be the second link on the chain of environments when the procedure is invoked in the future.

The evaluator in action

Let's look at everything that happens as the interpreter evaluates an expression. An exposition such as this is formally known as a shaggy dog story. Our example Scheme expression will be

    ((lambda (x y) (+ (* 2 x) y)) (+ 5 5) 9)

We begin with the expression as a value (specifically, a pair) read by your parser.

The toplevel in scheme51.cc calls v->eval().
This invokes pair::eval in eval.cc, which begins making a Scheme list of the evaluations of everything in the list.
The head (the first car) is a pair, so pair::eval gets called again.
The head of this expression is lambda. lambda is in the syntax environment, home to all special functions, which need to operate on unevaluated arguments. interp::init in interp.cc has called _bind_syntax to associate the name ``lambda'' with C++ function stx_lambda.
stx_lambda in eval.cc builds an expression to call named-lambda:
```
    (named-lambda (quote -anon-) (x y) (+ (* 2 x) y))
```
Evaluating this expression (we'll use some recursive wishful thinking here and assume our evaluator works) invokes stx_named_lambda, which calls the constructor for lambda, returning a new procedure object.
The original pair::eval evaluates (+ 5 5), again using pair::eval. This will result in calls to symbol::eval and value::eval (the default evaluator, used for numbers since numbers simply evaluate to themselves).
pair::eval now has a pointer to the + primitive, which is of type primitive. Calling primitive::operator() results in a call to the appropriate C++ function, prim_plus in prims.cc, which returns new number(10).
evaluates to itself.
Now our original pair::eval is ready to apply the procedure from the head to its arguments.
This calls lambda::operator() in procedure.cc, which makes a new env. It loops over its arguments to bind x to 10 and y to 9 in that environment.
Now we evaluate all the forms in the lambda's body in sequence. In this case there is only one. eval is called with the newly-minted env as its argument.
During evaluation of the body, symbol::eval will find the correct values of x and y in the env passed to it.
pair::eval will invoke prim_times and then prim_plus to produce the answer, 29.

Try to list all the places in this process where type errors could occur.

C++ default arguments

takes advantage of a convenient C++ feature that lets the programmer specify default values for function arguments. When an argument has a default value, it can be omitted in a call to the function and the compiler will automatically pass the default for you.

Default values are specified in the function prototype, but not in the function definition:

    In value.h:
    static void type_check(tag got, tag expected, string context = "");

    In value.cc:
    void value::type_check(tag got, tag expected, string context)
    {
        ...
    }

About this document ...

Section Notes 10--Lambda the Ultimate

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

The command line arguments were:
latex2html -no_navigation -split 0 sec10.tex

The translation was initiated by CS51 Course Library on 2008-05-05

CS51 Course Library 2008-05-05