Purpose:

The goal of this problem set is to help you design generative recursive functions and 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:

Note: You must use DrScheme's HtDP Intermediate Student Language plus Lambda for this problem set.

1. Abstract over xexpr-find, xexpr-depth, and xexpr-elements. That is, create a single function that consumes and processes an Xexpr and demonstrate that the three functions are simple "instances" of this function.

   Hint: Start from the template for all three functions. (Remember that since all three functions process the same kind of input data their templates -- i.e., their organizational skeletons -- are identical. Then create a function that consumes appropriate functions and "base values". Recall that -- in general -- when you go from a template to the final code, you use built-in functions or your own to "combine" the values in a clause (from the recursive calls, the remaining fields, other parameters, and global constants).

   Knowledge: This abstraction is at the core of many XML processing languages and thus shows up at the heart of many XML libraries.

2. Solve all exercises in section 28.2 of HtDP (pages 414-416). Then design an animated version of the program. The animation should show one queen placement and its threats at a time.

3. Design an evaluator for the following snippet of Perthon, a brand-new C-like scripting language:

   A Program is a Definition followed by an Expression within parens: 
     (Definition Expression)
   
    A Definition has the following shape: 
     (def Variable (Variable) ret Expression)
   
    An Expression is one of 
     -- a Variable 
     -- a Constant 
     -- (Expression ++ Expression)
     -- (Variable $$ Expression)
     -- (? Expression : Expression , Expression)
   
    A Constant is a String, which is ", followed by a sequence of keyboard
     characters, followed by another ". 
   
    A Variable is one of: 
     -- A 
     -- ...
     -- Z 
   

   where "(", ")", "def", "ret", "?", ":", ",", "$$", "++", and A through Z are keywords (literal tokens), i.e., they are "words" that must appear as such in Perthon sentences. Example:

   (
    (def F (X) ret (? X : "hello" , "world"))
    ((F $$ "") ++ (F $$ "hello"))
   )
   

   While a definition introduces a function of one argument, an expression is the mechanism to produce a value. A Variable in an expression is just a placeholder for some value. A literal Constant is already a String. The ++ expressions concatenates the results of the two sub-expressions, and the $$ expression is a function call. The last expression (? test : then , else) is a conditional expression; it produces the value of the then branch if the value of the test position is the empty String; otherwise the result of the conditional expression is the value of the else branch.

   The evaluator for Perthon programs consumes one program and produces a String. The latter is the result of the program's expression.

   Background knowledge: A function call (Variable $$ Expression) is evaluated in two steps: first the expression evaluator determines the value of the argument expression, and then it determines the value of the function body after substituting the value of the argument for all occurrences of the function parameter.

   Task: Your primary task is to design the function Perthon, which consumes (the data representation of) a Perthon program and, if it is good (see below), produces its value. If the program is not good, return the string "bad program". We recommend that you think along the following lines:

   1. Develop a data representation of Perthon programs in ISL+.
   2. Develop the function static-check. It consumes (the data representation of) a Perthon program and ensures that two constraints hold. First, the only variable name that may occur in the program expression is the name of the defined function as the first part of a function call. Second, the only variable names that may occur in the body of the function are the name of the function and the name of the function's parameter. If a program satisfies these constraints we call it good.
   3. Develop the function expression-evaluator, which consumes (the data representation of) a Perthon expression and a Perthon (data representation of a) function. Its result is the value of the expression where all function calls are interpreted as calls to the given function.
   Alternative designs are welcome, just be sure you can justify them.