Lisp in Small Pieces
Format: PDF / Kindle (mobi) / ePub
This is a comprehensive account of the semantics and the implementation of the whole Lisp family of languages, namely Lisp, Scheme and related dialects. It describes 11 interpreters and 2 compilers, including very recent techniques of interpretation and compilation. The book is in two parts. The first starts from a simple evaluation function and enriches it with multiple name spaces, continuations and side-effects with commented variants, while at the same time the language used to define these features is reduced to a simple lambda-calculus. Denotational semantics is then naturally introduced. The second part focuses more on implementation techniques and discusses precompilation for fast interpretation: threaded code or bytecode; compilation towards C. Some extensions are also described such as dynamic evaluation, reflection, macros and objects. This will become the new standard reference for people wanting to know more about the Lisp family of languages: how they work, how they are implemented, what their variants are and why such variants exist. The full code is supplied (and also available over the Net). A large bibliography is given as well as a considerable number of exercises. Thus it may also be used by students to accompany second courses on Lisp or Scheme.
second field in any of those primitives contains the "address" of the primitive, that is, something executable by the underlying machine. A primitive is thus triggered like this: (define-method (invoke (f primitive) v* r k) «primitive-address f) v* r k) ) Then to start the interpreter, and begin to enjoy its facilities, we will define an initial continuation in a way similar to null-env. That initial continuation will print the results that we provide it. (define-class bottom-cont continuation
CHAPTER 3. ESCAPE & RETURN: CONTINUATIONS (wrong "Incorrect arity" 'call/cc v*) ) ) ) ) Even though there are few lines there, we should explain them a little. Although it is a function, call/cc is defined by definitial because it needs access to its continuation so badly. The variable call/cc (now here we are in a LisPl) is thus bound to an object of the class primitivee The call protocol for these objects associates them with an "address" represented in the defining Lisp by a function with the
defined by a lambda form. Just after the keyword lambda, you'll find the variables of the function, followed by the expressions that indicate how to calculate the function. These variables can be modified by assignment, indicated by set!. Literal constants are introduced by quote. The forms let, let*, and letrec introduce local variables; the initial value of such a local variable may be calculated in various ways. With the form define, you can define named values of any kind. We'll exploit the
functions like car. How can we compare cons and cons without invoking tautology? The function cons is an allocator of mutable data, and thus, even if the arguments seem comparable, the results are not necessarily equal since they are allocated in different places. Thus we're right to demand that cons should not be equal to cons and thus (eqv? cons cons) should return false since it is false that (eqv? (cons 1 2) ( cons 1 2))! Now is it really true that car should be equal to car as we argued in
Scheme, that program loops and consequently leads to no term at all, thus certainly not to a normal form. Here's a term that has a normal form, but the evaluation rule in Scheme prevents us from finding it: «AX.Ay.y (ww)) z) ~ (Ay.y z) ~z 5.2. SEMANTICS OF SCHEME 151 In Scheme, that first argument (w w) would be computed and loop infinitely, so the normal form would never be found. Conversely, and also unfortunately, in Scheme we can evaluate a term without a normal form. The reason is