Lecture 5, Comp 311

A Meta-Interpreter for LC (Meaning)

In Lecture 4, we developed a "syntactic" interpreter for LC that relied exclusively on substitution to interpret variables.

At the end of Lecture 4, we introduced a different form of interpreter that relies on a table of varible/value pairs, called an environment to interpret variables. Our rationale for introducing this approach was computational efficiency.

In this lecture, we will look at a different motivation for environment-based interpreters, which we henceforth call meta-interpreters.

A meta-interpreter for LC uses an environment to assign meaning to arbitrary program expressions not just closed ones. An environment is a table mapping variables names (symbols) to values in the programming language. A meta interpreter takes an environment as an auxiliary argument and relies on this environment to assign meaning to the free variables in the input expression.

The primary motivation for the term ``meta'' in ``meta-interpreter'' is that a a meta-interpreter assigns meaning to programs by reducing the meaning of program phrases to the meanings of their components. A meta-interpreter assigns meaning to program phrases using the same inductive framework that logicians use to assign meaning to mathematical formulas.

In the last lecture, we wrote a meta-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 also represented LC numbers as Scheme integers. This convention enables us to interpret LC addition as Scheme addition. We can make this interpreter for LC more abstract by representing closures (evaluated lambda-expressions) as Scheme procedures. Then, we can use Scheme application to interpret LC application.

The following definition off MEval leaves the representations of environments and closures unspecified.

(define-struct pair (var val))
(define-struct closure (body env))

(define MEval
  (lambda (M env)
    (cond
      ((var? M) (lookup (var-name M) env))
      ((number? M) 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. Why?

What are the values in LC? There are two: numbers and procedures. Numbers can be represented directly in the meta-language. To avoid a premature choice of representation for closures, we use the abstract operations make-closure and MApply.

(make-closure M env) builds a closure representation with proc M and environment env.

(MApply cl arg) applies the closure cl to the value arg.

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)))

Abstractly, we can characterize MApply and MEval as follows:

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

(define-structure (closure P E))

Environment Representation

(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? Since the number of variables in existence in a program at any point during a computation is finite we can use some form of sequence it such as a list or a vector. But this is not the only possible representation.

Representing Environments as Procedures

Consider the following implementation of environments

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

(define empty-env
  (lambda ()
    (lambda (Var)
      (error 'lookup "variable ~a not found" Var))))

(define extend
  (lambda (Env VarN Val)
    (lambda (name)
      (if (eq? name VarN)
	Val
	(Env name)))))

  (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)

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. Then we want

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

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