Problem$^a$ 6.   Your boss developed this program fragment:

;; Expression is one of: 
;; -- Number 
;; -- Symbol 
;; -- (cons - (cons Expression (cons Expression empty)))

(define-struct entry (name expr))
;; Entry is: (make-entry Symbol Expression)

;; defs : Listof[Entry]
(define defs (list (make-entry 'x '(- y 5))
                   (make-entry 'y '(- z 1))
                   (make-entry 'z 2)))

;; salve : Expression -> Number 
;; determine the value of a expression
(define (salve x) _____________________________________)

;; lookup : Symbol Listof[Entry] -> Expression
;; find the Entry with x as name in env, produce its expr
(define (lookup x env)
  (cond
    [(empty? env) (error "can't happen")]
    [else (local ((define fst (first env)))
            (cond
              [(symbol=? (entry-name fst) x) (entry-expr fst)]
              [else (lookup x (rest env))]))]))

;; Tests: 
(equal? (lookup 'z defs) 2)
(equal? (lookup 'y defs) '(- z 1))

(equal? (salve 22) 22)
(equal? (salve 'z) 2)
(equal? (salve 'x) -4)

Now he's stuck. His goal was to write a ``homework solver'' for his son in 7th grade who has to evaluate 100s of Expressions for his homework. Naturally the solver (called salve) consumes a Expression and spits out the Number that his son would find using the rules in his book. He thought he had it all worked out, but for some reason, he can't figure out the actual definition for salve.

Here is what he knows from his son's book:

1. A number evaluates just to itself. That's easy.

2. A symbol's meaning is determined by def and lookup can extract this meaning. But the meaning is just another expression. So he needs to figure out this expression's value, too.

3. A --expressions is easy to evaluate. Figure out the values of the two embedded expressions and those are numbers. Then add them up.

Why is item 2 strange for your boss who never mastered more than Part III of HtDP?

Solution PT 1 for ``generative'' in the answer.

Finish the definition of salve.

Solution

;; salve : Expression -> Number 
;; determine the value of a expr 
(define (salve x) 
  (cond 
    ;; [PT 1: one for three cond clauses, one for correct questions]
    [(number? x) x]
    ;; [PT 1: for gen rec call of salve on lookup]
    [(symbol? x) (salve (lookup x defs))]
    ;; [PT 1: for structural recursion here]
    [else (- (salve (second x)) (salve (third x)))]))

Is it possible for salve to not produce an answer for some Expression and some different definition for def? If so, show how. If not, write down one sentence that explains why.

Solution Yes: if we use (define defs (make-entry 'x 'x)) and run (salve 'x).