Assignment 1

Description

This lab assignment asks you to implement a library for so-called turtle graphics. The library will be interfaced to as an embedded language. Several extensions are then made to the original turtle language.

We recommend that you implement the graphics part of the lab either using WxHaskell or to generate SVG files. If you would like to use a different graphics library please contact Jean-Philippe before starting the assignment.

Turtle Graphics

The idea of turtle graphics was originally part of the Logo programming language. It originated from an environment where a real robot (the "turtle") could move around and act on simple commands. The two basic commands it understood were: 


forward n
right d
Here, n is the number of steps the robot should move forward, and d the number of degrees the robot should turn. More information can be found on the Turtle graphics wikipedia page (or in a local copy of the "Logo primer"). The idea is that you will implement a part of this turtle graphics language. Your program will be able to produce something like the following output:

Below follow a number of tasks. Needless to say, please read these carefully and make sure you do not miss parts of an assignment! Most assignments require coding and descriptions + motivations of what you have done.

Part I

Deadline: Wed Jan 26

The first part of this assignment is just to get you started. You should get started also on Part II before the deadline for Part I.

Part I - Task 1 - WxHaskell

Familiarise yourself with WxHaskell by writing a simple program which opens a window and draws something in it.

Part I - Task 2 - Library interface

The turtle graphics language should be implemented as an embedded language library in Haskell. The turtle language should be provided to the user as a single module, exporting abstract datatypes and operations.

An important part of creating an embedded language is to think carefully about what interface you want to offer to the user. Think about compositionality (how easy is it to combine simpler programs to build more complex ones?), and abstraction (hiding irrelevant implementation details from the users).

For instance, your library might define and export the following things (different interfaces are conceivable and perhaps even desirable, as long as they implement the same basic functionality): 


type Program -- the abstract type of a turtle program
forward :: Double -> Program
right   :: Double -> Program
...
Other turtle commands you should provide are: penup, pendown, which stop drawing and start drawing respectively, color, which changes the color of the turtle's pen, stop, which stops the execution of a program, backward, left, and times (that repeats a turtle program a certain number of times), and forever that repeats a program forever. Also think in what ways you would like to combine two turtle programs!

Write down the interface of your library, like in the example above, listing the types you plan to export (without definitions) and type signatures for the operations. When appropriate add explanations of what your operations are intended to do. Make sure you don't forget to add a run function for your programs.

Part I - Task 3 - Example

Write down the spiral example from Logo language using your interface. In their syntax it looks like:


spiral 0 91 
    
      to spiral :size :angle
        if :size > 100 [stop]
        forward :size
        right :angle
        spiral :size + 2 :angle
      end
You won't be able to run your spiral example yet.

Part II

Deadline: Wed Feb 2

In this part of the assignment you will implement your turtle language and add a few extensions.

Part II - Task 1 - Implementation

Implement the library you designed in Part I. Think about the distinction between primitive operations and derived operations, and try to keep the set of primitive operations as small as possible.

At this point you might realise that the interface you've designed is missing some operations, or that parts of it are difficult to implement. Don't hesitate to change the interface in these cases--just be clear that you did change it and motivate why you felt a change was necessary.

Make sure that you carefully define the borders of your library by explicitly exporting only the things you want a user to see (as given by the interface you've designed).

Part II - Task 2 - Parallel composition

Add a parallel composition combinator to your turtle language. One possible interface parallel composition could have is: 
(<|>) :: Program -> Program -> Program
When you run a turtle program p <|> q, there suddenly will be two turtles, one running p and the other running q, in parallel. Decisions you have to make are: What happens after a parallel composition finishes? Is your parallel composition commutative, is it associative? (To answer this question you must first define what it means for programs to be equal.) Describe and motivate your decisions!

Part II - Task 3 - Extensions

Several extensions to the simple turtle language can be made. Implement at least one extension from this list:
  1. 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. 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. You can use other methods to wait for the user (keyboard); but make sure to make clear in the report.

  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 "Logo primer".

  5. Add a way to your language of finding out information about for example, where the turtle currently is, where the mouse pointer is, or if the user clicks the mouse. It should 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. (But be creative, we may judge your extension to be too easy!)

Part II - Task 4 - Examples

Implement some examples that together use all of the constructs you have implemented. (Do this in a different module that imports the module defining the embedded language.) Also indicate your "favorite" turtle program, resulting in a cool picture or animation. I will publish these somewhere on the course homepage.

Part II - Task 5 - Thoughts and reflections

Answer the following questions:
  1. Did you use a shallow or a deep embedding, or a combination? Why? Discuss in a detailed manner how you would have implemented the Program type if you had chosen the other approach. What would have been easier/more difficult?
  2. What changes did you have to make to your program to implement the extensions? Do you think you could have avoided some of these by having chosen a different library design from the start?
  3. 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 your embedding?
  4. 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 your embedding?
  5. In what way have you used the following programming language features: higher-order functions, laziness, polymorphism?

Submission

Deadline

The deadline for the first part is Wed Jan 26 and the deadline for the second part is Wed Feb 2. The final deadline is Wed Mar 16. (Please read the rules on what first and final deadline mean.) Both parts of the assignment should be submitted in the same place, under Assignment 1 in the reporting system.

Clean Code

Before you submit your code, Clean It Up! Submitting clean code is Really Important, and simply the polite thing to do. After you feel you are done, spend some time on cleaning your code; make it simpler, remove unneccessary things, etc. We will reject your solution if it is not clean. Clean code:

Submission

Your submission needs to include the following information:

Before you submit, please read the note on cheating.

You are supposed to submit your solution using the Fire system.

Note: You do NOT have to use zip/gzip/tar/bzip on your files! Just upload and each file that is part of your solution. Don't forget to submit when you have uploaded all the files.

To the Fire System

Good luck!