More Scheme
Go over append – noting its speed, explaining, reverse (2 versions), Fibb (2 versions).
Explain perm’s construction.
Scheme interpreter in Scheme:
Interpreter simulates execution of any program P in language L. Interpreter is written in language L’. It performs the same actions as the executor of P in language L would perform, in the same order. Often used to show that language L’ programs can do anything that language L programs can.
In this case, the interpreter is used to explain the details of how Scheme functions are called, and how variables are handled.
;(assoc key L) looks up "key" in the list of pairs L, and returns the value associated with the first match. A match occurs when (eq key (car P)) for some pair P on L.
(define (assoc key L) (cond
((null? L) (error "unbound variable" key L))
((eq (car (car L)) key) (car (cdr (car L))))
(else (assoc key (cdr L)))
))
; Assoc is used to determine the value of a variable in a particular "context" or "environment" defined by L.
;(apply def args Le Ge) applies a function definition "def" to arguments "args" in environment Le, Ge. "def" has the form ((params) body). Le is the local environment, and Ge the global.
(define (apply def args Le Ge) (eval (cdr def) (bind (car def) args Le Ge) Ge))
; bind evaluates each argument in environment (Le Ge), and pairs the value with the corresponding parameter in "par". Bind returns a list of all these pairs.
(define (bind par args Le Ge) (cond
((null? par) ())
(else (cons (list (car par) (eval (car args) Le Ge))
(bind (cdr par) (cdr args) Le Ge)))
))
;(eval S Le Ge) evaluates S-expression S in environment (Le Ge)
(define (eval S Le Ge) (cond
((atom? S) (assoc S (append Le Ge))) ; look up variable S
; S is ( oper args)
((eq? (car S) ‘cond) (evcon (cdr S) Le Ge))
((eq? (car S) ‘quote) (car (cdr S)))
; "’X" is translated during reading into (quote X).
((eq? (car S) ‘car) (car (eval (car (cdr S)) Le Ge))
; other built-in function definitions here.
(else (apply (eval (car S) Le Ge) (cdr S) Le Ge))
Note the simplicity of this definition. It doesn’t explain HOW car, cdr, cons are implemented, but it does explain the details of how environments work – a variable is looked for first in the local environment, then in the global one.
Not shown here is the way "define" works – it adds a definition to the global environment. The "read-eval-print" loop then uses the new global environment to process subsequent definitions and function calls.
Alternate rules for variable look-up can be used here, giving different variants of Lisp slightly different semantics.
Scheme implementation
The original definition of Lisp presented an interpreter like that above to explain the "meaning" of Lisp programs. The interpreter was written in terms of the 6 built in Lisp functions, "cond" and a function call mechanism. To create a running Lisp interpreter, you need to give definitions for each built-in function, the "Lisp reader", and the cond and call mechanisms.
Lists and atoms need representation:
An area of memory is reserved for atoms (say, all locations <0x4000000), and the rest of memory is reserved for "pairs". This lets atom? Do s simple comparison of the pointer it is passed, to decide if it is True or not. Traditionally, () is placed at location 0, so null? is also a simple test. Eq? Compares the 2 pointers it is passed for equality.
Typedef struct at {
/* complex. Includes the "property list", the type, etc. */
} Atom;
Typedef It union {
Pair *p;
Atom *a;
} Item;
Typedef struct pr {
Item car;
Item cdr;
Int mark;
} Pair;
car and cdr are straightforward. Each is passed a pointer to what should be a Pair. Each then returns the appropriate field of that Pair.
Cons is more complicated. It usually locates a new Pair on a pre-built list of "free pairs". If none can be found, cons must then call the "garbage collector", GC. GC tries to find list structure that isn’t being used, because it cannot be accessed from:
Any location on the function call stack, or
Any list in the global environment.
GC first searches all accessible list structures, avoiding extending the search into the "atom" area of memory. GC marks each pair it finds (using the "mark" field). This allows even circular structures to be searched. GC then does a linear sweep over memory, adding all unmarked pairs to a new free list, and unmarking all other pairs. This is somewhat slow – when Scheme executes GC, a notable pause occurs.
The Lisp reader reads S-expressions and data lists from the input, and translates them into the internal list structure representation. This includes computing the values of integers and reals read from input, and hashing symbols, so that all symbols that are "spelled" the same are considered the same atom.
The read-eval-print loop reads each expression from the input, evaluates it in the current global environment and prints the result. It then uses the new global environment to evaluate the next one.
The conditional expressions in "eval" must be translated into appropriate sequences of If statements. The function calling is then done using the implementation language’s function call mechanism, with some care, since argument lists must remain accessible to GC.
The ACTUAL implementation of Scheme is designed to give the BEHAVIOR specified by the Scheme interpreter, but in a more efficient way.
The Scheme interpreter spends much time searching environment lists.
This can be avoided:
A real Scheme maintains a "val" field as part of each Atom. This field is made to hold the current value of the corresponding Atom. When the Atom is used as a parameter of a function being called, the current value is entered on a "push-down list", and the new value is assigned to the Atom’s "val" cell. The reverse happens when the called function exits.