Home » Assignments » Assignment 2: Turtle Graphics
Assignment 2: Turtle Graphics
In this assignment, you will explore another way of thinking about graphics, inspired by the robotic “turtles” that some of you might associate with the LOGO programming language. You can think of the turtle as a machine with a pen, that sits on a sheet of paper. As it moves around the page, it drags the pen along the paper to draw pictures. You will be writing Haskell to generate instructions for a virtual turtle, and writing more Haskell to interpret these instructions into a CodeWorld Picture.
This assignment is worth 12% of your final grade.
Deadline: Monday May 6, 2019, at 9:00am Canberra time sharp
Overview of Tasks
You will be required to complete different tasks depending on your enrolled course. This assignment is marked out 100 (for COMP1100) or 120 (for COMP1130):
COMP1100
COMP1130
Task 1: Drawing Shapes
10 Marks
10 Marks
Task 2: Interpreting Turtle Commands
30 Marks
30 Marks
Task 3A: Sierpinski’s Triangle (Direct Drawing)
25 Marks
N/A
Task 3B: LSystems
N/A
40 Marks
Unit Tests
10 Marks
10 Marks
Style
10 Marks
10 Marks
Technical Report
15 Marks
20 Marks
From this assignment onward, code that does not compile will be penalised heavily. It is essential that you can write code that compiles and runs. If you have a partial solution that you cannot get to compile, you should comment it out and write an additional comment directing your tutor’s attention to it.
Getting Started
Fork the assignment repository and create a project for it in IntelliJ IDEA, following the same steps as in Lab 2. The assignment repository is at https://gitlab.cecs.anu.edu.au/comp1100/comp1100assignment2.
Overview of the Repository
Most of your code will be written in src/Turtle.hs. You will also need to write tests in test/TurtleTest.hs, which contains some example tests for you to study.
Other Files
test/Testing.hs is the same testing library we used in Assignment 1. You should read this file as well as test/TurtleTest.hs, and make sure you understand how to write tests.
app/Main.hs is a small test program that uses your turtle code. We discuss its features in “Overview of the Test Program”.
comp1100-assignment2.cabal tells the cabal build tool how to build your assignment. You are not required to understand this file, and we will discuss how to use cabal below.
Setup.hs tells cabal that this is a normal package with no unusual build steps. Some complex packages (that we won’t see in this course) need to put more complex code here. You are not required to understand it.
Overview of Cabal
As before, we are using the cabal tool to build the assignment code. The commands provided are very similar to last time:
cabal build: Compile your assignment.
cabal run turtle: Build your assignment (if necessary), and run the test program.
cabal repl comp1100-assignment2: Run the GHCi interpreter over your project.
cabal test: Build and run the tests. This assignment is set up to run a unit test suite like in Assignment 1, but this time you will be writing the tests. The unit tests will abort on the first failure, or the first call to a function that is undefined.
You should execute these cabal commands in the toplevel directory of your project: ~/comp1100/assignment2 (i.e., the directory you are in when you launch the IntelliJ Terminal tool for your project).
Overview of the Test Program
The test program in app/Main.hs uses CodeWorld, just like Assignment 1, and responds to the following keys:
2019/4/27 Assignment 2: Turtle Graphics – Assignments – Programming as Problem Solving (including Advanced) [2019 S1]
Key
Effect
T
Display a triangle (from Task 1)
P
Display a polygon (from Task 1)
=/-
Increase/decrease the number of sides (polygon mode only, from Task 1)
C
Display a test pattern (a way to test your Task 2 code)
S
Display Sierpinski’s Triangle (from Task 3A or 3B)
L
Display a picture generated from an LSystem (from Task 3B)
If you try to use the test program without completing Task 2, or you try to draw something you haven’t implemented yet, the test program will crash with the following error:
“Exception in blank-canvas application:”
Prelude.undefined
If this happens, refresh the browser to continue using the test program.
Turtles and the TurtleCommand Type
We are going to imagine a turtle as a pointsized robot that sits on a canvas. This robot has:
a pen, which can be either up or down; a position on the canvas; and
an angle called its facing.
There are four classes of commands that we can send to the turtle, and we represent those commands with the constructors of the TurtleCommand type: type Radians = Double
data TurtleCommand
= Forward Double
| Turn Radians
| PenUp
| PenDown
deriving Show
The commands have the following meaning:
Command
Meaning
Forward d
Drive forward d units from the current position, along the current facing. If the pen is down, draw a line between the old and new positions.
Turn t
Turn t radians (360 degrees = 2 * pi radians) from the current facing. This changes the direction that the turtle will drive in response to future Forward commands. Anticlockwise turns are represented by positive values of t; clockwise turns are represented by negative values of t.
PenUp
Lift up the pen. Future calls to Forward will not draw lines.
PenDown
Put the pen on the canvas. Future calls to Forward will draw lines.
Task 1: Drawing Shapes (10 marks)
To draw a (CodeWorld) Picture with turtle graphics, we need two things: the commands to draw, and a way of interpreting those commands. In this task, you will define some functions that generate lists of turtle commands. When you have built the interpreter in Task 2, these functions will be a source of test data that you can use to check your interpreter.
Your Task
Define the following two functions in src/Turtle.hs: triangle :: Double -> [TurtleCommand]
Returns a list of commands that will draw an equilateral triangle with side length equal to the argument. The turtle should finish with the same position and facing as when it started.
polygon :: Int -> Double -> [TurtleCommand]
polygon n s should return a list of commands that will draw a regular nsided polygon, with side length equal to s. The turtle should finish with the
same position and facing as when it started. If n < 3, raise an error. Hints
You won’t yet have an interpreter to test your generated [TurtleCommand] results. You can read ahead to the section on Unit Tests and write tests for these functions, or try working through a list of commands with a ruler and graph paper.
Try drawing a regular triangle, square or regular hexagon on a sheet of graph paper. Then place your pen on one corner and pretend that it is the turtle. What commands do you have to tell your turtle to make it trace the figure you drew on the graph paper?
The two points above are very similar, but work in opposite directions: the first one is asking you to check the result of your code by interpreting the results literally. The second point is looking at a correct result and asking yourself “what needed to happen to produce this?”. Being able to think in both directions is very useful.
Task 2: Interpreting Turtle Commands (30 marks)
Lists of TurtleCommand values are just data, but are useful because we can interpret them into a (CodeWorld) Picture. This is morally the same as the programming you are doing right now a .hs file is just textual data, but becomes more useful because we can interpret it as a Haskell program. The difference is only in degree, not kind.
Your Task
Define a function runTurtle :: [TurtleCommand] -> Picture in src/Turtle.hs, which interprets the [TurtleCommand] according to the rules laid out in the “Turtles and the TurtleCommand” section above. Assume that the turtle starts at (0, 0), facing north (straight up), with the pen down (on the paper).
If you have completed this task correctly, the test pattern you get by pressing C in the test program will look like this (click for larger version):
Hints
You cannot consider a turtle command on its own; you need to know what the turtle has already done. For example, you need to know whether the pen is up or down to determine whether Forward should draw a line. We recommend defining:
a type TurtleState, which tracks the turtle’s position, facing, and whether the pen is up or down, and a value initialState :: TurtleState, for the turtle’s initial position, facing, etc.
2019/4/27 Assignment 2: Turtle Graphics – Assignments – Programming as Problem Solving (including Advanced) [2019 S1]
Work through a simple [TurtleCommand] on paper, to see what your program needs to do.
Break your solution apart into several functions, and test each in isolation. If you find that function is not behaving like you expect, you will have smaller
units of code to debug, which is easier to get your head around.
Task 3A: Sierpinski’s Triangle Direct Drawing (COMP1100 only: 25 marks)
Sierpinski’s Triangle is a famous fractal (selfsimilar structure). We can generate approximations to Sierpinski’s Triangle using the following rules:
1. An approximation at depth 1 is a single equilateral triangle.
2. An approximation at depth n is made up of three approximations at depth n 1, with their side length reduced by half. These approximations are
arranged to cover the original triangle.
We can draw approximations to Sierpinski’s triangle using our turtle system (click for larger versions):
2019/4/27 Assignment 2: Turtle Graphics – Assignments – Programming as Problem Solving (including Advanced) [2019 S1]
2019/4/27 Assignment 2: Turtle Graphics – Assignments – Programming as Problem Solving (including Advanced) [2019 S1]
2019/4/27 Assignment 2: Turtle Graphics – Assignments – Programming as Problem Solving (including Advanced) [2019 S1]
2019/4/27 Assignment 2: Turtle Graphics – Assignments – Programming as Problem Solving (including Advanced) [2019 S1]
2019/4/27 Assignment 2: Turtle Graphics – Assignments – Programming as Problem Solving (including Advanced) [2019 S1]
Your Task
Define a function sierpinski :: Int -> Double -> [TurtleCommand] in src/Turtle.hs, which generates the necessary commands to draw an approximation to Sierpinski’s Triangle. The first argument specifies the depth, and the second specifies the side length. The turtle should finish with the same position and facing as when it started.
Hints
Task 3B: LSystems (COMP1130 only: 40 marks)
During his study of filamentous fungi and other simple biological structures, Hungarian biologist Astrid Lindenmayer invented a type of formal language that can model their development. These languages have come to be called LSystems, and are comprised of three parts:
1. An alphabet of symbols.
2. An initial string, consisting of symbols from that alphabet.
Be very clear in your mind about what happens at each level. Trace out a path for the turtle on graph paper, using the diagrammed behaviour as a guide. Actual drawing only happens at depth 1, and the other levels of the recursion position the turtle without drawing.
It’s very important that the turtle finishes with the same position and facing as when it started, because that’s how you know where it will be when you come out of a recursive call.
If you get stuck, try writing out the steps for drawing a depth2 approximation without recursion (but following the diagram closely), then look for subsequences that look like the instructions to draw a depth1 approximation.
https://cs.anu.edu.au/courses/comp1100/assignments/02/ 9/13
Unit Tests (10 marks)
How do you know that the program you’ve written is correct? GHC’s type checker rejects a lot of invalid programs, but you’ve written enough Haskell by now to see that a program that compiles is not necessarily correct. Testing picks up where the type system leaves off, and gives you confidence that changing one part of a program doesn’t break others. You have written simple doctests in your labs, but larger programs need more tests, so the tests you will write for this assignment will be labelled and organised in a separate file from the code.
Open test/TurtleTest.hs. This file contains a number of example test cases, written using a simple test framework defined in test/Testing.hs. These files are heavily commented for your convenience.
2019/4/27 Assignment 2: Turtle Graphics – Assignments – Programming as Problem Solving (including Advanced) [2019 S1]
You can run the tests by executing cabal test. If it succeeds it won’t print out every test that ran, but if it fails you will see the output of the test run. If you want to see the tests every time, use cabal test –show-details=streaming instead.
Your Task
Replace the example tests with tests of your own. The tests that you write should show that the Haskell code you’ve written in Tasks 13 is working correctly.
Hints
Try writing tests before you write code. Then work on your code until the tests pass. Then define some more tests and repeat. This technique is called testdriven development.
The expected values in your test cases should be easy to check by hand. If the tested code comes up with a different answer, then it’s clear that the problem is with the tested code and not the test case.
Sometimes it is difficult to check an entire structure that’s returned from one of your functions. Maybe you can compute some feature about your result that’s easier to test? You could try computing the total distance your turtle travels, its final point after interpreting all the commands, or some other properties that are easier to reason about.
If you find yourself checking something in GHCi (i.e., cabal repl comp1100-assignment2), ask yourself “should I make this into a unit test?”
If you are finding it difficult to come up with sensible tests, it is possible that your functions are doing too many things at once. Try breaking them apart
into smaller functions and writing tests for each.
The assertEqual and assertNotEqual functions will not work on the CodeWorld Picture type. If you want to write a test regarding the lines you draw on the canvas, you might have to come up with an intermediate representation for those lines.
If you want to write tests about new types you have defined, add deriving (Eq, Show) to the end of the type definition, like this:
data MyType = A | B | C deriving (Eq, Show)
Style (10 marks)
“[…] programs must be written for people to read, and only incidentally for machines to execute.”
From the foreword to the first edition of Structure and Interpretation of Computer Programs.
Programming is a brainstretching activity, and you want to make it as easy on yourself as possible. Part of that is making sure your code is easy to read, because that frees up more of your brain to focus on the harder parts.
Guidance on good Haskell style can be found in this course’s Style Guide, and in lecture notes.
Your Task
Ensure that your code is written in good Haskell style.