Thursday, October 30, 2008

Turtle Graphics :: The big refactoring

Last time on "Turtle Graphics", we ended up having the type Turtle -> [Turtle] on functions. The combine function had the type [Turtle] -> (Turtle -> [Turtle]) - Turtle. Let's have some "fun"!

First, we add a helpful parameter to the turtle - penIsDown, i.e., the turtle is writing.
data Turtle = Turtle 
x :: Double,
y :: Double,
alpha :: Double, -- alpha = 0 means East
penIsDown :: Bool
}
deriving (Show)

We then add two useful functions for pen modification:
penDown t = let t' = t {penIsDown = True} in Logged {value = t', logs = [t']} 

penUp t = let t' = t {penIsDown = False} in Logged {value = t', logs = [t']}

Second, we assume that it would be useful to split the functionality of returning a value and log, pretty much following separation of concerns. We could do this in a tuple, but I prefer having names on things:
data Logged l = Logged {
value :: l,
logs :: [l] } deriving (Show)

This has some implications on our code. All the "core" functions must now return both a turtle value and a singleton log. Oh, and by the way, the Command type changed as well.

type Command = Turtle -> Logged Turtle

go, left, right, penDown, penUp :: Command
go t = let t' = t {x = x t + step * cos (alpha t),
y = y t + step * sin (alpha t)

}
in Logged {value = t', logs = [t']}

left = rotate (pi/2)

right = rotate (-pi/2)

penDown t = let t' = t {penIsDown = True} in Logged {value = t', logs = [t']}
penUp t = let t' = t {penIsDown = False} in Logged {value = t', logs = [t']}

We must also change the function for combining functions:
(|>|) :: Logged Turtle -> Command -> Logged Turtle 

logged |>| f = let logged' = f (value logged)

in Logged {value = value logged',
logs = logs logged' ++ logs logged}

As you see, there's a lot of duplicate code. Let's do an ExtractMethod (sort of):

logThis val = Logged {value = val, logs = [val]}

go, penDown, penUp :: Command
go t = logThis $ t {x = x t + step * cos (alpha t),
y = y t + step * sin (alpha t)
}
penDown t = logThis $ t {penIsDown = True}

penUp t = logThis $ t {penIsDown = False}

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

Still, we could be more generic in our logging type. That is, there is still a restriction on that the value returned and the log have the same type: the log is a list of the same type as the value has. We try to relax this restriction:

data Logged v l = Logged {
value :: v,
logs :: l
}

deriving (Show)

Maybe we did too much, logs isn't a list anymore. However, if it's really necessary, we'll find out through type inference. It's not obvious that we really need a list, just something we can append "stuff" to. Anyway, we get some compiler errors now:

`Logged Turtle' is not applied to enough type arguments Expected kind `?', but `Logged Turtle' has kind `k -> *' In the type synonym declaration for `Command'

We "fix" this by removing the Command type synonym and all references to it. I have a feeling that we'll need to fiddle some more with the types, so right now they're only in the way. If the types really are needed, we will find out (by a compiler error)! Though, it could be interesting to see what the type of e.g., "go" is:

*Main> :t go
go :: Turtle -> Logged Turtle [Turtle]

Ah, just what I expected, but was too lazy too write. ;) Let's check the combining function:

*Main> :t (|>|) 
(|>|) :: Logged v [a] -> (v -> Logged v1 [a]) -> Logged v1 [a]

Hmm, this is rather weird! Before, the function was strongly bound to the Turtle type, which doesn't seem to be the case anymore. Moreover, we see that the input value type (v) doesn't need to be the same as the output value type (v1). How cool is that!?! It would be hard for me to look at the function and calculate the type myself, but Haskell just inferred the most generic type it could find. Coolness!

As always, a design pattern can be hard to spot, especially if you haven't spotted it before. Here's how Gregg Irwin puts it (from an Øredev presentation by Jimmy Nilsson):
1. You use it without being aware that you’re using it
2. You hear about it, read up on it, and tinker a bit
3. You learn more and start using it explicitly, if naively
4. You get the fire and evangelize (optional)
5. Something ”clicks”
6. You learn more and apply it ”less naively”and more implicitly
7. Time passes and you see flaws
8. You question the concept (often because you misapplied it)
9. You either forget about it or add knowledge and experience
(Repeat steps 5-9 if necessary)
10. You use it without being aware that you are using it
Essentially, our Logger type is a monad. Or, actually, the type of |>| resembles >>=, which is the associative function that composes a particular monad. Since monads are important in Haskell, some syntactic sugar (the do-notation) has been added to make it easier to work with them.

Let's try to instantiate the monad class:

instance Monad (Logged a b) where

We get a compiler error:

Kind mis-match
Expected kind `* -> *', but `Logged a b' has kind `*'
In the instance declaration for `Monad (Logged a b)'

We try to remove both type parameters:

instance Monad (Logged) where

..but still an error (yet, another one)

`Logged' is not applied to enough type arguments
Expected kind `* -> *', but `Logged' has kind `* -> * -> *'
In the instance declaration for `Monad (Logged)'

As you might see, we need to bind one of the types, whereas the other one needs to be "free". This puts us in a dilemma, since we know that we have both a type "v" and "v1". Thus, the type of the log must be bound (or, at least given a parametrized name):
data Logged l v = Logged {  --notice the different order      
value :: v,
logs :: l
}
deriving (Show)

instance Monad (Logged l) where

So Logged is missing out one type parameter. It's kind of a function over types, that takes a type and returns another type - just as the error message above implied. Though, we get an error again when we try to implement bind:

instance Monad (Logged l) where  l >>= f = l |>| f

Couldn't match expected type `[a]' against inferred type `l' (a rigid variable)
`l' is bound by the instance declaration at writer5.hs:46:0

Expected type: Logged [a] v

Inferred type: Logged l a1

In the first argument of `(|>|)', namely `l'

In the expression: l |>| f

Now, we actually need to say that the log is a list. Maybe we can remove this requirement in a later blog post, but right now we go with the compiler.

data Logged l v = Logged {
value :: v,
logs :: [l]
}

deriving (Show)

Hey, it works! Or, at least it compiles. But that tends to be synonyms in Haskell ;) We specify "return":

instance Monad (Logged l)
where
l >>= f = l |>| f
return val = Logged {value = val, logs = []}

Notice that we can still use |>| as usual:

*Main> start |>| go |>| go  
Logged {value = Turtle {x = 2.0, y = 0.0, alpha = 0.0, penIsDown = True},
logs = [Turtle {x = 2.0, y = 0.0, alpha = 0.0, penIsDown = True},
Turtle {x = 1.0, y = 0.0, alpha = 0.0, penIsDown = True},
Turtle {x = 0.0, y = 0.0, alpha = 0.0, penIsDown = True}]}

So, why all this trouble? Well, it wasn't that hard! Essentially, all we did was to make the logging a bit more separated and generic. Then we adjusted the types a bit to make them align with Haskell's monad class. The big win is that our Logger is now reusable if we want to log something else than turtles in the future. So, by adjusting towards a common pattern, we gained both syntactic sugar and reusability.

Of course, there are some ways to improve. I'll perhaps cover this in future posts. Oh, and by the way, our Logger monad is actually the Writer monad. Just thought you should know that.. ;)

Conclusion: Brian Beckman was right, we've invented monads by ourselves, maybe without thinking about it. Or?

Note: Since I'm not a master in category theory, I'm not sure if Logger actually was a "real" monad (strictly speaking), before we changed the order of the type parameters and removed a type parameter in the monad instantiation, making it have the right kind. Any ideas?

Tuesday, October 28, 2008

My first F#, Binary Chop

Yesterday, I really felt like trying out F#. To get some inspiration, I visited PragProgs katas, and chose Kata Two -- Karate Chop. Or, actually, I just implemented a "functional" solution. I tried to make an imperative pointer-based solution (which I might post later, when I have resolved a strange bug). Anyway, I had never coded F# before, so there might be a few places where I could have e.g. chosen a library function instead of implementing it myself. If you have any suggestions or general comments, please post them!

By the way, is there any way to program in literate F#?
#light
First, a few helper functions for triples.
let fst3 (a,b,c) = a
let snd3 (a,b,c) = b
let trd3 (a,b,c) = c
Define the middle index, for simplicity return 0 if list is empty.
let middleIndex xs = if List.is_empty xs then 0 else (List.length xs - 1)/2
Define a function that returns the middle element of a list, and two functions that returns the first/last remaining halfs. Note that there might not be a middle element, so we use the option type.
let firstHalf xs = Seq.take (middleIndex xs) xs

let middleElem xs =
match (xs) with
| [] -> None
| xs -> Some (xs.Item (middleIndex xs))

let lastHalf xs =
match xs with
| [] -> Seq.empty
| xs2 -> Seq.skip (middleIndex xs + 1) xs2
Let us group the functions in a convenient triple.
let splitInHalf xs = (firstHalf xs, middleElem xs, lastHalf xs)
Now, define a recursive function that 1) splits the list in three parts 2) reuse some definitions 3) return "None" if middle is empty 4) otherwise we can test the middle for equality, if equal then return the current index 5) if not equal, choose appropriate half and recurse.
let rec exists x xs i = 
let triple = splitInHalf xs in //1
let maybeMiddle = snd3 triple //2
let firstPart = Seq.to_list (fst3 triple)
let lastPart = Seq.to_list (trd3 triple)
if Option.is_none maybeMiddle then None //3
else let middle = Option.get maybeMiddle in //4
if x.Equals middle then Some(i) //5
elif middle > x then exists x firstPart (middleIndex firstPart)
else exists x lastPart ((i+1) + middleIndex lastPart)
This is the function a user would call.
let public ex x xs = exists x xs (middleIndex xs)
Some tests, just to check, plus a helper function for equality over options.
//Tests

let eq x y = if Option.is_none x then Option.is_none y else x.Equals y

let res = [
ex 3 [];
ex 3 [1];
ex 1 [1];

ex 1 [1;3;5];
ex 3 [1;3;5];
ex 5 [1;3;5];
ex 0 [1;3;5];
ex 2 [1;3;5];
ex 4 [1;3;5];
ex 6 [1;3;5];

ex 1 [1;3;5;7];
ex 3 [1;3;5;7];
ex 5 [1;3;5;7];
ex 7 [1;3;5;7];
ex 0 [1;3;5;7];
ex 2 [1;3;5;7];
ex 4 [1;3;5;7];
ex 6 [1;3;5;7];
ex 8 [1;3;5;7];

]

let answers = [None; None; Some 0;
Some 0; Some 1; Some 2; None; None; None; None;
Some 0; Some 1; Some 2; Some 3; None; None; None; None; None
]

let asserts = Seq.for_all2 eq res answers
asserts
Now, I must say that I had a real good time developing this! Ok, some minor things didn't went as smoothly as I'd hope for, but it was actually the first time that I tried F#. I've never had such a good experience with a language the first day of use.

I will definitly be posting more F# posts in the future!

Cheers

Wednesday, October 22, 2008

Category Theory

Guess what landed on my hallway floor today: "Basic Category Theory for Computer Scientists". Thank you Mr Mailman!


There's a lot of "greek" in there! Hopefully, I'll decipher it (and understand it, of course).

Tuesday, October 21, 2008

CoachTV

In the middle of August, David Heinemeier Hansson twittered this:
Lars Pind is doing video coaching: http://coachtvblog.com/?p=3 -- good thoughts on probability and significance. 4:59 PM Aug 16th
Since that date, I have been following Lars Pind's fantastic video blog, CoachTV.

I think it's hard to analyze yourself from the outside. Reminds me of a quote of Richard Feynman, the 1965 Nobel prize winner in physics:
"The first principle is that you must not fool yourself—and you are the easiest person to fool."
It's hard to summarize what Pind's message is, so I rather not try. Instead, I want to re-post a comment that I did on one of his episodes. What triggered me to post the comment was that Pind talked about eating and that the next time the viewer ate something, he/she should try to really look at the food, feel the texture, slowly swallow, feel the taste, etc, etc. You get the picture? Obviously, the overall "taste experience" is not only about always eating good food, but rather that it is up to you, if you bother to enjoy it or not. Made me think about music:
Lars, you said that when we eat or drink something, we should try to feel the taste and texture more. That reminded me of the composer John Cage, who had the same opinion about sound. His most famous piece is “4′33″, which is 4 minutes and 33 seconds of silence, written for piano. In summary, Cage had the opinion that there’s music everywhere, but it’s up to us to listen to it. So, even rush hour traffic can be music. Or when it’s so quiet that you can hear our own blood flow and pulse.

It’s up to ourselves to broaden our senses and perspectives, so that we can enjoy the music in our everyday life, also when sound is not involved per se.
Could it be that the same reasoning goes for your other sensations and feelings as well? If not, why?

Note: I actually wrote this post before watching episode #26 of CoachTV, where Lars asks the viewers to "tell our friends" about his show. Just thought you should know that.. :)

Monday, October 20, 2008

Podcast: Herding Code

There is a fairly new (May 2008) podcast that I listened to a lot lately (including their old episodes): Herding Code. These episodes are particularly nice:
Enjoy :)

Sunday, October 19, 2008

TDD, reflection and the PropertiesEqual extension method

In my last post I wrote about the extension method ForEach, which is a very simple but useful method, at least when it comes to readability.

In this post I'll try to explain another extension method, which I'll call PropertiesEqual. It's purpose is to extend the object class with a method to compare the properties of two objects:

public static bool PropertiesEqual<T>(this T obj1, T obj2)
{
return true if all properties of obj1 equals all properties of obj2
}

You probably know of the object.Equals method, which per default compares the memory addresses of two objects. That is, two objects are equal only if they are exactly the same object. If you really want to compare the content of two objects, you need to override this function in your class and manually compare them.

When I designed this function, I started with two simple test cases:
1. If two objects of the same class have the same public properties, yield true
2. If two objects of the same class have different public properties, yield false

Translated to code, this becomes:

class TestClass
{
public int A { get; set; }
public int B { get; set; }
}
[TestMethod()]
public void PropertiesEqualTest()
{
Assert.IsTrue(new Test { A = 1, B = 1 }.PropertiesEqual(new Test { A = 1, B = 1 }));
Assert.IsFalse(new Test { A = 1, B = 1 }.PropertiesEqual(new Test { A = 1, B = 0 }));
}

The implementation is very straight forward:

public static bool PropertiesEqual<T>(this T obj1, T obj2)
{
return typeof(T).GetProperties().All(property =>
{
var prop1 = property.GetValue(obj1, null);
var prop2 = property.GetValue(obj2, null);
return prop1.EqualsTo(prop2);
});
}

typeof(T).GetProperties() will return all public properties of T, and property.GetValue(obj, null) will return the value of a given property. The All extension method returns true only if all elements of the sequence satisfy the given condition, i.e. all properties are equal.

The test cases will pass fine, and we now have a simple way of comparing properties of two objects! In the next post I'll try to describe how to extend the method with support for recursive properties (compare properties of a property), and in the one after that I'll write about how to implement an IEqualityComparer based on this method.

EDIT: Note, these series aren't much of the type "here is a revolutionary new technique", but more of "here is how I would write the code for this". My focus is to get you to understand how I think when I design methods, not to tell you that "this is the way"!

Code Kata : Monopoly

Yesterday evening, me and two other friends arranged a highly spontaneus and inofficial code kata, at my friend's apartment. The task was to develop a Monopoly game, using TDD. It was sort of an experiment as well, we wanted to see how TDD could help us discovering design, rather than inventing it.

We started by talking about the domain, listing some words that we thought were important to the game. Then we made a small domain model diagram, just with boxes and lines (the relations had no directions or multiplicities). This was fun! It felt like we were back in school again.. :)

After that, we started to make some user stories, each on a small piece of paper. Here are the stories we came up with (in prioritized order):
  • A player walks the number of steps the dices show.
  • In the beginning of the game, the ordering of player moves is determined.
  • Players act in the predetermined order (was later removed, redundant with previous).
  • A player hits or passes "Go" and earn 4000.
  • A player buys the street he/she is on.
Now, we could start to implement the game! :) But, as we realized, the first story was very hard, since we had no code to start with. Actually, starting to write the first test was probably the hardest. I think we made the conclusion that the first test we tried to write was to big, so we divided the test into smaller parts, and BOOM, it went much more smoother. Also, we tried to follow YAGNI, as much as possible.

An interesting detail is that we kind of get stuck on the "the dices show" part of the first story. It's obviously something that has to do with random number(s), but how should we test that? I.e., we thought that only players would need dices, but if a player use the Random() system method, then we must capture it in a public state in order to know if the player actually walked the number of steps that the dices show. Not nice! We felt the urge to really talk about this, to see if logical arguments could lead us into a good, and hopefully pragmatic, solution to this problem. We ended up with dependency injecting an "IDice" - something that could give us a random number between two and twelwe, and mocking the IDice in the test. Nice! Now we could manipulate the player through fake dices, without having code smells all over the place!

Though, in retrospective, it would have been nice with an expert on TDD in the room. In the end, you would like yourself (or the group) to ask good questions and answer them logically, but without experience, asking the right questions in the right time is hard. A teacher behind the back, mentoring and supporting would be nice to have. Reminds me a little about Polya, "How to Solve It". Though, doing the excercise without a "master" was probably a good idea, in some way: it made us (more) convinced about what we were doing, and if we weren't convinced, we had to talk about it.

We did the excercise for about six hours, but we had dinner and wine during that time as well, and perhaps we weren't that effective all the time :) Anyway, we implemented all the stories, except the last one (a half-baked story).

Thank you for a very nice evening!

Thursday, October 16, 2008

Turtle Graphics :: Changing Interface

Recalling, my first idea of the Turtle Graphics posts was to see if it was likely that a beginner in functional programming would have invented monads by himself/herself.

Let's change the interface a bit, such that a command is a function from log to log.

(I will reuse definitions from the original post, i.e. turtle definition and step)

> type Command = [Turtle] -> [Turtle]

> start = Turtle { x=0, y=0, alpha=0 }

> go, left, right :: Command
> go [] = []
> go (t:ts) = t {x = x t + step * cos (alpha t),
>   y = y t + step * sin (alpha t),

>   alpha = alpha t} : t : ts

> rotate :: Double -> Command

> rotate v [] = []

> rotate v (t:ts) = t {alpha = alpha t + v} : t : ts

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

> execute :: [Command] -> Turtle -> [Turtle]
> execute cs l = (foldr (.) id cs) [l]

Basically, the primitive commands have to work on the whole list and consider the case of an empty list, whereas commands defined in terms of other commands don't have that restriction. It's also easy to define new commands:

> go3 = go . go . go

But the primitive commands don't look good at all! But, it's an easy fix..

The problem is of course with the type of Command. A primitive command only cares about the first turtle in the list (the newest one), so why should a command take a whole list as parameter?

> type Command = Turtle -> [Turtle]


> go, left, right :: Command

> go t = return $ t {x = x t + step * cos (alpha t),

>
  y = y t + step * sin (alpha t),
>   alpha = alpha t}

> rotate :: Double -> Command

> rotate v t = return $ t {alpha = alpha t + v}

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


> -- [Turtle] -> (Turtle -> [Turtle]) -> [Turtle]

> |>| :: [Turtle] -> Command -> [Turtle]
> [] |>| f = []

> (l:ls) |>| f = (f l) ++ (l:ls)


So, for go and rotate, we use a little trick, using return instead of putting the result in a list. What is much more interesting is that we now have a little asymmetry in the type of a command. It is not possible anylonger to use (.) for combining commands, so we define |>| to do that for us.

We must use a little lambda to define new commands..

> go3 = \t -> t |>| go |>| go |>| go

..but that shouldn't be too much of a problem.

We're not done yet, but at least we took care about our little logging problem we had the previous post.

The ForEach extension method (C#)

Everyone knows about the foreach keyword, but have you ever noticed there are no equivalent extension method for IEnumerables? I.e. execute "this action" on each element. Perhaps the most simple extension method of them all, which is the reason I'll share it with you :)

public static class MyExtensionMethods
{
public static void ForEach<T>(this IEnumerable<T> list, Action<T> action)
{
foreach(var item in list) action(item);
}
}

For you who aren't familiar with extension methods, what it really says is that, ForEach is a member method of IEnumerable<T>, and can be called by simply writing
myList.ForEach(myAction)

For example, to output each item of a list to the console, you could write:
myList.ForEach(x => Console.Write(x));

instead of
foreach(var x in in myList) Console.Write(x);

In this case you might not gain so much in terms of code size, but I think it makes the code more readable. You are reading text from left to right, so it makes sense having the for each statement to the right, right? :)
myList.WhereThis().SelectThat().DoThis();

(There is probably some kind of cool name for this pattern, like "The opposite of law of demeter"... Gustaf probably has more knowledge in this!)

Here is a more complex example of a combination of extension methods:
myList.Where(x => x.IsValid()).Select(x => x.ComputeValue()).Where(x => x > 0).ForEach(x => Console.Write(x));

Where and Select are also extension methods of IEnumerable. Without these you would have to write:

foreach(var x in myList)
{
if (x.IsValid())
{
var value = x.ComputeValue();
if (value > 0) Console.Write(value);
}
}

8 lines instead of 1! Impressed? :)

So, extension methods! Learn them, use them, and write your own!

Wednesday, October 15, 2008

Some thoughts on Turtle Graphics Basics

In the comments of last turtle post, Joel pointed out a way to get commands composable. I didn't quite get it to work, probably because of that Command is a type synonym and not a concrete type. The first time I saw the proposed solution, to combine commands with <|>, I got a little afraid. I'll explain why..

<Update>

Joel pointed out (in a mail) that Haskell98 doesn't permit instances of type synonyms or lists of types. If the flag "fglasgow-exts" is used, then the problem is solved.

</Update>

The biggest reason I got afraid was that it is still up to the consumer of the code to combine commands in a "good" way, i.e., to log intermediate positions. But, It would be perfectly legal to combine commands with (.) instead of (<|>), making the API quite risky. I now think a bit different..

It would be possible to kind of wrap the commands into a data structure of their own (as the Command pattern in OO):

> data C = C { unC :: Command }

In some way, this is very type-safe, since it will be cumbersome to un-wrap the commands to combine them in a "bad" way..

> go2 = C { (unC go) . (unC go) }

..thus, users are forced to use our special operator for combining commands. But there something I don't like about this. We're kind of forcing the users into a datastructure, just to restrict them. I think we loose a lot of nice functions (i.e. from the prelude) this way. Of course, we could define functions that makes it easier for the user, but the user still has to learn those functions. What I'm trying to say is that it sometimes is bad to invent a whole new API style from scratch, when for example a monadic style API has the benefit that more people know about it and that we can "piggyback" on all the tutorials on monads. Or maybe it's just me that is too focused on monads at the moment. ;)

I guess this could be a nice discussion? What do you think?

Right now, my biggest reason to be afraid of Joels solution is that it uses type classes, which is a very exotic feature, compared to other functional languages. There are obviously nice, but it would be hard to see how a "nice" Turtle Graphics API could be ported to i.e. F#, if we based the API on type classes.

Next: Changing interface on primitive commands

Tuesday, October 14, 2008

Joining Dotway!

Last Friday I joined Dotway! Dotway is a .NET consulting company and was founded in Malmö, but I will be working in the Gothenburg office.

Dotway is a Microsoft Gold partner (achieved through competencies) and offers services such as software development, design support, and training/mentoring. Dotway also practices agile and TDD, and "Dotway consultants are Certified ScrumMasters".

I will start working in the beginning of November. Very exciting!

Some links:
Dotway
Mikael Freidlitz
Johan Normén
Magnus Mårtensson
Øredev (a conference and a sister company)

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)

<Update>

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.

</Update>

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.

Wednesday, October 8, 2008

Better DI

I was watching "InfoQ: Mock Roles Not Object States" with Nat Pryce and Steve Freeman yesterday. I had read the paper previous to watching the video, and I pretty much expected the same content but in a different form. Boy was I wrong..

In particular, they talked a few minutes on an argument against Dependency Injection (DI), namely that the constructor gets lots and lots of arguments. I used DI the first time a couple of weeks ago, so I'm pretty new to it, and I wasn't sure I was doing exactly the right thing. And, yes, the constructors at some places became huge.

What the InfoQ presentation thought me was that not all interfaces a class use are dependencies per se. Classes can for example be equipped with default parts or policies, that can be changed after creation. The important thing is that the instance will work anyway, which is not the case if an instance is missing out a dependency.

This nice picture (screenshot from their slides) made it click for me:



Big thanks to Johan Normén who mentioned the paper on the SweNug meeting two weeks ago!