Lisp in Small Pieces
Christian Queinnec
Language: English
Pages: 536
ISBN: 0521545668
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.
binding by changing the representation of the environment. In what follows, we'll assume that lists of variables are not dotted. This assumption will make it easier to decode lists of variables. We'll also assume that we don't need to verify the arity of functions. These new functions will be prefixed by s. to make them easier to recognize. (define (s.make-function variables body env) (lambda (values current.env) (let «old-bindings (map (lambda (var val) (let «old-value (getprop var 'apval»)
«dynamic) (lookup (cadr e) deny»~ «dynamic-let) (df.eprogn (cddr e) (special-extend env ; ** Modified ** (map car (cadr e» ) fenv (extend deny (map car (cadr e» (map (lambda (e) (df.evaluate e env fenv deny) (map cadr (cadr e» ) ) ) ) (else (df.evaluate-application (car e) (df.evlis (cdr e) env fenv deny) env fenv deny » ) ) ) (define (special-extend env variables) (append variables env) ) (define (cl.lookup var env deny) (let look «env env» (if (pair? env) (if (pair? (car env» (if (eq? (caar
(flet «fact (n) (if (= n 0) 1 (* n (fact (- n 1») ») (fact 6) ) The function fact is bound in the current function environment. This closure captures both the function environment and the parametric environment current in the locality where the form flet is evaluated. In consequence, the function fact that appears in the body of fact refers to the function fact valid outside of the form flet. There's no reason for that function to be the factorial, and as a consequence, we don't really get
variable suffixed by a star represents a list of whatever the same variable without the star would represent. e, et, ec, ef r k, kk . . . v f . . n ... expression, form environment continuation value (integer, pair, closure, etc.) function identifier Now here's the interpreter. It assumes that anything that is atomic and unknown to it as a variable must be an implicit quotation. (define (evaluate e r k) (if (atom? e) (cond «symbol? e) (evaluate-variable e r k)) (else (evaluate-quote e r k))
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