Due date: 10/28
The goal of this problem set is to help you design generative recursive
functions and dealing with graph-shaped data.
HtDP: 27.3.1, 27.3.6, 28.2.1, 28.2.2, 28.2.3, 28.2.4
Note: You must use DrScheme's HtDP Intermediate Student
Language plus Lambda for this problem set.
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.
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.
Design an evaluator for the following snippet of Perthon, a
brand-new C-like scripting language:
where "(", ")", "def", "ret", "?", ":", ",", "$$", "++", and A
through Z are keywords (literal tokens), i.e., they are "words" that must
appear as such in Perthon sentences.
A Program is a Definition followed by an Expression within parens:
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:
(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
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
$$ 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.
Your primary task is to design the function
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:
Alternative designs are welcome, just be sure you can justify them.
- Develop a data representation of Perthon programs in ISL+.
- 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.
- 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.