grammar book

-> (define add (lambda (z) (lambda (z) (+ z 6))))
-> (define add6 (add 1))
-> (add6 3)
9

In scheme everything is a so-called S-Expression. (symbolic expression). There are three or four types of S-Expressions: numbers, symbols, lists and closures (read: functions). a number is , well, you get it. a symbol is anything that isn't a parenthesis or a number, and a list is defined recursively as

( S-Expression * )

Each of these things can be evaluated. A number evaluates to itself, a symbol evaluates to whatever S-Expression it's bound to in the current, or any enclosing, scope (more on that later). A list can also be evaluated. It's like a function call. The first expression in the list is evaluated, and it must return a function. So to evaluate (+ 2 3) we first evaluate the '+' symbol to get the 2-ary function implementing addition. The rest of the list is passed into the function, and the function is evaluated.

So 123 evalutes to the number 123, (+ 2 3) evaluates to 5, + evaluates to the function implementing addition, and evaluating () is an error (since there is no function to execute.

The single quote, ', is actually a short form. It works like this, ' is short for (quote ). The 'quote' function is 1-ary function which just returns its argument. So 'a is short for (quote a) which evaluates to the symbol "a". '123 is (quote 123) which evalutes to the number 123, '() evaluates to (), ''() evaluates to (quote ()), etc..

Now, the function

(define add (lambda (z) (lambda (z) (+ z 6))))

So you know what a 'define' does.. it evaluates its second argument and binds that to the symbol that is its first argument. In this case we evaluate

(lambda (z) (....))

and bind it to 'add'. well.. (lambda (z) (...)) evaluates to a closure, which for the moment we can think of as a function. It's a 1-ary function with parameter 'z' and body (lambda (z) (+ z 6)). Forget the fact that the body is another lambda expression, we'll deal with that in a moment, it could just as well be something like (print z) or (+ z 1).

So now if i were to type 'add' at the prompt i should get whatever's bound to the symbol 'add' which is the 1-ary function I described above. But your question is, what does the function bound to 'add' actually do. Well, if I type (add 1) I invoke the function add with the argument '1'. What does that give us? Well, when we invoke a function we return the evaluation of the function's body, where we evaluate the body in a new scope in which we bind each parameter of the function to the evaluation of its respective argument. In our case, we are going to evaluate (lambda (z) (+ z 6)) in the scope where 'z' is bound to 1.

so what does (lambda (z) (+ z 6)), when 'z' is '1', return? first, forget about 'z' being bound to '1', and you'll see that the lambda expression evaluates to a 1-ary function with the body (+ z 6).. in other words, it's a function which adds 6 to its single argument. got it? the fact that 'z' is bound to '1' in the scope actually plays no role in the behaviour of this particular function because this function overrides the scope's "z" with the parameter with the same name. It's kind of like this in Java:

class add {
    int z = 1;

    int add6 (int z)
    {
        return z + 6;
    }       
}

If you created an instance of 'add' and called add6(3) you'd get 9.

(I'm still not even sure what the difference between a list and a function application is...

well, hopefully this makes a little more sense now. a list is what i defined above, a function application is the evaluation of a list, where the first element evaluates to a function. So (+ 2 3) is a list, but when we try to evaluate it we first eval + to get the addition function and so on.. we could also write an equivalent list ((lambda (x y) (+ x y)) 2 3). You see, this is the same thing as (+ 2 3). When we evaluate it we evaluate the first element (lambda (x y) (+ x y)) to get a 2-ary function that adds its arguments and then we apply it to the two arguments 2 and 3.

for instance, is (7 3) a valid expression in scheme? Or do you have to say ('7 '3) for it to make sense? Or '(7 3)??)

Well, this should make sense now. (7 3) is a list. If you tried to evaluate it you'd first try to evaluate 7 and get the number 7, which isn't a function so you'd get an error.

('7 '3) is also a list, which when evaluated would give you an error because '7 evaluates to 7 -- not a function. '(7 3) is a list too, namely the list (quote (7 3)) which evalutes to the list (7 3).

Also, what does Miles mean by <<(lambda (x) e), {p}>>? Is he just referring to an ordered pair that corresponds to one of your internal data structures? If so, then maybe I don't need to understand that.

Okay, so this is what I was glossing over when I said closures where just functions. A lambda expression (lambda (...) (...)) evaluates to a closure, which is the function implementing the lambda expression AS WELL as the current scope p (sometimes refered to as the environment). The idea is that when a closure is evaluated you evaluate it in the scope p.

So, let's say you do this:

-> (define a 2)                ; bind 2 to the symbol a

Then the current environment is {a <- 2}.

-> (define plus-two (lambda (x) (+ 2 a))

so 'plus-two' is bound to a closure which contains the lambda function and the current environment. You can see this play out if I was to do this:

-> (plus-two 2)
4
-> (define a 4)
-> (plus-two 2)
6

get it? So above when we defined add6 we actually created the closure:

    << (lambda (z) (+ z 6)), {z <- 1} >>

But applying the lambda expression to some number we first bind the argument to the parameter 'z' which overrides the things in the closure's environment.. like the example I gave with the method parameter overriding the class member.

So check this:

-> (define add (lambda (z) (lambda (x) (+ z x))))
-> (define add7 (add 7))
-> (add7 1)
8

There I changed the parameter for the inner lambda expression so that it uses a different name, which doesn't override the closure's environment binding.