Sketchy LISP

An Introduction to Functional Programming in Scheme

1.6 Procedures and Local Scopes

You may have wondered what the lambda in procedures like fact2 is about:

(define (fact n)
  (letrec
    ((fact2
       (lambda (n r)
         (cond ((zero? n) r)
               (else (fact2 (- n 1) (* n r)))))))
    (fact2 n 1)))

Again, there is a simple explanation and a more complex one. The simple explanation is that lambda is just a placeholder name for anonymous procedures. For instance,

(lambda (x) (* x x))

creates an anonymous procedure that computes the square of its argument:

(lambda (x) (* x x)) => #<procedure (x)>

The question what exactly a procedure is is part of the more complex answer and will be discussed a bit later. What is more important now is the fact that there is not much of a difference between named procedures and anonymous procedures. You can apply lambda functions to arguments just like any ordinary procedure:

((lambda (x) (* x x)) 7) => 49

You can even bind an anonymous procedure to a symbol, making the anonymous procedure a named procedure:

(define square (lambda (x) (* x x)))

In fact the above definition is perfectly equivalent to

(define (square x) (* x x))

and in early versions of Scheme the variant involving lambda was the only way to define new procedures. Letrec does not support the new syntax, so binding an anonymous procedure to a name is the only way to create a local procedure inside of it. So much for the simple answer.

All Scheme procedures are either primitive procedures or closures. Primitive procedures are procedures that can not (or, at least, not easily) be implemented in Scheme. They form the very core of the language, and they are mostly implemented in some other, typically more low-level, language. The following procedures are examples for primitives:

car => #<primitive car>
cons => #<primitive cons>
write => #<primitive write>

Constructs like lambda, define, and cond are also primitives in the sense that they are part of the core language, but they are not really procedures at all. They are part of the syntax of the language.

Some people may tell you that lambda is the only primitive that is really needed to build a working Scheme. While this is true and even may be a challenging mental exercise, it is not very practical, so do not listen to these people until you feel a bit more familiar with Scheme.

Whether a pre-defined procedure is a primitive procedure or a closure is merely an implementation detail. Some Scheme systems do not even distinguish between them:

reverse => #<procedure (x)>
(lambda (x) x) => #<procedure (x)>

BTW: All external representations that begin with the prefix #< are unreadable, which means that they cannot be parsed by the read procedure. This is because there is no practical external representation for procedures. What should write output for a primitive procedure? Its machine code? That would not be very portable. The same is valid for closures. Their implementation depends highly on the Scheme system in use, so they do not have a universal external representation, either.

What exactly is a closure? To answer this question in detail, another pseudo function will be explained first: let. This construct is a close relative of letrec, which has been used to create local procedures in some example programs so far. Let binds symbols locally, creating a new context. The following Scheme session illustrates how it works:

(define a 'foo)
(define b 'bar)
(let ((a 3)
      (b 4))
  (* a b))
=> 12
a => foo
b => bar

First a is bound to foo and b to bar. Let then binds a to 3 and b to 4 locally, thereby creating a new context. In this context, * is applied to a and b. When the let finishes, the original bindings of the symbols that were re-bound locally are restored. The context outside of a let is also called the outer context of that let and the context created by it is called its inner context. Variables of the inner and outer context can be merged:

(define foo 100)
(let ((bar 70))
  (- foo bar))
=> 30

Only when an inner and an outer variable have the same name, the outer binding becomes invisible inside of an inner context. Symbols that are unbound in an outer context remain unbound after their use in an inner context:

xyz => bottom
(let ((xyz 'some-value))
  xyz)
=> some-value
xyz => bottom

A variable that occurs in an argument list of a lambda function or in the definition part of let (or letrec) is said to be bound in that procedure or binding construct. For instance, the symbol x is bound in

(lambda (x) x)

and in

(let ((x 'foo)) x)

but it is not bound in

(lambda (y) x)

A variable that is not bound in a given context is said to be free in that context. Note that a variable can be bound in one context and free in another at the same time:

(lambda (x) (lambda (y) (cons x y)))

In this example, x is bound in the whole expression, but y is only bound in the inner lambda function. X is free in the inner function alone:

(lambda (y) (cons x y))

A variable is called bound in a given context, like a lambda function, because it is bound to a value when the procedure is applied. Free variables, on the other hand, remain unchanged when the procedure is called. The values of free variables are defined in the outer context of the procedure.

Let is very similar to a procedure application: it binds values to local symbols (which are therefore bound in its context), evaluates a body, restores the original bindings of its local variables, and returns the normal form of the body. This is exactly what happens during a procedure application:

((lambda (a b)   (let ((a 5)
   (* a b))            (b 7))
 5 7)              (* a b))
=> 35            => 35

So let is just an alternative syntax for the application of lambda functions:

((lambda (a1 ... an)  =  (let ((a1 v1)
   body)                       ...
 v1 ... vn)                    (an vn))
                           body)

One major difference between let and the application of a lambda function is that the application can be decomposed into two parts: the lambda function itself and the list of its arguments:

(car '((lambda (a b) (* a b)) 3 4))
=> (lambda (a b) (* a b))
(cdr '((lambda (a b) (* a b)) 3 4))
=> (3 4)

An interesting question to ask at this point would be: what is the outer context of the lambda function? The inner context is created when the procedure is applied to its arguments, but this application may take place a long time after defining the procedure and the outer context might have changed in the meantime. For example, what is the following program supposed to evaluate to:

(let ((v 1))
  (let ((f (lambda (x) (* x v))))
    (let ((v 0))
      (f 5))))

In the outermost let, v is assigned to one. In this context the procedure f is created. In the context of f, v is bound to zero. In this context, finally, f is applied to five. To find out what (f 5) reduces to, the value of v in f must be known. The fact that the innermost binding always takes precedence suggests that the expression evaluates to zero, but in fact it reduces to five:

(let ((v 1))
  (let ((f (lambda (x) (* x v))))
    (let ((v 0))
      (f 5))))
=> 5

How can this be? Because the outer context may change between the definition of a procedure and its application, lambda freezes the outer context at the time of its application and takes it with it. This is what the experienced LISPer calls lexical scoping. It is called lexical because the value of a variable depends on its lexical (or textual) context. F is created in a context where v is bound to one, so appearances of v in the body of f evaluate to one.

BTW: If the above expression would have reduced to zero, the dynamic value of v would have been used. This principle is known as dynamic scoping, but Scheme uses lexical scoping exclusively.

The frozen context of a procedure is also called the lexical environment of that procedure. The combination of a lambda function and a lexical environment is called a closure. In Scheme, every (non-primitive) procedure is a closure, so the terms closure and procedure are mostly used as synonyms.

1.6.1 What are Closures Good for?

In case you wonder what the use of lambda is: it can be used to create new procedures on the fly. Here is a rather classic example:

(define (compose f g)
  (lambda (x) (f (g x))))

The compose procedure takes two arguments f and g (which must be procedures themselves). It evaluates to a procedure of one argument that applies the two procedures passed to compose to its own argument (x). The variables f and g belong to the outer context of the lambda, so they are captured by the resulting closure. One says that lambda closes over f and g:

(compose car cdr) => #<procedure (x)>
                     ; body = (f (g x))
                     ; f = car, g = cdr

The resulting procedure applies the composition of car and cdr to its argument, thereby extracting the second member of a list:

((compose car cdr) '(a b c)) => b

BTW: The procedure (compose car cdr) is part of the Scheme standard. Its name is cadr. Of course, you could define cadr in a much more straight forward way:

(define (cadr x) (car (cdr x)))

So the above example is indeed a bit artifical. Here is another example: Imagine a procedure named filter which extracts all members with a given property from a list:

(define (filter p a)
  (cond ((null? a) '())
        ((p (car a))
          (cons (car a)
                (filter p (cdr a))))
        (else (filter p (cdr a)))))

Filter uses a predicate to check whether a member has a given property. All members x which satisfy (p x) are collected in the resulting list. The following sample application of filter extracts all numbers from a list (the number? predicate tests whether its argument is a number):

(filter number? '(a 31 b 41 c 59)) => (31 41 59)

If you want to extract all non-numbers from the same list, you could pass a lambda function negating the predicate number? to filter:

(filter (lambda (x)
          (not (number? x)))
        '(a 31 b 41 c 59))
=> (a b c)

However, the above lambda function leads to another interesting procedure:

(define (complement p)
  (lambda (x) (not (p x))))

The complement procedure creates the complement P' of a predicate P. Wherever P returns #t, P' returns #f and vice versa. Using complement, above application of filter can be written like this:

(filter (complement number?) '(a 31 b 41 c 59))
=> (a b c)

Complement can also be used to create a procedure that collects all members of a list which do not satisfy the given predicate, thereby effectively removing all matching members:

(define (remove p a)
  (filter (complement p) a))

which would allow you to write:

(remove number? '(a 31 b 41 c 59)) => (a b c)