Due: Friday, October 29th, 2010 9:40am
In this homework assignment, you will implement an miniature version of DrRacket — or, at least, the part that evaluates expressions.
Based on section 14.4 in the book, complete exercises HtDP exercise 14.4.1 (page 208) through HtDP exercise 14.4.4 (page 209).
For 14.4.3, if you’re reading the paper copy of the book that calls the function evaluate, call it evaluate-expression instead. Also, instead of making evaluate-expression produce false for a non-numeric expression, make it report an error using the error function. Use check-error to test non-numeric examples. Overall, evaluate-expression doesn’t need to use numeric?.
These exercises are stepping stones to part 2. As you implement part 2, your evaluate-expression function should turn into evaluate-with-defs, and then evaluate-expression can be implemented by simply calling interp-with-defs with an empty list of definition.
Based on section 17.7 in the book, complete exercises HtDP exercise 17.7.1 (page 248) through HtDP exercise 17.7.4 (page 249).
For 17.7.1, you will need to add a define-struct for representing function applications. Call it app, so that (make-app 'f 20) represents a call to a function named f with the argument 20. Note that you will need to update subst (or any other function that works on expressions) when you add a new expression variant.
For 17.7.2, you will need to add a define-struct for representing function definitions. Call it def, so that (make-def 'f 'x (make-add 'x 1)) represents the definition of a function named f that takes an argument named x and adds 1 to it.
Exercise 17.7.3 is a stepping stone to 17.7.4. You can skip 17.7.3 if you prefer. Use check-error for examples where a function name in an app has no coresponding defn.
If you’re reading the paper copy of the book that calls the functions interpret-with-one-def and interpret-with-defs, call the functions evaluate-with-one-def and and evaluate-with-defs instead.
(define test-defns (list
(make-def 'f 'x (make-add 'x 1))
(make-def 'g 'x (make-add 'x 10))))
(check-expect (evaluate-with-defs (make-app 'g (make-app 'f 7)) test-defns)
18)This part is optional.
Extend your interpreter with three more kinds of expressions: literal booleans, a zero? operation, and an if form.
Represent a use of the zero? operation with a struct named is-zero that has a single sub-expression field, so that (make-is-zero 'x) represents the expression that applies the zero? operator to the variable x.
Represent an if form with a branch struct that has three fields — one each for the test, then case, and else case — so that (make-branch (make-is-zero 'x) 0 (make-add 'x -1)) represents an expression that checks whether x is zero and returns 0 if so, otherwise returns x minus 1.
Change the contract on evaluate-with-defs so that it can produce a result that is either a number or boolean. Also, change the contract on subst so that it can accept any result (number or boolean) for the value to substitute. For updating numeric?, let’s say that an expression is numeric even if it contains booleans.
With this addition, your interpreter can execute classic toy programs, such as computing factorial:
(define fact-defn
(make-defn 'fact
'n
(make-branch (make-is-zero 'n)
1
(make-mul 'n (make-app 'fact
(make-add 'n -1))))))
(check-expect (evaluate-with-defs (make-app 'fact 4) (list fact-defn))
24)This part is optional and more challenging.
Extend your interpreter with one more kinds of expression: lambda for single-argument functions. Call the new struct lam. Revise your data definition so that make-app allows an expression as its first argument, and change the definition of results to include lams. Don’t bother updating numeric?.
Mixing top-level definitions and functions-as-expressions complicates the interpretation of identifiers. Change your interpreter so that an identifier can be an expression as long as the identifier has a function definition. In that case, synthesize a lam expression to serve as the value for the identifier:
(check-expect (evaluate-with-defs 'f (list (make-def 'f 'x (make-add 'x 1))))
(make-lam 'x (make-add 'x 1)))Adding lambda also complicates subst. If subst is given (make-lam 'x (make-app 'x 1)) and asked to replace every 'x with 7, then it should leave the lam struct alone, because the 'x for the lam argument must be a different 'x than the one that is being replaced. More generally, subst should leave a lam alone when the name of the lam’s argument matches the name that is being replaced.
(check-expect (subst 'x 10 (make-lam 'x 'x)) (make-lam 'x 'x)) (check-expect (subst 'x 10 (make-lam 'y 'x)) (make-lam 'y 10))
Adding lam to your interpreter makes it extremely powerful, although that may not be immediately apparent. It turns out, for example, that you can encode lists using lam without explicitly adding support for lists to your interpreter. Below is a stress test for your interpreter that defines and encoding of lists and uses it to sum the numbers in a list containing 8 and 17.
(define defns
(list
;; Encode `cons', `first', `rest', `empty', and `empty?'
;; using functions:
(make-def 'pair 'a
(make-lam 'b (make-lam 'p (make-app (make-app 'p 'a) 'b))))
(make-def 'fst 'v
(make-app 'v (make-lam 'a (make-lam 'b 'a))))
(make-def 'snd 'v
(make-app 'v (make-lam 'a (make-lam 'b 'b))))
(make-def 'empty 'p
(make-app (make-app 'p 0) 0))
(make-def 'cons 'a
(make-lam 'b (make-app (make-app 'pair 1) (make-app (make-app 'pair 'a) 'b))))
(make-def 'empty? 'x
(make-is-zero (make-app 'fst 'x)))
(make-def 'cons? 'x
(make-branch (make-is-zero (make-app 'fst 'x)) false true))
(make-def 'first 'c
(make-app 'fst (make-app 'snd 'c)))
(make-def 'rest 'c
(make-app 'snd (make-app 'snd 'c)))
;; Implement `sum' using `empty?', `first', and `rest':
(make-def 'sum 'l
(make-branch (make-app 'empty? 'l)
0
(make-add (make-app 'first 'l)
(make-app 'sum (make-app 'rest 'l)))))))
;; Call the `sum' function:
(check-expect (evaluate-with-defs (make-app 'sum
(make-app (make-app 'cons 8)
(make-app (make-app 'cons 17)
'empty)))
defns)
25)| Last update: Monday, October 25th, 2010mflatt@cs.utah.edu |