;;; ;;; recitation-eval.scm ;;; ;;; From SICP Instructor's Manual, pp. 121-122. ;;; ;;; ADU SICP, October 2000. ;;; ;;; Comments and minor modifications, John Pezaris, 10/2000. ;;; Exercises taken from the Instructor's Manual and comments extended. ;;; The ADU-Evaluator is a modification of the full-blown evaluator which was ;;; presented in lecture and is part of the problem set for this unit. This ;;; evaluator is smaller, and all of the abstraction barriers have been broken ;;; down -- we use the concrete CADDR (and similar) selectors to get at the ;;; various bits and pieces of expressions. *This is not the way you would ;;; really build an evaluator!* But it makes understanding ours a little ;;; easier. ;;; ;;; Our language here will be ADU-Scheme where all keywords have been prefixed ;;; by "adu:". So, for example, we will write expressions like, ;;; ;;; (adu:define (square x) (adu:* x x)) ;;; ;;; to help us keep track of exactly which primitives and special forms are ;;; which. It is, in every other sense, just like Scheme. To make things ;;; *completely* clear, we could even prepend the "adu:" moniker to symbols, ;;; as in: ;;; ;;; (adu:define (adu:square adu:x) (adu:* adu:x adu:x)) ;;; ;;; but that gets a bit tiresome. Use colored chalk (or ink) instead. ;;; ;;; For the examples at the end of this file, we assume the following bindings ;;; have already been made in the GLOBAL-ENVIRONMENT: ;;; ;;; adu:+ ... [ prim-proc-add ] ;;; adu:- ... [ prim-proc-sub ] ;;; adu:* ... [ prim-proc-mul ] ;;; adu:< ... [ prim-proc-less-than? ] ;;; ;;; Everything else is either a special form (in ADU-Scheme) or a variable ;;; that gets bound as expressions are evaluated. ;;; ADU-EVAL ;;; ;;; The first half! ;;; ;;; This takes an expression (which is a list!) and evaluates it in the ;;; supplied environment. (define (adu-eval exp env) ;; dispatch on expression type (cond ;; BASE CASES ;; self-evaluating (eg, numbers) ((number? exp) ; self-evaluating? exp) ; return exp ;; symbols -- value will be fetched from environment ((symbol? exp) ; variable? (lookup-variable-value exp env)) ; look up value in env ;; SPECIAL FORMS ;; rule for quoted objects ;; (adu:quote ) ((eq? (car exp) 'adu:quote) ; quoted? (cadr exp)) ; return rest of list! ;; rule for procedure objects in the environment model ;; (adu:lambda () ) ((eq? (car exp) 'adu:lambda) ; lambda? (list 'proc-obj ; make-procedure (cadr exp) ; the lambda parameters (caddr exp) ; the lambda body env)) ; the defining environment ;; rule for if statements ;; (adu:if ) ((eq? (car exp) 'adu:if) ; adu:if? (eval-adu:if exp env)) ; pass on the joy ;; can add other special forms -- define, set!, begin, cond ;; the code would go here ... ;; COMBINATIONS ;; -- a.k.a. non-special forms -- ;; ( ... ) (else (adu-apply (adu-eval (car exp) env) ; operator (list-of-values (cdr exp) ; operands env))))) ;;; ADU-APPLY ;;; ;;; The other half! ;;; ;;; This takes an procedure object (the first argument) and applies it to a ;;; list of evaluated arguments (the second argument). (define (adu-apply procedure arguments) ;; dispatch on procedure type (cond ;; primitive procedure? ;; (most every fully-evaluatable expression eventually gets here) ((primitive-procedure? procedure) ; magic (apply-primitive-procedure procedure arguments)) ;; procedure object? ((eq? (car procedure) 'proc-obj) ;; procedure is (proc-obj