CS212
Structure and Interpretation
of Computer Programs

Computer Science Department
Cornell University
Spring 1998


Problem Set 1

Issued: Tuesday, January 26
Due: Thursday, February 5 in class

Before you do anything, please read about the entire homework carefully. It contains a wealth of good advice that can save you (and us) a lot of headaches later on.

For this assignment, you are to work alone. Please turn in a copy of your code in class on Thursday, February 5. No late assignments will be accepted, so start early.

If you have trouble with the course software or are generally stuck, come to our office hours or consulting hours. Alternatively, post a question to the newsgroup cornell.class.cs212. As a last resort, send email to cs212@cs.cornell.edu.

Programming Assignment: The von Koch Snowflake

In this problem set, you will be experimenting with line systems. Among the most famous line systems are the von Koch snowflake, first described by Helge von Koch in 1904, the Peano curve, the Hilbert curve, and the Cantor set. These figures not only look pretty, but also have important applications in many fields. For example, the Hilbert curve is used in dithering and compressing images.

A line system is specified by two geometrical figures called an initiator and a generator. Intuitively, the initiator defines the overall "shape" of the image, whereas the generator is used to (recursively) define the shape of the edges. For the von Koch snowflake, the initiator is an equilateral triangle. The generator consists of a line segment with the middle third removed and replaced by two sides of an equilateral triangle, as shown below:

To generate the infinite line system, we conceptually generate a sequence of figures, each one more refined than the next. The zero'th figure is generated by the initiator as a set of line segments. Figure i+1 is generated by taking each line segment in in figure i, and replacing it with a copy of the generator, oriented in the same fashion as the line segment. In the case of the von Koch snowflake, the zero'th figure would be an equilateral triangle, the first figure would be a a six-pointed star, the second figure would be a six-pointed star with little bumps on each point, etc.

The limit of the figures is a strange geometric object called a fractal. Fractals have a number of fascinating properties. They are self-similar, which means every piece looks like the whole object (not too surprising from the way we constructed it.) Fractals are continuous but nowhere differentiable. Their length is either 0 or infinite. Their dimension is not 1 like curves or 2 like surfaces, but somewhere in between, which is why they are called fractals. The dimension of the von Koch snowflake is log 4/log 3 = 1.2618...

In this assignment you will construct level k approximations to fractals. These are the figures obtained by stopping the construction described above after stage k. For example, a level 0 von Koch snowflake consists of just an equilateral triangle; a level 1 von Koch snowflake is the six-pointed star; etc.

These figures can be created without having to actually generate the intermediate figures by using a recursive strategy for drawing a side of the figure. A level 0 side is just a straight line. A level k+1 side is made up of several level k sides. In the von Koch snowflake, a level k+1 side consists of four level k sides.

We can translate this strategy into a Dylan procedure that draws a side of level k and length m in a direction specified by a given angle. If k=0, we simply draw a line of length m. If k>0, we draw four sides of level k-1 and length m/3 in the appropriate directions relative to the given angle.

(define (side <function>) 
 (method ((length <float>) (heading <float>) (level <integer>)) 
  (if (= level 0)
   (plot-line heading length)
   (begin
     (side (/ length 3) heading (- level 1))
     (side (/ length 3) (- heading pi3) (- level 1))
     (side (/ length 3) (+ heading pi3) (- level 1))
     (side (/ length 3) heading (- level 1))))))

The procedure plot-line draws a line segment by moving a graphics "pen" through a specified angle and distance.

We can draw the level k snowflake by drawing three level k sides oriented at 0 radians, 2pi/3 radians, and -2pi/3 radians, where pi = 3.14159...

(define (snowflake <function>)
  (method ((length <float>) (level <integer>))
   (side length 0.0 level)
   (side length (* 2 pi3) level)
   (side length (- 0.0 (* 2 pi3)) level)))

The file ps1.dyl contains two parts. The first part contains various graphics routines that you may find useful. This code uses some features of Dylan that you have not yet learned, so don't worry if you don't understand it. You will be writing similar code yourself in a few weeks. The second part consists of routines side and snowflake. This is the part you will be modifying.

Once you have loaded this code, you can test the program by evaluating the expression:

(snowflake 100.0 3) 

to draw a level 3 snowflake of side-length 100. The length of the side must be explicitly written as 100.0, since NOODLLE will not convert an integer to a floating point number.

You may have a little trouble maneuvering the graphics window which pops up. Keep trying until you can get the entire image on your screen.


Problem 1: Different Initiators and Generators

The snowflake figure is just one of a large family of figures that can be drawn using the same general method. Changing the generator and/or the initiator can completely change the shape of the figure.

Write a new generator method flip-side which is a line segment with the first half replaced by two sides of equilateral triangle pointing down, and the second half replaced by two sides of an equilateral triangle pointing up:

It should be considered as 4 segments of equal length, not 3 segments.

Write a new initiator method square-snowflake that is a square and uses flip-side as a generator. Try out your new initiator and see what kind of image it generates.

What to turn in: For problem 1, please submit a listing of the new methods flip-side and square-snowflake. Also print the snowflake generated by the following code:

(square-snowflake 100.0 3)

You may find the instructions on printing the contents of the Noodlle Graphics Console here


Problem 2: Generalizing the Line System

Principle: Functional abstraction, functions as parameters.

In the initiator given to you and in the initiator you wrote, the shape of the generator is "hard-coded". But it makes perfect sense to define line systems using any combination of generator and initiator. For instance, we should be able to use the square initiator with the original von Koch generator. What we need is some general way to glue together a generator and initiator so that we can try out different combinations.

One idea is to parameterize the initiator by the generator. That is, we could modify initiators so that they take the generator as an argument.

Modify the definitions of snowflake and square-snowflake so that they take a generator as an argument and invoke this generator instead of a hardcoded one. Try out all four combinations of initiators and generators:

(snowflake 100.0 3 side)
(snowflake 100.0 3 flip-side)
(square-snowflake 100.0 3 side)
(square-snowflake 100.0 3 flip-side)

In particular, evaluating the first expression should yield the same figure as the original snowflake code.

What to turn in: For problem 2, please submit a listing of the modified procedures snowflake and square-snowflake and a printout of all 4 generated snowflakes.


Problem 3: Inverting the Generator

Principle: Functions as parameters.

There is no reason why the generators should stay the same all the time, even in the same figure. Interesting designs can be obtained by inverting the generator on some levels.

We can easily invert an arbitrary generator by changing the signs of the angles that we add to the original heading. The decision whether to use a regular or inverted generator could be a function of the level; for example, we might decide to invert the generator on odd levels and not to invert on even levels. Alternatively, we might decide to invert on every third level, or we might decide to never invert at all.

To support an arbitrary inversion strategy, we need to pass a procedure inverter to the initiator which then forwards inverter to the generator. The generator should call the inverter, passing in the current level, to determine the sign of the angle to add to the original heading. The inverter procedure should return either -1 or 1, telling whether to invert or not to invert, respectively.

Implement the changes indicated above by adding function inverter to the parameter list of snowflake and side. To test your code, evaluate:

(snowflake 100.0 3 side (method ((level <integer>)) 1))

and verify that you obtain the original snowflake figure as before.

What to turn in: For problem 3, please submit listings of the modified snowflake and side procedures and a printout of the snowflake, generated by the following code:

(snowflake 100.0 3 side (method ((level <integer>)) (if (odd? level) 1 -1)))

Problem 4: Calculating the length of the snowflake figure

Principle: Functional programming vs. side effects.

Write two new procedures side-length and snowflake-length,that take the same type of arguments as the procedures created in problem 2 (parameterized). However, instead of drawing anything, snowflake-length should return the total length of the figure that snowflake draws (i.e., the total distance moved by the pen), given the same arguments.

The overall structure of the two new procedures should be the same as the original, but each should return the length of the part of the figure that would have been drawn. It should be possible to do this with a fairly minimal change to the your solution to Problem 2. You do not need to write flip-side-length or square-snowflake-length

What to turn in: For problem 4, please hand in a listing of these procedures side-length and snowflake-length and a printout of the output generated by the following code:

(snowflake-length 100.0 3 side-length (method ((level <integer>)) 1))

Perfect Snowflake Contest (Optional)

Hopefully, you generated some interesting snowflakes in the course of this assignment. If you wish, you can select your best designs and enter them in the CS212 Perfect Snowflake Contest. Submit the code which generates your snowflake and a printout of the result. To be fair, please do not turn in more than two pictures. Designs will be judged by the CS212 staff. The winner will receive a prize.


CS212 home page


Last Modified: 01/19/00 11:36 PM by JGM and the CS212 staff