Lindenmayer.jl: Defining recursive patterns in Julia

https://cormullion.github.io/Lindenmayer.jl/stable/

by WillMorr • 5 months ago

72 10 5 months ago

cormullion.github.io

AxiomLab• 5 months ago

L-systems perfectly illustrate how massive visual complexity can be mathematically derived from a handful of discrete axioms.

It’s a core mental model. When building generative systems, the designer's job fundamentally shifts from manually drawing the final shape to strictly engineering the initial recursive rules. A design system that cannot be expressed as a recursive function is usually just arbitrary styling, not a true system.

canjobear3• 5 months ago

For the computational linguistics aficionados: L-systems are context-free grammars by another name.

YeGoblynQueenne3• 5 months ago

L-Systems are not phrase-structure grammars. Some are similar to Regular, others to Context-Free grammars, but they're a different grammar formalism.

The difference is that L-system rules are all applied simultaneously and consume an entire string before repeating the process in steps called "generations", where each generation takes as input the output of the previous one. Generations continue indefinitely, generating ever-longer strings, up to a limit set by the user.

For instance, take the Dragon Curve L-System,

  Axiom: f
  Constants: +,-
  f -> f+g
  g -> f-g

Suppose we wanted to execute two generations of this L-System. Starting with the axiom, "f", the first generation replaces "f" with "f+g". The next generation operates on this new string. The "f" in "f+g" is replaced with "f+g", the "+" stays the same because it's a constant and the "g" is replaced with "f-g". This creates the string f+g+f-g. And so on.

If the same L-System was given as a phrase-structure grammar, given the axiom, "f", as input, the "f" would be expanded to f+g, and the process would stop there. No concept of recursive "generations" in phrase structure grammars! If we wanted to generate the string "f+g+f-g" with a phrase structure grammar we'd need to give the input "f+g", i.e. the L-System output of the first generation.

More to the point, the execution of L-Systems in successive generations limits the strings that can be generated by a set of rules, if we take those rules as an L-System grammar. For example, the Dragon Curve Rules above, interpreted as an L-System can only generate the strings:

  f --> f+g
  f+g --> f+g+f-g
  f+g+f-g --> f+g+f-g+f+g-f-g

Where the strings before the "-->" are inputs and the ones after, outputs, and each string is the output of one generation.

Whereas the same rules, interpreted as a Regular, phrase-structure, grammar, accept all the following one- to three-character strings :

  + --> +
  - --> -
  ++ --> ++
  +- --> +-
  -+ --> -+
  -- --> --
  +++ --> +++
  ++- --> ++-
  +-+ --> +-+
  +-- --> +--
  -++ --> -++
  -+- --> -+-
  --+ --> --+
  --- --> ---
  f --> f+g
  g --> f-g

And so on up to 229 strings of one to six characters (as in the input of the third-generation Dragon Curve above).

But none of those strings, other than the penultimate one, are correct Dragon Curve strings, meaning that they can't be interpreted so as to draw a Dragon Curve fractal, e.g. with a Turtle interpreter as in the article above.

To be fair to your comment, the first time I read the claim that L-Systems are different in that way I scoffed and wrote it off as an attempt to justify an unnecessary new notation. I put the insistence on a new notation down to vanity and forgot about it.

I only realised that L-Systems are really a different grammar formalism when I tried to implement a simple L-System as a Regular grammar, in Prolog's Definite Clause Grammars (DCG) notation. DCGs are syntactic sugar for ordinary Prolog definite clauses so a "grammar" in DCG notation is at the same time a L/R parser, that can also be executed as a generator without any changes, a nifty trick that is well suited to the role of L-Systems as generators, rather than recognisers. I won't bore you with the details, but suffice it to say that this natural style of parsing simply doesn't work with L-System grammars, you need a special interpreter to count the generations and pass the output of one to the next. Not complicated, but the point is that just parsing an L-System string as a phrase-structure grammar string, doesn't give you the same results.

Bottom line: L-Systems aren't just trying to be different; they are. They're not phrase-structure grammars. For real.

P.S. And for our shameless plug today, my paper on learning grammars, both phrase-structure grammars and L-Systems:

https://arxiv.org/abs/2507.16405

canjobear3• 5 months ago

No concept of recursive "generations" in phrase structure grammars!

Not sure what you're getting at here. Generation in a CFG proceeds recursively until no more terminals can be rewritten. If "f" is a nonterminal then you'd keep rewriting just as in an L-system and you'd generate the strings you want just fine. Or is what is distinctive the fact that you can limit the number of "generations"? It seems you could simulate this in a CFG too.

Tarrosion• 5 months ago

This author is really prolific in the Julia visualization ecosystem. One of my favorite projects from them is actually quite useful outside Julia: a super minimal but slick Unicode character lookup, glyphy.info.

vivzkestrel• 5 months ago

stupid question from a guy who has no idea about this language. what is special about this language that say python or rust or zig dont have?

leephillips• 5 months ago

https://arstechnica.com/science/2020/10/the-unreasonable-eff...

Lindenmayer.jl: Defining recursive patterns in Julia

Related Stories