Logo, Fractals, and Recursion; Programming, and Removing Repetition

Monday 29 December 2008 at 23:42

Last summer while volunteering for OWL I spent several weeks working with a fifth grader we'll call Sam who'd already blown through all of OWL's exercises. Logo is a dialect of lisp and I was particularly interested in teaching Sam some different ways to use lists and functions. I searched the net a bit hoping to find something short and interesting, but with some repetition in its implementation that would help me teach how to remove repetition.

When learning literacy, one begins with reading before writing. Then the two skills grow together, one complementing the other. Working with someone else's code was an important dimension of this lesson.

I found an example logo program in the Dictionary of Programming Languages which turned out to be even better than I expected. I've copied the code from that example below making minor changes to run it in MicroWorlds Logo. In addition to all of my own criteria, this example introduces recursion and fractals.

; Recursive procedure to line, fractalized
to DrawFractalLine :level :length
  ifelse :level < 1 [
    forward :length] [
    DrawFractalLine (sum -1 :level) (quotient :length 3.00)
    left 60
    DrawFractalLine (sum -1 :level) (quotient :length 3.00)
    right 120 
    DrawFractalLine (sum -1 :level) (quotient :length 3.00)
    left 60
    DrawFractalLine (sum -1 :level) (quotient :length 3.00)
  ]
end

; procedure to clear screen and position turtle
to SetupTurtle
  cg setpensize 1 setpos [-160 -10] right 60 clean pd
end

; setup turtle then draw Koch's snowflake(5)
SetupTurtle
repeat 3 [DrawFractalLine 5 330 right 120]

Having seen the above, we typed in the following:

cg pu setpos [-160 250] right 90 pd
DrawFractalLine 0 330
pu setpos [-160 150] pd
DrawFractalLine 1 330
pu setpos [-160 50] pd
DrawFractalLine 2 330

Sam pretty quickly understood that we can compare level=0 with level=1 to understand the basic transformation that happens at each additional level of recursion. At each level we divide the previous level's line segments into three pieces and replace the middle one with two sides of an equilateral triangle.

pu setpos [-160 -50] pd
DrawFractalLine 3 330
pu setpos [-160 -150] pd
DrawFractalLine 4 330
pu setpos [-160 -250] pd
DrawFractalLine 5 330

My first surprise was how quickly Sam began developing an intuitive grasp of recursion. Watching the turtle draw each shape in real-time helped make clear what was happening. A simple set of rules created a fairly complex shape. What a concrete and compelling introduction to recursion compared to computer science tradition in the Fibonacci series!

Although I didn't go there while working with Sam, I realize while writing this there's an opportunity to plant seeds of understanding for "significant digits." We can only barely see a difference between a curves drawn with level=6 and level=7. The differences are smaller than the pixels on our screen -- visually they are insignificant. In other words, there's no extra value to be gained by setting the level any more than 6, and it's obviously not worth the significant extra time.

Having worked with Rob "Once and only once" Nagler for five years now, I cannot look at a routine like DrawFractalLine without seeing the repetition. DrawFractalLine DrawFractalLine DrawFractalLine. Let's clean that up a bit. (By the way, Logo really shines here. It would be considerably more difficult and verbose to do this in Java or C#.)

to DrawFractalLine :level :length
  ifelse :level < 1 [
    forward :length
  ] [
    dolist [command [
      [left 60]
      [right 120]
      [left 60]
      []
    ]] [
      DrawFractalLine (sum -1 :level) (quotient :length 3.00)
      if not empty? :command [run :command]
    ]
  ]
end

This is a small enough bit of code that one might reasonably ask "why bother?" However one additional change lets us reuse DrawFractalLine for another classic fractal: the Peano curve.

to DrawFractalLine :commands :level :length
  ifelse :level < 1 [
    forward :length
  ] [
    dolist [command :commands] [
      DrawFractalLine :commands (sum -1 :level) (quotient :length 3.00)
      if not empty? :command [run :command]
    ]
  ]
end

to VonKoch :level :length
  DrawFractalLine [
    [left 60]
    [right 120]
    [left 60]
    []
  ] :level :length
end

to Peano :level :length
  DrawFractalLine [
    [left 90]
    [right 90]
    [right 90]
    [right 90]
    [left 90]
    [left 90]
    [left 90]
    [right 90]
    []
  ] :level :length
end

In shape, the Von Koch snowflake and the Peano curve are markedly different. But with the code in front of us the similarity of construction is quite concrete. Both involve replacing the middle of one segment with the same basic shape. That's exactly what DrawFractalLine now does. As another point of comparison between these two fractals, the Peano curve is space-filling: the more deeply we recurse, the more completely the space is colored in (for example, this was level=4):

By the time we'd made these changes to the code and talked about a these two classic fractals, Sam started suggesting different base shapes to try. Here was one where he suggested doing things a little differently with the peano curve.

to sam-curve :level :length
 DrawFractalLine [
  [left 90]
  [right 90]
  [right 90]
  []
  [right 90]
  [right 90]
  [right 90]
  [forward (2 * :length / 3)]
 ] :level :length
end

And next is a variation on the Von Koch curve. Why does this one grow in size with the depth of recursion?

to vkzig :level :length
  DrawFractalLine [
    [left 30]
    [right 120]
    [left 120]
    [right 30]
    []
  ] :level :length
end

Sam's attention was really captured thinking of new base shapes and trying to understand why they behave the way they do.

There's also a really important lesson about programming and automation in general. With a couple fairly simple refinements to the original program, we have created our own power tool for exploring this class of fractal. We created our own power tool. As programs go, this one is incredibly simple and small, yet has some amazing reach instructionally. What if we started kids in elementary school building up their own collection of computational tools? What if they shared tools? Computers are more than just fancy typewriters, or televisions. They're more than excellent gaming systems. Used thoughtfully, software offers leverage unlike anything that's come before. The problem we solved today can become a tool that lets us solve more complex problems tomorrow.