L-system: Difference between revisions
m turned back into a draft task |
|||
(13 intermediate revisions by 6 users not shown) | |||
Line 86: | Line 86: | ||
:* Wikipedia: [[wp:L-system|L-system]] |
:* Wikipedia: [[wp:L-system|L-system]] |
||
=={{header|ALGOL 68}}== |
|||
{{libheader|ALGOL 68-l-system}} |
|||
Note, the Algol 68 L-System library source code is on a separate page on Rosetta Code - follow the above link and then to the Talk page. |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # Example of L-System evaluation and interpretation # |
|||
PR read "lsystem.incl.a68" PR # include L-System utilities # |
|||
# task rabbit population example # |
|||
LSYSTEM rabbit population = ( "I", ( "I" -> "M" |
|||
, "M" -> "MI" |
|||
) |
|||
); |
|||
INT young := 0, old := 0; |
|||
STRING result = rabbit population EVAL 5; |
|||
result INTERPRET ( ( CHAR c )VOID: IF c = "I" THEN young +:= 1 ELSE old +:= 1 FI ); |
|||
print( ( "After 5 iterations there are ", whole( old, 0 ), " old rabbits and " |
|||
, whole( young, 0 ), " young ones (", result, ")", newline |
|||
) |
|||
) |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM) |
|||
</pre> |
|||
=={{header|BASIC}}== |
|||
==={{header|Applesoft BASIC}}=== |
|||
The [[#GW-BASIC|GW-BASIC]] solution works without any changes. |
|||
==={{header|BASIC256}}=== |
|||
<syntaxhighlight lang="vbnet">rabbit_population$ = "I" |
|||
young = 0 |
|||
old = 0 |
|||
for i = 1 to 5 |
|||
new_population$ = "" |
|||
for j = 1 to length(rabbit_population$) |
|||
t$ = mid(rabbit_population$, j, 1) |
|||
begin case |
|||
case t$ = "I" |
|||
new_population$ += "M" |
|||
case t$ = "M" |
|||
new_population$ += "MI" |
|||
end case |
|||
next j |
|||
rabbit_population$ = new_population$ |
|||
next i |
|||
for i = 1 to length(rabbit_population$) |
|||
t$ = mid(rabbit_population$, i, 1) |
|||
begin case |
|||
case t$ = "I" |
|||
young += 1 |
|||
case t$ = "M" |
|||
old += 1 |
|||
end case |
|||
next i |
|||
print "After 5 iterations there are "; old; " old rabbits and "; young; " young ones ("; rabbit_population$; ")"</syntaxhighlight> |
|||
{{out}} |
|||
<pre>After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)</pre> |
|||
==={{header|Chipmunk Basic}}=== |
|||
{{works with|Chipmunk Basic|3.6.4}} |
|||
<syntaxhighlight lang="vbnet">100 cls |
|||
110 rabbit_population$ = "I" |
|||
120 young = 0 |
|||
130 old = 0 |
|||
140 for i = 1 to 5 |
|||
150 new_population$ = "" |
|||
160 for j = 1 to len(rabbit_population$) |
|||
170 select case mid$(rabbit_population$,j,1) |
|||
180 case "I" |
|||
190 new_population$ = new_population$+"M" |
|||
200 case "M" |
|||
210 new_population$ = new_population$+"MI" |
|||
220 end select |
|||
230 next j |
|||
240 rabbit_population$ = new_population$ |
|||
250 next i |
|||
260 for i = 1 to len(rabbit_population$) |
|||
270 select case mid$(rabbit_population$,i,1) |
|||
280 case "I" |
|||
290 young = young+1 |
|||
300 case "M" |
|||
310 old = old+1 |
|||
320 end select |
|||
330 next i |
|||
340 print "After 5 iterations there are ";old;"old rabbits and ";young;"young ones (";rabbit_population$;")" |
|||
350 end</syntaxhighlight> |
|||
{{out}} |
|||
<pre>After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)</pre> |
|||
==={{header|Gambas}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="vbnet">Public rules As String[] = ["I", "M", "M", "MI"] |
|||
Public Sub Main() |
|||
Dim s As String = "I" |
|||
Dim count As Integer = 5 |
|||
For i As Integer = 0 To count |
|||
Print s |
|||
Dim nxt As String = "" |
|||
Dim j As Integer = 0 |
|||
While j < Len(s) |
|||
Dim c As String = Mid(s, j + 1, 1) |
|||
Dim found As Boolean = False |
|||
Dim k As Integer = 0 |
|||
While k <= rules.Max And Not found |
|||
If c = rules[k] Then |
|||
Dim rep As String = rules[k + 1] |
|||
found = True |
|||
Endif |
|||
k += 2 |
|||
Wend |
|||
nxt &= If(found, rep, c) |
|||
j += 1 |
|||
Wend |
|||
s = nxt |
|||
Next |
|||
End </syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|GW-BASIC}}=== |
|||
{{works with|PC-BASIC|any}} |
|||
{{works with|BASICA}} |
|||
{{works with|Applesoft BASIC}} |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|QBasic}} |
|||
{{works with|MSX BASIC}} |
|||
<syntaxhighlight lang="qbasic">110 R$ = "I" |
|||
120 Y = 0 |
|||
130 O = 0 |
|||
140 FOR I = 1 TO 5 |
|||
150 P$ = "" |
|||
160 FOR J = 1 TO LEN(R$) |
|||
170 IF MID$(R$,J,1) = "I" THEN P$ = P$ + "M" |
|||
180 IF MID$(R$,J,1) = "M" THEN P$ = P$ + "MI" |
|||
190 NEXT J |
|||
200 R$ = P$ |
|||
210 NEXT I |
|||
220 FOR I = 1 TO LEN(R$) |
|||
230 IF MID$(R$,I,1) = "I" THEN Y = Y+1 |
|||
240 IF MID$(R$,I,1) = "M" THEN O = O+1 |
|||
250 NEXT I |
|||
260 PRINT "After 5 iterations there are"; O; " old rabbits and"; Y; " young ones ("; R$; ")" |
|||
270 END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)</pre> |
|||
==={{header|MSX Basic}}=== |
|||
{{works with|MSX BASIC|any}} |
|||
The [[#GW-BASIC|GW-BASIC]] solution works without any changes. |
|||
==={{header|QBasic}}=== |
|||
{{works with|QB64}} |
|||
{{works with|QBasic|1.1}} |
|||
{{works with|QuickBasic|4.5}} |
|||
<syntaxhighlight lang="qbasic">DECLARE SUB Lindenmayer (s AS STRING, rules() AS STRING, count AS INTEGER) |
|||
DIM rules(3) AS STRING |
|||
rules(0) = "I" |
|||
rules(1) = "M" |
|||
rules(2) = "M" |
|||
rules(3) = "MI" |
|||
CALL Lindenmayer("I", rules(), 5) |
|||
END |
|||
SUB Lindenmayer (s AS STRING, rules() AS STRING, count AS INTEGER) |
|||
DIM i AS INTEGER, j AS INTEGER, k AS INTEGER, found AS INTEGER |
|||
DIM t AS STRING, nxt AS STRING, c AS STRING, rep AS STRING |
|||
FOR i = 0 TO count |
|||
PRINT s |
|||
nxt = "" |
|||
FOR j = 1 TO LEN(s) |
|||
c = MID$(s, j, 1) |
|||
found = 0 |
|||
FOR k = LBOUND(rules) TO UBOUND(rules) STEP 2 |
|||
IF c = rules(k) THEN |
|||
rep = rules(k + 1) |
|||
found = -1 |
|||
EXIT FOR |
|||
END IF |
|||
NEXT k |
|||
IF found = -1 THEN t = rep ELSE t = c |
|||
nxt = nxt + t |
|||
NEXT j |
|||
s = nxt |
|||
NEXT i |
|||
END SUB</syntaxhighlight> |
|||
{{out}} |
|||
<pre>After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)</pre> |
|||
==={{header|QB64}}=== |
|||
The [[#QBasic|QBasic]] solution works without any changes. |
|||
==={{header|XBasic}}=== |
|||
{{works with|Windows XBasic}} |
|||
<syntaxhighlight lang="qbasic">PROGRAM "L-system" |
|||
VERSION "0.0001" |
|||
DECLARE FUNCTION Entry () |
|||
FUNCTION Entry () |
|||
rabbit_population$ = "I" |
|||
young = 0 |
|||
old = 0 |
|||
FOR i = 1 TO 5 |
|||
new_population$ = "" |
|||
FOR j = 1 TO LEN(rabbit_population$) |
|||
SELECT CASE MID$(rabbit_population$, j, 1) |
|||
CASE "I" |
|||
new_population$ = new_population$ + "M" |
|||
CASE "M" |
|||
new_population$ = new_population$ + "MI" |
|||
END SELECT |
|||
NEXT j |
|||
rabbit_population$ = new_population$ |
|||
NEXT i |
|||
FOR i = 1 TO LEN(rabbit_population$) |
|||
SELECT CASE MID$(rabbit_population$, i, 1) |
|||
CASE "I" |
|||
INC young |
|||
CASE "M" |
|||
INC old |
|||
END SELECT |
|||
NEXT i |
|||
PRINT "After 5 iterations there are "; old; " old rabbits and "; young; " young ones ("; rabbit_population$; ")" |
|||
END FUNCTION |
|||
END PROGRAM</syntaxhighlight> |
|||
{{out}} |
|||
<pre>After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)</pre> |
|||
==={{header|Yabasic}}=== |
|||
<syntaxhighlight lang="vb">rabbit_population$ = "I" |
|||
young = 0 |
|||
old = 0 |
|||
for i = 1 to 5 |
|||
new_population$ = "" |
|||
for j = 1 to len(rabbit_population$) |
|||
switch mid$(rabbit_population$, j, 1) |
|||
case "I" |
|||
new_population$ = new_population$ + "M" |
|||
case "M" |
|||
new_population$ = new_population$ + "MI" |
|||
end switch |
|||
next j |
|||
rabbit_population$ = new_population$ |
|||
next i |
|||
for i = 1 to len(rabbit_population$) |
|||
switch mid$(rabbit_population$, i, 1) |
|||
case "I" |
|||
young = young + 1 |
|||
case "M" |
|||
old = old + 1 |
|||
end switch |
|||
next i |
|||
print "After 5 iterations there are", old, " old rabbits and", young, " young ones (", rabbit_population$, ")"</syntaxhighlight> |
|||
{{out}} |
|||
<pre>After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)</pre> |
|||
=={{header|C++}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="cpp">#include <iostream> |
|||
#include <map> |
|||
#include <string> |
|||
using namespace std; |
|||
void lindenmayer(string s, map<char, string> rules, int count) { |
|||
for (int i = 0; i < count; ++i) { |
|||
cout << s << endl; |
|||
string nxt = ""; |
|||
for (char c : s) { |
|||
if (rules.find(c) != rules.end()) { |
|||
nxt += rules[c]; |
|||
} else { |
|||
nxt += c; |
|||
} |
|||
} |
|||
s = nxt; |
|||
} |
|||
} |
|||
int main() { |
|||
map<char, string> rules = {{'I', "M"}, {'M', "MI"}}; |
|||
lindenmayer("I", rules, 5); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>I |
|||
M |
|||
MI |
|||
MIM |
|||
MIMMI</pre> |
|||
=={{header|Dart}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="dart">void lindenmayer(String s, Map<String, String> rules, int count) { |
|||
for (int i = 0; i < count; ++i) { |
|||
print(s); |
|||
String nxt = ""; |
|||
for (int j = 0; j < s.length; ++j) { |
|||
String c = s[j]; |
|||
nxt += rules.putIfAbsent(c, () => c); |
|||
} |
|||
s = nxt; |
|||
} |
|||
} |
|||
void main() { |
|||
var rules = {"I": "M", "M": "MI"}; |
|||
lindenmayer("I", rules, 5); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as C++ entry.</pre> |
|||
=={{header|FreeBASIC}}== |
|||
L-system functionality as a Role that may be mixed in to a scalar. |
|||
<syntaxhighlight lang="vbnet">Sub Lindenmayer(s As String, rules() As String, count As Integer) |
|||
Dim As Integer i, j, k, found |
|||
Dim As String nxt, c, rep |
|||
For i = 0 To count |
|||
Print s |
|||
nxt = "" |
|||
For j = 1 To Len(s) |
|||
c = Mid(s, j, 1) |
|||
found = 0 |
|||
For k = Lbound(rules) To Ubound(rules) Step 2 |
|||
If c = rules(k) Then |
|||
rep = rules(k + 1) |
|||
found = 1 |
|||
Exit For |
|||
End If |
|||
Next k |
|||
nxt &= Iif(found = 1, rep, c) |
|||
Next j |
|||
s = nxt |
|||
Next i |
|||
End Sub |
|||
Dim As String rules(3) = {"I", "M", "M", "MI"} |
|||
Lindenmayer("I", rules(), 5) |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre>I |
|||
M |
|||
MI |
|||
MIM |
|||
MIMMI |
|||
MIMMIMIM</pre> |
|||
Also see:</br> |
|||
[[Dragon_curve#FreeBASIC]]</br> |
|||
[[Hilbert_curve#FreeBASIC]]</br> |
|||
[[Koch_curve#FreeBASIC]]</br> |
|||
[[Peano_curve#FreeBASIC]]</br> |
|||
[[Penrose_tiling#FreeBASIC]]</br> |
|||
[[Sierpinski_curve#FreeBASIC]]</br> |
|||
[[Sierpinski_arrowhead_curve#FreeBASIC]]</br> |
|||
[[Sierpinski_square_curve#FreeBASIC]]</br> |
|||
among others... |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
Line 104: | Line 483: | ||
MIMMIMIM |
MIMMIMIM |
||
</pre> |
</pre> |
||
=={{header|Fōrmulæ}}== |
=={{header|Fōrmulæ}}== |
||
Line 165: | Line 545: | ||
</syntaxhighlight>{{out}} |
</syntaxhighlight>{{out}} |
||
[[File:Kochsnowflakefractal.png|thumb|center|alt=fractal image|Koch Snowflake]] |
[[File:Kochsnowflakefractal.png|thumb|center|alt=fractal image|Koch Snowflake]] |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 184: | Line 563: | ||
</syntaxhighlight> |
</syntaxhighlight> |
||
Invoke using eg <code><nowiki>lindenmayer("I",{{'I',"M"},{'M',"MI"}},5)</nowiki></code> which yields "MIMMIMIM" |
Invoke using eg <code><nowiki>lindenmayer("I",{{'I',"M"},{'M',"MI"}},5)</nowiki></code> which yields "MIMMIMIM" |
||
=={{header|Python}}== |
|||
{{works with|Python|3.x}} |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="python">#! /usr/bin/env python3 |
|||
def lindenmayer(s, rules, count): |
|||
for i in range(count): |
|||
print(s) |
|||
nxt = "" |
|||
for c in s: |
|||
found = False |
|||
for j in range(0, len(rules), 2): |
|||
if c == rules[j]: |
|||
rep = rules[j + 1] |
|||
found = True |
|||
break |
|||
nxt += rep if found else c |
|||
s = nxt |
|||
rules = ["I", "M", "M", "MI"] |
|||
lindenmayer("I", rules, 5)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>I |
|||
M |
|||
MI |
|||
MIM |
|||
MIMMI</pre> |
|||
=={{header|Quackery}}== |
|||
This solution reproduces the method used in other, pre-existing, tasks including [[Cantor set#Quackery|Cantor set]], [[Hilbert curve#Quackery|Hilbert curve]], [[Padovan sequence#Quackery|Padovan sequence]], [[Peano curve#Quackery|Peano curve]], [[Sierpinski curve#Quackery|Sierpinski curve]], and [[Sierpinski square curve#Quackery|Sierpinski square curve]]. |
|||
The alphabet is a set of single character (of necessity) Quackery words, which are uppercase by convention (to distinguish them from, and avoid conflict with, other Quackery words, which are exclusively lowercase by convention.) |
|||
Rules are Quackery words in the alphabet which return a string as a result. The word <code>expand</code> takes an axiom (a string of rules) and applies the rule associated with each character sequentially and concatenates the returned strings. In other words it performs a single iteration of the L-system. The word <code>times</code> can be used to perform a specified number of iterations. |
|||
This example illustrates this method for the life cycle of the Gallifreyan Fibonacci Rabbit, which lives forever, matures after the first cycle, and thereafter [https://tardis.fandom.com/wiki/Bi-generation bi-generates], producing a single kitten (i.e. an immature rabbit) on every cycle. |
|||
<syntaxhighlight lang="Quackery"> [ $ "" swap witheach |
|||
[ nested quackery join ] ] is expand ( $ --> $ ) |
|||
[ $ "M" ] is I ( --> $ ) |
|||
[ $ "MI" ] is M ( --> $ ) |
|||
$ "I" 5 times expand echo$</syntaxhighlight> |
|||
{{out}} |
|||
<pre>MIMMIMIM</pre> |
|||
Interpreting the resulting string is implemented by stepping through each character of the string and applying the actions associated with each character in the alphabet. In most of the tasks listed above this is achieved with the Quackery equivalent of a switch statement. Here, the action is to increment either a count of the number of mature rabbits, or the number of kittens, both of which are maintained on the stack, so <code>char I = if dip 1+</code> is sufficient. |
|||
<syntaxhighlight lang="Quackery"> [ 0 0 rot witheach |
|||
[ char I = if dip 1+ ] |
|||
say "Rabbits: " echo cr |
|||
say "Kittens: " echo cr ] is countrabbits ( $ --> ) |
|||
$ "I" 5 times expand countrabbits</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Rabbits: 5 |
|||
Kittens: 3</pre> |
|||
=={{header|Raku}}== |
|||
L-system functionality as a Role that may be mixed in to a scalar. |
|||
<syntaxhighlight lang="raku" line># L-system functionality |
|||
role Lindenmayer { |
|||
has %.rules; |
|||
method succ { |
|||
self.comb.map( { %!rules{$^c} // $c } ).join but Lindenmayer(%!rules) |
|||
} |
|||
} |
|||
# Testing |
|||
my $rabbits = 'I' but Lindenmayer({I => 'M', M => 'MI'}); |
|||
.say for $rabbits++ xx 6;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>I |
|||
M |
|||
MI |
|||
MIM |
|||
MIMMI |
|||
MIMMIMIM</pre> |
|||
Also see:</br> |
|||
[[Dragon_curve#Raku]]</br> |
|||
[[Hilbert_curve#Raku]]</br> |
|||
[[Koch_curve#Raku]]</br> |
|||
[[Peano_curve#Raku]]</br> |
|||
[[Penrose_tiling#Raku]]</br> |
|||
[[Sierpinski_curve#Raku]]</br> |
|||
[[Sierpinski_arrowhead_curve#Raku]]</br> |
|||
[[Sierpinski_square_curve#Raku]]</br> |
|||
among others... |
|||
=={{header|RPL}}== |
|||
≪ SWAP → rules |
|||
≪ 1 SWAP '''FOR''' a |
|||
→ in |
|||
≪ "" |
|||
1 in '''FOR''' b |
|||
in b DUP SUB |
|||
1 rules SIZE '''FOR''' c |
|||
rules c GET |
|||
'''IF''' DUP2 1 GET == '''THEN''' |
|||
SWAP DROP 2 GET |
|||
rules SIZE 'c' STO |
|||
'''ELSE''' DROP '''END''' |
|||
'''NEXT''' |
|||
+ |
|||
'''NEXT''' |
|||
≫ |
|||
'''NEXT''' |
|||
≫ ≫ ´<span style="color:blue">LSYS</span>' STO |
|||
"I" {{"I" "M"} {"M" "MI"}} 5 <span style="color:blue">LSYS</span> |
|||
{{out}} |
|||
<pre> |
|||
1: "MIMMIMIM" |
|||
</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|DOME}} |
|||
{{libheader|Wren-lsystem}} |
{{libheader|Wren-lsystem}} |
||
{{libheader|Wren-fmt}} |
|||
The source code for the Wren-lsystem module is available on this site by clicking the above link and then navigating to the Talk page. |
The source code for the Wren-lsystem module is available on this site by clicking the above link and then navigating to the Talk page. |
||
We can use this to generate the results for the rabbit population example as follows. |
|||
<syntaxhighlight lang="wren">import "./lsystem" for LSystem, Rule |
|||
import "./fmt" for Fmt |
|||
var lsys = LSystem.new( |
|||
["I", "M"], // variables |
|||
[], // constants |
|||
"I", // axiom |
|||
[ // rules |
|||
Rule.new("I", "M"), |
|||
Rule.new("M", "MI") |
|||
] |
|||
) |
|||
System.print("Step String") |
|||
System.print("---- --------") |
|||
var steps = lsys.listSteps(5) |
|||
for (i in 0..5) Fmt.print("$-4d $8m", i, steps[i])</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Step String |
|||
---- -------- |
|||
0 I |
|||
1 M |
|||
2 MI |
|||
3 MIM |
|||
4 MIMMI |
|||
5 MIMMIMIM |
|||
</pre> |
|||
{{libheader|DOME}} |
|||
We can also use it to draw a curve such as the Koch Snowflake. |
|||
<syntaxhighlight lang="wren">import "graphics" for Canvas, Color |
<syntaxhighlight lang="wren">import "graphics" for Canvas, Color |
||
import "dome" for Window |
import "dome" for Window |
Latest revision as of 21:24, 17 June 2024
- Introduction
An L-system, or Lindenmayer system, is a Turing-complete form of computaion, based in the parallel rewriting of symbols, usually provided and managed as strings. The name comes after Aristid Lindenmayer, a biologist who created it in order to simulate the growth of plants.
An L-system consists of:
- An alphabet of symbols
- An initial string, known as the axiom
- A set of rewriting rules, in he form A → B, where A is a single symbol and B is a string. The B string can contain zero, one or multiple symbols, including A.
- Computation
At start, the current string is the axiom.
On each step of computation, every symbol Aₙ in the current string, having a rewriting rule Aₙ → Bₙ, is replaced by Bₙ. if the string Bₙ of the rule Aₙ → Bₙ contains the symbol Aₙ, the rule is not applied recursively. This is why this form of computation is called "parallel". Once the rewriting of symbols have been performed, the string was converted to another string, usually longer.
After a defined number of steps, the string is the result of the computation.
- Example (rabbit population)
Alphabet: { I
, M
} for immature and mature rabbit. Only a mature rabbit can procreate a bunny
Rules:
I
→M
(An immature rabbit will be a mature one in the next step)M
→MI
(A mature rabbit will procreate a bunny in the next step)
Axiom: I
(Let us start with a immature rabbit)
Computation (5 steps):
Step | String | Notes |
---|---|---|
0 | I |
the axiom |
1 | M |
|
2 | MI |
|
3 | MIM |
|
4 | MIMMI |
|
5 | MIMMIMIM |
the result |
As you can see, the number of rabbits (the string length) in each step corresponds to the Fibonacci numbers.
- Interpretation
It is common to make a further use of the resulting string. For example, symbols can represents musical notes, graphic operations, etc. In this sense, the string is like a program, and each symbol is a instruction of that program.
When using graphic operations, sometimes specific symbols represent turtle graphics operations such as moving forward, moving forward and drawing, turning a certain angle, etc. Other symbols could represent push/pop operations in a stack data structure, in order to save the position/angle of the pen, to be retieved later.
- Task
Create a function, method, procedure, class, script, etc. (the solution) to compute the steps of a given L-system, and then, to perform the interpretation of the resulting string.
The inputs of the solution must be:
- The axiom
- The rewritig rules, in a data structure natural to your language, it could be, for example, an array of pairs of strings (S, R) where S is the symbol and R is the :rewriting of the symbol
- The number of steps to perform
- The set of operations associated to each symbol of the resulting string, in a natural structure of your language, it could be, for example, an array of pairs (S, O) where S is a symbol and O is a structure that denotes delayed functionallity, such as anonymous functions, callbacks, pointers to functions, names of functions that can be invoked at run time with EVAL, lambda expressions, etc. (list is not exhaustive)
It is highly recommended for the solution to be absracted enought to let the inputs to be given separated from the solution, this is, the solution should be coded as its final place is inside a library which is invoked with specific values or parameters. It is not required for the solution to contain the necessary code be an actual library, it is enough that the code of the solution is separarted from the code of the invocation.
Accesing environment objects. When interpretation produces graphical output, it is common to have objects that operations should access, such as graphic handlers, a stack, etc. A solution is to define the operations requestng such objects as parameters. Another (maybe better) option is to use closures.
If there already exists a library, package, etc. for your language to perform execution of L-systems, indicate the name of the library, how to get it, if it is open source, and examples of how to use it (see below).
- Test cases
Provide one or more test cases of L-systems executed and interpreted by your solution.
- References
- Wikipedia: L-system
ALGOL 68
Note, the Algol 68 L-System library source code is on a separate page on Rosetta Code - follow the above link and then to the Talk page.
BEGIN # Example of L-System evaluation and interpretation #
PR read "lsystem.incl.a68" PR # include L-System utilities #
# task rabbit population example #
LSYSTEM rabbit population = ( "I", ( "I" -> "M"
, "M" -> "MI"
)
);
INT young := 0, old := 0;
STRING result = rabbit population EVAL 5;
result INTERPRET ( ( CHAR c )VOID: IF c = "I" THEN young +:= 1 ELSE old +:= 1 FI );
print( ( "After 5 iterations there are ", whole( old, 0 ), " old rabbits and "
, whole( young, 0 ), " young ones (", result, ")", newline
)
)
END
- Output:
After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)
BASIC
Applesoft BASIC
The GW-BASIC solution works without any changes.
BASIC256
rabbit_population$ = "I"
young = 0
old = 0
for i = 1 to 5
new_population$ = ""
for j = 1 to length(rabbit_population$)
t$ = mid(rabbit_population$, j, 1)
begin case
case t$ = "I"
new_population$ += "M"
case t$ = "M"
new_population$ += "MI"
end case
next j
rabbit_population$ = new_population$
next i
for i = 1 to length(rabbit_population$)
t$ = mid(rabbit_population$, i, 1)
begin case
case t$ = "I"
young += 1
case t$ = "M"
old += 1
end case
next i
print "After 5 iterations there are "; old; " old rabbits and "; young; " young ones ("; rabbit_population$; ")"
- Output:
After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)
Chipmunk Basic
100 cls
110 rabbit_population$ = "I"
120 young = 0
130 old = 0
140 for i = 1 to 5
150 new_population$ = ""
160 for j = 1 to len(rabbit_population$)
170 select case mid$(rabbit_population$,j,1)
180 case "I"
190 new_population$ = new_population$+"M"
200 case "M"
210 new_population$ = new_population$+"MI"
220 end select
230 next j
240 rabbit_population$ = new_population$
250 next i
260 for i = 1 to len(rabbit_population$)
270 select case mid$(rabbit_population$,i,1)
280 case "I"
290 young = young+1
300 case "M"
310 old = old+1
320 end select
330 next i
340 print "After 5 iterations there are ";old;"old rabbits and ";young;"young ones (";rabbit_population$;")"
350 end
- Output:
After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)
Gambas
Public rules As String[] = ["I", "M", "M", "MI"]
Public Sub Main()
Dim s As String = "I"
Dim count As Integer = 5
For i As Integer = 0 To count
Print s
Dim nxt As String = ""
Dim j As Integer = 0
While j < Len(s)
Dim c As String = Mid(s, j + 1, 1)
Dim found As Boolean = False
Dim k As Integer = 0
While k <= rules.Max And Not found
If c = rules[k] Then
Dim rep As String = rules[k + 1]
found = True
Endif
k += 2
Wend
nxt &= If(found, rep, c)
j += 1
Wend
s = nxt
Next
End
- Output:
Same as FreeBASIC entry.
GW-BASIC
110 R$ = "I"
120 Y = 0
130 O = 0
140 FOR I = 1 TO 5
150 P$ = ""
160 FOR J = 1 TO LEN(R$)
170 IF MID$(R$,J,1) = "I" THEN P$ = P$ + "M"
180 IF MID$(R$,J,1) = "M" THEN P$ = P$ + "MI"
190 NEXT J
200 R$ = P$
210 NEXT I
220 FOR I = 1 TO LEN(R$)
230 IF MID$(R$,I,1) = "I" THEN Y = Y+1
240 IF MID$(R$,I,1) = "M" THEN O = O+1
250 NEXT I
260 PRINT "After 5 iterations there are"; O; " old rabbits and"; Y; " young ones ("; R$; ")"
270 END
- Output:
After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)
MSX Basic
The GW-BASIC solution works without any changes.
QBasic
DECLARE SUB Lindenmayer (s AS STRING, rules() AS STRING, count AS INTEGER)
DIM rules(3) AS STRING
rules(0) = "I"
rules(1) = "M"
rules(2) = "M"
rules(3) = "MI"
CALL Lindenmayer("I", rules(), 5)
END
SUB Lindenmayer (s AS STRING, rules() AS STRING, count AS INTEGER)
DIM i AS INTEGER, j AS INTEGER, k AS INTEGER, found AS INTEGER
DIM t AS STRING, nxt AS STRING, c AS STRING, rep AS STRING
FOR i = 0 TO count
PRINT s
nxt = ""
FOR j = 1 TO LEN(s)
c = MID$(s, j, 1)
found = 0
FOR k = LBOUND(rules) TO UBOUND(rules) STEP 2
IF c = rules(k) THEN
rep = rules(k + 1)
found = -1
EXIT FOR
END IF
NEXT k
IF found = -1 THEN t = rep ELSE t = c
nxt = nxt + t
NEXT j
s = nxt
NEXT i
END SUB
- Output:
After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)
QB64
The QBasic solution works without any changes.
XBasic
PROGRAM "L-system"
VERSION "0.0001"
DECLARE FUNCTION Entry ()
FUNCTION Entry ()
rabbit_population$ = "I"
young = 0
old = 0
FOR i = 1 TO 5
new_population$ = ""
FOR j = 1 TO LEN(rabbit_population$)
SELECT CASE MID$(rabbit_population$, j, 1)
CASE "I"
new_population$ = new_population$ + "M"
CASE "M"
new_population$ = new_population$ + "MI"
END SELECT
NEXT j
rabbit_population$ = new_population$
NEXT i
FOR i = 1 TO LEN(rabbit_population$)
SELECT CASE MID$(rabbit_population$, i, 1)
CASE "I"
INC young
CASE "M"
INC old
END SELECT
NEXT i
PRINT "After 5 iterations there are "; old; " old rabbits and "; young; " young ones ("; rabbit_population$; ")"
END FUNCTION
END PROGRAM
- Output:
After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)
Yabasic
rabbit_population$ = "I"
young = 0
old = 0
for i = 1 to 5
new_population$ = ""
for j = 1 to len(rabbit_population$)
switch mid$(rabbit_population$, j, 1)
case "I"
new_population$ = new_population$ + "M"
case "M"
new_population$ = new_population$ + "MI"
end switch
next j
rabbit_population$ = new_population$
next i
for i = 1 to len(rabbit_population$)
switch mid$(rabbit_population$, i, 1)
case "I"
young = young + 1
case "M"
old = old + 1
end switch
next i
print "After 5 iterations there are", old, " old rabbits and", young, " young ones (", rabbit_population$, ")"
- Output:
After 5 iterations there are 5 old rabbits and 3 young ones (MIMMIMIM)
C++
#include <iostream>
#include <map>
#include <string>
using namespace std;
void lindenmayer(string s, map<char, string> rules, int count) {
for (int i = 0; i < count; ++i) {
cout << s << endl;
string nxt = "";
for (char c : s) {
if (rules.find(c) != rules.end()) {
nxt += rules[c];
} else {
nxt += c;
}
}
s = nxt;
}
}
int main() {
map<char, string> rules = {{'I', "M"}, {'M', "MI"}};
lindenmayer("I", rules, 5);
return 0;
}
- Output:
I M MI MIM MIMMI
Dart
void lindenmayer(String s, Map<String, String> rules, int count) {
for (int i = 0; i < count; ++i) {
print(s);
String nxt = "";
for (int j = 0; j < s.length; ++j) {
String c = s[j];
nxt += rules.putIfAbsent(c, () => c);
}
s = nxt;
}
}
void main() {
var rules = {"I": "M", "M": "MI"};
lindenmayer("I", rules, 5);
}
- Output:
Same as C++ entry.
FreeBASIC
L-system functionality as a Role that may be mixed in to a scalar.
Sub Lindenmayer(s As String, rules() As String, count As Integer)
Dim As Integer i, j, k, found
Dim As String nxt, c, rep
For i = 0 To count
Print s
nxt = ""
For j = 1 To Len(s)
c = Mid(s, j, 1)
found = 0
For k = Lbound(rules) To Ubound(rules) Step 2
If c = rules(k) Then
rep = rules(k + 1)
found = 1
Exit For
End If
Next k
nxt &= Iif(found = 1, rep, c)
Next j
s = nxt
Next i
End Sub
Dim As String rules(3) = {"I", "M", "M", "MI"}
Lindenmayer("I", rules(), 5)
Sleep
- Output:
I M MI MIM MIMMI MIMMIMIM
Also see:
Dragon_curve#FreeBASIC
Hilbert_curve#FreeBASIC
Koch_curve#FreeBASIC
Peano_curve#FreeBASIC
Penrose_tiling#FreeBASIC
Sierpinski_curve#FreeBASIC
Sierpinski_arrowhead_curve#FreeBASIC
Sierpinski_square_curve#FreeBASIC
among others...
F#
// L-system. Nigel Galloway: April 1th., 2024
type rabbit= M|I
let rules=function I->[M] |M->[M;I]
let L axiom rules=Seq.unfold(fun n->Some(n,n|>Seq.map(rules)|>Seq.concat)) axiom
L [I] rules|>Seq.take 6|>Seq.iter(fun n->n|>Seq.iter(printf "%A");printfn "")
- Output:
I M MI MIM MIMMI MIMMIMIM
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
The following function performs the L-system computation given the axiom, the rules and the number of steps:
The following function performs the L-system interpretation given the resulting string and the operations:
The following functions is useful when computation and interpetation parameters is desired in a single function:
Test case 1. Koch's snowflake
Test case 2. Sierpiński curve
Test case 3. Peano curve
Test case 4. Hilbert curve
Julia
Julia has the Lindenmeyer.jl package downloadable via the package manager in the usual fashion.
using Lindenmayer
scurve = LSystem(Dict("F" => "F+F--F+F"), "8F--F--F") # 8 sets stroke width to 8 px
drawLSystem(scurve,
forward = 16,
turn = 60,
startingx = -200,
startingy = 100,
iterations = 3,
backgroundcolor = "white",
filename = "kochsnow.png",
showpreview = true
)
- Output:
![fractal image](http://static.miraheze.org/rosettacodewiki/thumb/2/2b/Kochsnowflakefractal.png/300px-Kochsnowflakefractal.png)
Phix
Just the generic part:
function lindenmayer(string s, sequence rules, integer count)
sequence {chars, reps} = columnize(rules)
for i=1 to count do
string nxt = ""
for c in s do
integer k = find(c,chars)
nxt &= iff(k?reps[k]:c)
end for
s = nxt
end for
return s
end function
Invoke using eg lindenmayer("I",{{'I',"M"},{'M',"MI"}},5)
which yields "MIMMIMIM"
Python
#! /usr/bin/env python3
def lindenmayer(s, rules, count):
for i in range(count):
print(s)
nxt = ""
for c in s:
found = False
for j in range(0, len(rules), 2):
if c == rules[j]:
rep = rules[j + 1]
found = True
break
nxt += rep if found else c
s = nxt
rules = ["I", "M", "M", "MI"]
lindenmayer("I", rules, 5)
- Output:
I M MI MIM MIMMI
Quackery
This solution reproduces the method used in other, pre-existing, tasks including Cantor set, Hilbert curve, Padovan sequence, Peano curve, Sierpinski curve, and Sierpinski square curve.
The alphabet is a set of single character (of necessity) Quackery words, which are uppercase by convention (to distinguish them from, and avoid conflict with, other Quackery words, which are exclusively lowercase by convention.)
Rules are Quackery words in the alphabet which return a string as a result. The word expand
takes an axiom (a string of rules) and applies the rule associated with each character sequentially and concatenates the returned strings. In other words it performs a single iteration of the L-system. The word times
can be used to perform a specified number of iterations.
This example illustrates this method for the life cycle of the Gallifreyan Fibonacci Rabbit, which lives forever, matures after the first cycle, and thereafter bi-generates, producing a single kitten (i.e. an immature rabbit) on every cycle.
[ $ "" swap witheach
[ nested quackery join ] ] is expand ( $ --> $ )
[ $ "M" ] is I ( --> $ )
[ $ "MI" ] is M ( --> $ )
$ "I" 5 times expand echo$
- Output:
MIMMIMIM
Interpreting the resulting string is implemented by stepping through each character of the string and applying the actions associated with each character in the alphabet. In most of the tasks listed above this is achieved with the Quackery equivalent of a switch statement. Here, the action is to increment either a count of the number of mature rabbits, or the number of kittens, both of which are maintained on the stack, so char I = if dip 1+
is sufficient.
[ 0 0 rot witheach
[ char I = if dip 1+ ]
say "Rabbits: " echo cr
say "Kittens: " echo cr ] is countrabbits ( $ --> )
$ "I" 5 times expand countrabbits
- Output:
Rabbits: 5 Kittens: 3
Raku
L-system functionality as a Role that may be mixed in to a scalar.
# L-system functionality
role Lindenmayer {
has %.rules;
method succ {
self.comb.map( { %!rules{$^c} // $c } ).join but Lindenmayer(%!rules)
}
}
# Testing
my $rabbits = 'I' but Lindenmayer({I => 'M', M => 'MI'});
.say for $rabbits++ xx 6;
- Output:
I M MI MIM MIMMI MIMMIMIM
Also see:
Dragon_curve#Raku
Hilbert_curve#Raku
Koch_curve#Raku
Peano_curve#Raku
Penrose_tiling#Raku
Sierpinski_curve#Raku
Sierpinski_arrowhead_curve#Raku
Sierpinski_square_curve#Raku
among others...
RPL
≪ SWAP → rules
≪ 1 SWAP FOR a
→ in
≪ ""
1 in FOR b
in b DUP SUB
1 rules SIZE FOR c
rules c GET
IF DUP2 1 GET == THEN
SWAP DROP 2 GET
rules SIZE 'c' STO
ELSE DROP END
NEXT
+
NEXT
≫
NEXT
≫ ≫ ´LSYS' STO
"I" {{"I" "M"} {"M" "MI"}} 5 LSYS
- Output:
1: "MIMMIMIM"
Wren
The source code for the Wren-lsystem module is available on this site by clicking the above link and then navigating to the Talk page.
We can use this to generate the results for the rabbit population example as follows.
import "./lsystem" for LSystem, Rule
import "./fmt" for Fmt
var lsys = LSystem.new(
["I", "M"], // variables
[], // constants
"I", // axiom
[ // rules
Rule.new("I", "M"),
Rule.new("M", "MI")
]
)
System.print("Step String")
System.print("---- --------")
var steps = lsys.listSteps(5)
for (i in 0..5) Fmt.print("$-4d $8m", i, steps[i])
- Output:
Step String ---- -------- 0 I 1 M 2 MI 3 MIM 4 MIMMI 5 MIMMIMIM
We can also use it to draw a curve such as the Koch Snowflake.
import "graphics" for Canvas, Color
import "dome" for Window
import "math" for Math
import "./lsystem" for LSystem, Rule
var TwoPi = Num.pi * 2
class KochSnowflake {
construct new(width, height, back, fore) {
Window.title = "Koch Snowflake"
Window.resize(width, height)
Canvas.resize(width, height)
_w = width
_h = height
_bc = back
_fc = fore
}
init() {
Canvas.cls(_bc)
var cx = 80
var cy = 270
var theta = Num.pi/2
var h = 9
var lsys = LSystem.new(
["F"], // variables
["+", "-"], // constants
"F--F--F", // axiom
[Rule.new("F", "F+F--F+F")], // rules
Num.pi / 3 // angle (60 degrees in radians)
)
var result = lsys.iterate(3)
var operations = {
"F": Fn.new {
var newX = cx + h*Math.sin(theta)
var newY = cy - h*Math.cos(theta)
Canvas.line(cx, cy, newX, newY, _fc, 2)
cx = newX
cy = newY
},
"+": Fn.new {
theta = (theta + lsys.angle) % TwoPi
},
"-": Fn.new {
theta = (theta - lsys.angle) % TwoPi
}
}
LSystem.execute(result, operations)
}
update() {}
draw(alpha) {}
}
var Game = KochSnowflake.new(400, 400, Color.blue, Color.yellow)
- Output: