Scheme

Scheme [9,1] is a dialect of the programming language Lisp. As for this paper, the most important differences between Scheme and traditional Lisp languages are:

1. Static binding of free names in procedures.
   Free names in a Scheme procedure are bound in the context of the procedure definition. More traditional Lisp dialects bind the names in the context of the procedure call (dynamic binding).

2. First class procedures.
   Being ``first class'' means that a procedure can be stored and retrieved from data structures, passed as a parameter, and returned as the result from another procedure.

3. Uniform evaluation of all positions in a procedure call form.
   If (p a b c) is a procedure call in a traditional Lisp dialect, p is supposed to be a symbol, and the procedure property of the symbols must be a procedure object. In Scheme, the p position does not need to be a symbol. The only important thing in Scheme is that the p position is an expression the value of which is a procedure object. Variables in Scheme do not have a separate procedure value besides the ``normal'' value. All positions in a (non-special) Scheme form are evaluated in the same way.

4. Program is not data.
   In a traditional Lisp dialect, the list representation of a piece of program can be manipulated (examined, aggregated, and taken appart) via the primitives of the languages. Furthermore, the main interpreter primitive eval is considered as part of the language. In Scheme a piece of program cannot easily be accessed as a list structure, and eval is not part of the language.

Points number one and two make it possible to model objects using only procedures. To make this more concrete for readers who have not already gained this insight, look at the following simple example:

(define (a)
  (let ((a-var nil))

    (define (b x)
      (set! a-var x))

    b)

A is a procedure, which has a local variable a-var . Local to a there is also a procedure b . Due to point number one, the free variable a-var in b is bound to a-var in a . Due to point number two, b can be returned from a because procedures are first class objects. If c

is defined in the following way

(define c (a))

c refers to a procedure object, which has access to the local variable a-var in a . Consequently the local state of a , represented by a-var

in the example, cannot be deallocated upon return from a . C can be thought of as a representation of an object with state hold by the variable a-var .

I will elaborate a little bit more on the example, in order to illustrate point number three from above. It is possible to call the local procedure b in an a-object in the following way

((a) (+ 2 3))

There are two positions in this form. Both positions are evaluated using exactly the same rules. This is due to point number three from above. The first position is supposed to return a procedure object, which is applied on the result of the other position (the number 5).

In chapter I will describe more carefully how these principles can be used to simulate classes, instances, and message passing between the instances.