L-systems in Haskell

This project is relatively advanced L-system library written in Haskell. Out of the box it supports symbols with parameters, conditional rewriting, and it can evaluate expressions with binary and unary operators. There are two available L-system interpreters: text and SVG vector graphics. The code is well commented and written with extensibility in mind. It is easy to add new operators, new interpreters, or even extend the grammar. This project was my final program of Non-procedural programming class.

Source code is available on GitHub: NightElfik/L-systems-in-Haskell

Introduction

During my undergrad studies I was interested in L-systems and I wrote interpreters in many languages. This one is made in Haskell and it was made as a final project to my undergrad Non-procedural Programming class at Charles University in Prague. I think it is interesting piece of code that it is worth sharing. The main goal was design and also speed so the library is relatively easy to extend and quite fast.

This article assumes that reader has basic knowledge of L-systems.

Compilation and running

In order to compile Haskell you need a Haskell compiler. On Windows, you can install Haskell Platform that comes with GHC compiler. Then open a console (or PowerShell) and navigate to the source directory src. Invoke compilation with command ghc Main.hs which will produce executable Main.exe. You should see something similar to Code listing 1.

1
2
3
4
5
6
7
8
9
10

$ ghc Main.hs
[1 of 8] Compiling LSystem.Utils    ( LSystem\Utils.hs, LSystem\Utils.o )
[2 of 8] Compiling LSystem.ShowReadUtils ( LSystem\ShowReadUtils.hs, LSystem\ShowReadUtils.o )
[3 of 8] Compiling LSystem.GeneralDataTypes ( LSystem\GeneralDataTypes.hs, LSystem\GeneralDataTypes.o )
[4 of 8] Compiling LSystem.Expressions ( LSystem\Expressions.hs, LSystem\Expressions.o )
[5 of 8] Compiling LSystem.DataTypes ( LSystem\DataTypes.hs, LSystem\DataTypes.o )
[6 of 8] Compiling LSystem.Interprets ( LSystem\Interprets.hs, LSystem\Interprets.o )
[7 of 8] Compiling LSystem          ( LSystem.hs, LSystem.o )
[8 of 8] Compiling Main             ( Main.hs, Main.o )
Linking Main.exe ...

The executable expects paths to three files as input arguments. The First file contains definition of L-system (rewrite rules). The Second file is L-system symbols interpretation definition. The Third file contains the input (axioms, output file names). Initially the input was accepted directly from the console but due to encoding issues was moved to a file.

Directory testData contains several example files for testing. Files with extensions .lsd are L-system definition files (the first argument). Extension .lsi denotes L-system symbols interpretation definition file (the second argument). Finally, files with extension .in are input files (the third argument). To run all the examples just run the code shown in Code listing 2.

1
2
3
4
5
6
7

cd testData
..\src\Main.exe .\Hilbert.lsd .\i.lsi .\Hilbert.in
..\src\Main.exe .\Htree.lsd .\i.lsi .\Htree.in
..\src\Main.exe .\Koch.lsd .\i.lsi .\Koch.in
..\src\Main.exe .\Hilbert.lsd .\i.lsi .\Hilbert.in
..\src\Main.exe .\PenroseTiling.lsd .\i.lsi .\PenroseTiling.in
..\src\Main.exe .\RoseLeaf.lsd .\i.lsi .\RoseLeaf.in

L-system definition file format

L-system definition file contains one rewrite rule per line. Formal grammar is shown in Code listing 3. I understand that formal grammar is not readable for everybody so I have described the format in words below. You can jsut check out examples if you know L-systems well.

The symbol is any non-whitespace character (other than parenthesis). The arguments is comma separated lists of argument names. Every argument can contain only alphanumeric characters and should start with a letter. The condition is mathematical expression that can use arguments as variables. And the replacement is a list of symbols with optional list of parameters in parenthesis. Every parameter can be mathematical expression using variables from arguments list. The replacement can be empty. The arguments and condition can be omitted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

rewriteRule = symbolWithArgs condition? '−>' symbolWithParams*

symbolWithArgs = symbol args?
args = '(' argName moreArgs* ')'
moreArgs = ',' argName

condition = '?(' expr ')'

symbolWithParams = symbol params?
params = '(' expr moreExprs* ')'
moreExprs = ',' expr

symbol = non-whitespace character other than parenthesis
argName = alpha-numeric string starting with letter
expr = standard mathemarical expression

Examples of rewrite rules are probably more useful than formal definition. Code listing 4 shows couple of them (one per line). For more examples please see files in the testData directory.

Defined operators are ^, *, /, +, -, ==, !=, <, <=, >, >=, ||, &&, √. The list can be simply extended by adding a few lines to Expressions.hs file.

1
2
3
4
5
6
7
8
9
10
11

F -> FFF

F(l, r, a) -> H(l) [+(a) F(l*r, r, a)] [-(a) F(l*r, r, a)]

F(x,a) -> F(x,a) +(a) F(x,a) -(2*a) F(x,a) +(a) F(x,a)

y(t)     ?(t > 0)   -> g(1.3, 1.25, -1) y(t-1)

g(s,r,t) ?(t > 1)   -> g(s*r, r, t - 1)

g(s,r,t) ?(t == -1) -> g(s*r, r, -1)

L-system symbols interpretation definition file format

The second input file contains L-system symbol interpretation definition — one per line. Every line should contain symbol-instruction pair separated by a space. List of all defined instructions with their parameter interpretation is:

Name               Perameter
-----------------------------
DoNothing
DrawLineForward    Distance
MoveForward        Distance
TurnLeft           Angle in degrees
TurnRight          Angle in degrees
StartBranch
CompleteBranch

SVG only:
StartPolyline
RecordPolylineVertex
EndPolyline        Close polyline (bool, non-zero for 'true')

I hope that their names are self-explanatory. All symbols can have any number of parameters but some symbols' first argument is interpreted as denoted. All the examples in testData directory are using the same definitions from file i.lsi. The file is shown in Code listing 5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

F DrawLineForward
H DrawLineForward

W DrawLineForward
X DrawLineForward
Y DrawLineForward
Z DrawLineForward

f MoveForward
g MoveForward

l DoNothing
r DoNothing
x DoNothing
y DoNothing

+ TurnRight
- TurnLeft

[ StartBranch
] CompleteBranch

{ StartPolyline
. RecordPolylineVertex
} EndPolyline

Input file format

Input file format is line based as well. Every valid input has to contain three lines. On the first line is the name of output file. Its extension specifies the interpreter and it can be either .txt or .svg. If the output file name without extension is a dash then the output will be printed to standard output separated by a lightsaber: <==============))((((o))))((==============>

On the second line is expected non-negative number that represents number of iterations. Number two means to perform two iterations and then interpret the result. Zero means that axiom will be interpreted without performing any rewriting.

The third line contains the axiom with syntax identical to the right had side of rewrite rule — symbols with parameters. It is possible to specify more axioms on additional lines.

If you wish to put another triplet of lines for another file processing you can do so by separating previous triplet by a blank line. Code listing 6 shows example of input file.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

KochCurve-5.svg
5
F(10,60)

-.txt
2
F(10,60)

KochSnowflake-4.svg
4
F(10,60) -(120) F(10,60) -(120) F(10,60)

-.svg
2
F(10,60)

KochCurve85-6.svg
6
F(10,85)

Implementation details

In this chapter I will just mention some features of the library.

Expressions

Arithmetic expressions can be used in rewrite rules to compute values of parameters of symbols. This library contains robust parsing functions that converts infix expressions to postfix representaion. It is fun to play with the Expressions module in the Haskell interpreter and see the results. The function readsPeFromInfix takes a string and returns all possible postfix representations and the rest of the string that was not successfully parsed. Code listing 7 shows some examples of parsing expressions.

1
2
3
4
5
6
7
8
9
10
11

$ghci
> :l LSystem.Expressions
Ok, modules loaded: LSystem.Expressions, LSystem.ShowReadUtils, LSystem.GeneralDataTypes, LSystem.Utils.
> readsPeFromInfix "1+(2*3)^4+1"
[(1.0 2.0 3.0 * 4.0 ^ + 1.0 +,"")]
> readsPeFromInfix "1+2**3^4+1"
[(1.0 2.0 +,"**3^4+1")]
> readsPeFromInfix "-2^-3"
[(-2.0 -3.0 ^,""),(-2.0 3.0 - ^,""),(2.0 -3.0 ^ -,""),(2.0 3.0 - ^ -,"")]
> readsPeFromInfix "1+--(+-+-5)+-+1"
[(1.0 -5.0 + - + - - + 1.0 + - +,""),(1.0 5.0 - + - + - - + 1.0 + - +,"")]

Evaluation of postfix expression is done with function evalPe. With a little code it is also possible to add variables to the expressions. Code listing 8 shows some examples.

1
2
3
4
5
6
7
8
9
10
11

> :l LSystem.Expressions
> evalPe $ fst $ head $ readsPeFromInfix "2+3^3"
Just 29.0

> import LSystem.GeneralDataTypes
> import Data.Maybe

> let exprVar = fst $ head $ readsPeFromInfix "2^x"
> let varValue = ( fromJust $ nameFromString "x" , 10.0)
> evalPeVar [ varValue ] exprVar
Just 1024.0

Adding unary or binary operators is really simple. You just have to add a line to the Expressions.hs file and specify its string representation, precedences, and a function that should be invoked. There are two precedences to allow left and right associative operators. I have added interesting unary square root operator √ to avoid need of implementing function calls.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

unaryOperators = [
	UnaryOperator "√" 2 3 sqrt,
	UnaryOperator "+" 5 2 (0+),
	UnaryOperator "-" 5 2 (0-)]

binaryOperatorsSpec = [
	SpecialOperator "(" 99 0,
	SpecialOperator ")" 0 99]

binaryOperators = [
	BinaryOperator "^" 3 3 (**),

	BinaryOperator "*" 7 8 (*),
	BinaryOperator "/" 7 8 (/),

	BinaryOperator "+" 9 10 (+),
	BinaryOperator "-" 9 10 (-),

	BinaryOperator "==" 15 16 $ doubleCmpToDoubleLogic (==),
	BinaryOperator "!=" 15 16 $ doubleCmpToDoubleLogic (/=),
	BinaryOperator "<" 15 16 $ doubleCmpToDoubleLogic (<),
	BinaryOperator "<=" 15 16 $ doubleCmpToDoubleLogic (<=),
	BinaryOperator ">" 15 16 $ doubleCmpToDoubleLogic (>),
	BinaryOperator ">=" 15 16 $ doubleCmpToDoubleLogic (>=),

	BinaryOperator "||" 17 18 $ boolCmpToDoubleLogic (||),
	BinaryOperator "&&" 17 18 $ boolCmpToDoubleLogic (&&)]

Parsing the input

Parsing system is conveniently using recursion to parse the input. The parser functions have signature type ReadS a = String -> [(a, String)] where a is the parsed type. Every parse functions will try to parse given input in every possible way and return the rest of unused string. The parser is your typical recursive parser with back-tracking. The backtracking makes sure that if the parser made incorrect decision and it is not able to parse the input it back-tracks to try another way. It is basically finding the left-most derivation of the grammar. The cool part is that the search is terminated when the first correct derivation is found. This is possible due to Haskell's lazy evaluation. The recursive back-tracking parser is not the most efficient thing under the sun but it will always find the solution if exists. Also, the inputs are fairly small anyways.

All the output is printed using shows :: a -> ShowS where ShowS = String -> String. This is crucial because thanks to ShowS the concatenation of strings is done in constant time with regards to length of already printed output. Even better, the output propagates as a stream through function calls and it is not accumulated anywhere in the memory. This means that producing very large outputs should not be any problem.

It is relatively easy to add new features to the grammar. If you are interested in the parsing details then check out file DataTypes.hs.

Symbol interpretation

The library was written to allow new types of interpreters. As an example there is the SVG interpreter that produces vector graphics.

In order to implement new interpret you have to just create a function with signature InterpretFunc which is InstructionMap -> [SymbolDouble] -> String. Then you add it to the map avibleInterprets in Interpret.hs and that's it.

It is also easy to define new interpretation commands. This is shown on the SVG interpreter which adds instructions StartPolyline, RecordPolylineVertex, and EndPolyline. See Interpret.hs for details.

Conclusion

This library covers some interesting techniques such as parsing of grammar, evaluation of expressions, and L-systems and efficient work with IO. I hope it will help or inspire somebody in their endeavors through Haskell universe.

I really like some aspects of Haskell but the fact that it is strictly functional language makes it somewhat less usable in the real world. In some scenarios side effects are quite useful and safe (like debug printing!). I think that F# offers nice compromise between the two worlds plus it has the whole .NET framework behind it. However, I have not written an L-system library in the F# (yet :).

Code

You can find the full code published under Public Domain on the GitHub.