[PLT logo] Lecture 5, Comp 311

A Meta-Interpreter for LC (Meaning)

In summary, Lecture 4 was about syntactic interpreters, which rewrite programs in the syntax of the source language. This is a powerful interpretation technique. For instance, even utilities as seemingly far removed from programming languages as the sendmail daemon use it for configuration files. In this lecture, we will look at meta-interpreters, which are used to denote meanings of phrases in a program.

A meta-interpreter represents procedures in LC as combinations (closures) of syntactic procedures and environments. The initial motivation for the name ``meta'' is that, instead of taking the program text and reducing it to new program text, we choose an element of the implementing (or `meta') language to represent a phrase in the implemented language. In essence, we reduce the meaning of the the entire language to the meaning of a single program. If this program happens to be purely functional, then (as we will see later in the course) there we can define the meaning of this program logically in the same sense that mathematicians define the meaning of set theory logically. A secondary motivation for the "meta" terminology is that we interpret every construct as directly as possible in the interpreted language (provided that we stay in the functional subset).

Last time, we wrote an interpreter for LC in Scheme that represented environments as lists of variable/value pairs and closures as records containing the procedure text and the closing environment. We have also been using Scheme numbers to represent LC numbers. This convention enables us to interpret LC addition as Scheme addition. This strategy suggests that we consider an alternate representation of LC closures (lambda-expressions) as Scheme procedures. In this case, that we can use Scheme application to interpret LC application.

Here is a sketch of MEval, which is essentiallte our environment-based envEval from last lecture with the representations of environments and closures left unspecified. 

(define MEval
  (lambda (M env)
    (cond
      ((var? M) (lookup (var-name M) env))
      ((num? M) (num-num M))
      ((add? M) (+ (MEval (add-left M) env)
		  (MEval (add-right M) env)))
      ((proc? M) (make-closure M env))
      ((app? M) (MApply (MEval (app-rator M) env)
		  (MEval (app-rand M) env))))))

Note: The + operation used above must be chosen with care, since the addition operation in the meta-language won't necessarily be the same as that of the implemented language.

What are the values in LC? There are two: numerals and procedures. Numerals can be represented directly in the meta-language. To avoid a premature choice of representation for closures, we have chosen to use the abstractions make-closure and MApply. Thus, if we ever need to change the interpretation of closures, we can do so without changing the interpreter itself.

Exercise: Which elements of the interpreter would we have to change if we change one of our representation choices?

In the special case when the language we are interpreting is the same as that in which the interpreter is written (for instance, a Scheme interpreter written in Scheme), we call the interpreter meta-circular.

Let us examine the representation of procedures. 

(define make-closure
  (lambda (proc-exp env)
    (lambda (value-for-param)
      (MEval (proc-body proc-exp)
	(extend env (proc-param proc-exp) value-for-param)))))

(define MApply
  (lambda (val-of-fp val-of-arg-p)
    (val-of-fp val-of-arg-p)))
Note that the closure returned by make-closure closes over env.

Abstractly, we can characterize MApply and MEval as follows: 

  (MApply (make-closure (make-proc x B) Env) Val)
= (MEval B (extend Env x Val))

Puzzle: Given the declaration 
(define-structure (closure P E))
how do we write MApply?

Environment Representation

One part of the interpreter has still been left unspecified: the representation of environments. Before considering the available alternatives, it is worth-while to consider environments abstractly too. There are three things we need to understand with respect to environments: the lookup method, the extension method, and the empty environment. The latter two create new environments, while the first of these extracts information from information. Here are the equations that relate the constructors and the selector: 

(lookup Var (empty-env)) = (error 'lookup "variable ~a not found" Var) 
(lookup Var (extend Env VarN Val)) =
  (if Var is VarN
      Val
      (lookup Var Env))

What is a good representation choice for environments? Note that there is only a fixed number of free variables in a given program, and that we can ascertain how many there are before we begin evaluating the program. On the other hand, we can be lax and assume that there can be arbitrarily many free variables. A good representation in the former case is the vector; in the latter case, we might wish to use lists. However, there is at least one more representation.

Representing Environments as Procedures

Consider the following implementations: 

(define lookup
  (lambda (Var Env)
    (Env Var)))

(define empty-env
  (lambda ()
    (lambda (Var)
      (error 'lookup "variable ~a not found" Var))))
We can then prove that this implementation satisfies one of the equations that characterize environments: 
  (lookup var (empty-env))
= (lookup var ((lambda () 
      (lambda (Var) (error 'lookup "variable ~a not found" Var)))))
= (lookup var (lambda (Var) (error 'lookup "variable ~a not found" Var)))
= ((lambda (Var) (error 'lookup "variable ~a not found" Var)) var)
= (error 'lookup "variable ~a not found" var)
as desired. We can similarly define extend: 
(define extend
  (lambda (Env VarN Val)
    (lambda (name)
      (if (eq? name VarN)
	Val
	(Env name)))))

Exercise: Verify that extend and lookup satisfy the above equation.

Binding Constructs

Now suppose we added some new binding constructs to LC. For instance, suppose we added seq-let, and defined its behavior as follows: 

  (MEval "(seq-let Var RHS Body)" env)
=
  (MEval Body (extend env Var
	        (MEval RHS env)))

However, now say we add recursive lexical bindings: 

  (MEval "(rec-let Var RHS Body)" env)
=
  (MEval Body (extend env Var
	        (MEval RHS ...)))
where the ... represents the (extend env Var ...) term. How can we implement such a construct? We clearly need a way to create an environment that refers to itself. If we represent environments as procedures, we can use recursive procedures to implement this kind of extension.

Exercise: Can we use lists or other representations to accomplish this goal?

Hint: What did we do in Comp 210 to create data structures that refer to themselves?

cork@cs.rice.edu/ (adapted from shriram@cs.rice.edu)