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
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 following webpage:
http://el.www.media.mit.edu/groups/logo-foundation/logo/turtle.html
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:
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:
Please add brief comments to your Haskell modules explaining what the
functions do, but pointing out the obvious is unneccessary. Also, please
take a few minutes to remove all functions, definitions, debug information,
etc. that are not used from your code.
Good luck!
Bengt Nordstrom
This laboration was originally constructed by
Koen Claessen
at Chalmers.
Last modified: Sun Oct 26 12:12:27 KST 2003
|