Monday, October 13, 2008

Turtle Graphics Basics

Some weeks ago, I watched Don't fear the Monads, again. Beckman said something like "there nothing about monads that you don't already know" and "after some time, you'd be inventing monads yourself, but you probably wouldn't know that they were monads". Beckman inspired me to start a small (!) project on Turtle Graphics blog posts.

The idea is to write a very small piece of Haskell code in each post, where every post is a Turtle Graphics implementation. Or, not implementation, but rather just a model, so no real graphics. You can see them as small Turtle Graphics APIs, that focus entirerly on the data and not anything about presenting the data.

Now, not every API is an internal DSL, but for these posts I'll try to put on my language sun-glasses..

First we need a definition of a Turtle:
> data Turtle = Turtle {
> x :: Double,
> y :: Double,
> alpha :: Double -- alpha = 0 means East
> }
> deriving (Show)
The first idea (the trivial/naïve implementation) is to define functions with the type signatures Turtle -> Turtle. The functions I have in mind is go, left, right, and rotate, hopefully all self-explanatory. Let's do a type synonym, because it's fun:

> type Command = Turtle -> Turtle

Here are the commands, very basic:
> go, left, right :: Command
> go t = t { x = x t + step * cos (alpha t),
> y = y t + step * sin (alpha t),
> alpha = alpha t }

> left t = t { alpha = alpha t + pi/2 }
> right t = t { alpha = alpha t - pi/2 }

> rotate :: Double -> Command
> rotate v t = t { alpha = alpha t + v }

> step = 1
Note that rotate has a different type. Also note the order of the arguments: we can use currying so that if we give rotate just one argument (an angle), we will get a Command.

Let us just see what the user code looks like:

*Main> let t = Turtle {x = 1, y = 1, alpha = 0}
*Main> t
Turtle {x = 1.0, y = 1.0, alpha = 0.0}

*Main> go t
Turtle {x = 2.0, y = 1.0, alpha = 0.0}

We can combine functions with the operator (.)

*Main> (go . go) t
Turtle {x = 3.0, y = 1.0, alpha = 0.0}

And, of course, we can define new functions in terms of the basic ones:

*Main> let go2 = go . go
*Main> go2 t
Turtle {x = 3.0, y = 1.0, alpha = 0.0}

The presentation is a bit rough, especially for non-zero angles..

*Main> right t
Turtle {x = 1.0, y = 1.0, alpha = -1.5707963267948966}

..but I assume you can calculate from radians to degrees in your head.. ;)

As you might have seen, the ordering of arguments for rotate was important:

*Main> (go . (rotate pi) . go) t
Turtle {x = 1.0, y = 1.0000000000000002, alpha = 3.141592653589793}

If the ordering of arguments were different, the above would not have been possible to write. Instead we would have been forced to write a lambda-expression, which is maybe not the best example of a good user code (if you can avoid it, at least).

Note that we also can remove the definitions of left and right, and replace them with

> left' = rotate (pi/2)
> right' = rotate (-pi/2)

Now, a nice feature would be to let a user give a list of Commands and a Turtle to a function, returning the final position:

> runR :: [Command] -> Turtle -> Turtle
> runR [] t = t
> runR (c:cs) t = runR cs (c t)

Here's where I think it can be useful to know something about functions is general. For example, functions with type a -> a forms a monoid [1,2] together with the operator (.) and identity id. This allows us to write runR in a more readable form (now called run):

> run :: [Command] -> Turtle -> Turtle
> run cs t = (foldr (.) id cs) t

A monoid is a nice thing to be, but what is really the purpose with the run function? Isn't the whole goal with a "Turtle Graphics" that we compute a list of positions, so that we can plot them somewhere? It's no use just to calculate a final position: the picture will become pretty boring eventually.. ;)

What we need is a function that takes a list of commands and a start position, returning a list of positions:

> runHistory :: [Command] -> Turtle -> [Turtle]

We make runHistory a wrapper function around runToList:

> runHistory cs t = runToList cs [t]

> runToList :: [Command] -> [Turtle] -> [Turtle]
> runToList [] ts = ts
> runToList _ [] = []
> runToList (c:cs) (t:ts) = runToList cs ((c t) : t : ts)


Joel pointed out (in the comments) that runHistory could be written as:

> runHistory = flip (scanr ($)) . reverse

It's of course a lot better than my definition(s), from a readable code perspective. I imagine that my version is more performant (since I do not reverse), but as we all know, performance only matters until you notice the problem (as I pointed out in the comments myself). So, I fell into the trap of pre-optimizing.. Oh my, oh my.


Let's try it out:

*Main> runHistory [go,right,rotate pi, go,go] t
[Turtle {x = 2.0, y = 3.0, alpha = 1.5707963267948966},Turtle {x = 2.0, y = 2.0, alpha = 1.5707963267948966},Turtle {x = 2.0, y = 1.0, alpha = 1.5707963267948966},Turtle {x = 2.0, y = 1.0, alpha = -1.5707963267948966},Turtle {x = 2.0, y = 1.0, alpha = 0.0},Turtle {x = 1.0, y = 1.0, alpha = 0.0}]

Hmm, the presentation gets real ugly. Perhaps an implementation of (Show) would be nice, but that's out of scope for this post.

I think there's some smelly code here. We have "bolted on" a history feature on top of the basic commands, so the only knowledge of a history (or log) is in runHistory itself. From a logging perspective, the basic functions do not compose at all! Let me show you what I mean..

Suppose we define a go2 in terms of go (see above). Clearly, we would like go2 to write to the log twice. With the current implementation, this is impossible! There's no way that runHistory can write more than one time to the log, per command. Well, it could be done, but it's not pretty:

*Main> let go2 = [go,go]
(*Main> let prog = [go,go2,go] -- type error)
*Main> let prog = [[go],go2,[go]]
*Main> runHistory (concat prog) t

Even uglier:

*Main> let go3 = [go2,[go]]
(*Main> let prog = [[go],go3,[go]] -- type error)
*Main> let prog = [[[go]],go3,[[go]]]
*Main> runHistory (concat (concat prog)) t

From this, it's obvious that we need to let the basic functions be aware of history/logging. That would be the goal of future posts.

Comment/spoiler: Kenn Knowles has also written a blog post on a Turtle Graphics implementation. Though, the aim of my post(s) is to start out real basic and then evolve the code through several posts. Basically, Kenn's implementation is a "state-over-writer" monad transformer, with a self-implemented difference list as the writer monoid.


Joel said...

Hi, nice post! Will be interesting to follow the progress of the turtle :-)

I was a bit confused by the 'runToList' function. 'runHistory' seemed like it could be written straight forwardly with tail recursion as in:

runHistory cs = reverse . rH cs
rH [] t = [t]
rH (c:cs) t = t : (rH cs) (c t)

or a bit more implicit utilizing the 'scanr' function from Haskell Prelude:

runHistory = flip (scanr ($)) . reverse

Joel said...

My second comment on this post seem to have disapeeard into the void. If it reappers, sorry for double posting/commenting.

Anyhow, I was thinking about if it really is impossible to achieve nicer composibilty while keeping the data types and here is an attempt to solve the composibilty problem by defining a more flexible composition operator (<|>)

This solution requires 'multi-param-type-classes' (or fglasgow-exts).

First, a type class for represeting values that may be turned into lists of commands comes in handy:

class Commands a where
toCommands :: a -> [Command]

instance Commands Command where
toCommands c = [c]

instance Commands [Command] where
toCommands = id

Then a class for representing a polymorphic composition operator is defined:

class Compose a b where
(<|>) :: a -> b -> [Command]

with instances for any type of Commands values.

instance (Commands c1 , Commands c2) => Compose c1 c2 where
c1 <|> c2 = toCommands c1 ++ toCommands c2

Now, diffent both single commands and command lists could be composed using (<|>):

go2 = [go,go]
go3 = go <|> go2
myCmds = left <|> go3 <|> right

Joel said...

At a second thought, multi-param-type-classes is really not required here.

As long as the composable types are limited to the Commands class the operator is offcourse much more simply defined as:

c1 <|> c2 = toCommands c1 ++ toCommands c2

Btw, is it possible to use something like the 'pre' tag when commenting?

Gustaf Nilsson Kotte said...

Cool! I just KNEW there had to be a prelude function for the thing I did, but I couldn't find it. The tail-recursive version is also nicer.

Reversing the list costs performance, but it is worth it (until you notice a problem, there is no problem). "Pre-optimization is the root of all evil!" :)

Regarding the "compose operator", I'm not terribly convinced. Users can still use (.) as composition, thus disconnecting logging. Right? I.e.: go2 = go . go

Thank you so much for the good comments! (I will update this post tomorrow)

Joel said...

I agree on both of your claims regarding reversing :-)

Well, the (.) works but disables logging. But if the problem was to provide a "nicer" composition operator allowing logging then I still claim the (<|>) could be helpful :-)

viagra online said...

I had no idea why this is important what we do studies about the turtles and their development
even seek more government help for this noble cause