The goal of this problem set is to understand the representation and evaluation of simple programs.

---

Problem A1:

Review section 14.4 in the book, including the problems. Now, consider these data definitions:

  ; a Value is one of: Number String
  ;
  ; a Prim is one of:
  ; '+ '- '* '/ 'sqrt
  ; 'string-length 'string-append 'number->string
  ;
  ; a PExp (primitive expression) is one of: Value PApp
  ;
  ; a PApp (primitive application) is a (cons Prim [Listof PExp])

In all of the following, use loop functions such as map and member? where possible, and consider using apply where appropriate as well. You may find it easier to first implement the functions without these "power tools" and then look for ways to simplify the code by using them.

Part 1: fill in the ... in the following functions, and make sure all the tests pass:

  ; prim?: Any -> Boolean
  ; is the argument a primitive?
  (define (prim? v) ...)
  
  (check-expect (prim? '+) true)
  (check-expect (prim? 'number->string) true)
  (check-expect (prim? 'foo) false)
  
  ; apply-prim: Prim [Listof Value] -> Value
  ; apply a primitive to a list of parameter values
  ; the primitives '+ '- '* '/ and 'string-append accept two or more inputs each
  ; the remaining primitives accept one input only
  (define (apply-prim fn vals) ...)
  
  (check-expect (apply-prim '+ '(1 2 3)) 6)
  (check-expect (apply-prim '- '(1 2 3)) -4)
  (check-expect (apply-prim '* '(1 2 3)) 6)
  (check-expect (apply-prim '/ '(1 2)) (/ 1 2))
  (check-expect (apply-prim 'sqrt '(4)) 2)
  (check-expect (apply-prim 'string-length '("foo")) 3)
  (check-expect (apply-prim 'string-append '("a" "b")) "ab")
  (check-expect (apply-prim 'number->string '(23)) "23")
  

Part 2: fill in the ... in the following function, and make sure all the tests pass:

  ; prim-eval: PExp -> Value
  ; evaluate a primitive expression
  (define (prim-eval s) ...)

  (check-expect (prim-eval 2) 2)
  (check-expect (prim-eval "a") "a")
  (check-expect (prim-eval '(+ 3 (* 2 3))) 9)
  (check-expect (prim-eval '(string-append "a" (number->string 2))) "a2")
  (check-expect (prim-eval '(* (string-length "bob") 2)) 6)
  

Congratulations, you have now made a Scheme expression interpreter that can handle numeric and string operations, including nested subexpressions! However, it does not know about user-defined functions...

Problem A2:

Review section 17.7 in the book, including the problems. Then consider these data definitions, in addition to those from Problem A1:

  ; a Name is a Symbol
  ;
  ; a Func is one of: Prim Name
  ;
  ; a SExp (simple scheme expression) is one of: Value Name App
  ;
  ; an App (application) is a (cons Func [Listof SExp])
  ;
  ; a Def (definition) is a (make-def Name [Listof Name] SExp)
  (define-struct def (name args body))

And this "starter" list of definitions:

  (define the-defs (list (make-def 'pi '() 3.14)
                         (make-def 'length '(x y) '(sqrt (+ (* x x) (* y y))))
                         (make-def 'circumference '(r) '(* 2 pi r))
                         (make-def 'prepend-bob '(s) '(string-append "bob" s))))

In all of the following, use loop functions such as map where possible, and consider using lambda where appropriate as well. And, of course, use your solutions from problem A1 as needed.

Part 1: fill in the ... in the following function, and make sure all the tests pass:

  ; lookup: Name Number [Listof Def] -> Def
  ; find the definition with the given name and number of args in defs
  ; or (error name " not defined")
  (define (lookup name nargs defs) ...)
  
  (check-expect (def-body (lookup 'pi 0 the-defs)) 3.14)
  (check-expect (def? (lookup 'length 2 the-defs)) true)
  (check-error (lookup 'length 3 the-defs))
  (check-error (lookup 'sqr 1 the-defs))

Part 2: fill in the ... in the following function, and make sure all the tests pass:

  ; subst: [Listof Value] [Listof Name] SExp -> SExp
  ; substitute the corresponding value for each listed variable name in s
  ; leave all other names in s unmodified
  (define (subst vals vars s) ...)

  (define s1 '(foo a 29 (bar "z" b)))
  (check-expect (subst '(3 "x") '(a b) s1) '(foo 3 29 (bar "z" "x")))

Part 3: fill in the ... in the following functions, and make sure all the tests pass:

  ; my-apply: Func [Listof Value] [Listof Def] -> Value
  ; apply either a primitive or a defined function to a list of parameter values
  (define (my-apply fn vals defs) ...)

  ; my-eval: SExp [Listof Def] -> Value
  ; evaluate a scheme expression given a list of definitions
  (define (my-eval s defs) ...)

  (check-expect (my-apply '+ '(1 2 3) the-defs) 6)
  (check-expect (my-apply 'length '(3 4) the-defs) 5)
  (check-error (my-apply 'sqr '(2) the-defs))
  (check-error (my-apply 'circumference '(1 2) the-defs))

  (check-expect (my-eval 2 the-defs) 2)
  (check-expect (my-eval "b" the-defs) "b")
  (check-expect (my-eval '(+ 3 4) the-defs) 7)
  (check-expect (my-eval 'pi the-defs) 3.14)
  (check-expect (my-eval '(* 2 pi) the-defs) 6.28)
  (check-expect (my-eval '(prepend-bob (number->string 18)) the-defs) "bob18")
  (check-expect (my-eval '(circumference 2) the-defs) (* 4 3.14))
  (check-expect (my-eval '(circumference (/ 10 (length 3 4))) the-defs) (* 4 3.14))
  (check-expect (my-eval '(* (string-length (string-append "a" "b")) 4) the-defs) 8)
  (check-error (my-eval '(sqr 4) the-defs))
  (check-expect (my-eval '(sqr 4) (cons (make-def 'sqr '(x) '(* x x)) the-defs)) 16)

Hint: my-apply and my-eval should be mutually recursive.

Double congratulations! You have now extended your Scheme interpreter to handle user-defined names for both values (when the number of arguments in the definition is 0) and functions with one or more named parameters (i.e. variables).

Challenge: This assignment is not easy. That said, it is possible to solve it in less than 45 lines, not counting comments and tests, without going over 80 characters on any line, and without sacrificing readability. That's about 35 additional lines of code to finish out the code we provided above. It's pithy code, but not a lot of it. (The graders will consider clarity and conciseness in evaluating your code, but you do not have to strive to make it as short as possible. Just try to make a good clear design.)