COMP 3007 -- Programming Paradigms 2009

 7  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

7.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:
      1. 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.
      2. 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.

    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

    7.2 The Core of the Evaluator


    (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)
            ((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)))
             (error "Unknown expression type -- EVAL" exp))))

    Primitive Expressions

    Special Forms



    Procedure Arguments

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


  • 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


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

    7.3 Representing Expressions

    7.4 The  Environment

    Representing Environment

    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

    7.5 Running the Evaluator

    Support procedures

    Key Procedures