95.501

2000

5 Metalinguistic Abstraction

What's in This Set of Notes ?

Metacircular Evaluator
The Core of the Evaluator
Representing Expressions
The Environment
Running the Evaluator
Metacircular Code

5.1 Metacircular Evaluator

Establishing a new language is a powerful strategy for controlling complexity in engineering design

We can enhance our ability to deal with a complex problem by adopting a new language that enables us to describe the problem in a different way using primitives, means of combination and means of abstraction that is well suited for the problem at hand

Not only can we formulate new languages, but we can also implement these languages by constructing evaluator

An evaluator (or interpreter) for a program languages is a procedure that when applied to an expression of the language, performs the actions required to evaluate that expression

This is the most fundamental idea in programming:

The evaluator, which determines the meaning of expressions in a programming language. is just another program

An evaluator that is written in the same language that it evaluates is said to be metacircular

The metacircular evaluator is a Scheme formulation of an environment model containing two basic parts:

To evaluate a combination (a compound expression other than a special form) evaluate the subexpression and then apply the value of the operator subexpression to the values of the operand subexpressions.
To apply a compound procedure to a set of arguments, evaluate the body of the procedure in the new environment. To construct the environment extend the environment part of the procedure object by a frame in which the formal parameters of the procedure are bound to the arguments to which the procedure is applied.

Useful to write because it forces us to :

Show how to define the operational semantics of the language

Provides an executable specification for the language

Understand how bindings and environments work.

Can an Entire Language Be Described in Itself?

No,

Need to have somethings defined externally

Usually called a BootStrap for the language

i.e., somethings must be defined externally.

List can be defined completely in terms of cons, car and cdr

Smalltalk has a kernel written in C.

Completeness of the Interpreter

A meta circular interpreter is just an abstraction of the language
i.e., it doesn't describe all the details needed.
It doesn't describe an editor or debugger
It doesn't describe how memory management and garbage colletion are done
Assumes that procedures can be invoked in the usual way.

5.2 The Core of the Evaluator

Eval

Takes as arguments an expression and an environment
It classifies the expression and directs its evaluation.

(define (eval exp env)
(cond ((self-evaluating? exp) exp)
        ((variable? exp)         (lookup-variable-value exp env))
        ((quoted? exp)           (text-of-quotation exp))
        ((assignment? exp)     (eval-assignment exp env))
        ((definition? exp)       (eval-definition exp env))
        ((if? exp)                    (eval-if exp env))
        ((lambda? exp)           (make-procedure (lambda-parameters exp)
                                                                     (lambda-body exp)
                                                                     env))
        ((begin? exp)              (eval-sequence (begin-actions exp) env))
        ((cond? exp)               (eval (cond->if exp) env))
        ((application? exp)      (apply (eval (operator exp) env)
                                                       (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type -- EVAL" exp))))

Primitive Expressions

For self-evaluating expressions, such as numbers, eval returns the expression itself
Eval must look up variables in the environment to find their values.

Special Forms

For quoted expressions, eval returns the expression that was quoted
An assignment to (or a definition of) a variable must recursively call eval to compute the new value to be associated to the variable. The environment must be modified to change (or create) he binding of the variable
An if expression requies special processing of its parts, so as to evaluate the consequent if the predicate is true, and otherwise to evaluate the alternative
A lambda expression must be transformed into an applicable procedure by packaging together the parameters and body specified by the lambda expression with the environment of the evaluation
A cond requires evaluating the predicates until on is true and then evaluating the consequence.
A begin expression requires evaluating its sequence of expressions in the order in which they appear.

Combinations

For a procedure application, eval must recursively evaluate the operator part and the operands of the combination. The resulting procedure and arguments are passed to apply, which handles the actual procedure application.

Apply

Apply takes a procedure and a list of arguments to which the procedure should apply,
Classifies procedure into either primitive or compound
If compound procedure, extend the environment with a frame that that binds the parameters of the procedure with the arguments then evaluate the sequence body of the procedure.

(define (apply procedure arguments)
(cond ((primitive-procedure? procedure)
                           (apply-primitive-procedure procedure arguments))
            ((compound-procedure? procedure)
                            (eval-sequence
                                      (procedure-body procedure)
                                      (extend-environment
                                                  (procedure-parameters procedure)
                                                   arguments
                                                   (procedure-environment procedure))))
        (else
                 (error "Unknown procedure type -- APPLY" procedure))))

Procedure Arguments

Use by eval to take the operands of a combination and return a list of their evaluations

(define (list-of-values exps env)
      (if (no-operands? exps)
          '()
          (cons (eval (first-operand exps) env)
                    (list-of-values (rest-operands exps) env))))

Sequences

Used by apply to evaluate the sequence of expressions in a procedure body

(define (eval-sequence exps env)
      (cond ((last-exp? exps)     (eval (first-exp exps) env))
                (else          (eval (first-exp exps) env)
                                  (eval-sequence (rest-exps exps) env))))

Assignments and Definitions

Handle assignment to variables

(define (eval-assignment exp env)

(set-variable-value! (assignment-variable exp)

(eval (assignment-value exp) env)

env)

'ok)

(define (eval-definition exp env)
      (define-variable! (definition-variable exp)
                                   (eval (definition-value exp) env)
                                   env)
      'ok)

Conditionals

(define (eval-if exp env)
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))

5.3 Representing Expressions

Formats:

self evaluating (numbers variables)

(quote <text-of-quotation>)

(set! <var> <value>)

(define <var> <value>)

(if (predicate) consequent alternative)

(define (<var> <parameter1> .. <parametern>) <body>)

(lambda (<parameter1> .. <parametern>) <body>)

(cond (<p1> <c1>)

(<p2> <c2>)

.. ..

(<pn> <cn>))

(begin e1 e2 ..en)

(procedure <argument1> .. <argumentn>)

Need procedures to find out which expression was entered and to get at the parts of an expression

(define (tagged-list? exp tag)

(if (pair? exp)

(eq? (car exp) tag)

false))

(define (self-evaluating? exp)
(cond ((number? exp) true)
((string? exp) true)
(else false)))

(define (quoted? exp)
(tagged-list? exp 'quote))

(define (text-of-quotation exp) (cadr exp))

(define (variable? exp) (symbol? exp))

(define (assignment? exp)
(tagged-list? exp 'set!))

(define (assignment-variable exp) (cadr exp))

(define (assignment-value exp) (caddr exp))

(define (definition? exp)
(tagged-list? exp 'define))

(define (definition-variable exp)
(if (symbol? (cadr exp))
(cadr exp)
(caadr exp)))

(define (definition-value exp)
(if (symbol? (cadr exp))
      (caddr exp)
      (make-lambda (cdadr exp)
                   (cddr exp))))

(define (lambda? exp) (tagged-list? exp 'lambda))

(define (lambda-parameters exp) (cadr exp))
(define (lambda-body exp) (cddr exp))

(define (make-lambda parameters body)
(cons 'lambda (cons parameters body)))

(define (if? exp) (tagged-list? exp 'if))

(define (if-predicate exp) (cadr exp))

(define (if-consequent exp) (caddr exp))

(define (if-alternative exp)
(if (not (null? (cdddr exp)))
(cadddr exp)
'false))

(define (make-if predicate consequent alternative)
(list 'if predicate consequent alternative))

(define (begin? exp) (tagged-list? exp 'begin))

(define (begin-actions exp) (cdr exp))

(define (last-exp? seq) (null? (cdr seq)))
(define (first-exp seq) (car seq))
(define (rest-exps seq) (cdr seq))

(define (sequence->exp seq)
(cond ((null? seq) seq)
((last-exp? seq) (first-exp seq))
(else (make-begin seq))))

(define (make-begin seq) (cons 'begin seq))

(define (application? exp) (pair? exp))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))

(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))

(define (cond? exp) (tagged-list? exp 'cond))

(define (cond-clauses exp) (cdr exp))

(define (cond-else-clause? clause)
(eq? (cond-predicate clause) 'else))

(define (cond-predicate clause) (car clause))

(define (cond-actions clause) (cdr clause))

(define (cond->if exp)
(expand-clauses (cond-clauses exp)))

(define (expand-clauses clauses)
(if (null? clauses)
      'false                          ; no else clause
      (let ((first (car clauses))
            (rest (cdr clauses)))
        (if (cond-else-clause? first)
            (if (null? rest)
                (sequence->exp (cond-actions first))
                (error "ELSE clause isn't last -- COND->IF"
                       clauses))
            (make-if (cond-predicate first)
                     (sequence->exp (cond-actions first))
                     (expand-clauses rest))))))

5.4 The Environment

Representing Environment

The environment is a list of frames
Each frame is a table of bindings that associates variables with their corresponding values
Frames are added to environment from the front

(define (enclosing-environment env) (cdr env))

(define (first-frame env) (car env))

(define the-empty-environment '())

Each frame is represented as a pair of lists

(define (make-frame variables values)
(cons variables values))

(define (frame-variables frame) (car frame))

(define (frame-values frame) (cdr frame))

(define (add-binding-to-frame! var val frame)
(set-car! frame (cons var (car frame)))
(set-cdr! frame (cons val (cdr frame))))

Representing Variables

(define (set-variable-value! var val env)
(define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable -- SET!" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
(env-loop env))
(define (define-variable! var val env)
(let ((frame (first-frame env)))
    (define (scan vars vals)
      (cond ((null? vars)
             (add-binding-to-frame! var val frame))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (scan (frame-variables frame)
          (frame-values frame))))

Operations on Environments

Find the value bound to a variable in current environment

(define (lookup-variable-value var env)
(define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (car vals))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
(env-loop env))

(define (extend-environment vars vals base-env)
(if (= (length vars) (length vals))
      (cons (make-frame vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many arguments supplied" vars vals)
          (error "Too few arguments supplied" vars vals))))

Search for first frame with binding, Note this is lexical scoping at work

5.5 Running the Evaluator

Support procedures

Primitive procedure names and object

(define (primitive-procedure? proc)
(tagged-list? proc 'primitive))

(define (primitive-implementation proc) (cadr proc))

(define primitive-procedures
(list (list 'car car)
        (list 'cdr cdr)
        (list 'cons cons)
        (list 'null? null?)
;;      more primitives
        ))

(define (primitive-procedure-names)
(map car
primitive-procedures))

(define (primitive-procedure-objects)
(map (lambda (proc) (list 'primitive (cadr proc)))
primitive-procedures))

(define (apply-primitive-procedure proc args)
(apply-in-underlying-scheme
(primitive-implementation proc) args))

Display of evaluator objects

(define (user-print object)
(if (compound-procedure? object)
      (display (list 'compound-procedure
                     (procedure-parameters object)
                     (procedure-body object)
                     '<procedure-env>))
      (display object)))

Key Procedures

Return the initial environment containing bindings for primitives and special variables

(define (setup-environment)
(let ((initial-env
         (extend-environment (primitive-procedure-names)
                             (primitive-procedure-objects)
                             the-empty-environment)))
    (define-variable! 'true true initial-env)
    (define-variable! 'false false initial-env)
    initial-env))

(define (driver-loop)
(prompt-for-input input-prompt)
(let ((input (read)))
    (let ((output (eval input the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
(driver-loop))

Create the global/first environment

(define the-global-environment (setup-environment))

The main user loop

(driver-loop)