Introduction to Scheme++ for C311

On copper Scheme++ is provided automatically by running ~c311/bin/scheme. The Scheme++ implementation source code for Chez Scheme uses define-syntax, but this need not concern the user.

Terminology

An instance is an object that contains a set of instance variables that record its state and a set of methods that alone can access the instance variables. An instance is created using a class, known as the class of the instance. Classes are also used to derive (help create) other classes via inheritance. Those classes used to derive a class are known as its base classes.

If C is the class of an instance, then the instance is an instance of C. An instance of a class is also an instance of the base classes of the class.

An abstract base class is used only to derive other classes. Other classes are used only to create instances, while some classes are used for both purposes.

A class is said to be defined via multiple inheritance if it has more than one base class, and via single inheritance otherwise. Every class inherits from at least one class, except for the top class, which has no instance variables.

The inheritance relation must define a directed acyclic graph, called the class hierarchy, rooted by the top class.

Each instance has its own instance variable values, but all instances of a given class contain the same set of methods and instance variable names. Thus methods and instance variable names are thought of as belonging to the class of an instance rather than the instance itself.

A method introduced in a class belongs to the class. A method belonging to a base class of a class, C, also belongs to C unless C introduces a new method of the same name. If more than one base class defines a method of the same name, references to this name must be qualified to remove ambiguity. The techniques for doing this are not covered here, as they are not needed in this course.

Protection

• A method introduced in a class may only be called from methods belonging to the same class, unless the method is declared to be public, in which case it can be called from anywhere.

Environment example

(define <environment>
  (class ()
    (public apply extend)
    (methods
      (define extend 
        (method (vars vals) 
          (<extended-environment> this vars vals)))
      (apply))))

The keyword class is immediately followed by a formal parameter specification. The formal parameters are associated with arguments when the class is initialized, as in a procedure application. Since the environment class is always initialized with no arguments, its formals specification is the empty list.

The formals specification of a class form is followed by various parenthesized clauses, each introduced by a keyword. Though there is a bit more flexibility in the order of clauses, it is suggested that they always appear in the order indicated in our examples.

The environment class contains a public clause and a methods clause. The apply and extend methods are declared to be public, for we want to be able to apply or extend environments in any context.

The method form's syntax is the same as a lambda expression except for the keyword. It returns a new method when evaluated. The first argument in every method invocation is always an instance that is used to select the method. This instance is always bound in the method's body to the variable this. In the environment class a method named extend is defined that when invoked takes two additional arguments named vars and vals. We shall see how this method is used presently.

The environment class is an abstract base class. It is intended it be inherited only by classes that always define a method named apply. It should be possible to extend or apply any environment. To make access to this method more efficient and easy, the environment class declares an apply method binding without a corresponding method-valued expression.

An empty-environment class is defined next, along with an empty-environment instance.

(define <empty-environment>
  (class ()
    (base <environment>)
    (methods
      (define apply 
        (method (v) 
          (error '<empty-environment> "Variable ~s is not bound" v))))))

(define empty-environment (<empty-environment>))

Classes are represented as procedures that return instances of themselves when invoked. Any arguments passed to the procedure are used to initialize the newly created instance. The empty environment class does not require any initialization arguments, so its formals specification is also the empty list.

Non-empty environments are represented as instances of the extended-environment class, which also inherits from the environment class.

(define <extended-environment>
  (class (env vars vals)
    (base <environment>)
    (inst-vars env vars vals)
    (methods
      (define apply
	(method (sym)
	  (let ((x (memq sym vars)))
	    (if x
	      (list-ref vals (- (length vars) (length x)))
	      (apply env sym))))))))

Methods are invoked via method calls. These are calls in which the procedure is a generic and the first argument is an instance. The generic selects the method to be called from the instance and invokes the method with the instance and any other arguments of the method call.

Generics may be either local or universal. A universal generic may be invoked with any instance, but may only be used to invoke public methods. A local generic for a method named M created in class C may only be invoked with an instance of a class that introduces a method binding for M and is on a path from C to the top class. Local generics are more efficient than universal generics.

Universal generics must be created using the generic form. For example, we next define a universal generic for the extend method name and use it to invoke the extend method of our empty environment instance.

(define extend (generic extend))

(define abc (extend empty-environment '(a b c) '(1 2 3)))

Next we define an apply procedure that acts like a universal generic on instances and otherwise acts like the standard apply procedure (available in Chez Scheme as #%apply).

(define apply
  (lambda args
    (if (procedure? (car args)) 
      (#%apply #%apply args)
      (#%apply (generic apply) args))))

(apply abc 'b) ==> 2

If the symbol is not on the list of variables, this apply method executes the method call in the last line of the extended environment class definition. The procedure of this call is a local generic for the apply method that is associated with the extended environment class. Such local generics are created for each method name bound in the methods clause of a class.

We conclude this example with a new version of the extended environment class that incorporates two improvements. First, the length of the vars list is computed at instance creation time and stored in an additional instance variable called length-vars. Second, an after-inst-var-init clause is used to check after the instance variables are initialized to be sure the variable and value lists are of the same length and issue an error message otherwise.

(define <extended-environment>
  (class (vars vals env)
    (base <environment>)
    (inst-vars vars vals env 
      (define length-vars (length vars)))
      (if (not (eq? length-vars (length vals)))
	(error '<extended-environment>
	  "vars ~s and vals ~s lists not the same length"
	  vars
	  vals)))	    
    (methods
      (define apply
	(method (v)
	  (let ((x (memq v vars)))
	    (if x
	      (list-ref vals (- length-vars (length x)))
	      (apply env v))))))))

Lambda calculus example

Abstract syntax requires a distinct type of node for each non-terminal production. For each type of node we define a class with an instance variable for each non-terminal in the right-hand side of its production.

Each of these classes has its own unparse method, so we define an abstract base class from which they all inherit. In anticipation of another set of abstract syntax classes, the base class introduces the public method rename, as well as unparse.

(define <syntax>
  (class ()
    (public unparse rename)
    (methods
      (define unparse)
      (define rename))))

(define <variable>
  (class (var)
    (base <syntax>)
    (inst-vars var)
    (methods
      (define unparse 
        (method () var)))))

(define <lambda>
  (class (formal body)
    (base <syntax>)
    (inst-vars formal body)
    (methods
      (define unparse 
        (method () 
          (list 'lambda (list formal) (unparse body)))))))

(define <call>
  (class (rator rand)
    (base <syntax>)
    (inst-vars rator rand)
    (methods
      (define unparse 
        (method () 
          (list (unparse rator) (unparse rand)))))))

The parse procedure takes a Scheme datum representing a lambda calculus expression (as a subset of Scheme syntax) and returns the representation of the expression in abstract syntax. Viewing each abstract syntax class as a node type the abstract syntax may be viewed as a tree in which the instance variables of each instance contain the branches to subtrees.

(define parse
  (lambda (exp-datum)
    (form-case exp-datum
      (variable var
	(<variable> var))
      (lambda (formals body)
	(<lambda> (car formals) (parse body)))
      (call (rator rand)
	(<call> (parse rator) (parse rand))))))

(define <variable>
  (class (var)
    (base <variable>)
    (base-inst-vars var)
    (base-init var)
    (methods
      (define rename
	(method (old new)
	  (if (eq? old var)
	    (<variable> new)
	    this))))))

(define <lambda>
  (class (formal body)
    (base <lambda>)
    (base-inst-vars formal body)
    (base-init formal body)
    (methods
      (define rename
	(method (old new)
	  (if (eq? old formal)
	    this
	    (<lambda> formal (rename body old new))))))))

(define <call>
  (class (rator rand)
    (base <call>)
    (base-inst-vars rator rand)
    (base-init rator rand)
    (methods	    
      (define rename
	(method (old new)
	  (<call>
	    (rename rator old new)
	    (rename rand old new)))))))