Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'Linguistic abstraction
25.  Lisp in Lisp

Let us now jump to a topic, which is quite different from language embedding and language mirroring as discussed in Chapter 23 and Chapter 24. Recall, however, that the topic of the current lecture is linguistic abstraction, which is about establishing new languages in an existing language.

We will now see how to establish Lisp in Lisp. Thus, we will study a situation where the new language and the existing language are (almost) identical. This calls for a more detailed explanation and rationale, which is given in Section 25.1.

25.1 Why 'Lisp in Lisp'25.3 Scheme in Scheme
25.2 An overview of Scheme constructs25.4 The eval and apply primitives

25.1.  Why 'Lisp in Lisp'
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Why do we study an implementation of Scheme in Scheme?

  • Motivations:

    • To illustrate the idea of linguistic abstraction in Lisp

      • Lisp is both the implementation language and the new language

    • To understand the overall principles of interpreters

    • To illustrate the use of important Lisp implementation concepts, such as environments

    • To provide a playground that provides for easy experimentation with the semantics of Scheme

We will refer to a concrete Scheme implementation from the book 'Structure and Interpretation of Computer Programs' (SICP).

We have earlier referred to the book 'Structure and Interpretation of Computer Programs' [Abelson96]. The part of the book which is relevant for linguistic abstraction and Scheme interpreters is chapter 4.


25.2.  An overview of Scheme constructs
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

When we are interested in implementing Scheme in Scheme it is important to have a good classification of constructs in Scheme.

As a basic distinction, some forms are denoted as syntax, and others as procedures. (In this particular context, 'procedures' also covers 'functions'). As another distinction, some abstractions are fundamental - they form the core language; Others are library abstractions in the sense that they can be implemented by use of the fundamental abstractions. You can consult section 1.3 of the Scheme report [Abelson98] to learn more about these distinctions.

What is the basic classification of constructs in Scheme?

  • Syntax

    • Fundamental syntactical constructs such as lambda , define , and if

  • Primitive functions and procedures

    • Fundamental functions and procedures, which cannot in a reasonable way be implemented in the language

  • Library Syntax

    • Syntactical extensions which can be implemented by macros

  • Library functions and procedures

    • Functions and procedures which can be implemented on the ground of more primitive features

Parenthesized prefix notation is used as a common notation for all kinds of constructs

This provides for an uniform notation across the different kinds of constructs in the language


25.3.  Scheme in Scheme
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

It is interesting and instructive to understand the most general processing primitive in a Scheme system, namely eval. Together with apply - which calls primitive functions, library functions, and your own functions - it is shown in Program 25.1.

It is possible to write a relatively full, but brief meta circular Scheme interpreter in Scheme

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((quoted? exp) (text-of-quotation exp))
        ((variable? exp) (lookup-variable-value exp env))
        ((definition? exp) (eval-definition exp env))
        ((assignment? exp) (eval-assignment exp env))
        ((lambda? exp) (make-procedure exp env))
        ((conditional? exp) (eval-cond (clauses exp) env))
        ((application? exp)  (apply (eval (operator exp) env)
                                          (list-of-values (operands exp) env)))
        (else (error "Unknown expression type -- EVAL" exp))))

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure
            (apply-primitive-procedure procedure arguments)))
        ((compound-procedure? procedure)
            (eval-sequence (procedure-body procedure)
                                     (parameters procedure)
                                     (procedure-environment procedure))))
        (else  (error "Unknown procedure type -- APPLY" procedure))))
Program 25.1    The eval and apply functions (procedures) of the Scheme interpreters.

The two central functions of the language implementation - eval and apply - are made available in the language itself

You are encouraged to read a much more comprehensive story about the Scheme in Scheme interpreter in chapter 4 of [Abelson96].

Below we will dwell a little on eval and apply, in the form they are available in Scheme.


25.4.  The eval and apply primitives
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The eval procedure makes the Scheme interpreter directly available as a primitive in the language.

The apply procedure is handy when we call a function on a 'first class parameter list'; That is, in situations where the parameters are available in a list.

The implementation primitive eval of a Lisp systems is typically made available in the language, hereby providing access to evaluation of syntactical expressions (lists) in a given environment

The apply primitive is also available as a convenient mechanism for application of a function, in cases where all the parameters are available in a list

Examples of both are given in Table 25.1 below.



(let* ((ttl "My Document")
       (bdy (list 'p "A paragraph"))
        (list 'html
         (list 'head
          (list 'title ttl))
         (list 'body bdy)))
 (render (eval doc)))
  <title>My Document</title>
  <p>A paragraph</p>
(let* ((ttl "My Document")
       (bdy (list 'p "A paragraph"))
           (head (title ,ttl))
           (body ,bdy))))
  (render (eval doc)))
  <title>My Document</title>
  <p>A paragraph</p>
(+ 1 2 3 4)
(+ (list 1 2 3 4))
Error: + expects argument of type number; 
 given (1 2 3 4)
(apply + (list 1 2 3 4))
Table 25.1    An illustration of eval and apply. In the first two rows we construct a list structure of the usual html , head , title , and body HTML mirror functions. In the first row, the list structure is made by the list function. In the second row, we use the convenient backquote (semiquote) facility. In both cases we get the same result. The last three rows illustrate the use of apply . apply is handy in the cases where the parameters of a function is already organized in a list. What it interesting in our current context, however, is that apply is really an implementation primitive of Scheme, which is made available in the language itself.

With this we are done with Linguistic abstraction, and as such with the main lectures of this material.

The remaining chapters represent side tracks, in which we cover additional details about LAML, object-oriented programming in Scheme, and the imperative aspects of Scheme.


25.5.  References
[Abelson98]Richard Kelsey, William Clinger and Jonathan Rees, "Revised^5 Report on the Algorithmic Language Scheme", Higher-Order and Symbolic Computation, Vol. 11, No. 1, August 1998, pp. 7--105.
[Abelson96]Abelson, H., Sussman G.J. and Sussman J., Structure and Interpretation of Computer Programs, second edition. The MIT Press, 1996.

Generated: Tuesday July 2, 2013, 09:15:57
Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'