Turtle Soup

I've been reading Seymour Papert's  Mindstorms book about Logo; very interesting! I'm just dying to add Turtle Graphics to my little toy language from last post (BTW, a friend suggested I call it "Ape" and I think I will!).

Logo with a twist

What I wanted was essentially Logo but not exactly. The "turtle" starts in the center of the canvas facing up (North). It can be instructed to turn "right" or "left" or to move "forward" or "back". It can also be asked to draw a "line" to its current position.

I didn't want to have some arbitrary distance for movement (turtle steps) or an arbitrary number of degrees for turning. Instead I did something a little strange :-) Everything is based on a unit circle in the center of the canvas. Moving "forward" will traverse the radius. Each move though divides the distance in half. So, for example, moving "forward back back back" will move from the center to the edge of the canvas, then "back" half of that (halfway between the center and the edge), "back" again will move another quarter, then an eighth. The net result is the same as moving forward an eighth of the radius. The same is true for turning "left" and "right". The first turn does a 180 (or a π if you think in radians). The second makes a quarter turn, then an eighth, etc. So something like "right left left" is the same as turning clockwise 45 degrees. The move/turn deltas reset whenever a non-move/turn instruction is executed. Additionally, you can "stop" to reset. Also, you can return to "home" position (center facing up) any time. Sheesh, this is more difficult to explain in English than to just write the code already!

[31 OCT 2009 - I've since decided the above scheme is rediculous! :-)]

30-line Implementation

I didn't want to add new primitives to the language. If you read the last post, you know I quite like having boiled the language down to it's essence with just four primitives. Instead, think of Turtle Graphics as an output format. Rather than just printing a resulting symbol tree to the console, we paint a sequence of "turtle instructions." The AST passed in is not a tree. It's just a single flat list of Symbols. (The code below depends on the Ape implementation from this previous post)

open System.Drawing
open System.Windows.Forms
 
let draw turtle =
  let span = 200.
  let paint turtle (g : Graphics) =
    g.SmoothingMode <- Drawing2D.SmoothingMode.HighQuality
    g.Clear(Color.White)
    let line (x1, y1) (x2, y2) =
      let trans p = float32 (p * span + span)
      g.DrawLine(Pens.Black, trans x1, trans y1, trans x2, trans y2)
    let move (x, y) delta heading =
      let h = heading * 2. * Math.PI
      let dx = delta * sin h
      let dy = delta * cos h
      (x + dx, y + dy)
    let rec paint' turtle p1 p2 head dmove dturn =
      match turtle with
      | Symbol("right") ::t-> paint' t p1 p2 (head - dturn) 1. (dturn/2.)
      | Symbol("left") ::t-> paint' t p1 p2 (head + dturn) 1. (dturn/2.)
      | Symbol("forward")::t-> paint' t p1 (move p2 +dmove head) head (dmove/2.) 0.5
      | Symbol("back") ::t-> paint' t p1 (move p2 -dmove head) head (dmove/2.) 0.5
      | Symbol("line") ::t-> line p1 p2; paint' t p2 p2 head 1. 0.5
      | Symbol("stop") ::t-> paint' t p1 p2 head 1. 0.5
      | Symbol("home") ::t-> paint' t (0., 0.) (0., 0.) 0.5 1. 0.5
      | [] -> ()
      | invalid -> failwith "Invalid graphics output!"
    paint' (List.rev turtle) (0., 0.) (0., 0.) 0.5 1. 0.5
  let size = int (span * 2.)
  let form = new Form(Text = "Turtle Graphics",
                      ClientSize = new Size(size, size),
                      Visible = true)
  form.Paint.Add(fun a -> paint turtle a.Graphics)
  Application.Run(form)

Take the Turtle for a Spin

We can now execute simple Ape programs and feed the output to this little rendering engine. For example:

forward back line right left left forward back line

Cool! That's not even really an Ape program; just a list of symbols being pushed through as literals. But we can refactor a bit into [forward back line] foo let foo right left left foo which does the same thing.

Prelude

Before we really get started, let's build up a little bit of "library" support. We have yet to add numbers to Ape, but we'll need a way of at least repeating operations some number of times:

[f let f f] 2 let
[f let f f f] 3 let
[f let f f f f] 4 let
...
[f let f f f f f f f f f f f f f f f] 15 let
[f let f f f f f f f f f f f f f f f f] 16 let

Silly but it works! Almost like a "tally mark" counting system, each of these will take a quoted expression and apply it n times.

I didn't want to bake in arbitrary movement and turning increments, but it is convenient to at least define some (but within Ape, not within the engine):

[forward back 4 stop] F let
[right left 4 stop] R let
[left right 4 stop] L let

Then from these define some common angles:

[[R] 8] R90 let
[[R] 4] R45 let
[[L] 8] L90 let
[[L] 4] L45 let

Interestingly, a series of "left right left right ..." will converge at 60° degrees, so an approximation:

[[right left] 16] R60 let
[[left right] 16] L60 let

And we can compose these to get other angles:

[R90 L60] R30 let
[L90 R60] L30 let

Shape Up!

Now that we have a bit of a foundation, it starts getting fun!

[[[F] 8 line R90] 4] square let
[[[F] 8 line R60] 3] triangle let
[[F line R] 8] arc let
[[arc] 4] circle let

We can compose these:

[R90 square L90 L30 triangle] house let
house

We can start doing some powerful things; define procedures taking shapes and do things with them. Here, we draw a shape 16 times while rotating a bit each time:

[shape let [shape [R] 2] 16] pattern let

The results are very cool:

[square] pattern
[triangle] pattern
[circle] pattern

It's just so fun to play with!

[[arc R90] 2] peddle let
[[peddle R90] 4] flower let
[F] 6 [flower R45] 2 R90 [F] 12 line R90 peddle L90 [F] 6 line

Now remember that this is just 30 lines of code for the graphics rendering engine, 50 lines for the Ape interpreter, and another 30 lines for the lexer and parser. Pretty darn cool!