Turtle Graphics and L-systems
Informatics 1 – Introduction to Computation
Functional Programming Tutorial 7
Cooper, Heijltjes, Lehtinen, Melkonian, Scott, Vlassi-Pandi, Wadler, Yallop
Week 8
due 4pm Wednesday 11 November 2020
tutorials on Friday 13 November 2020
Attendance at tutorials is obligatory; please send email to lambrose@ed.ac.uk if you
cannot join your assigned tutorial.
Good Scholarly Practice: Please remember the good scholarly practice requirements
of the University regarding work for credit. You can find guidance at the School page
http://web.inf.ed.ac.uk/infweb/admin/policies/academic-misconduct.
This also has links to the relevant University pages. Please do not publish solutions to
these exercises on the internet or elsewhere, to avoid others copying your solutions.
1
Turn 120
Start
Turn 120
Go 30
Go 30
Go 30
1 Turtle graphics
Turtle graphics is a simple way of making line drawings.The turtle has a given location on the canvas
and is facing in a given direction. A command describes a sequence of actions to be undertaken by
a turtle, including moving forward a given distance or turning through a given angle.
Turtle commands can be represented in Haskell using an algebraic data type:
type Distance = Float
type Angle = Float
data Command = Go Distance
| Turn Angle
| Sit
| Command :#: Command
The last line declares an infix data constructor. We have already seen such constructors in Tutorial 6,
where we used them for the binary connectives of propositional logic. While ordinary constructors
must begin with a capital letter, infix constructors must begin with a colon. Here, we have used the
infix constructor :#: to join two commands.
Thus, a command has one of four forms:
• Go d, where d is a distance — move the turtle the given distance in the direction it is facing.
Distances must be non-negative.
• Turn a, where a is an angle — turn the turtle anticlockwise for a positive angle, clockwise for
a negative angle.
• Sit — do nothing: leaves the turtle’s position and direction unchanged.
• p :#: q, where p and q are themselves commands — execute the two given commands in
sequence.
For instance, to draw an equilateral triangle with sides of thirty units, we need to order the turtle
to move forward three times, turning 120◦ between moves (see Figure 1):
Go 30 :#: Turn 120 :#: Go 30 :#: Turn 120 :#: Go 30
Figure 1: Drawing a triangle with turtle commands
2
1.1 Viewing paths
You can view a turtle’s path by typing:
*Main> display pathExample
where pathExample is an expression of type Command. This will output an SVG image as output.html,
which you can view on your browser. For instance, pathExample was already defined for you as:
pathExample = Go 30 :#: Turn 120 :#: Go 30 :#: Turn 120 :#: Go 30
and draws the triangle described above.
1.2 Equivalences
Note that :#: is an associative operator with identity Sit. So we have:
p :#: Sit = p
Sit :#: p = p
p :#: (q :#: r) = (p :#: q) :#: r
We can omit parentheses in expressions with :#: because, wherever they are placed, the meaning
remains the same. In this assignment, when we say that two commands are equivalent we mean that
they are the same according to the equalities listed above.
However, to evaluate an expression Haskell has to place parentheses; if you ask it to show a command,
it will also show where it has placed them:
*Main> Sit :#: Sit :#: Sit
Sit :#: (Sit :#: Sit)
Exercise 1
In this first exercise we will explore the equivalence of turtle commands and convert them
into lists and back.
(a) Write a function
split :: Command -> [Command]
that converts a command to a list of individual commands containing no :#: or Sit
elements. For example,
*Main> split (Go 3 :#: Turn 4 :#: Go 7)
[Go 3, Turn 4, Go 7]
(b) Write a function
join :: [Command] -> Command
that converts a list of commands into a single command by joining the elements together.
For example,
*Main> join [Go 3, Turn 4, Go 7]
Go 3 :#: Turn 4 :#: Go 7 :#: Sit
As in all our examples, the result can be any command equivalent to the given command.
(c) Note that two commands are equivalent, in the sense of the equivalence laws above, if
split returns the same result for both.
3
*Main> split ((Go 3 :#: Turn 4) :#: (Sit :#: Go 7))
[Go 3, Turn 4, Go 7]
*Main> split (((Sit :#: Go 3) :#: Turn 4) :#: Go 7)
[Go 3, Turn 4, Go 7]
Write a function equivalent that tests two commands for equivalence. Give both its
type and definition.
(d) Write two QuickCheck properties to test split and join. prop_split_join should
check that join (split c) is equivalent to c, where c is an arbitrary command.
prop_split should check that the list returned by split contains no Sit and (:#:)
commands.
Exercise 2
Using the above translation from lists, we will write a function to draw regular polygons.
(a) Write a function
copy :: Int -> Command -> Command
which given an integer and a command returns a new command consisting of the given
number of copies of the given command, joined together. (If the requested number of
copies is 0 or negative, just return Sit.) Thus, the following two commands should be
equivalent:
copy 3 (Go 10 :#: Turn 120)
Go 10 :#: Turn 120 :#: Go 10 :#: Turn 120 :#: Go 10 :#: Turn 120
(b) Using copy, write a function
pentagon :: Distance -> Command
that returns a command which traces a pentagon with sides of a given length. The
following two commands should be equivalent:
pentagon 50
and
Go 50.0 :#: Turn 72.0 :#:
Go 50.0 :#: Turn 72.0 :#:
Go 50.0 :#: Turn 72.0 :#:
Go 50.0 :#: Turn 72.0 :#:
Go 50.0 :#: Turn 72.0
(c) Write a function
polygon :: Distance -> Int -> Command
that returns a command that causes the turtle to trace a closed path making a regular
polygon with the given number of sides, of the specified length. Thus, the following two
commands should be equivalent:
polygon 50 5
pentagon 50
Hint: You may need to use the Prelude function fromIntegral to convert an Int to a
Float. 4
Exercise 3
Next, we will approximate a spiral, by making our turtle travel increasing (or decreasing)
lengths and turning slightly in between. Our function copy is of no help here, since the
distance our turtle needs to travel changes after each corner it takes. Therefore, your spiral
function will have to be recursive. Its type signature should be as follows:
spiral :: Distance -> Int -> Distance -> Angle -> Command
Its parameters are
• side, the length of the first segment,
• n, the number of line segments to draw,
• step, the amount by which the length of successive segments changes, and
• angle, the angle to turn after each segment.
To draw such a spiral, we draw n line segments, each of which makes angle angle with the
previous one; the first should be as long as side and thereafter each one should be longer by
step (or shorter, if step is negative).
Thus, the following two commands should be equivalent:
spiral 30 4 5 30
Go 30.0 :#: Turn 30.0 :#:
Go 35.0 :#: Turn 30.0 :#:
Go 40.0 :#: Turn 30.0 :#:
Go 45.0 :#: Turn 30.0
Note: your recursion should definitely stop after n steps (the second parameter), but you
will also need to keep in mind that line segments should not become negative in length.
Sample output is shown in Figure 2.
Figure 2: A spiral (spiral 0.1 1000 0.1 4)
Exercise 4
Besides the equalities we saw earlier, we might also want to consider the following ones:
Go 0 = Sit
Go d :#: Go e = Go (d+e)
Turn 0 = Sit
Turn a :#: Turn b = Turn (a+b)
5
So the Sit command is equivalent to either moving or turning by zero, and any sequence of
consecutive moves or turns can be collapsed into a single move or turn (as long as moves have
a non-negative distance!). Write a function:
optimise :: Command -> Command
which, given a command p, returns a command q that draws the same picture, but has the
following properties:
• q contains no Sit, Go 0 or Turn 0 commands, unless the command is equivalent to Sit.
• q contains no adjacent Go commands.
• q contains no adjacent Turn commands.
For example:
*Main> optimise (Go 10 :#: Sit :#: Go 20 :#:
Turn 35 :#: Go 0 :#: Turn 15 :#: Turn (-50))
Go 30.0
Hints: You can use split and join to make your task easier. If your version of join adds
a Sit command, you will need to define a new version which does not. Remember that Go
does not take negative arguments.
2 Branching and colours
So far we’ve only been able to draw linear paths; we haven’t been able to branch the path in any
way. In the next section, we will make use of two additional command constructors:
data Command = ...
| GrabPen Pen
| Branch Command
where Pen is defined as:
data Pen = Colour Float Float Float
| Inkless
These give two additional forms of path.
• GrabPen p, where p is a pen: causes the turtle to switch to a pen of the given colour. The
following pens are predefined:
white, black, red, green, blue :: Pen
You can create pens with other colours using the Colour constructor, which takes a value
between 0 and 1.0 for each of the red, green and blue components of the colour. The special
Inkless pen makes no output; you can use Inkless to create disjoint pictures with a single
command.
• Branch p, where p is a path: draws the given path and then returns the turtle to direction
and position which it had at the start of the path (rather than leaving it at the end). Pen
changes within a branch have no effect outside the branch.
To see the effect of branching, draw the following path.
let inDirection angle = Branch (Turn angle :#: Go 100) in
join (map inDirection [20,40..360])
6
3 Optional Material
Please note that optional exercices do contribute to the final mark. If you don’t do the
optional work and get the rest mostly right you will get a mark of 3/4. To get a mark
of 4/4, you must get almost all of the tutorial right, including the optional questions.
3.1 Introduction to L-Systems
The Swedish biologist Aristid Lindenmayer developed L-Systems to model the development of
plants.1
An L-System consists of a start pattern and a set of rewrite rules which are recursively applied to
the pattern to produce further increasingly complex patterns. For example, Figure 3 was produced
from the “triangle” L-System:
angle: 90
start: +f
rewrite: f → f+f-f-f+f
Each symbol in the string generated by an L-System represents a path command: here, + and -
represent clockwise and anticlockwise rotation and f represents a forward movement. Which symbols
represent which commands is a matter of convention.
In this system, only the symbol f is rewritten, while the + and - symbols are not. The rewriting
replaces the straight lines with more complex figures.
Figure 3: Triangle L-System output
Here is how to generate a picture with an L-System. Begin with the start pattern. Then apply the
rewrite rule some number of times, replacing the character on the left by the sequence on the right.
For instance, applying the above rule three times gives the following strings in successive steps:
1For more on L-Systems, see http://en.wikipedia.org/wiki/L-System. A book, The Algorithmic
Beauty of Plants, contains beautiful color illustrations produced by L-Systems; it is available online at
http://algorithmicbotany.org/papers/#abop
7
Step Pattern
0 +f
1 +f+f-f-f+f
2 +f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f
3
+f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f
+f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f
-f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f
-f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f
+f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f
Note that you could continue this process for any number of iterations.
After rewriting the string the desired number of times, replace each character that remains by some
drawing commands. In this case, replace f with a move forward (say, by 10 units), replace each +
by a clockwise turn through the given angle, and replace each - by an anticlockwise turn through
the given angle.
Converting L-Systems to functions that return turtle commands is straightforward. For example,
the function corresponding to this “triangle” L-System can be written as follows:
triangle :: Int -> Command
triangle x = p :#: f x
where
f 0 = Go 10
f x = f (x-1) :#: p :#: f (x-1) :#: n :#: f (x-1)
:#: n :#: f (x-1) :#: p :#: f (x-1)
n = Turn 90
p = Turn (-90)
Study the above definition and compare it with the L-System definition on the previous page. The
above definition is included in LSystem.hs, so you can try it out by typing (for instance):
display (triangle 5)
A couple of things are worth noting. The symbols from the system that are rewritten are implemented as functions that take a “step number” parameter—in this case, only f is rewritten. When
we have taken the desired number of steps, the step number bottoms-out at 0, and here f is just
interpreted as a drawing command. The symbols that are not rewritten are implemented as variables, such as n and p. In general, there will be one definition in the where clause for each letter in
the L-System.
A rewrite rule for the L-System may contain clauses in square brackets, which correspond to branches.
For example, here is a second L-System, that uses two letters and branches.
angle: 45
start: f
rewrite: f → g[-f][+f][gf]
g → gg
Here is the corresponding code (also included in LSystem.hs).
tree :: Int -> Command
tree x = f x
where
8
Figure 4: Tree L-System output
f 0 = GrabPen red :#: Go 10
f x = g (x-1) :#: Branch (n :#: f (x-1))
:#: Branch (p :#: f (x-1))
:#: Branch (g (x-1) :#: f (x-1))
g 0 = GrabPen blue :#: Go 10
g x = g (x-1) :#: g (x-1)
n = Turn 45
p = Turn (-45)
A picture generated by this definition is shown in Figure 4. Here we use different pens to draw the
segments generated by different symbols: this is not part of the description of the L-system, but it
generates prettier pictures.
Exercise 5
Write a function arrowhead :: Int -> Command implementing the following L-System:
angle: 60
start: f
rewrite: f → g+f+g
g → f-g-f
Exercise 6
Write a function snowflake :: Int -> Command implementing the following L-System:
angle: 60
start: f--f--f--
rewrite: f → f+f--f+f
Exercise 7
Write a function hilbert :: Int -> Command implementing the following L-System:
9
angle: 90
start: l
rewrite: l → +rf-lfl-fr+
r → -lf+rfr+flNote: Not all of the symbols here need to move the turtle. Check your result against
the pictures at http://en.wikipedia.org/wiki/Hilbert_curve and adjust the final values
(e.g. r 0 = ...) until it looks like those.
10
4 (Really Optional) Challenge
Please note that challenges are entirely optional; you can receive full marks without
attempting the challenge.
Just for fun, here are more L-Systems for you to try.
• Peano-Gosper:
angle: 60
start: f
rewrite: f → f+g++g-f--ff-g+
g → -f+gg++g+f--f-g
• Cross
angle: 90
start: f-f-f-frewrite: f → f-f+f+ff-f-f+f
• Branch
angle: 22.5
start: g
rewrite: g → f-[[g]+g]+f[+fg]-g
f → ff
• 32-segment
angle: 90
start: F+F+F+F
rewrite: F → -F+F-F-F+F+FF-F+F+FF+F-F-FF+
FF-FF+F+F-FF-F-F+FF-F-F+F+F-F+
11
5 (Really Optional) Challenge 2: Pretty Printing
Please note that challenges are entirely optional; you can receive full marks without
attempting the challenge.
As you worked through this tutorial, you will have noticed that when printing the turtle’s path in
the REPL, it grows hard to read as it gets longer. The challenge is to use a Pretty-Printer to make
reading a Command easier!
5.1 Setup
You need to install the “GenericPretty-1.2.2” package and update the tutorial files.
1. Open a terminal of your choice and execute the command cabal update.
2. Use cabal to install the “GenericPretty-1.2.2” package by executing the following command:
cabal install GenericPretty-1.2.2
The relevant code to use this package is already contained in the LSystem.hs file. There are five
lines of code that you must comment or uncomment; they are clearly marked with comments.
5.2 Pretty Printing
The GHCi REPL can already print out a command, however, it places the entire output on a single
line. The first example below has only five commands, yet barely fits without running over. To use
the pretty-printer derived by GenericPretty instead, use the function pp as shown:
*Main> pathExample
Go 30.0 :#: (Turn 120.0 :#: (Go 30.0 :#: (Turn 120.0 :#: Go 30.0)))
*Main> pp pathExample
Go 30.0 :#:
(Turn 120.0 :#:
(Go 30.0 :#: (Turn 120.0 :#: Go 30.0)))
The name it refers to the result of the previously evaluated expression. Therefore pp it is a
convenient shorthand for pretty-printing the last command created. For example:
*Main> tree 1
(GrabPen (Colour 0.0 0.0 1.0) :#: Go 10.0) :#: (Branch (Turn 45.0 :#: (GrabPen
(Colour 1.0 0.0 0.0) :#: Go 10.0)) :#: (Branch (Turn (-45.0) :#: (GrabPen (Col
our 1.0 0.0 0.0) :#: Go 10.0)) :#: Branch ((GrabPen (Colour 0.0 0.0 1.0) :#: G
o 10.0) :#: (GrabPen (Colour 1.0 0.0 0.0) :#: Go 10.0))))
*Main> pp it
(GrabPen (Colour 0.0 0.0 1.0) :#: Go 10.0) :#:
(Branch (Turn 45.0 :#:
(GrabPen (Colour 1.0 0.0 0.0) :#: Go 10.0)) :#:
(Branch (Turn (-45.0) :#:
(GrabPen (Colour 1.0 0.0 0.0) :#: Go 10.0)) :#:
Branch ((GrabPen (Colour 0.0 0.0 1.0) :#:
Go 10.0) :#:
(GrabPen (Colour 1.0 0.0 0.0) :#: Go 10.0))))
Which do you find easier to read?
12
5.3 Feedback
The pretty-printer is the result of a student project to improve Inf1A. We would like to hear your
thoughts on the installation process, the usage, and any interesting commands you found to print.
Details of how to submit this feedback will be provided in a Piazza post.
The 2020 Inf1A FP Programming Competition
You are invited to enter this year’s Inf1 programming competition. The first prize is a book token.
The prize is sponsored by Galois. Last year’s entries are at:
http://homepages.inf.ed.ac.uk/wadler/fp-competition-2019/
Depending on quality of entries, we may award several prizes.
The competition is optional and unassessed. The prize will go to the best picture generated by a
Haskell program. You may use turtle commands or any other Haskell graphics package. You may
generate this picture with an L-System or with any other technique. You may generate still images
or use animation or interaction. You may enter alone or with a group of other students. Be creative!
Mail your entry to xxx. The judges will be Philip Wadler, Orestes Melkonian, Jesse Sigal, and Dee
Yeum.
• Label you entry with the names of everyone who worked on it.
• Include clear instructions for running your entry.
Entries are due 4pm Monday 30 November 2020.