[FrontPage] [TitleIndex] [WordIndex

Here is the expression evaluator we discussed in class today. There are actually two versions here: One using only the forms we've actually discussed in class, including if and car/cdr, and the other as actually shown on the screen today. There are also some definitions at the end that begin to show how variable lookup could work. For even more, see a full scheme interpreter at InterpreterDotScm.

Simpler vocabulary:

;; note this one skips MUL and DIV to avoid running off the right side of the screen....

(define evaluate
  (lambda (expr)
    (if (number? expr)
        expr
        (if (eq? expr 'ADD)
            +
            (if (eq? expr 'SUB)
                -

                (if (list? expr)
                    (apply (evaluate (car expr))
                           (map evaluate (cdr expr)))
                    "error:  unknown expr type"))))))

What we looked at in class:

(define evaluate
  (lambda (expr)
    (cond ((number? expr) expr)
          ((eq? expr 'ADD) +)
          ((eq? expr 'SUB) -)
          ((eq? expr 'MUL) *)
          ((eq? expr 'DIV) /)
          ((list? expr) 
             (apply (evaluate (first expr)) 
                    (map evaluate (rest expr))))
          (#t "error:  unknown expr type"))))

Adding a lookup feature:

(define lookup
  (lambda (sym bindings)
    (if (empty? bindings)
        ("error: binding not found")
        (if (eq? sym (caar bindings))
            (cadar bindings)
            (lookup sym (cdr bindings))))))

(define evaluate-in-environment
  (lambda (expr env)
    (cond ((number? expr) expr)
          ((symbol? expr) (lookup expr env))
          ((list? expr) 
             (apply (evaluate-in-environment (first expr) env) 
                    (map (lambda (x)
                           (evaluate-in-environment x env))
                         (rest expr))))
          (#t "error:  unknown expr type"))))

(define the-global-environment
  (list (list 'ADD +)
        (list 'SUB -)
        (list 'MUL *)
        (list 'DIV /)
        (list 'ONE 1)
        (list 'TWO 2)
        (list 'THREE 3)
        (list 'FOUR 5)
        (list 'SEIS 6)
        (list 'SEPT 7)
        (list 'ACHT 8)
        (list 'KU 9)
        (list 'TEN 10)
        (list 'FALSE #f)
        (list 'TRUE #t)
        (list 'NONE '())))

Try:

(evaluate (list 'ADD 3 (list 'SUB 2 6 (list 'SUB 1)) 4))

(evaluate-in-environment (list 'ADD 'THREE (list 'DIV 'SEIS 'TWO) 'ACHT (list 'MUL 'KU (list 'SUB 'SEPT 1))) the-global-environment)

2013-07-17 10:42