Functions and all that

I suppose I should learn Lisp, but it seems so foreign.

Paul Graham, Nov. 1983

Last week we got some of the nuts and bolts of Scheem working. This week we work on its soul. The soul of Scheem is that magical thing called a function.

Before we can properly talk about how functions work and what's going on when we call them, we need a way to represent scope and variable bindings. Once we have a handle on environments, scopes, and bindings we'll be able to figure out functions.

let form in Scheme

In Scheme there is a special form for introducing a local binding to a variable called let. Here's an example of how it's used.

The example binds x to 2 and y to 5, then evaluates to 7. Importantly, after the expression evaluates to 7 the bindings for x and y disappear. The bindings are only active inside the body of the let.

The syntax of let is (let (_bindings...) _body) where each binding looks like (_var _expr).

let-one

For Scheem we will start by adding a simpler let-one form. This version will just bind one variable. Let's give it the syntax (let-one _var _expr _body). Here's an example:

The example binds x to 2 then evaluates to 3.

Shadowing

Our Scheem interpreter so far has been using a simple dictionary to keep track of variable bindings. It has worked well so far. But now that we have local bindings we need to modify our definition of environment.

Why isn't a dictionary good enough? Consider this code:

What happens? First x is bound to 2. Then two subexpressions are evaluated for the addition. The top one binds x to 3 then evaluates to 3. The bottom one binds y to 4 and evaluates to 2. In particular, as we evaluate the top subexpression we temporarily bind x to 3. But we can't forget about the previous binding to 2 even though the inner binding has shadowed the x name. After we're done evaluating the top subexpression we still need the binding of x to 2 for evaluating the bottom subexpression.

New environment data structure

Let's create a new environment data structure to deal with variable binding. Our requirements are that it has to support adding new bindings that might have the same name as previous bindings. It has to be able to lookup variable names and find the correct value, namely the most recent binding. We'll also need it to support set! and changing variable values.

Our solution will be to nest bindings. An environment is either { } which indicates no bindings, or like this:

For the expression (let-one x 2 (let-one y 3 (+ x y))), the subexpression (+ x y) will be evaluated in the environment:

You can see that the innermost binding is at the top of the environment data structure.

Write a function lookup that takes an environment and a variable name and returns the value the variable is bound to. Don't worry about error conditions and not finding the variable anywhere right now.

1:1

To check if an object x has a field y you can use x.hasOwnProperty(y), which returns a boolean.



Next