C311 script3.txt -- 1/27/97

---

INTERPRETERS

---

Language:

<expession> --> <variable> | <literal> | (<operator> <operand>*)

  * means "zero or more of the preceding" (Kleene-star)

<operator>, <operand> --> <expression>

  both operator and operand are expressions

<literal> --> <Scheme number>

<variable> --> <Scheme symbol>


E.g. Assuming the environment binds the binary operators +, -, and *,
and the unary operators add1 and sub1, we might have the following
expression:

(+ (* 1 2) (- 3 (sub1 4)))

---

> (define variable? symbol?)

> (define literal? number?)

> (define app->rator car)

> (define app->rands cdr)

> (define eval-exp
    (lambda (exp)
      (cond
	((literal? exp) exp)
	((variable? exp) (apply-env init-env exp))
	(else
	  (let ((proc (eval-exp (app->rator exp)))
		(args (eval-rands (app->rands exp))))
	    (apply-proc proc args))))))

> (define eval-rands
    (lambda (rands)
      (map eval-exp rands)))

> (define create-empty-ff
    (lambda ()
      (lambda (symbol) 
	(error 'empty-ff "no association for symbol: ~s" symbol))))

> (define extend-ff*
    (lambda (sym-list val-list ff)
      (lambda (symbol)
	(let ((x (memq symbol sym-list)))
	  (if (not x)
            (apply-ff ff symbol)
            (list-ref val-list (- (length sym-list) (length x))))))))

> (define apply-ff
    (lambda (ff symbol) 
      (ff symbol)))

> (define the-empty-env (create-empty-ff))

> (define extend-env extend-ff*)

> (define apply-env apply-ff)

> (define *prim-op-names* '(+ - * add1 sub1))

---

Represent primative procedures by their names.

--- 

> (define init-env
    (extend-env
      *prim-op-names*
      *prim-op-names*
      the-empty-env))

> (define apply-proc
    (lambda (prim-op args)
      (case prim-op
	((+) (+ (car args) (cadr args)))
	((-) (- (car args) (cadr args)))
	((*) (* (car args) (cadr args)))
	((add1) (+ (car args) 1))
	((sub1) (- (car args) 1))
	(else (error 'apply-prim-op "Invalid prim-op name: ~s" prim-op)))))

> (eval-exp 5)
5
> (define run eval-exp)
> (run '(* (add1 2) (- 6 4)))
6
> (define repl ; read-eval-print loop
    (lambda ()
      (display "--> ")
      (write (run (read)))
      (newline)
      (repl)))
> (repl)
--> 5
5
--> (add1 2)
3
--> (* (add1 2) (- 6 4))
6

---

Represent primitive procedures as list-records.

---

> (define make-prim-proc
    (lambda (prim-op-name)
      (list 'prim-proc prim-op-name)))

> (define init-env 
    (extend-env
      *prim-op-names*
      (map make-prim-proc *prim-op-names*)
      the-empty-env))

> (define apply-prim-op apply-proc)

> (define apply-proc
    (lambda (proc args)
      (if (pair? proc)
	(record-case proc
	  (prim-proc (prim-op) (apply-prim-op prim-op args))
	  (else (error 'apply-proc "Invalid procedure: ~s" proc)))
	(error 'apply-proc "Invalid procedure: ~s" proc))))

---

Compare with the interpreter in the book:

(define eval-exp
   (lambda (exp)
      (variant-case exp
	(lit (datum) datum)
	(varref (var) (apply-env init-env var))
	(app (rator rands)
	  (let ((proc (eval-exp rator))
		(args (eval-rands rands)))
	    (apply-proc proc args)))
	(else (error "Invalid abstract syntax: " exp)))))

(define the-empty-env (create-empty-ff))
(define extend-env extend-ff*)
(define apply-env apply-ff)

(define-record prim-proc (prim-op))

(define apply-proc
  (lambda (proc args)
    (variant-case proc
      (prim-proc (prim-op) (apply-prim-op prim-op args))
      (else (error "Invalid procedure:" proc)))))
---

The rest, such as apply-prim-op, is the same as our version.  

    > (define run
	(lambda (x)
	  (eval-exp (parse x))))
    > (run '5)
    5
    > (run '(add1 2))
    3

---

Assignment: add if

---

END

---