 Due date: 10/23
Purpose:
The goal of this problem set is to help you design generative recursive
functions, dealing with graphshaped data.
Drill:
HtDP: 27.3.1, 27.3.6, 28.2.1, 28.2.2, 28.2.3, 28.2.4
Required Problems:

The goal of this exercise is to design an evaluator for boolean
expressions in the presence of a booleantyped 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


(definestruct nt (sub))
(definestruct nd (lft rgt))
;; A BER is one of:
;;  Boolean
;;  Symbol
;;  (makent BER)
;;  (makend 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 BER s. 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 expressionif 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;
}


(definestruct fun (name para body))
;; FBER = (makefun 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)


(definestruct cll (name arg))
;; BER with
;; ...
;;  (makecall Symbol BER)

The interpretation is of course that
(makefun 'f 'x (makent 'x)) represents
boolean f(boolean x) { return !x; } and that
(makecall 'f (makend true false))
stands for
f(true && false) .
Design the fevaluate functionusing 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 expressionif
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 (makecll 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?

Solve all exercises in section 27.5 of HtDP (pages 401406).
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) ...)
(checkexpect (remove 'a '(b c a a)) '(b c a))
(checkexpect (remove '(a b) '((c d) (b a) (a b))) '((c d) (b a)))
Design the function, before tackling exercise 27.5.5.
