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 problems.

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.

Problem 1:

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 string.

Here is a rigorous, structured description, similar to the grammars found in the Java language specification:

A Mobile is one of:

• a Weight
• a combination of two Mobiles and a weight.

A Weight is a natural number (0, 1, 2, ...).
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:

1. weights#, which consumes a mobile and counts the number of atomic sculptures it contains;
2. total-weight, which consumes a mobile and determines its total weight;
3. average-weight, which consumes a mobile and determines the average of its weight over all the atomic sculptures it contains;
4. depth, which consumes a mobile and determines the maximal number of links from the top of the mobile to one of its atomic sculptures;
5. 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.

Problem 2:

Recall the data definition for S-expressions over strings:

   (define-language Sexpr
     (s string
	(s ...)))
   

For this problem, we ignore the interpretation of this data representation.

Design the following functions:

1. count, which counts the number of strings in an S-expression;
2. flatten, which produces the list of all strings in an S-expression (duplicates allowed)
3. substitute, which replaces some old string with a new string in the given S-expression.

Problem 3:

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 the Mobile.

Problem 4:

Prove that

1. for all mobiles m, total-weight(m) ≥ average-weight(m)
   (see problem 1)
2. for all S-expressions s and strings o and n,
   substitute(o,n,flatten(s)) = flatten(substitute(o,n,s))
   (see problem 2)

Problem 5:

Design the function sd. It consumes an expression of the following language

An XY is one of:

• Variable
• (function Variable XY)
• (XY XY)

and produces one this shape:

An AB is one of:

• a Number
• a Variable
• (function Variable AB)
• (AB AB)

In both cases,

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

        (function y
	  ((function x 
	     (x y))
	    (x y)))

sd produces

        (function y
	  ((function x 
	     (0 1))
	    (x 0)))

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.