Iβm not sure what trace1 and trace2 are meant to do in the spec below.

Introduction

An interesting challenge in the games and cinematic effects industries is

that of generating and rendering visually realistic scenes containing organic

structures like plants, bushes and trees.

One approach is to have a database of predefined objects that can be

looked up and placed into a scene on request. However, if the same structure

is used repeatedly then the rendered scene tends to looks very artificial β in

nature not all trees are alike!

An alternative is to use a program to generate artificial plant-like structures from scratch using rules for generating trunks, branches, flowers etc.

as the program executes. With a little additional effort, these rules can be

applied probabilistically so that no two structures end up looking the same.

A popular way of defining plant-like structures is to use Lindenmayer

Systems, or L-Systems for short. L-Systems are named after the biologist

Aristid Lindenmayer who was interested in describing the apparently fractal

nature of plant growth using simple rewriting rules. L-Systems can be used

to define some of the well-known fractals you might have come across already.

In this exercise, we are going to work with very simple deterministic

two-dimensional structures, but it should be easy to see how the process

might be generalised, for example to build probabilistically-generated threedimensional objects.

1

How L-Systems work

L-Systems work by repeatedly replacing the items in a list according to a

fixed set of rewrite rules. Starting from an initial βseedβ list, or axiom, the

list grows in size as the rewrites are repeatedly applied. In this exercise the

items will be characters, so the rewrite problem becomes one of expanding

an axiom string into an output string respresenting the final structure. To

render the structure the characters in the output string are mapped to a

sequence of commands for a turtle - an imaginary device on wheels with a

pen underneath that draws as it moves.

Turtle graphics

A graphics turtle can be thought of as a simple robot which moves around

on a sheet of paper according to a set of basic commands. The robot has a

pen built into it which, in general, can be raised or lowered onto the paper.

If the robot moves whilst the pen is βdownβ the movement will trace a line

on the paper. This exercise uses a simple imaginary robot turtle whose pen

is always in the βdownβ position and which moves around using just three

commands encoded as characters:

βFβ Moves the turtle forward a fixed distance in the direction in which the

turtle is facing.

βLβ Rotates the robot by a given angle anticlockwise (i.e. to the left) on

the spot.

βRβ Rotates the robot by a given angle clockwise (i.e. to the right) on the

spot.

The movement distance will be fixed here arbitrarily at 1 unit; the angle of rotation will be an attribute of the L-System used to generate the

command string.

Rewrite rules

In this exercise each turtle command will be a character (βFβ, βLβ or βRβ)

and a sequence of commands will be a string. An L-System again works with

strings but the characters within the strings can be arbitrary. A rewrite rule

is a mapping from characters to strings and each will be represented as a

(Char, String) pair. A set of rules will be represented as a list of such

pairs (a table), thus:

```
type Rule = (Char, String)
type Rules = [Rule]
```

An L-System consists of an axiom string, a list of rewrite rules and an

associated rotation angle used to drive the turtle. In principle any characters

can appear in an axiom string and rewrite rules. However, in order to drive

the turtle the characters in the final output string must be mapped to the

command characters βFβ, βRβ or βLβ in some way (see later).

To help you get started a number of L-Systems have been defined for

you in the skeleton file for this exercise, LSystems.hs. Each is stored as a

triple of the form (angle, axiom, rules):

```
type LSystem = (Angle, Axiom, Rules)
cross, ..., arrowHead, ... :: LSystem
cross
= (90,
"M-M-M-M",
[(βMβ, "M-M+M+MM-M-M+M"),
(β+β, "+"),
(β-β, "-")
]
)
...
arrowHead
= (60,
"N",
[(βMβ, "N+M+N"),
(βNβ, "M-N-M"),
(β+β, "+"),
(β-β, "-")
]
)
...
```

As a simple example, suppose we work with the arrowHead L-system.

The axiom is the string βNβ. After the first rewrite the βNβ will be replaced

by the string βM-N-Mβ, using the rewrite rules obtained by calling rules

arrowHead. If the string is rewritten again, each βNβ will be replaced likewise, each βMβ will be replaced by the string βN+M+Nβ and the β+βs and β-βs

will be replaced by themselves. Thus, after a second application of the rules,

the string becomes βN+M+N-M-N-M-N+M+Nβ, and so on.

Notice that there are different rules for rewriting βNβs and βMβs, but

both will be ultimately interpreted as βmoveβ commands for the turtle. The

reason for having multiple move commands is thus not to control the turtle

in more elaborate ways, but to enable more interesting rewrite systems to

be expressed.

If you apply the rules for arrowHead a total of six times the command

string has 1457 characters! If the βMβs and βNβs in this string are both

mapped to turtle command βFβ and β+β and β-β to βLβ and βRβ respectively

the turtle will trace out the picture shown in Figure 1.

Bracketed L-Systems

In the above example the string contains just the characters βMβ, βNβ, β+β,

β-β and the final sequence of turtle commands generated from the final

string defines a continuous linear path, i.e. with no branches. You can

build more elaborate branching structures using bracketed L-Systems, as in

systems bush and tree.

Bracketed systems present an interesting problem because the commands

between a β[β and its matching β]β, corresponds to a branch in the structure. To render this, the turtle will have to draw the bracketed term as if it

were a separate L-System. When we reach the matching β]β we will have to

restore the turtle state to where it was before it hit the β[β. We thus need

a mechanism for βrememberingβ the turtle state throughout the execution

of the bracketed commands, so that we can process the commands after the

β]β starting from the same state. There are two ways to do it; both involve

writing a helper function.

Method 1: By recursion

Think about the problem: when we hit a β[β we have no idea where the

matching β]β is. Therefore, we cannot immediately determine the list of

commands that follow the matching β]β. One way to fix this is to get the

helper function to return not only a list of coloured lines, corresponding to

the trace, but also any remaining commands that have yet to be processed.

When you hit a β]β command you return an empty trace (nothing more to

do) and the list of commands that follow the β]β. When you hit a β[β you

first produce the trace for the commands up to the matching β]β. Then you

process the remaining commands, which you now know as they are returned

along with the trace. The final trace is obtained by appending the two

together.

Note that nested bracketed terms fall out naturally by recursion.

Method 2: Using an explicit stack

The second solution remembers the turtle state explicitly at each β[β command by carrying around a stack of turtle states β an additional argument

to the helper function. When you process a β[β command you push the

current turtle state onto the stack. When you process a β]β command you

need to process the remaining commands (after the β]β) but using the same

turtle state that you had when you hit the matching β[β command. But

this turtle state is precisely what now sits on top of the stack! Therefore,

all you need to do is pop this state from the stack and continue processing

the remaining commands.

Notice again that nested bracketed command sequences present no problems: each time you come across a β[β you push the current turtle state. If

there was already a state on top of the stack that state will now sit one element lower. So, it will take two β]β commands before that state is restored

β exactly what you want.

This solution avoids the need to produce and dismantle pairs (Method

1). However, it requires an extra parameter to be carried with each call to

the helper function.

Note that stacks are easily implemented in Haskell using lists. An item

can be placed on top of the stack (βpushedβ) using the : operator. An item

can be removed from the top of the stack (βpoppedβ) by pattern matching,

e.g. f (top : stack) = β¦

Important: Stacks are arguably the most important data structures in

computer science, precisely because they provide a way of traversing rich

branching structures in a sequential manner. You should implement both

of the above methods as it will help you to understand the role of stacks in

the implementation of recursive functions.

Β Define three functions angle, axiom and rules for extracting the angle, axiom and rules components of an LSystem.

```
angle :: LSystem -> Float
axiom :: LSystem -> String
rules :: LSystem -> Rules
```

Β Define a function

```
lookupChar :: Char -> Rules -> String
```

that will look up a character in a list of expansion rules, each of which (a

Rule) associates a character with a string. The function should return

the associated string. A precondition is that a binding exists for the

character in the expansion rules. For example:

```
lookupChar βMβ (rules peanoGosper)
"M+N++N-M--MM-N+"
lookupChar β+β (rules triangle)
"+"
```

Β Using `lookupChar`

define a function

```
expandOne :: String -> Rules -> String
```

that will return the string formed by replacing each character in the given argument string with the string associated with that

character in the given list of expansion rules. For example:

```
expandOne (axiom triangle) (rules triangle)
"-M+M-M-M+M"
```

Β Define a function

```
expand :: String -> Int -> Rules -> String
```

that will invoke expandOne a specified number of times on a given initial string (axiom) using the given list of expansion rules. For example:

```
expand (axiom arrowHead) 2 (rules arrowHead)
"N+M+N-M-N-M-N+M+N"
```

Β Define a function

```
move :: Command -> Angle -> TurtleState -> TurtleState
```

that will calculate the new position of a turtle given a

move command (synonymous with [Char]). The move command can

be either to turn left (βLβ) or right (βRβ) or to move forward (βFβ) in

the present direction.

The angle is the one associated with the L-System that was used to

generate the list of commands.

The state of the turtle is given by its current (x, y) co-ordinate and

its orientation, which is measured in degrees, anticlockwise from the

positive x-axis.

The type synonyms referred to above are defined in the template as

follows:

```
type Vertex = (Float, Float)
type TurtleState = (Vertex, Float)
type Command = Char
type Commands = [Command]
```

For example:

```
*LSystems> move βLβ 90 ((100, 100), 90)
((100.0,100.0),180.0)
*LSystems> move βFβ 60 ((50, 50), 60)
((50.5,50.866024),60.0)
*LSystems> move βFβ 45 ((-25, 180), 180)
((-26.0,180.0),180.0)
```

Β Using move, define two trace functions:

```
trace1, trace2 :: Commands -> Angle -> Colour -> [ColouredLine]
```

that implement the two

turtle tracing methods described above. They each take a string of

turtle commands and convert them into a list of lines drawn with

the specified colour that can be subsequently drawn on the screen by

drawLines. The angle is the one associated with the L-System that

was used to generate the list of commands β it is required when invoking move.

The type ColouredLine defines the start and end points of a line in

the Euclidean plane, along with its colour:

```
type ColouredLine
= (Vertex, Vertex, Colour)
```

Note: If you are facing angle ΞΈ degrees anticlockwise from 3 oβclock,

then a movement of length 1 would correspond to a displacement of

(cos ΟΞΈ

180 , sin ΟΞΈ

180 ) in (x, y) terms. L means add 90 (degrees) to ΞΈ and R

means subtract 90 from ΞΈ. Initially the turtle is at (0, 0) and has angle

ΞΈ = 90.

In each case you need to keep track of the state of the turtle as it is

moved and rotated; you will therefore need a helper function.

For Method 1 you need to keep track of both the generated trace and

the remaining command sequence. Itβs a little fiddly, as each call to the

helper function now returns a pair of items, so youβll need to pattern

match on the result each time in order to dismantle the pair. If you

get stuck here you might like to get Method 2 working first.

Recall that turtles have a single βmove forwardβ command (βFβ) whilst

the strings generated by the rewrite rules here use two characters βMβ

and βNβ to mean the same thing. Also, the characters β+β and β-β

are used to mean βrotate leftβ and βrotate rightβ respectively whereas

the corresponding turtle commands are βLβ and βRβ. Before a string is

passed to trace, therefore, the characters must be mapped into turtle

commands. Fortunately, you have just built such a function which can

perform such a mapping, i.e. expandOne! To use this to perform the

mapping we need to define a new Rules table that maps characters

to commands, e.g. βMβ and βNβ to βFβ, β+β to βLβ etc., and then call

expandOne accordingly. To save you time, we have provided this in the

skeleton β itβs called commandMap for obvious reasons. For example:

```
*LSystems> let (a, ax, rs) = arrowHead
*LSystems> let s = expand ax 3 rs
*LSystems> s
"M-N-M+N+M+N+M-N-M-N+M+N-M-N-M-N+M+N-M-N-M+N+M+N+M-N-M"
*LSystems> expandOne s commandMap
"FRFRFLFLFLFLFRFRFRFLFLFRFRFRFRFLFLFRFRFRFLFLFLFLFRFRF"
*LSystems> let (a, ax, rs) = triangle
*LSystems> trace1 (expandOne (expand ax 1 rs) commandMap) a blue
[((0.0,0.0),(1.0,0.0),(0.0,0.0,1.0)),((1.0,0.0),(0.99999994,1.0),
9
(0.0,0.0,1.0)),((0.99999994,1.0),(2.0,1.0),(0.0,0.0,1.0)),
((2.0,1.0),(2.0,0.0),(0.0,0.0,1.0)),((2.0,0.0),(3.0,0.0),
(0.0,0.0,1.0))]
```

Note the use of a let here to bind identifiers. GHCi remembers these

up until next file (re-)load, or until they are redefined by a subsequent

let. Instead of defining the components of arrowhead and triangle

using a let we could, of course, have used the functions angle, axiom

and rules.

To save typing in long expressions involving expandOne the template

contains the following function:

```
expandLSystem :: LSystem -> Int -> String
expandLSystem (_, axiom, rs) n
= expandOne (expand axiom n rs) commandMap
```

This takes the numeric index of a predefined L-System and the number of expansions required and returns the final sequence of turtle

commands. You might find this useful.