Recitation 15

Today's Ideas:
-- recursive evaluation of expressions
-- global environments
-- evaluating BASIC

Part 1: Expression Evaluation

We started by playing with a slightly modified version of the expression evaluator presented in class yesterday. The only difference was that sum expressions had the plus sign in the middle, and not at the beginning. Our new evaluator also didn't handle define. So

We noted that we could evaluate simple sums

    (eval-expr '(1 + 2))

and nested sums

    (eval-expr '(1 + (2 + 3)))

We drew an abstract syntax tree for this kind of expression and talked about the idea of recursive evaluation. There are two kinds of expressions, sums and numbers, and the evaluator simply returns a number and calls itself recursively for a sum, adding the results. I pointed out that all the programming work is actually in the procedures that determine what an expression is and break it into parts -- boring but essential stuff. We discussed why you couldn't just order the checks in the cond statement with an else in place of the sum? test.
We want

    (eval-expr '(1 1))

to signal an appropriate error.

We noted that of course a number is an expression to, so we can do

    (eval-expr 34)

and (to my surprise) this surprised some of you.

The second crucial aspect of the expression evaluator was binding of names. We noted that

  (eval-expr '(x + 2))

threw an error ("unbound variable"), but gave 5 after we first executed

  (table-put! environment 'x 3)

I pointed out that we have a simple notion of binding here -- a single, global environment -- and promised that in lecture on Thursday you'd see real environments.

Finally, we noted that the expression evaluator handles one kind of test: a comparison of two numbers, so

    (eval-expr '(4 > 3))

gives #t.

Part 2: Statement Evaluation

I then showed you an evaluator for a BASIC-like language. Given a program such as
  (x = 0)
  (LOOP : x = (x + 1))
  (print (x + x))
  (if (10 > x) goto LOOP)
it successfully printed out
I then gave you a challenge to write the top-level evaluator that would execute such a program. I told you that this language has only three kinds of statement: a print statement of the form

    print <expr>

an assignment statement of the form

    <var> = <expr>

and an if statement of the form

    if <test-expr> goto <label>

and that each statement can have an optional label and semicolon at the front.

I told you to assume that you had all the boring utility procedures you needed, and showed you some of these working:

> (assign? '(print 3))

> (assign? '(x = 3))

> (assign-var '(x = 3))

> (assign-expr '(x = 3))

I told you to start thinking first about programs without if statements. Most of you got the basic idea:

-- the top-level evaluator takes a list of statements
-- if the list is empty, it prints done
-- otherwise, it evaluates the first, then calls itself recursively on the rest

To evaluate a statement, we simply use the expression evaluator. An assignment, for example, is handled by expression-evaluating the expression, then doing a table-put! to bind the name to that value in the environment.

Then you thought about labels.

Several of you came up with a clever idea. When you see a statement list starting with a statement that is labelled, you insert into the environment a binding of that label to that list. This is elegant, but has two problems:

1. You can't use a label name that is also a variable name. This could be fixed by having separate label and variable environments.

2. A bigger snag -- you can't handle an if-statement that jumps to a label that hasn't yet been encountered. To fix this, you need to pass over the program in advance and prepare a table that binds labels to statement lists.

The code below shows how to do this. Note that I've used a data abstraction to represent the program state. It combines in a single abstract object the label table and the current statement list (representing essentially the program counter). Its operations are:

    end? : ProgramState -> Bool                                        ; returns true if there are no more statements to execute
    next-state : ProgramState -> ProgramState                ; returns the state corresponding to a single step
    lookup-label : ProgramState, Label -> ProgramState  ; returns the state following a goto to the given label



(define (sum? e)
  (and (pair? e) (pair? (cdr e)) (eq? (cadr e) '+)))
(define (greater? e)
  (and (pair? e) (pair? (cdr e)) (eq? (cadr e) '>)))

(define (eval-greater exp)
  (> (eval-expr (car exp)) (eval-expr (caddr exp))))

(define (eval-sum exp)
   (+ (eval-expr (car exp)) (eval-expr (caddr exp))))

(define (eval-expr exp)
   ((number? exp) exp)
   ((sum? exp)    (eval-sum exp))
   ((symbol? exp) (lookup exp))
   ((greater? exp) (eval-greater exp))
    (error "unknown expression " exp))))

(define environment (make-table))

(define (lookup name)
  (let ((binding (table-get environment name)))
    (if binding
        (binding-value binding)
        (error "unbound variable: " name))))


; evaluate from a program state ps
(define (eval ps)
  (if (end? ps)
      (display 'done)
      (let ((stmt (first-stmt ps)))
        (cond ((print? stmt) (display (eval-expr (print-expr stmt))) (newline))
              ((assign? stmt)
                 (table-put! environment
                             (assign-var stmt)
                             (eval-expr (assign-expr stmt)))))
        (cond ((and (if? stmt) (eval-expr (if-test stmt)))
                 (eval (lookup-label ps (if-label stmt))))
              (else (eval (next-state ps)))))))


; a program state is represented as a pair
; the car part is a table mapping labels to lists
; where the first element in the list for label X is the statement labelled X,
; and the second element is the statement following that one, etc.
; the car part is a list of statements starting at the next to be executed

;; return the program state after executing current statement
(define (next-state ps) (cons (car ps) (cddr ps)))

;; return the statement about to be executed
(define (first-stmt ps) (cadr ps))

;; return the program state resulting from a goto to label
(define (lookup-label ps label)
  (let ((result (table-get (car ps) label)))
    (if result
        (cons (car ps) (binding-value result))
        (error "no such label" label))))

(define (end? ps) (null? (cdr ps)))

;; take program text p consisting of a list of statements
;; and return the program state corresponding to the initial state
(define (text-to-initial-state pgm)
  (let ((table (make-table)))
    (insert-label-entries table pgm)
    (cons table pgm)))

(define (insert-label-entries table pgm)
  (if (null? pgm)
        (insert-label-entry table (car pgm) pgm)
        (insert-label-entries table (cdr pgm)))))

(define (insert-label-entry table s pgm)
  (if (stmt-labelled? s)
      (table-put! table (stmt-label s) pgm)))


;; Boring, but necessary

(define (stmt-labelled? s)
  (and (pair? s)
       (pair? (cdr s))
       (eq? (cadr s) ':)))

(define (strip-label s) (cddr s))
(define (stmt-label s) (car s))
(define (apply-to-stripped proc)
  (lambda (stmt)
    (if (stmt-labelled? stmt)
        ((apply-to-stripped proc) (strip-label stmt))
        (proc stmt))))

(define print?
   (lambda (s)(and (pair? s) (eq? (car s) 'print)))))
(define assign?
   (lambda (s)(and (pair? s) (pair? (cdr s)) (eq? (cadr s) '=)))))
(define if?
   (lambda (s)(and (pair? s) (eq? (car s) 'if)))))

(define print-expr
   (lambda (s)(cadr s))))
(define assign-var
   (lambda (s)(car s))))
(define assign-expr
   (lambda (s)(caddr s))))
(define if-test
   (lambda (s)(cadr s))))
(define if-label
   (lambda (s)(cadddr s))))

Definitions used


(define table-tag 'table)
(define (make-table) (cons table-tag '()))
(define (tag-check e sym) (and (pair? e) (eq? (car e) sym)))
(define (table? x) (tag-check x table-tag))

(define (add-assoc key val alist) (cons (list key val) alist))

(define (table-put! tbl key val)
  (set-cdr! tbl (add-assoc key val (cdr tbl))))
(define (table-get tbl key)
  (assq key (cdr tbl)))
(define binding-value cadr)

Daniel Jackson
October 27, 1999