AFP assignment: turtle graphics.

You are going to implement an embedded domain specific language to describe turtle graphics. The goal of this assignment is to give you a feel for the design issues involved with an embedded language and experience with first-class IO values and graphical user interfaces.

The idea is that there is a turtle that carries a pencil that can draw on a canvas. The turtle is knows just two primitive commands:

right d
forward n

That is, it can go forward for n units, or it can turn right over d degrees. For example, we can draw a square using the following commands: 

forward 50
right 90
forward 50
right 90
forward 50
right 90
forward 50

You can find more examples and information at the following webpage: http://el.www.media.mit.edu/groups/logo-foundation/logo/turtle.html

Prerequisites

It is encouraged to do this assignment with the wxHaskell 0.2 library at http://wxhaskell.sourceforge.net. Unfortunately, this means that you need ghc 6.01 and administrator rights.  This implies that only people with access to a computer that they own, can do this assignment with wxHaskell. I can probably provide a few people (up to 4) with a dedicated computer in the ST-lab in the CGN building. 

If you really need to work on a standard lab machine, you can also do the assignment using the SOE graphics library for Hugs: http://cvs.haskell.org/Hugs/pages/downloading.htm. See their documentation about how to open windows and do drawing. 

Assignments

Assignment 1

Implement the turtle language as an embedded language in Haskell. The language is embedded in Haskell as a single module that exports abstract data types and associated operations. You should consider carefully what operations you want to expose to the user so that programming with turtles becomes convenient. For example, you could start with an interface like this:

data Drawing  
forward :: Double -> Drawing
right   :: Double -> Drawing
...

Of course, this is just an example and you can define another kind of interface, as long as it has the same basic functionality. In both cases, you need to be able to defend why you have chosen for a particular approach. Other turtle commands you should implement are penup and pendown, to either hide or show the trail of the turtle, color that changes the color of the pen, and stop to end a program.

Other commands are somewhat easier to add: backward, left, and repeat. Why are these easier to add?

You should also provide an execute function that takes a turtle program and runs it. Think about how general your function should be: should it open its own window and take of everything itself, or should it be parameterised by a window or drawing functions? Explain why you have chosen a particular approach. Think also about a coordinate system: do you use pixels as units? what happens on a resize of the window?  Note that your turtle should start in the center, going upwards.

You implementation doesn't have to show a turtle: it just has to show how the final result looks like. Check your implementation by implementing the spiral example from the http://el.www.media.mit.edu/groups/logo-foundation/logo/turtle.html webpage.

to spiral :size :angle 
  if :size > 100 [stop] 
  forward :size 
  right :angle 
  spiral :size + 2 :angle 
end

Of course, you would implement your examples in a separate module than the Turtle module.

Assignment 1a (optional)

Instead of drawing the result of a turtle drawing, show how the drawing is drawn. You don't have to show a turtle itself, just showing the effect of the turtle moving around is good enough. You could use a timer together with a mutable variable and repaint to animate the drawing. Look at the wxHaskell bouncing balls example for an illustration of their usage. If you use SOE graphics, you can probably use sleep (or Win32.sleep) to achieve the same effect.

Once this works, you can also try to implement the forever operator.

Assignment 2

Implement parallel composition to your interface. One possible interface could be:

(<|>) :: Drawing -> Drawing -> Drawing

When you execute the drawing p <|> q there will be two turtles, one drawing p, the other drawing q in parallel.

Think about what happens after a parallel composition finishes? Is the operator commutative? and associative? Why would these laws be important to a programmer?

Assignment 3

Several other extensions to the simple turtle language can be made. Implement at least one extension from this list:

1. You could add a save construct to the language. 

  save :: Program -> Program
The meaning of the program save p is to recall the current position of the turtle and to continue with the program as if nothing happened. But as soon as we are done, we return to the saved state and execute the program p from that point. When you have several save statements in your program, all of them should be saved and later executed, but you may decide yourself in what order.

2. You could add a pause construct to your language. In this case, you will add a button with the text "Continue" to the graphical interface. This button is normally inactive, but when the turtle program executes the pause command, it halts, and the "Continue" button becomes active. When the user clicks on the "Continue" button, the program continues and the continue button becomes inactive again.

3. Similar to 2., but instead of an explicit pause, you have a combinator called stepping. 

  stepping :: Program -> Program
The meaning of the program stepping p is: execute p as normal, but the user is required to click the "Continue" button at every step during the execution of p.

4. Add the commands showturtle and hideturtle to your language, which toggle between having a turtle picture shown when drawing the pictures or not. A variant of this allows different turtle bitmaps and maybe even a background image. One can then describe simple animations. Also see the section "Up and Away" from the above mentioned turtle web page.

5. Add a way to your language of finding out information about for example, where the turtle currently is, or if the user clicks or drags the mouse. It should of course be possible to then use this information in your turtle programs.

6. Invent your own extension to the turtle language. By extension I mean something that cannot be implemented in terms of the existing language constructs.

Assignment 4

Create a cool picture that uses some or all the extensions that you have made. To keep up a long standing tradition, the team with the best demo, subjectively chosen by me :-), wins a bag of M&M's.

Assignment 5

Answer and motivate the following questions:

  1. Compare the usability of your embedding against a custom-made implementation of a turtle language with dedicated syntax and interpreters. How easy is it to write programs in your embedded language compared to a dedicated language? What are the advantages and disadvantages of an embedding?
  2. Compare the ease of implementation of your embedding against a custom-made implementation. How easy was it to implement the language and extensions in your embedded language compared to a dedicated language? What are the advantages/disadvantages of an embedding?
  3. In what way have you used the following programming language features: higher-order functions, laziness, and polymorphism?

Submission

You should send your submission before Sunday, 28 September, 23:59h to daan@cs.uu.nl with the subject afp submission. In the body, you should  put the names of your team and the student numbers. You should attach the following (zipped/tarred) files:

  1. A module Turtle.hs that contains your embedding of the turtle language.
  2. A module Main.hs that contains your examples. If I run main, I should see the coolest example you have made.
  3. A text file named report that contains the answers to the questions and comments and motivations about your implementation.
Your code will also be judged on elegance!

Success!