Purpose:

The goal of this problem set is to help you design generative recursive functions, dealing with graph-shaped data.

---

Drill:

HtDP: 27.3.1, 27.3.6, 28.2.1, 28.2.2, 28.2.3, 28.2.4

---

Required Problems:

1. The goal of this exercise is to design an evaluator for boolean expressions in the presence of a boolean-typed function definition. Consider the following information "world" and data definitions:

   Information		Data Representation
   A BE is one of: -- true -- false -- x, y, z, ... -- ! BE -- BE && BE		(define-struct nt (sub)) (define-struct nd (lft rgt)) ;; A BER is one of: ;; -- Boolean ;; -- Symbol ;; -- (make-nt BER) ;; -- (make-nd BER BER)

   On the left, you see conventional boolean expressions from the kind of programming languages you know from your undergraduate education. Of course, you can also express these "programs" in DrScheme's BSL, enter them into the Definitions window, and run them (or step through them). If you are more comfortable with the C programming language or the Java language, use that "world" to explore the information that we are representing with this data collection.

   On the right you see a data representation for this "world" in ISL. This is formulated in the data sublanguage of ISL. Your solution must be designed and presented in ISL (plus lambda), but for the intellectually curious, I recommend that you also solve this problem in your favorite language (no matter what it is). It will definitely help you understand the design recipe.

   Make up data examples of BERs. Interpret them in the "world". Create equivalent Scheme expressions. Then, as a first step, design an evaluator function, which consumes a BER and produces the boolean value that DrScheme would produce for an equivalent boolean expression--if possible. Naturally, if the given BER -- contains symbols evaluating the expression is impossible; in that case, evaluator returns the symbol '*error*.

   Let's extend this small language a tiny bit:

   Information		Data Representation
   FBE is: -- boolean f(boolean x) { return BE; }		(define-struct fun (name para body)) ;; FBER = (make-fun Symbol Symbol BER)

   On the left you see function definitions on boolean values as you know them, and on the right is our favorite data representation for them. For this to make sense, we also need to extend our boolean language with function calls:

   Information		Data Representation
   A BE is one of: ... -- name(BE)		(define-struct cll (name arg)) ;; BER with ;; ... ;; -- (make-call Symbol BER)

   The interpretation is of course that (make-fun 'f 'x (make-nt 'x)) represents boolean f(boolean x) { return !x; } and that (make-call 'f (make-nd true false)) stands for f(true && false).

   Design the fevaluate function---using and in the process modifying evaluator from above. The function consumes a BER and an FBER and produces the boolean value that DrScheme would produce for an equivalent boolean expression---if possible. If

   • the given BER contains symbols other than the function name in the given FBER, or
   • if the body of the given FBER contains any other symbols than the name of the function or the name of the parameter
   fevaluate produces '*error*.

   Background knowledge: A function call (make-cll f b) is evaluated by evaluating the body of f after replacing all occurrences of f's parameter with the value of arg. Of course, this is nothing but the rule of function evaluation you know from high school algebra, but we thought a reminder wouldn't hurt.

   Make sure your fevaluate can cope with the evaluation of f(false) where the definition of f is given as follows:

   
    boolean f(boolean x} {
     return !x && f(!x); 
    }
   
   

   Why does this work in your favorite language?

2. Solve all exercises in section 27.5 of HtDP (pages 401-406). The second paragraph on page 402 starts with a possibly misleading sentence. Here is a better version: The generative step in the triangulation phase is to subtract appropriate multiples of the first row of numbers from all other rows of numbers, with the goal of obtaining leading 0s in these rows. -- Also exercise 27.5.5 falsely claims that the HtDP languages support the library function remove. This statement is incorrect; in return, I am specifying its functionality with a contract, purpose statement, and an example:

   
    ;; remove : X [Listof X] -> [Listof X]
    ;; remove the first occurrence of x that is equal? to some item on l
    (define (remove x l) ...) 
   
    (check-expect (remove 'a '(b c a a)) '(b c a))
    (check-expect (remove '(a b) '((c d) (b a) (a b))) '((c d) (b a)))
   

   Design the function, before tackling exercise 27.5.5.