ProtoTurtle - The tale of the bleeding turtle

2010-04-28 20:11:01

This is the small tale of a turtle living on the bleeding edge. I'm not the first guy to talk about Protocols in Clojure, but I certainly wont be the last either, here we go...




Preface

Everybody who's over the age of 25 has probably seen 1 or 2 turtle graphics implementations in his day - this was what most of us grew up with before penumbra came along. In this small post I'll show one way of doing some simple turtle graphics, with a surprising result.


Old School

So to get the ball rolling I'll show you how we would usually make the little guy:

(def turtle-map {:x 50 :y 50 :dir 0})

Thats an ordinary hash-map, nothing fancy about it. The turtle carries around a position on the board as well as a direction (degrees). To work the map we would then make up a few helper functions like move/turn/run etc. But to make sure I got it just right in the first take I consulted with Chris Houser, co-author of this book, and asked him what we had to say about a protocol wielding turtle.


New School

In the olden days we used multimethods for any kind of dispatching and those truely were the good ol' days. But because of multimethods lack of speed, Rich has recently implement protocols. They allow us to program to abstractions which provide a type of polymorphism, but this time with a higher potential for speed, thus paving the way for clojure-in-clojure. To get a good grip on the motivation behind protocols and the implementation I highly recommend that you view: this video. Its 27 minutes long and Stuart Halloway does a fantastic job of explaining the basics!

For the turtle, life is simpler: First we define the Turtle itself:

user> (defrecord Turtle [x y dir canvas panel])
user.Turtle
user> (Turtle. 5 5 0 nil nil)
#:user.Turtle{:x 5, :y 5, :dir 0, :canvas nil, :panel nil}

As you can see defrecord makes a class in your current namespace called Turtle. I can construct an instance of this Turtle in the exact same manner as I would a regular Java Class. In case you're wondering about the extra 2 params, thats just for drawing the trail and updating the window. Second order of business is to define a protocol which acts as an interface to this Turtle, exposing methods and fields but not handling any implementation code:

(defprotocol PTurtle
  (move [this dist])
  (turn [this deg]))

That simply defines an interface, which provides 2 methods, both taking a mandatory first argument 'this' and then whatever we like. The wonderful thing about protocols is that I can now extend that protocol to handle any type of data I want, which uses those 2 method-names. If I wanted to challenge myself, I'd implement something like the Mars-Rover which moves, then signals back home where its at now etc, but since I already titled this blogpost ProtoTurtle, lets stick with that:

(extend-protocol PTurtle Turtle
        (move [{:keys [x y dir canvas panel]} dist]
              (let [dx (+ x (* dist (Math/cos (Math/toRadians dir))))
                    dy (+ y (* dist (Math/sin (Math/toRadians dir))))]
                (.drawLine canvas x y dx dy)
                (.repaint panel)
                (Turtle. dx dy dir canvas panel)))
        (turn [{:keys [x y dir canvas panel]} deg]
              (Turtle. x y (+ dir deg) canvas panel)))

I'm extending the protocol PTurtle, to handle the case where it gets passed a 'Turtle' and I'm providing the implementation of move and turn. Neither of them should have any surprises if you've been following this blog for a while. What happend to the mandatory 'this' first argument you ask? Its still there, but its destructured in place into its keys - this isn't as fast as (:key map), but its more concise and you get the point anyway.


Turtle-Motion

So now that we have our shiny new turtle, lets see how it works:

user> (def turtle (Turtle. 5 5 90 nil nil))
#'user/turtle
user> (move turtle 2)
#:user.Turtle{:x 5.0, :y 7.0, :dir 90, :canvas nil, :panel nil}

So just as you would expect: I start the turtle off at a 90 degree angle (ie. looking upwards) and then I move it 2 units in its current direction, changing y from 5 to 7. But where we differ substantially from the OO mindset, is in the fact that good ol' Turtle is still the same:

user> turtle
#:user.Turtle{:x 5, :y 5, :dir 90, :canvas nil, :panel nil}

He's still in (5,5) looking upwards because he's immutable and always returning new instances of himself. That means if we want to do some fancy dance moves, it'll look something like:

(-> turtle
    (move 30)  (turn -90)
    (move 10)  (turn -90)
    (move 20)  (turn  90)
    (move 10)  (turn  90)
    (move 20)  (turn -90))

But as any other Lisper I'm not too fond of writing move/turn constantly, so we need a way of abstracting that away. It would be tempting to write a macro, which you just feed pairs of [steps angles] and then it expands into the code you see above:

(defmacro turtle-motion [turtle reps & motions]
  `(-> ~turtle
       ~@(interleave
          (for [step  (map first motions)] `(move  ~step))
          (for [angle (map last  motions)] `(turn  ~angle)))))

user> (macroexpand-1 '(turtle-motion "turtle" 2 [5 6] [7 8] [9 0]))
(-> "turtle"
   (move 5) (turn 6)
   (move 7) (turn 8)
   (move 9) (turn 0))

But while that works, it's not well suited for iterative patterns where you want to keep working on the latest coordinate, so a way to accumulate the coordinates could be:

(defmacro turtle-motion [turtle reps & motions]
  (reduce (fn [turtle _]
            `(-> ~turtle
                 ~@(interleave
                    (for [step  (map first motions)] `(move  ~step))
                    (for [angle (map last  motions)] `(turn  ~angle)))))
          turtle (range reps)))

But while that works, we must remember that the first rule of macros is: Dont write macros. So after chatting a little with my good friend Christophe Grand, he proposed an iterative version, which I mangled into:

(defn turtle-motion [turtle reps motions]
  (-> (iterate #(reduce (fn [turtle [step angle]]
                          (-> turtle (move step) (turn angle))) % motions)
               turtle)
       (nth reps)))

As always Christophe was cheering for a full-blown Turtle DSL with Monads and all the trimmings, but if he wants that he will have to write it himself :) The above works fine, creating an infinite stream of patterns and then returning the nth-reps item of that stream.

Test Drive

So now that our ProtoTurtle is all fired up and ready to go, try some simple patterns:

(turtle-motion turtle 1 (for [i (range 120)] [i 45]))

Which then becomes something like the Dharma logo

Simple Turtle

Or try something like:

(turtle-motion turtle 1 (for [i (range 1 w 5)] [(- w i) -90]))

Which then just becomes a little bit weird:

Weird Turtle

Oh and then there's the iterative patterns. He's a formula I saw somewhere on the interweb [[90 -a] [30 -a] [60 a] [30 a] [60 -a]], which when you run all the angles (a) from 1 to 180 looks like this:

Turtle Animation

Now please don't think that I'm in any way endorsing Nazism or anything remotely similar, I just found it interesting to see 2 well known symbols emerge from that simple formula.

 


Conclusion

So protocols have landed and they seem extremely cool while filling a much needed gap in Clojure-land. If you can think of a fun use-case for extending the above Turtle, please send it my way :)

If you're exploring Clojure for fun I hope you'll poke around some more on my blog, there should be something for new-comers as well as experts. On the other hand, if you're a professional looking to improve your game - You should really check out: Conj Labs

Code is here: link (clone it, run 'lein deps' to get bleeding edge jars)

Thomas Wagner
2010-04-28 23:30:42
Hi Lau, thank you for your always enlightening, nice and well thought articles. You are one of the clojure evangelists, infecting imperative programmers and bringing functional programming to the masses and the enterprise software engineering. Your blog entries are every time a "Joy of Clojure"! Mange take.
Dmitri
2010-04-29 00:37:33
As a bonus you could add :gen-class and change the main to


(defn -main [& args]
  (let [[w h] (map #(Integer/parseInt %) args)


and then it can be made into an uberjar :)
Lau
2010-04-29 08:05:46
Thomas, thanks a lot for your huge encouragement!

@Dmitri: Good tip :)
steve
2010-04-29 20:57:33
Very nice, been years since played around with turtle. Made me have a play again, thank you
Siddhartha
2010-05-05 19:27:25
Thanks for posting this, Lau. This blog post has helped me understand Protocols better than any other blog post or video I've seen.