Lindenmeyer fractals as data

Several years ago I wrote about creating fractals with Lindenmeyer systems, and at the time the code looked like this:

(defn koch-snowflake-old [step rule turn-angle depth]
  (if (pos? depth)
    (let [left [[:turn (- 360 turn-angle)]]
          right [[:turn turn-angle]]
          f (koch-snowflake-old step :f turn-angle (dec depth))]
      (condp = rule
        :a (concat f right right f right right f)
        :f (concat f left f right right f left f)))
    [[:forward step]]))

Calling the above function with the right parameters produced a sequence of turtle graphics operations:

(koch-snowflake-old 10 :a 60 1)

([:forward 10]
 [:turn 60]
 [:turn 60]
 [:forward 10]
 [:turn 60]
 [:turn 60]
 [:forward 10])

Today I'll revisit this code to make some improvements. While it is reasonably concise (only nine lines long), it buries the data at the heart of the L-system inside the function's logical execution; it's not enough to understand the rules of the L-system, readers also have to understand Clojure (e.g. pos?, condp, concat).

As an alternative to functional recursion, here's a pure-data approach that defines the L-system's axiom, rules, and the graphical meaning of the rules in a style which closely reflects Wikipedia's definition of the Lindenmeyer system for a Koch snowflake:

(def koch-snowflake
  '{:axiom [F - - F - - F]
    :rules {F [F + F - - F + F]}
    :moves {+ [:turn -60]
            - [:turn 60]
            F [:forward 1]}})

To convert this definition into turtle graphics operations, first expand the axiom and rules recursively:

(let [{:keys [axiom rules moves]} koch-snowflake]
  (loop [levels 1
         steps axiom]
    (if (and (pos? levels) (< (count moves) 1e5))
      (recur (dec levels) (mapcat #(get rules % [%]) steps))
      steps)))

(F + F - - F + F - - F + F - - F + F - - F + F - - F + F)

Again concise, but the logic has to be understood as a whole and doesn't break down into small, digestible pieces. For a more data-centric, decompleted style, let's use iterate:

(let [{:keys [axiom rules moves]} koch-snowflake]
  (->> axiom
    (iterate (fn [steps]
               (mapcat #(get rules % [%]) steps)))
    (drop 1)
    first))

(F + F - - F + F - - F + F - - F + F - - F + F - - F + F)

All recursion is now hidden inside iterate, which produces a lazy, infinite sequence of the rules at each level of the L-system's recursion. If we wanted, we could pass this sequence off to another function to decide what level of recursion to render, or it could even render the system at multiple levels of recursion.

Mapping each step to its turtle graphics operation only requires adding a final (map moves):

(let [{:keys [axiom rules moves]} koch-snowflake]
  (->> axiom
    (iterate (fn [steps]
               (mapcat #(get rules % [%]) steps)))
    (drop 1)
    first
    (map moves)))

([:forward 1]
 [:turn -60]
 [:forward 1]
 [:turn 60]
 [:turn 60]
 [:forward 1]
 [:turn -60]
 [:forward 1]
 [:turn 60]
 [:turn 60]
 [:forward 1]
 [:turn -60]
 [:forward 1]
 [:turn 60]
 [:turn 60]
 [:forward 1]
 [:turn -60]
 [:forward 1]
 [:turn 60]
 [:turn 60]
 [:forward 1]
 [:turn -60]
 [:forward 1]
 [:turn 60]
 [:turn 60]
 [:forward 1]
 [:turn -60]
 [:forward 1])

Which produces the following simple image:

The snowflakiness of the Koch snowflake appears at about four levels of recursion:

While the final version of the code is slightly longer than the original, it's now much easier to create new fractals, as we only have to define a few facts about the L-system and don't have to write any logic. I'll demonstrate the succinctness of a few more L-systems in the next post.