Lisp in Small Pieces

Syntactic vs. Semantic Elements

(define (evaluate expr env)
    (if (and (atom? expr) (symbol? expr))
        (lookup expr env)
        ...

To be more precise, we could instead write:

(lookup (symbol->variable expr) env)

and likewise, taking the abstraction one step further:

(lookup (variable->key (symbol->variable expr)) env)

However, when writing a meta-circular evaluator we normally rely on the fact that we can represent the concept of a "variable" in our source language and "key" in our defining language both as ordinary lisp symbols.

Autoquote

When an expression is atomic … and when that expression is not a symbol, we have the habit of considering it as the representation of a constant that is its own value. This idempotence is known as the autoquote facility. An autoquoted object does not need to be quoted, and it is its own value.

Fail Fast

The goal of a program is not so much to avoid committing errors but rather to fulfill its duty. … Errors and erroneous contexts need to be pointed out as early as possible so that their source can be corrected as soon as possible.

Lisp2 allows the evaluator to take a shortcut. When evaluating the function position of an application, we can restrict it to a symbol and do a simple lookup rather than a full eval. That is

(define (evaluate e env)
  (if (atom? e) ...
    (case (car e) ...
      ((lambda) (make-function (cadr e) (cddr e) env))
      (else (invoke (evaluate (car e) env)
                    (evlis (cdr e) env))))))

can be replaced with

...
(else (invoke (lookup (car e) env)
              (evlis (cdr e) env)))...

or, if we want to allow lambda in the function position as well as a symbol, we can replace the lookup with a call to evaluate-application, a mini eval that knows how to handle lambdas and symbol lookup.

(define (evaluate-application fn args env fenv)
  (cond ((symbol? fn) ((lookup fn fenv) args))
        ((and (pair? fn) (eq? (car fn) 'lambda))
         (f.eprogn (cddr fn) (extend env (cadr fn) args) fenv))
        (else (wrong "Incorrect functional term" fn))))

Lisp2 has the advantage of making function lookups faster, since we don't force another call to eval, but instead do the lookup directly, and also because the function environment will be more compact since it does not contain variable bindings. In addition, lambda forms in function position are greatly simplified. Consider:

(let ((state-tax 1.186))
  ((lambda (x) (* state-tax x)) (read)))

In the above case, the closure corresponding to the lambda will not be created, rather its body will be evaluated in the correct environment. We can also avoid checking that the symbol in the function position is indeed a function at application time if we perform the check before binding it.

However, many of these apparent advantages of Lisp2 can be overcome in Lisp1 if the function to apply can be determined statically, which is usually the case.

On the down side, with Lisp2 we lose the ability to calculate the function to apply, as in ((if cond + -) 3 4).

Is this sarcasm? I doubt it, but it got a chuckle out of me nonetheless. More likely something fell through the cracks in the translation from French.

Notice that the entire interpreter could easily be written in a real object-language, like Smalltalk, so we could take advantage of its famous browser and debugger. The only thing left to do is to add whatever is needed to open a lot of little windows everywhere.

In the world of Scheme, continuations can no longer be put on the stack because they can be kept in external data structures. Thus we have to adopt another model: a hierarchic model, sometimes called a cactus stack. The most naive approach is to leave the stack and allocate blocks for continuations directly in the heap… [but] the canonical implementation of call/cc copies the stack into the heap; the continuation is thus this very copy of the stack.

This section describes a variant called partial continuations, which are continuations that act like function calls in so far as they return their value to the current continuation. With standard continuations:

(+ 1 (call/cc (lambda (k) (set! foo k) 2)))
--> 3
(foo (foo 4))
--> 5

If foo were a partial continuation, the result of (foo (foo 4)) would be 6, not 5.

The following quote is essentially a continuation on the theme first presented in the sections Syntactic vs. Semantic Elements and More on Syntactic vs. Semantic Elements, above. That is, a distinction between objects and values in the definition language, as opposed to the defined language.

In the end, we can accept a compositional definition of quoting since, by transforming the program, we can revert to our usual habits. However, we might scrutinize these bad habits that depend on the fact that programs are often read with the function read and that thus the expression that appears in a quote and that specifies the immediate data to return is coded with the same conventions: same dotted pairs, same symbols, etc. Natural laziness impinges on the interpreter to use this same value and thus to return it every time it's needed.

The set of terms in the λ-calculus is given by Λ, which can be defined recursively as:

β-reduction occurs during an application when the parameters of a combination are substituted for some value in the body of the combination. E.g.

\[ \beta\textrm{-reduction}: (\lambda x. M \;\; N) \overset{\beta}{\to} M[x \to N] \]

A redex is a red-ucible ex-pression, i.e. an application in which the first term is an abstraction. A β-reduction supresses a redex.

When a term contains no redex…, we say that the term is in normal form. Terms in λ-calculus do no necessarily have a normal form, but when they have one, it is unique because of the Church-Rosser property. When a term has a normal form, there exists a finite series of β-reductions that convert the original term into the normal form. An evaluation rule is a procedure that indicates which redex (if there is more than one) ought to be β-reduced.

Common examples of evaluation rules are normal order (aka call by name), call by need, and call by value. Scheme uses the latter for efficiency reasons. Normal order is so named becaues it's guaranteed to find the normal form, if it exists, whereas call by value is not. Consider, for example:

\[ ((\lambda x.\lambda y.y \; (\omega \, \omega)) \: z) \\ \textrm{where} \ \omega = \lambda x.(x \, x) \]

In a normal-order language, the above β-reduces to \(z\), whereas in Scheme, the \((\omega \, \omega)\) term causes an infinite loop.

The following define various domains of objects handled by denotations.

And some greek letters that customarily represent the domains.

Extensionality is the property that \((\forall x, f(x) = g(x)) \implies (f = g)\). It is linked to the η-conversion…

\[ \eta\textrm{-conversion}: \lambda x.(M \;\; x) \overset{\eta}{\to} M \;\; \textrm{with x not free in M} \]

The denotation of a tiny scheme (missing variable airity, etc.). The denotation of call/cc is included in the book. I've left it out here because it's too tedious to typeset.

For comparison, here is the denotation given for the λ-calculus.

As a language, C does not support functions inside other functions. In other words, a lambda inside another lambda cannot be translated directly. Consequently, we must eliminate these cases in a way that turns the program to compile into a simple set of closed functions, that is, funcitons without free variables. Once again, we're lucky to find such a natural transformation. We'll call it lambda-lifting because it makes lambda forms migrate towards the exterior in such a way that there are no remaining lambda forms in the interior.