CprS376 Schedule
CprS376 Class 16
CprS376 Class 18

Separating Syntactic Analysis from Execution

Class 17 - Section 4.1



Contents

Analyzing mceval

;;;;METACIRCULAR EVALUATOR THAT SEPARATES ANALYSIS FROM EXECUTION
;;;; FROM SECTION 4.1.7 OF STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS

;;;;Matches code in ch4.scm

;;;;This file can be loaded into Scheme as a whole.
;;;;**NOTE**This file loads the metacircular evaluator of
;;;;  sections 4.1.1-4.1.4, since it uses the expression representation,
;;;;  environment representation, etc.
;;;;  You may need to change the (load ...) expression to work in your
;;;;  version of Scheme.
;;;;**WARNING: Don't load mceval twice (or you'll lose the primitives
;;;;  interface, due to renamings of apply).

;;;;Then you can initialize and start the evaluator by evaluating
;;;; the two lines at the end of the file ch4-mceval.scm
;;;; (setting up the global environment and starting the driver loop).


;;**implementation-dependent loading of evaluator file
;;Note: It is loaded first so that the section 4.1.7 definition
;; of eval overrides the definition from 4.1.1
; (load "ch4-mceval.scm")

;;===========================================

;; Modifications by Chris Parrish are tagged <cp: comment>

;; eval renamed to mceval to avoid redefining an important system primitive

;;===========================================

;;;SECTION 4.1.7

;; <cp: renamed eval to mceval>

(define (mceval exp env)
  ((analyze exp) env))

(define (analyze exp)
  (cond ((self-evaluating? exp) 
         (analyze-self-evaluating exp))
        ((quoted? exp) (analyze-quoted exp))
        ((variable? exp) (analyze-variable exp))
        ((assignment? exp) (analyze-assignment exp))
        ((definition? exp) (analyze-definition exp))
        ((if? exp) (analyze-if exp))
        ((lambda? exp) (analyze-lambda exp))
        ((begin? exp) (analyze-sequence (begin-actions exp)))
        ((cond? exp) (analyze (cond->if exp)))
        ((application? exp) (analyze-application exp))
        (else
         (error "Unknown expression type -- ANALYZE" exp))))

(define (analyze-self-evaluating exp)
  (lambda (env) exp))

(define (analyze-quoted exp)
  (let ((qval (text-of-quotation exp)))
    (lambda (env) qval)))

(define (analyze-variable exp)
  (lambda (env) (lookup-variable-value exp env)))

(define (analyze-assignment exp)
  (let ((var (assignment-variable exp))
        (vproc (analyze (assignment-value exp))))
    (lambda (env)
      (set-variable-value! var (vproc env) env)
      'ok)))

(define (analyze-definition exp)
  (let ((var (definition-variable exp))
        (vproc (analyze (definition-value exp))))
    (lambda (env)
      (define-variable! var (vproc env) env)
      'ok)))

(define (analyze-if exp)
  (let ((pproc (analyze (if-predicate exp)))
        (cproc (analyze (if-consequent exp)))
        (aproc (analyze (if-alternative exp))))
    (lambda (env)
      (if (true? (pproc env))
          (cproc env)
          (aproc env)))))

(define (analyze-lambda exp)
  (let ((vars (lambda-parameters exp))
        (bproc (analyze-sequence (lambda-body exp))))
    (lambda (env) (make-procedure vars bproc env))))

(define (analyze-sequence exps)
  (define (sequentially proc1 proc2)
    (lambda (env) (proc1 env) (proc2 env)))
  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc (car rest-procs))
              (cdr rest-procs))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence -- ANALYZE"))
    (loop (car procs) (cdr procs))))

(define (analyze-application exp)
  (let ((fproc (analyze (operator exp)))
        (aprocs (map analyze (operands exp))))
    (lambda (env)
      (execute-application (fproc env)
                           (map (lambda (aproc) (aproc env))
                                aprocs)))))

(define (execute-application proc args)
  (cond ((primitive-procedure? proc)
         (apply-primitive-procedure proc args))
        ((compound-procedure? proc)
         ((procedure-body proc)
          (extend-environment (procedure-parameters proc)
                              args
                              (procedure-environment proc))))
        (else
         (error
          "Unknown procedure type -- EXECUTE-APPLICATION"
          proc))))

'ANALYZING-METACIRCULAR-EVALUATOR-LOADED


Analyzing mceval Transcript

;; ch4-analyzingmceval.transcript

;; =============================

;; load mceval source code

;; load mceval source code

(load "ch4-mceval.ss")
(load "ch4-analyzingmceval.ss")

;; =============================

;; setup the global environment

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

;; enter the interpreter
;; type bye to quit

(driver-loop)

12
'hi-there
(quote hi-there)
(define a 2)
a
(set! a 9)
a
(define (add5 x) (+ 5 x))
(add5 5)
add5
(define add6 (lambda (x) (+ 6 x)))
(add6 6)
add6
(add6 (add5 4))
(define mult (lambda (x y) (* x y)))
(mult 3 4)
(= 0 1)
(= 1 1)
'()
(cond (true 'true) (else 'false))
(cond (false 'false) (else 'true))
(cond ((= 0 1) 'true) (else 'false))
(cond ((= 1 1) 'true) (else 'false))
bye

SICP Source Code

Programming Exercises

In class today we will continue our work on the following exercises from chapter 4: 1, 4, 5, 6, 7, 8, 11, 13, 14, 15, 16, 20, 23, 24, 25, 27, 29, 31, 33, 34, 38, 39, 42, 43, 45, 50, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 69.