Due date: 9/23 @ at the beginning of class
The goal of this problem set is to practice structurally recursive
programming and using inductive proofs.
Use the Redex programming language for all programming
WARNING: This problem set is labor-intensive for those of you who
have little or no practice with structural programming. Start early.
Do not for one moment believe, however, that this problem set is
difficult because it requires you to solve the problems in a new
language. If you have this impression, solve the problem in your favorite
programming language and show me your solution.
Develop a data representation for a mobile. Wikipedia describes
a moible as follows:
A mobile is a type of kinetic sculpture constructed to take advantage of
the principle of equilibrium. It consists of a number of rods, from which
weighted objects or further rods hang. The objects hanging from the rods
balance each other, so that the rods remain more or less horizontal. Each
rod hangs from only one string, which gives it freedom to rotate about the
Here is a rigorous, structured description, similar to the grammars found
in the Java language specification:
A Mobile is one of:
A Weight is a natural number (0, 1, 2, ...).
- a Weight
- a combination of two Mobiles and a weight.
Interpretation: The weight in the first case represents an "atomic"
sculpture. You may represent a weight as a plain number, say the number of
"kg" that the sculpture weighs. The weight in the second case is a
pointwise approximation of the beam that connects the two Mobiles.
Design the following functions:
weights#, which consumes a mobile and counts the number of atomic
sculptures it contains;
total-weight, which consumes a mobile and determines its total
average-weight, which consumes a mobile and determines the
average of its weight over all the atomic sculptures it contains;
depth, which consumes a mobile and determines the maximal number
of links from the top of the mobile to one of its atomic sculptures;
balanced?, which consumes a mobile and determines whether or not
it is balanced. A mobile is balanced if the weight of the mobile on one
end is equal to the weight of the mobile on the other end. The weight of a
mobile naturally includes the beams.
Recall the data definition for S-expressions over strings:
For this problem, we ignore the interpretation of this data representation.
Design the following functions:
- count, which counts the number of strings in an S-expression;
- flatten, which produces the list of all strings in an
S-expression (duplicates allowed)
- substitute, which replaces some old string with a
new string in the given S-expression.
Design the function silly. The function consumes a Mobile (see
Problem 1). It produces a Mobile, by adding to each sculpture S
(remember that it is represented by its weight) the depth of S in
for all mobiles m, total-weight(m) ≥ average-weight(m)
(see problem 1)
for all S-expressions s and strings o and n,
substitute(o,n,flatten(s)) = flatten(substitute(o,n,s))
(see problem 2)
Design the function sd. It consumes an expression of the
An XY is one of:
and produces one this shape:
- (function Variable XY)
- (XY XY)
An AB is one of:
In both cases,
- a Number
- a Variable
- (function Variable AB)
- (AB AB)
A Variable is a name drawn from the set x, y, ...
which is disjoint from the set of Numbers.
For each variable introduced by the first clause in an XY expression,
sd replaces it with the number of function nodes between
it and the closest function node that comes the same variable. If
there is no such node, the symbol is transferred to the output.
For example, when given
Note: This problem is already a true exercise in modeling
programming languages. It looks challenging and is the most complex
exercise of this problem set, but given that you are PhD students, it
should be well within reach.