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.
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:
- Divide the line segment in three parts.
- Draw an equilateral triangle with the middle segment as base.
- Remove the middle segment .
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.)
'(F + F - - F + F)
- (Rule of Production): Replace each symbol in the list by the symbols in its production.
'(F + F - - F + F)
'(F + F - - F + F + F + F - - F + F - - F + F - - F + F + F + F - - F + F)
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
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.
With the value-turtle.ss teachpack we can implement simple turtle
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.)
'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
- 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:
3a. Interpreting L-systems in Dr. Scheme
We will represent an interpretation of an L-system by
;; An instruction is a ;; symbol -> (snapshot -> snapshot)Write an
instructionfor interpreting the
;; 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 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 choiceYour 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.