Due date: 9/24 @ at the beginning of class

The goal of this problem set is to practice structural programming using structures, lists, S-expressions, recursive data definitions. Some problems demand accumulator-style programming. One of the problems is about proof-by-induction, but as you know by now, this is closely related to structural programming.

The problems cover material from HtDP, specifically parts I, II, III, and VI. To be reasonable effective in Racket, you also want to read part IV. HtDP is migrating to a second edition; the draft is on-line.

Use the Racket programming language and the DrRacket programming environment to solve the problems (#lang racket). The appendix of part II in your Redex textbook is a nutshell introduction to DrRacket. If you encounter errors you don't understand, you may wish to switch to the HtDP Intermediate Student programming language. See the DrRacket Language menu.

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

We use this rigorous, structured description. A Mobile

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

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 weights 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 weight of 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 symbols. An S-expression is one of:

• the empty list or '() for short;
• (cons Symbol S-expression)
• (cons S-expression S-expression)

For this problem, we ignore what this data represents. In general, though, S-expressions are useful to represent the abstract syntax of any form of program (Java, Scheme, XML, etc).

Design the following functions:

1. count, which counts the number of symbols in an S-expression;
2. flatten, which produces the list of all symbols in an S-expression (duplicates allowed)
3. substitute, which replaces some old symbol with a new symbol 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:

Design the function free. It consumes an S-expression of the following shape.

An XY is one of:

• a Symbol
• (list 'function Symbol XY)
• (list XY XY)

It produces an S-expression of this shape:

An AB is one of:

• a Number
• a Symbol
• (list 'function Symbol AB)
• (list AB AB)

For each symbol introduced by the first clause in an XY S-expression, free replaces it with the number of 'function symbols between it and the closest 'function node that lists the same symbol. 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)))

free produces

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

Problem 5:

Here is a rigorous definition of the set of shapes from the first quiz. A Shape is one of:

• a rectangle whose sides are parallel to the two axes, specified as the collection of four numbers: xmin, xmax, ymin, and ymax subject to the constraint that xmin < xmax and ymin < ymax.
• a combination of two shapes.

Nothing else is a shape.

Prove that

1. all elements of Shape contain an even number of numbers;
2. the number of rectangles in a Shape is always larger than the number of combinations;
3. the area covered by all rectangles in a Shape is smaller than the "general" area of a shape. The "general" area of a shape S is (max { xmax | xmax in all rectangles in S} - min { xmin | xmin in all rectangles in S})
   *
   (max { ymax | ymax in all rectangles in S} - min { ymin | ymin in all rectangles in S})