L-system

From Rosetta Code
L-system is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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

ALGOL 68

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

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)

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
Koch Snowflake


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"

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

Library: Wren-lsystem
Library: 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.

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
Library: DOME

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:

Retrieved from "https://rosettacode.org/wiki/L-system?oldid=363770"