## CMSC 15100 - Autumn 2005 Lab 7

### Save a copy of this lab for yourself

• Language: Intermediate Student with Lambda Expressions
• Teachpack: value-turtles.ss
• Lab 7 Template (scm) Change the name of this template file using your CNET ID.
Extra Credit problems are in red!!

### 0. Introduction to Fractals

A fractal is a geometric object which is highly irregular at every scale. Some of the most famous fractals have self-similar structure: they have a repeating structure at all level of magnitude. One of the most familiar examples is Sierpinski's Triangle. Many of these fractals can be generated by repeating a pattern in a recursive process.

The term fractal was coined in 1975 by Benoît Mandelbrot, but fractals were first discovered 100 years earlier by mathematicians investigating bizarre mathematical behavior, and called monster curves. In 1904 Helge von Koch introduced the Koch curve. Here is a Koch curve generated by a program you are going to write in Dr. Scheme:

(For those in the know, this curve is continuous, nowhere differentiable and has infinite length, although it fits in a compact box!! A true mathematical monster!)

Here is how the curve is recursively constructed:

We start with a line segment (step 0, top segment.) Then on each step we do the following:
1. Divide the line segment in three parts.
2. Draw an equilateral triangle with the middle segment as base.
3. Remove the middle segment
4. .
The above figure shows the first three steps, here are a couple more (starting with step 2):

 2 3 4 ...

### 1. L-systems

We are going to generate fractals by using a very simple recursive description of fractals by L-systems. These were first introduced by a botanist Aristid Lindenmayer in 1968 to give a formal description of the growth of multicellular organisms. They were later extended to complex plant growth, and of course, the description of mathematical monsters.

An L-system consists of three parts:

• An alphabet consisting of a list of symbols.
• An initial state consisting of a sequence of symbols from the alphabet, and which is the starting state.
• A collection of productions, which are rules for how to replace a single symbol in the alphabet by a new combination of symbols (all occurring in the alphabet.)
Here is an example of an L-system for the Koch-curve:
• Alphabet: `'+`, `'-`, `'F`
• Initial: `'(F)`
• ``` Productions: '+ ==> '(+) '- ==> '(-) 'F ==> '(F + F - - F + F) ```
``` An L-system generates sequences of symbols by starting with the initial state (step 0), and recursively applying the following rule: (Rule of Production): Replace each symbol in the list by the symbols in its production. For example, here are the results after three iterations of the L-system for the Koch curve: '(F) '(F + F - - F + F) '(F + F - - F + F + F + F - - F + F - - F + F - - F + F + F + F - - F + F) The list of symbols generated after some number of iterations of the L-system are called expressions. We will later see how to use the expressions to draw fractal curves. 1a. Exercise: Representing L-systems in Scheme ;; We will represent a L-system by a structure which consists of ;; -- an initial state, which is a (listof symbol), the starting point ;; of the grammar ;; -- a function (called the productions) of type ;; symbol->(listof symbol) ;; a grammar is ;; (make-grammar (listof symbol) (symbol -> (listof symbol))) (define-struct grammar (initial rules)) ;; An expression is a ;; (listof symbol) ;; where this is either the initial state, or produced by recursively ;; iterating the Rule of Productions. Write the following example of an L-system: ;; A grammar for the Koch curve: (define Koch-grammar (make-grammar ... ... )) Your task is to write the following function ;; generate: grammar number -> expression ;; generate the expression produced by n iterations of the ;; rule of productions for the grammar, gram. ;; When num=0, this is just the initial state (define (generate gram n) ... ) Test generate using Koch-grammar. 2. Turtle Graphics Turtle graphics originated as part of the Logo programming language developed at Berkeley in the late sixties. It was originally an adaptation of LISP (without parentheses!!) The idea of turtle graphics is that a turtle with a pen strapped to its tail can be instructed to do simple commands: Move with pen down. (Draw a line) Move with pen up. (Move without drawing a line) Turn left. Turn right. In fact, some early versions of Logo really did control a mechanical turtle (who even rang a bell!!) With the value-turtle.ss teachpack we can implement simple turtle commands. A snapshot is like an image, but it contains a turtle (literally!), and the turtle knows only simple commands for drawing: ;; There are four new commands in the Turtle teachpack: ;; ;; numbers: w, h x, y, a ;; (A) turtles: w h x y a -> snapshot ;; This command returns a snapshot of width w and height h ;; with a droopy-tailed turtle in position (x,y) and facing ;; a degrees from east (east faces the right-edge). The angle a ;; is measured counterclockwise from east (if a is positive) and ;; clockwise from east (if a is negative.) ;; ;; (A') turtles: w h -> snapshot ;; This command returns a snapshot of width w and height h ;; with a droopy-tailed turtle in the center of the snapshot ;; and facing east. ;; ;; (B) move: number snapshot -> snapshot ;; Move turtle in the direction it is facing by number steps. Turtle keeps ;; its tail raised so no line is drawn. ;; ;; (C) draw: number snapshot -> snapshot ;; Same as move, but turtle keeps its tail down so it draws a line of length ;; number. ;; ;; (D) turn: number snapshot -> snapshot ;; Turtle changes its direction by rotating number degrees. If number is ;; positive, Turtle turns to the left; if the number is negative Turtle turns ;; to the right. Here is a simple example which produces an equilateral triangle ;; Example: equilateral triangle ;; The turtle ends where it started facing east. (define triangle (turn 120 (draw 40 (turn 120 (draw 40 (turn 120 (draw 40 (turtles 100 100)))))))) 2a. Starting a snapshot It will not always be convenient to have your turtle start in the exact center of the snapshot. You will need to reposition your turtle to a new starting position, while still facing east (to the right.) ;; A startbox is a ;; (make-startbox number number posn number) (define-struct startbox (width height position direction)) Write the following function: ;; start: startbox -> snapshot ;; creates a snapshot of width and height given by startbox, and places ;; the turtle at the x,y-coordinates given by the position ;; (a posn) in startbox, and pointing in direction. (define (start sbox) ... ) You will find a good starting point for generating the Koch curve is placing the turtle on the left edge of the snapshot facing east. Here is a useful example for you to test (define Koch-start (make-startbox 500 500 (make-posn 0 250) 0)) 3. Interpreting L-systems with Turtle Graphics We will interpret the expressions produced by an L-system as commands to our turtle in the snapshot. An interpretation will need to provide three ingredients: Length (a positive number) Angle (a number between 0 and 360) Instructions for interpreting each symbol (which will be a function.) Four symbols will be given a fixed interpretation whenever they occur in an alphabet: 'F: Draw a line of Length in current direction 'G: Move Length in current direction (do not draw a line.) '+: Turn left by Angle '-: Turn right by Angle For example, an interpretation for the Koch curve L-system is given by Length = 10 (this choice is arbitary, and changes only the size of the curve) Angle = 60 Instructions: Given by the above fixed interpretation for the symbols of the alphabet: 'F, '+, '-. Here is the interpretation on the first three expressions generated by the Koch curve L-system (replete with Turtle): '(F) '(F + F - - F + F) '(F + F - - F + F + F + F - - F + F - - F + F - - F + F + F + F - - F + F) 3a. Interpreting L-systems in Dr. Scheme We will represent an interpretation of an L-system by an instruction ;; An instruction is a ;; symbol -> (snapshot -> snapshot) Write an instruction for interpreting the Koch-grammar: ;; Interpretation of Koch-grammar, for generating Koch curves: ;; Length = 10 (although you will want to experiement with this later) ;; Angle = 60 ;; Instructions: ;; 'F ==> Draw line of Length in current snapshot ;; '+ ==> Turn left Angle degrees in current snapshot ;; '- ==> Turn right Angle degrees in current snapshot (define Koch-instructions ... ) Your task is to write the following function ;; An expression is a (listof symbol) generated from a grammar ;; expr->snapshot: expression instruction snapshot -> snapshot ;; Uses expr as a sequence of instructions, interpreted by ;; instr to update the turtle in sbox (define (expr->snapshot expr instr sbox) ... ) ;; Example: let Koch-start be as in Part 2b, then ;; (expr->snapshot '(F + F - - F + F) ;; Koch-instructions ;; Koch-start ) ;; should output the figure shown below. The example should produce Hint: You can write expr->snapshot using built-in functions. Finally, package generate, start and expr->snapshot so that you can easily test your code on various iterations of an L-system, and see the output in the snapshot: ;; generate-curve: grammar number instruction startbox -> snapshot ;; Draw curve produced after n iterations of the L-system gramm ;; starting from the snapshot (start sbox). (define (generate-curve gramm n instr sbox) ... ) ;; Example: Draw the Koch curve after five iterations: ;; (generate-curve Koch-grammar 5 Koch-instructions Koch-start) Your curve should look like the Koch curve from Part 0 above. You may want to change the length to something smaller than 10 when generating curves this many iterations. 4. Examples of Fractal Curves Try the Koch Island (a snowflake design.) The grammar is almost the same except for the initial state ;;;; Koch Island ;;;; Snowflake design, differs from Koch Curve by starting initial state ;;;; (You should recognize this as the equilateral triangle.) ;;;; ;;;; Alphabet: 'F,'+, '- ;;;; Initial: '(F + + F + + F) ;;;; Production Rule: ;;;; 'F ==> '(F - F + + F - F) ;;;; '+ ==> '(+) ;;;; '- ==> '(-) ;;;; Interpretation: ;;;; Angle: 60 ;;;; Length: your choice Your output after 0, 1, 2 and 3 iterations should look like the following: There are a dozen examples on the lab template for you to try. Many, such as the Koch curve and Koch island, are mathematical monsters, but fractals designs have a rich tradition in decoration and design in other cultures. There are two examples of kolams, which are found in Indian decorative art. ```
``` ```