sicp-metacircular-evaluator/metacircular-evaluator.org

Introduction

This document follows the lecture "Lecture 7A: Metacircular Evaluator, Part 1" of the recorded SICP lectures from 2005:

MIT 6.001 Structure and Interpretation of Computer Programs, Spring 2005 Instructor: Harold Abelson, Gerald Jay Sussman, Julie Sussman

Definition of eval

Eval is described as a "universal machine", which takes any program description as an input and then manages to behave like that program, so that one can give input as expected by the program and get the output from the universal machine eval, which one expectes from the program.

Sussman warns the audience, that the program will contain many car and cdr, which he does not want people to use in professional programs. From earlier lectures it becomes clear, that he wants people to introduce a data abstraction layer, to abstract from the data structures being linked lists and enable easily switching to a different data structure later, by only adapting the data abstraction layer, not the actual main program logic. Furthermore Sussman mentions, that he would make the whole dispatch data-directed, so that he could dispatch on some bits of the expression and add things dynamically to it later, without changing the program much, as well as making it run fast.

However, for the purpose of demonstrating the eval universal machine, he does not worry about it at that moment.

(define eval ;; Take an expression and an environment. The environment is a dictionary, ;; which maps symbol names to their values. (λ (expr env) ;; Distinguish given expressions into various classes of expressions. (cond ;; Numbers stay numbers. [(number? expr) expr] ;; Lookup symbols in the environment (coding by wishful thinking, pushing ;; the work off to someone else). [(symbol? expr) (lookup expr env)] ;; Constants, which are not a number are written as (quote foo) and ;; evaluate to themselves. Constants remain constant. [(eq? (car expr) 'quote) (cadr expr)] ;; Lambda expressions like (λ (x) (+ x y)) are textual descriptions of ;; procedures. A kind of data structure (procedure object) is needed to ;; contain all parts, which are required for evaluation of such an ;; expression. [(eq? (car expr) 'lambda) ;; To evaluate a lambda the following things are needed: A list of bound ;; variable names (binding names), the body of the lambda, the environment ;; in which the lambda was encountered and a tag, which declares the ;; result to be a procedure. Note, that this is the place, where dynamic ;; VS lexical scoping is decided, by memorizing the environment, which was ;; present, when the lambda was encountered and putting it into the ;; resulting data structure. (list ;; tag 'closure ;; binding names and body -- These could also be split up. (cdr expr) ;; environment env)] ;; Conditional expressions -- These consist of predicates and expressions, ;; which are evaluated, when the predicate evaluates to true. [(eq? (car expr) 'cond) ;; Evaluate the cond expression by evaluating the list of predicates and ;; corresponding expressions. Programming by wishful thinking, pushing it ;; off to someone else. In this case eval-cond. (eval-cond (cdr expr) env)]

;; At this point the special cases are taken care of. Anything else is not ;; a special case.

;; Procedure calls -- application [else and find out, what ;; Apply the operator to its arguments. (apply ;; Find out what the name of the procedure relates to. (eval (car expr) env) ;; Find out what the arguments of the procedure relate to. Programming by ;; wishful thinking, pushing off the work to something else. Strict ;; evaluation here. (eval-list (cdr expr) env))])))

There are many things left undefined in this code, which need to be defined later:

• apply
• eval-list
• eval-cond
• lookup

Definition of apply

apply needs to process a procedure and its arguments. It needs to find the binding values of the bindings.

(define apply (λ (proc args) (cond [(primitive? proc) ;; Hand off to some (apply-primitive-operation args)] [(eq? (car proc) 'closure) (eval ;; Get the body of the procedure. The second element of the procedure is ;; the binding names list and the body together in a list. Of those we ;; need the second, which is the body. TODO: Use data abstraction layer ;; here. (cadadr proc) ;; In order to make progress in the computation using recursion, at least ;; one argument must change, in a way, that the computation gets closer ;; to finishing. The progress in this case is, that the environment of ;; the procedure is extended, by binding the argument values of the ;; procedure to the corresponding argument values. This is called ;; "binding". The result of binding an updated environment, which is in ;; turn handed over to eval. (bind ;; Find the binding names. (caadr proc) ;; Bind the binding names to the arguments that the procedure was ;; applied to. args ;; To evaluate the procedure in the correct environment, the environment ;; of the procedure needs to be extended, no the environment given to ;; apply. (caddr proc)))]

;; In a real implementation, there would be more cases here, for example ;; distinguishing compiled code from not compiled code.

;; If proc is no procedure, return an error. [else 'error:applying-non-procedure)])))

apply contains apply-primitive-operation, which is not explained in detail. Sussman states, that it is not strictly necessary to have primitives, as in theory everything could be done using lambda calculus (remember Church numerals), but that it is nice to have them. He does not want to look at the details of how they could be implemented, as it is not particularly relevant to the eval universal machine. Basically if one wants to have primitives, there would need to be some kind of logic to process them, which could depend on a type tag like there is one for procedures ('closure) or that there is some kind of machine language code taking care of it.

apply mentions some not yet defined things:

• primitive?
• apply-primitive-operation
• bind

Which will need to be defined elsewhere.

Definition of eval-list

(define eval-list (λ (lst env) (cond [(eq? lst '()) '()] [else (cons (eval (car lst) env) (eval-list (eval-list (cdr lst) env)))])))

Definition of eval-cond

(define eval-cond (λ (clauses env) (cond ;; If there are no more clauses, it means, that evaluation has not found a ;; matching case, which is an error in the program, which is evaluated. [(eq? clauses '()) 'error:no-matching-cond-clause] ;; Each clause is a list. So the predicate of the first clause is first one ;; looked at. NOTE: Order of cond-clause evaluation is defined here.

;; If the clause is an else clause, evaluate the corresponding consequent. [(eq? (caar clauses) 'else) ;; NOTE: TODO: should use data abstraction here. (eval (cadar clauses) env)] ;; If the predicate if the first clause evaluates to false, then look at ;; the other clauses. [(false? (eval (caar clauses) env)) (eval-cond (cdr clauses) env)] ;; Otherwise evaluate the consequent of the first of the remaining clauses. [else (eval (cadar clauses) env)])))