Description

This laboration asks you to implement a library for so-called turtle graphics. You can do this lab in groups of two persons. The library will be interfaced to as an embedded language. Several extensions are then made to the original turtle language. Here you will find a link to a paper by Paul Hudak giving a background. Another very good background is this description of shallow and deep embedding.

There is a graphics library for Haskell at http://www.haskell.org/graphics/, which you can download. The documentation is probably included in the distribution, but you can also read it from here.

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 ride around and listen to simple commands. The two basic commands it understood were:

  forward n
  right d

http://el.www.media.mit.edu/groups/logo-foundation/logo/turtle.html

Assignments

1.	Implement the turtle graphics language 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. Think carefully about what interface you want to offer to the user of your embedded language, so that it is convenient to write turtle programs! Hint: your library might define and export the following things (but you are allowed to have a different interface, as long as it implements 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, and stop, which stops the execution of a program. Also think in what ways you would like to combine two turtle programs! There are other commands which are probably easy to add: backward, left, repeat (note that you will have to change the name of this command, since there is a standard Haskell function with the same name), and forever. Why are these commands easy to add? Of course, you should provide a run function, which takes a turtle program as an argument and runs it. Think about how general your run function should be; should it open its own window and take care of everything itself? or should it be parametrised over these things? Motivate your decision! Your basic run function does not have to draw a turtle while it is running the program. Just show what the turtle draws while it is walking. Check if your implementation works by implementing the spiral example from the above mentioned webpage in your embedding. 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
2.	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?
3.	Several other extensions to the simple turtle language can be made. Implement at least one extension from this list: a. 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. b. 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. c. Similar to b., 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. d. 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 webpage. e. 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 of course be possible to then use this information in your turlte programs. f. 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, I may judge your extension to be too easy!)
4.	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.
5.	Also answer the following questions: a. Did you use a shallow or a deep embedding, or a combination? Why? What would have ben easier/more difficult if you had use the other? b. 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? c. 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? d. 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? e. In what way have you used the following programming language features: higher-order functions, laziness, polymorphism?

Deadline

The deadline for this laboration is at the lecture Thursday, October 23.

Submission

Before you submit, please read the note on cheating. This is the policy we use at Chalmers, and it is also the attitude I have.

Your submission needs to include the following information:

Good luck!
Bengt Nordstrom

This laboration was originally constructed by Koen Claessen at Chalmers.