Lindenmayer.jl: Defining recursive patterns in Julia(cormullion.github.io) |
Lindenmayer.jl: Defining recursive patterns in Julia(cormullion.github.io) |
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.
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
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
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
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:
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.
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
F -> F+G
G -> F-G
F -> f
G -> g
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.
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
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.