Description
In this assignment, you will implement in Haskell an interpreter for a toy language. This toy
language is designed so that all you need are recursion, the State monad, and trigonometry.
As usual, you should also aim for reasonably efficient algorithms and reasonably lucid code.
Turtle Graphics
There are some educational programming languages that draw simple pictures. Their model is
described to children as: Your program controls a turtle that can move around and draw. It has
a current position, a current direction, and a pen in one of two states: down (touches paper) and
up (away from paper). (More elaborate versions also have colours and stroke widths.) There are
commands to tell the turtle to:
• change the pen state
• turn counterclockwise by a number of degrees (change direction)
• move forward by a distance (whether this draws a line segment or not depends on the pen
state)
There are also the usual programming constructs to make things interesting: variables, arithmetic,
conditional branching, loops, procedures, even recursion.
In this assignment, you are given the abstract syntax tree of such a language—call it Turbo—
and you are to implement an interpreter for it. For simplicity, Turbo has only variables, arithmetic,
and for-loops.
The type of the abstract syntax tree is Stmt; its various cases are explained in ‘TurboDef.hs’.
There is also an accompanying RealExpr for the expressions.
The bulk of the interpreter works with a State monad to keep track of the variables (stored
in a dictionary type call ‘Map’), the current direction, and the pen state. For reasons explained
below, we don’t need the current position.
The interpreter returns a list of SVGPathCmd (explained below) to represent the resulting
moving and drawing. Naturally, most statement kinds don’t move or draw—so just return the
empty list. Forward is the only statement kind that causes outputting one command (in a list).
For-loops and compound statements will have to perform list concatenation.
SVG
The output of the interpreter is a list of commands for the ‘path’ construct in SVG files. The
‘path’ construct accepts a list of commands, two kinds of which we use are:
• relative move-to (δx, δy): add (δx, δy) to the current position, without drawing
• relative line-to (δx, δy): likewise, but also draws the line segment
1
This means the web browser that renders the SVG file will keep track of the current position, so
we don’t have to. But now you have to do polar-to-rectangular conversion: from “distance r, angle
a” to (δx, δy). Keep in mind that while Turbo uses degrees, Haskell’s sin and cos use radians.
Also you have to read the pen state to decide whether it’s a move-to or line-to.
The type SVGPathCmd represents these two kinds of commands.
‘PlayTurbo.hs’ is provided to run a Turbo program (with the interpreter you implement) and
convert [SVGPathCmd] to an SVG file, so you can view it in a web browser. It also contains
sample Turbo programs that draw a square, a pentagon, and a spiral, respectively.
What to hand in
‘Turbo.hs’ with working runTurbo.
End of questions.
2