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...

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.)