Logo, Fractals, and Recursion; Programming, and Removing Repetition
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.