Lindenmayer.jl: Defining recursive patterns in Julia | Hacker News Reader

Lindenmayer.jl: Defining recursive patterns in Julia

cormullion.github.io

72 pointsWillMorr10 comments

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.

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.

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

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

> 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.

Yes, that's what I mean by "recursive generations". L-System strings are interpreted in successive generations where the output of generation n becomes the input of generation n+1. The recursion I refer to here is at the level of generation steps.

You can simulate this with a parser for e.g. CFGs like you say, but then you need an outer loop that feeds the parsed strings back to the parser.

There's also a subtlety that I omitted in my earlier comment- apologies! but it's really a bit subtle. In L-Systems, strings are made up of "variables" and "constants", which are closely related to nonterminals and terminals, but are not exactly the same: in phrase-structure grammars, non-terminal symbols cannot appear in strings, only in grammar rules.

So for instance, the Dragon Curve rule I give above, "f -> f+g", means "wherever 'f' appears in a string, replace it with 'f+g'". To get the same result in a phrase-structure grammar you need to further define "f" as a pre-terminal, expanding to a single "f" character.

So for a CFG-parser-with-an-outer-loop to work on an L-System one would also need to modify the L-System to be a full CFG. To make it clear, here's the definition of the Dragon Curve L-System, from my example above:

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

And here is its redefinition as a CFG, with nonterminals capitalised:

  F -> F+G
  G -> F-G
  F -> f
  G -> g

I think it's easier to see that these are different objects. I bet we'd find that, for every L-System, there's a phrase-structure grammar that accepts the same strings (but not necessarily generates the same strings only) and that is a simple re-write of the L-System with variables replaced by pre-terminals, as I do above, kind of like a standard form (not normal; because not fully equivalent). That may even be something well-known by L-Systems folks, I don't know.

Btw, the Dragon Curve L-system is described as an OL-System, that matches a Regular language. The grammar above is context-free but that's OK, a CFG can parse strings of a Regular language. I believe L-System languages go up to context-free expressivity, but I'm not sure, there are also parameterised L-Systems that may go beyond that.

Interesting. What I was thinking was you could get the bounded-number-of-generations behavior by defining nonterminals with indices. Like this CFG which would rewrite for K steps.

S -> F_K

F_i -> F_{i-1} + G_{i-1} for i>0

G_i -> F_{i-1} - G_{i-1} for i>0

F_0 -> f

G_0 -> g

This kind of CFG is used for example by https://journals.aps.org/prx/pdf/10.1103/PhysRevX.14.031001

>> Like this CFG which would rewrite for K steps.

I believe that would work too and you could convert to this sub-scripted format with a simple pre-processor. I prefer the simpler and clearer notation that leaves the counting of generations to an interpreter because it's easier to read, but that's personal taste.

Thanks for the link to the paper which looks interesting. I'll have to read it more carefully.

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?

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

Reply on news.ycombinator.com