CS200: Computer Science, Spring 2004

Problem Set 3: LSystem Fractals Out: 2 February 2003
Due: 11 February 2003, before class
Collaboration Policy  Read Carefully
For this problem set, you may work alone or with a partner of your choice. If you work with a partner, you and your partner should turn in one assignment with both of your names on it and both people must participate equally in all of the work. You should read the whole problem set yourself and think about the questions before beginning to work on them with your partner.
You may discuss this assignment with other students in the class and ask and provide help in useful ways. You may consult any outside resources you wish including books, papers, web sites and people except for materials from last year's CS200 course. If you use resources other than the class materials, indicate what you used along with your answer.
Purpose
 Get more practice with recursive definitions and procedures
 Explore the power of rewrite rules
 Learn to use lists
 Write recursive functions that manipulate lists
 Make a better CS200 logo than "The Great Lambda Tree of Infinite Knowledge and Ultimate Power"
Reading: Before doing this problem set, you should read SICP 2.1 and 2.2 (you may skip section 2.2.4).
Download: Download ps3.zip to your machine and unzip it into your home directory J:\cs200\ps3. This file contains:
 ps3.ss — A template for your answers. You should do the problem set by editing this file.
 graphics.ss — Scheme code for drawing curves. This is similar to graphics.ss from PS2, except we have made some improvements (as described later) that will help you draw better LSystem Fractals.
 lsystem.ss — provided incomplete code for producing LSystem Fractals
Background
In this problem set, you will explore a method of creating fractals known as the Lindenmayer system (or Lsystem). Aristid Lindemayer, a theoretical biologist at the University of Utrecht, developed the Lsystem in 1968 as a mathematical theory of plant development. In the late 1980s, he collaborated with Przemyslaw Prusinkiewicz, a computer scientist at the University of Regina, to explore computational properties of the Lsystem and developed many of the ideas on which this problem set is based.
The idea behind Lsystem fractals is that we can describe a curve as a list of lines and turns, and create new curves by rewriting old curves. Everything in an Lsystem curve is either a forward line (denoted by F), or a right turn (denoted by Ra where a is an angle in degrees clockwise). We can denote left turns by using negative angles.
We create fractals by recursively replacing all forward lines in a curve list with the original curve list. Lindemayer found that many objects in nature could be described using regularly repeating patterns. For example, the way some tree branches sprout from a trunch can be described using the pattern: F O(R30 F) F O(R60 F) F. This is interpreted as: the trunk goes up one unit distance, a branch sprouts at an angle 30 degrees to the trunk and grows for one unit. The O means an offshoot — we draw the curve in the following parentheses, and then return to where we started before the offshoot. The trunk grows another unit and now another branch, this time at 60 degrees relative to the trunk grows for one units. Finally the trunk grows for one more unit. The branches continue to sprout in this manner as they get smaller and smaller, and eventually we reach the leaves.
We can describe this process using replacement rules:
Start: (F)Here are the commands this produces after two iterations:
Rule: F ::= (F O(R30 F) F O(R60 F) F)Iteration 0: (F)
Iteration 1: (F O(R30 F) F O(R60 F) F)
Iteration 2: (F O(R30 F) F O(R60 F) F O(R30 F O(R30 F) F O(R60 F) F) F O(R30 F) F O(R60 F) F O(R60 F O(R30 F) F O(R60 F) F) F O(R30 F) F O(R60 F) F)Here's what that looks like:
Iteration 0
Iteration 1
Iteration 2
Iteration 5
The Great Lambda Tree of Infinite Knowledge and Ultimate PowerNote that Lsystem command rewriting is similar to the replacement rules in a BNF grammar. The important difference is that with Lsystem rewriting, each iteration replaces all instances of F in the initial string instead of just picking one to replace.
We can divide the problem of producing an Lsystem fractal into two main parts:
We will first work on producing the list of Lsystem commands, and then work on how to draw a list of Lsystem commands.
 Produce a list of Lsystem commands that represents the fractal by rewriting according to the Lsystem rule; and
 Drawing a list of Lsystem commands.
Representing LSystem Commands
Here is a BNF grammar for Lsystem commands:
 CommandSequence ::= ( CommandList )
 CommandList ::= Command CommandList
 CommandList ::=
 Command ::= F
 Command ::= RAngle
 Command ::= OCommandSequence
 Angle ::= Number
Question 1: Show that (F O(R60 F) F) is a string in the language defined by our BNF grammar. To do this, you should start with CommandSequence, and show a sequence of replacements that follow the grammar rules that produce the target string. You can use the rule numbers above to identify the rules. We need to find a way to turn strings in this grammar into objects we can manipulate in a Scheme program. We can do this by looking at the BNF grammar, and converting the nonterminals into Scheme objects.
;;; CommandSequence ::= ( CommandList ) (define makelsystemcommand list) ;;; We represent the different commands as pairs where the first item in the ;;; pair is a tag that indicates the type of command: 'f for forward, 'r for rotate ;;; and 'o for offshoot. We use quoted letters to make tags, which evaluate to the ;;; letter after the quote. The tag 'f is short for (quote f). ;;; Command ::= F (define (makeforwardcommand) (cons 'f #f)) ;; No value, just use false. ;;; Command ::= RAngle (define (makerotatecommand angle) (cons 'r angle)) ;;; Command ::= OCommandSequence (define (makeoffshootcommand commandsequence) (cons 'o commandsequence))
Question 2: It will be useful to have procedures that take Lsystem commands as parameters, and return information about those commands. Define the following procedures in ps3.ss:
 (isforward? lcommand) — evaluates to #t if the parameter passed is a forward command (indicated by its first element being a 'f tag).
 (isrotate? lcommand)
 (isoffshoot? lcommand)
 (getangle lcommand) — evaluates to the angle associated with a rotate command. Produces an error if the command is not a rotate command (see below for how to produce an error).
 (getoffshootcommands lcommand) — evaluates to the offshoot command list associated with an offshoot command. Produces an error if the command is not an offshoot command.
You will find the following procedures useful:
If you define these procedures correctly, you should produce these evaluations:
 (car lst) — evaluates to the first element of the list parameter
 (eq? v1 v2) — evaluates to #t if v1 and v2 are exactly the same; otherwise evaluates to false. For example, (eq? 's 's) evaluates to #t and (eq? 's 't) evaluates to #f.
 (error message) — produces an error with message a string given as the first parameter. For example, (error "Yikes! Attempt to getangle for a command that is not an angle command") would display the message in red and stop execution. It is useful to use error in your code so you will more easily identify bugs.
You should be able to make up similar test cases yourself to make sure the other procedures you defined work.> (isforward? (makeforwardcommand))
#t
> (isforward? (makerotatecommand 90))
#f
> (getangle (makerotatecommand 90))
90
> (getangle (makeforwardcommand))
Yikes! Attempt to getangle for a command that is not an angle command
Rewriting Curves
The power of the LSystem commands comes from the rewriting mechanism. Recall how we described the tree fractal:Start: (F)To produce levels of the tree fractal, we need a procedure that takes a list of Lsystem commands and replaces each F command with the list of Lsystem commands given by the rule.
Rule: F ::= (F O(R30 F) F O(R60 F) F)
So, for every command in the list:
One slight complication is that the replacement commands are a list of Lsystem commands, and we want to end up with a flat list of LSystem commands.
 If the command is an F command, replace it with the replacement commands
 If the command is an RAngle command, keep it unchanged
 If the command is an OCommandSequence command, recursively rewrite every command in the offshoot's command list the same way
For example, consider a simple LSystem rewriting:
Start: (F)We want to get:
Rule: F ::= (F R30 F)Iteration1: (F R30 F)but if we just replace F's with (F R30 F) lists, we would get:
Iteration2: (F R30 F R30 F R30 F)Iteration1: ((F R30 F))The easiest way to fix this problem is to flatten the result. The code should look similar to many recursive list procedures you have seen (this code is provided in lsystem.ss):
Iteration2: ((F R30 F) R30 (F R30 F))(define (flattencommands ll) (if (null? ll) ll (if (islsystemcommand? (car ll)) (cons (car ll) (flattencommands (cdr ll))) (flatappend (car ll) (flattencommands (cdr ll)))))) (define (flatappend lst ll) (if (null? lst) ll (cons (car lst) (flatappend (cdr lst) ll))))
Question 3: Define a procedure rewritelcommands in ps3.ss that takes a list of Lsystem commands as its first parameter. The second parameter is a list of Lsystem commands that should replace every forward command in the first list of commands in the result. Here's the easy part:
Complete the definition of rewritelcommands.(define (rewritelcommands lcommands replacement) (flattencommands (map ; Procedure to apply to each command lcommands)))To make interesting Lsystem curves, we will need to apply rewritelcommands many times. We will leave that until the last question. First, we will work on turning sequences of Lsystem commands into curves we can draw.
Improving Our Curve Drawing
To help you draw better Lsystem Curves, we have provided a new version of the curve drawing code from PS2. You don't need to modify this code, but should understand the changes described below.
Points
In PS2, we represented points using a procedure:Now that you know about cons pairs, it would be more natural to represent points using a cons pair:(define (makepoint x y) (lambda (selector) (if selector x y))) (define (xofpoint point) (point #t)) (define (yofpoint point) (point #f))Note that we can change the way we represent points, and all the old PS2 code will still work without changing anything else (except it will run faster now). This is data abstraction, and is very important for building large programs.(define (makepoint x y) (cons x y)) (define (xofpoint point) (car point)) (define (yofpoint point) (cdr point))Color
Our pictures will be more interesting if points can have color too. We represent a colored point using a list of three values: x, y and color:We have defined colored points so the old colorless points still work (and appear black). We changed the definition of makepoint to produce a list of two values, instead of a cons pair, since that way the xofpoint and yofpoint procedures will work for both colored and uncolored points:(define (makecoloredpoint x y c) (list x y c)) (define (iscoloredpoint? point) (= (length point) 3))(define (makepoint x y) (list x y)) (define (xofpoint point) (car point)) (define (yofpoint point) (cadr point)) ;; (cadr x) = (car (cdr x)) ;;; Regular points are black. Colored points have a color. (define (colorofpoint point) (if (iscoloredpoint? point) (caddr point) (makecolor 0 0 0)))To make our curves appear in color, we need to change the way we draw points on the window to pass in the color also:
(define (windowdrawpoint point) ((drawpixel window) (converttoposition point) (colorofpoint point)))Manipulating Curves
The good thing about defining curves as functions is it is easy to modify and combine then in interesting ways.For example, the procedure rotateccw takes a curve and rotates it 90 degrees counterclockwise by swapping the x and y points:
(define (rotateccw curve) (lambda (t) (let ((ct (curve t))) (makecoloredpoint ( (yofpoint ct)) (xofpoint ct) (colorofpoint ct)))))Note that (rotateccw c) evaluates to a curve. The function rotateccw is a proceture that takes a procedure (a curve) and returns a procedure that is a curve.
Predict what (drawcurvepoints (rotateccw midline) 1000) and (drawcurvepoints (rotateccw (rotateccw midline)) 1000) will do. Confirm your predictions by trying them in your Interactions window.
Here's another example:
(define (shrink curve scale) (lambda (t) (let ((ct (curve t))) (makecoloredpoint (* scale (xofpoint ct)) (* scale (yofpoint ct)) (colorofpoint ct)))))Predict what (drawcurvepoints (shrink midline .5) 1000) will do, and then try it in your Interactions window.The shrink procedure doesn't produce quite what we want because in addition to changing the size of the curve, it moves it around. Make sure you understand why this happens. Try shrinking a few different curves to make sure.
One way to fix this problem is to center our curves around (0,0) and then translate them to the middle of the screen. We can do this by adding or subtracting constants to the points they produce:
(define (translate curve x y) (lambda (t) (let ((ct (curve t))) (makecoloredpoint (+ x (xofpoint ct)) (+ y (yofpoint ct)) (colorofpoint ct)))))Now we have translate, it makes more sense to define midline this way:(define (horizline t) (makepoint t 0)) (define midline (translate horizline 0 0.5))To check you understand everything so far, use translate, horizline and shrink to draw a line half the width of the window that is centered in the middle of the display window.In addition to altering the points a curve produces, we can alter a curve by changing the t values it will see. For example,
(define (firsthalf curve) (lambda (t) (curve (/ t 2))))is a function that takes a curve and produces a new curve that is just the first half of the passed curve.Predict what each of these expressions will do:
Try evaluating them in your Interactions window to check if you were right. (Remember to use (clearwindow) to clear the display window so you can see the new curve without the old one.)
 (drawcurvepoints (firsthalf midline) 1000)
 (drawcurvepoints (firsthalf (firsthalf midline)) 1000))
The provided code includes several other functions that transform curves including:
You should be able to understand the code in graphics.ss that defines these functions.
 (scalexy curve xscale yscale) — evalutes to curve stretched along the x and y axis by using the scale factors given
 (scale curve scale) — evaluates to curve stretched along the x and y axis by using the same scale factor
 (rotatearoundorigin curve degrees) — evaluates to curve rotated counterclockwise by the given number of degrees.
It is also useful to have curve transforms where curves may be combined. An example is (connectrigidly curve1 curve2) which evaluates to a curve that consists of curve1 followed by curve2. The starting point of the new curve is the starting point of curve1 and the end point of curve2 is the ending point of the new curve. Here's how connectrigidly is defined:
(define (connectrigidly curve1 curve2) (lambda (t) (if (< t (/ 1 2)) (curve1 (* 2 t)) (curve2 ( (* 2 t) 1)))))Predict what (drawcurvepoints (connectrigidly verticalmidline midline) 1000) will do. Is there any difference between that and (drawcurvepoints (connectrigidly midline verticalmidline) 1000)? Check your predictions in the Interactions window.
Distributing t Values
The drawcurvepoints procedure does not distribute the tvalues evenly among connected curves, so the later curves appear dotty. This isn't too big a problem when only a few curves are combined; we can just increase the number of points passed to drawcurvepoints to have enough points to make a smooth curve. In this problem set, however, you will be drawing curves made up of thousands of connected curves. Just increasing the number of points won't help much, as you'll see in Question 4.The way connectrigidly is defined above, we use all the tvalues below 0.5 on the first curve, and use the tvalues between 0.5 and 1.0 on the second curve. If the second curve is the result of connecting two other curves, like (connectrigidly c1 (connectrigidly c2 c3)) then 50% of the points will be used to draw c1, 25% to draw c2 and 25% to draw c3.
Question 4: Define a procedure numpoints that determines the approximate number of tvalues that will be used for the n^{th} curve when drawing (connectrigidly c1 (connectrigidly c2 (connectrigidly curve3 (... cn))))Think about this yourself first, but look in ps3.ss for a hint if you are stuck.Your numpoints procedure should produce results similar to:
This means if we connected just 20 curves using connectrigidly, and passed the result to drawcurvepoints with one million as the number of points, there would still be only one or two points drawn for the 20^{th} curve. If we are drawing thousands of curves, for most of them, not even a single point would be drawn!> (exact>inexact (numpoints 1000 10))
1.95
> (exact>inexact (numpoints 1000 20))
0.0019073486328125
> (exact>inexact (numpoints 1000000 20))
1.9073486328125
To fix this, we need to distribute the tvalues between our curves more fairly. We have provided a procedure connectcurvesevenly in graphics.ss that connects a list of curves in a way that distributes the range of t values evenly between the curves.
The definition is a bit complicated, so don't worry if you don't understand it completely. You should, however, be able to figure out the basic idea for how it distributed the tvalues evenly between every curve in a list of curves.
It will also be useful to connect curves so that the next curve begins where the first curve ends. We can do this by translating the second curve to begin where the first curve ends. To do this for a list of curves, we translate each curve in the list the same way using map:(define (connectcurvesevenly curvelist) (lambda (t) (let ((whichcurve (if (>= t 1.0) ( (length curvelist) 1) (inexact>exact (floor (* t (length curvelist))))))) ((getnth curvelist whichcurve) (* (length curvelist) ( t (* (/ 1 (length curvelist)) whichcurve)))))))(define (constocurvelist curve curvelist) (let ((endpoint (curve 1.0))) ;; The last point in curve (cons curve (map (lambda (thiscurve) (translate thiscurve (xofpoint endpoint) (yofpoint endpoint))) curvelist))))Drawing LSystem Curves
To draw an Lsystem curve, we need to convert a sequence of Lsystem commands into a curve. We defined the connectcurvesevenly procedure to take a list of curves, and produce a single curve that connects all the curves. So, to draw an LSystem curve, we need a procedure that turns an LSystem Curve into a list of curve procedures.Below is code for converting a list of LSystem commands with some parts missing (it is explained below, but try to understand it yourself before reading further; if you don't understand cond, review SICP 1.1.6.):
(define (convertlcommandstocurvelist lcommands) (cond ((null? lcommands) (list ;;; We make a leaf with just a single point of green: (lambda (t) (makecoloredpoint 0.0 0.0 (makecolor 0 255 0))) )) ((isforward? (car lcommands)) (constocurvelist verticalline (convertlcommandstocurvelist (cdr lcommands)))) ((isrotate? (car lcommands)) ;;; If this command is a rotate, every curve in the rest ;;; of the list should should be rotated by the rotate angle (let ;; Lsystem turns are clockwise, so we need to use  angle ((rotateangle ( (getangle (car lcommands))))) (map (lambda (curve) ;;; Question 5: fill this in ) ;;; Question 5: fill this in ))) ((isoffshoot? (car lcommands)) (append ;;; Question 6: fill this in )) (#t (error "Bad lcommand!"))))We define convertlcommandstocurvelist recursively. The base case is when there are no more commands (the lcommands parameter is null). It evaluates to the leaf curve (for now, we just make a point of green — you may want to replace this with something more interesting to make a better fractal). Since convertlcommandstocurvelist evaluates to a list of curves, we need to make a list of curves containing only one curve.Otherwise, we need to do something different depending on what the first command in the command list is. If it is a forward command we draw a vertical line. The rest of the fractal is connected to the end of the vertical line using constocurvelist. The recursive call to convertlcommandstocurve produces the curve list corresponding to the rest of the Lsystem commands. Note how we pass (cdr lcommands) in the recursive call to get the rest of the command list.
Question 5: Fill in the missing code for handling rotate commands (marked as Question 5 in ps3.ss). You will want to use (rotatearoundorigin curve rotateangle) somewhere in your code to rotate every curve after the rotate command by the rotateangle. You can test your code by drawing the curve that results from any list of Lsystem commands that does not use offshoots. For example, evaluating
should produce a "V".(drawcurvepoints (positioncurve (translate (connectcurvesevenly (convertlcommandstocurvelist (makelsystemcommand (makerotatecommand 150) (makeforwardcommand) (makerotatecommand 120) (makeforwardcommand)))) 0.3 0.7) 0 .5) 10000)
Question 6: Fill in the missing code for handling offshoot commands (marked as Question 6 in ps3.ss). We have provided the positioncurve procedure to make it easier to fit fractals onto the graphics window:
(positioncurve curve startx starty) — evaluates to a curve that translates curve to start at (startx, starty) and scales it to fit into the graphics window maintaining the aspect ratio (the x and y dimensions are both scaled the same amount)The code for positioncurve is in curve.ss. You don't need to look at it, but should be able to understand it if you want to.Now, you should be able to draw any lsystem command list using positioncurve and the convertlcommandstocurvelist function you completed in Questions 5 and 6. Try drawing a few simple Lsystem command lists before moving on to the next part.
Question 7: Define a procedure makelsystemfractal in ps3.ss that takes three parameters: replacecommands, a list of Lsystem commands that replace forward commands in the rewriting; start, a list of Lsystem commands that describes the starting curve; level, the number of iterations to apply the rewrite rule. Hint: You should use the rewritelcommands you defined in Question 4. You may also find it useful to use the ntimes function you defined in PS2.
You should be able to draw a tree fractal using maketreefractal and drawlsystemfractal (these and the treecommands list of Lsystem commands are defined in lsystem.ss):
(define (maketreefractal level) (makelsystemfractal treecommands (makelsystemcommand (makeforwardcommand)) level))(define (drawlsystemfractal lcommands) (drawcurvepoints (positioncurve (connectcurvesevenly (convertlcommandstocurvelist lcommands)) 0.5 0.1) 50000))For example, (drawlsystemfractal (maketreefractal 3)) will create a tree fractal with 3 levels of branching.
Question 8: Draw some fractals by playing with the Lsystem commands. Try changing the rewrite rule, the starting commands, level and leaf curve (in convertlcommandstocurvelist) to draw an interesting fractal. You might want to make the branches colorful also. Try an make a fractal picture that will make a better course logo than the current Great Lambda Tree Of Infinite Knowledge and Ultimate Power. The best pictures will appear on the course web page and will be rewarded with untold fame, invaluable fortune and maybe even a double gold star on this problem set. Turn in the code you used, as well as a printout of the display window. If your fractal deserves to be seen in color, email an image of it to cs200staff@cs.virginia.edu.
Credits: This problem set was originally created for CS200 Spring 2002 by Dante Guanlao, Jon Erdman and David Evans, and revised for CS200 Spring 2003 by Jacques Fournier and David Evans, and revised for CS200 Spring 2004 by David Evans.
cs200staff@cs.virginia.edu Using these Materials 