• (Rule of Production): Replace each symbol in the list by the symbols in its production.

0. '(F)
1. '(F + F - - F + F)
2. '(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.

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

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

;;   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))

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

(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:

1. Length (a positive number)
2. Angle (a number between 0 and 360)
3. 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

1. Length = 10 (this choice is arbitary, and changes only the size of the curve)
2. Angle = 60
3. Instructions: Given by the above fixed interpretation for the symbols of the alphabet: 'F, '+, '-.

'(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)

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

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)

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

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.