Rewrite rule definition

Rewrite rule will define what symbol under what conditions is rewritten (replaced) to sting of another symbols. Rewrite rule can rewrite just one symbol but its replacement can be string of symbols or nothing. In L-system can be defined any number of rewrite rules.

Basic rewrite rules

Rewrite rule can define rewriting one symbol for another (A for B in following example).

Input

1
2
3
4
5
6
7
lsystem RewriteRuleExample01 {
set iterations = 1;
set interpretEveryIteration = false;
set symbols axiom = A A;
rewrite A to B;
}
process all with SymbolPrinter;

Output

B B

It is also possible to rewrite symbol for string of symbols. Individual symbols are separated by space.

Input

1
2
3
4
5
6
7
lsystem RewriteRuleExample02 {
set iterations = 5;
set interpretEveryIteration = true;
set symbols axiom = A;
rewrite A to B A;
}
process all with SymbolPrinter;

Output

  1. A
  2. B A
  3. B B A
  4. B B B A
  5. B B B B A
  6. B B B B B A

We cal also "delete" symbol by defining replacement as nothing.

Input

1
2
3
4
5
6
7
lsystem RewriteRuleExample03 {
set iterations = 1;
set interpretEveryIteration = false;
set symbols axiom = A B A B;
rewrite A to nothing ;
}
process all with SymbolPrinter;

Output

B B

Order of rewrite rules matters

We can define any number of rewrite rules to L-system, but searching for matching rewrite rule will end after first success. This means that order if rewrite rule is significant. Compare following two L-systems.

Input

1
2
3
4
5
6
7
8
lsystem RewriteRuleExample04 {
set iterations = 5;
set interpretEveryIteration = false;
set symbols axiom = A;
rewrite A to B A;
rewrite A to C A;
}
process all with SymbolPrinter;

Output

B B B B B A

Input

1
2
3
4
5
6
7
8
lsystem RewriteRuleExample05 {
set iterations = 5;
set interpretEveryIteration = false;
set symbols axiom = A;
rewrite A to C A;
rewrite A to B A;
}
process all with SymbolPrinter;

Output

C C C C C A

Using arguments from symbols

Symbols can hold some arguments. To be able to work with them in rewrite rule we need to name them. This is done by adding list of names separated by comma after matching symbol. We can use matched arguments as local variables.

Input

1
2
3
4
5
6
7
lsystem RewriteRuleExample06 {
set iterations = 4;
set interpretEveryIteration = true;
set symbols axiom = A(1);
rewrite A(x) to B(x) A(x + 1);
}
process all with SymbolPrinter;

Output

  1. A(1)
  2. B(1) A(2)
  3. B(1) B(2) A(3)
  4. B(1) B(2) B(3) A(4)
  5. B(1) B(2) B(3) B(4) A(5)

If symbol do not have enough actual parameters to match all names NaN (not a number) value is set to them.

Input

1
2
3
4
5
6
7
lsystem RewriteRuleExample07 {
set iterations = 1;
set interpretEveryIteration = false;
set symbols axiom = A(1, 2);
rewrite A(x, y, z) to B(x, y, z);
}
process all with SymbolPrinter;

Output

B(1, 2, NaN)

Context rewriting

Rewriting may be conditioned by context of primary symbol. Context is symbols around main symbol (on left or on right). Left (resp. right) context is specified by putting symbols left (resp. right) of main symbol in braces. Rewrite rule in following example will match on symbol A only if before it is symbol B.

Input

1
2
3
4
5
6
7
8
lsystem RewriteRuleExample08 {
set iterations = 5;
set interpretEveryIteration = true;
set symbols axiom = B A A A A;
rewrite {B} A to B;
rewrite B to A;
}
process all with SymbolPrinter;

Output

  1. B A A A A
  2. A B A A A
  3. A A B A A
  4. A A A B A
  5. A A A A B
  6. A A A A A

Arguments of symbols in context can be matched in the same way as arguments of main symbol. Following L-system counts Fibonacci sequence by using context rewrite rules and symbol's arguments.

Input

1
2
3
4
5
6
7
8
9
10
lsystem RewriteRuleExample09 {
set iterations = 6;
set interpretEveryIteration = true;
set symbols axiom = A(0) B(1);
rewrite A(a) {
B(b) } to A(b);
rewrite {
A(a) } B(b) to B(a + b);
}
process all with SymbolPrinter;

Output

  1. A(0) B(1)
  2. A(1) B(1)
  3. A(1) B(2)
  4. A(2) B(3)
  5. A(3) B(5)
  6. A(5) B(8)
  7. A(8) B(13)

Branches and context

TODO

Local constant definition in rewrite rule

Sometimes can be handy to define constant locally in the rewrite rule to get rid of repetitive expressions. This is possible using keyword with after main symbol (and its context).

Input

1
2
3
4
5
6
7
lsystem RewriteRuleExample10 {
set iterations = 4;
set interpretEveryIteration = true;
set symbols axiom = A(2);
rewrite A(x) with z = x*(x-1) to B(z) A(z+1);
}
process all with SymbolPrinter;

Output

  1. A(2)
  2. B(2) A(3)
  3. B(2) B(6) A(7)
  4. B(2) B(6) B(42) A(43)
  5. B(2) B(6) B(42) B(1806) A(1807)

It is possible to define more than one local constant, they are separated with comma.

Input

1
2
3
4
5
6
7
lsystem RewriteRuleExample11 {
set iterations = 4;
set interpretEveryIteration = true;
set symbols axiom = A(1);
rewrite A(x) with a = 2x, b = a + 1 to A(b / a);
}
process all with SymbolPrinter;

Output

  1. A(1)
  2. A(1.5)
  3. A(1.33333333333333)
  4. A(1.375)
  5. A(1.36363636363636)

Conditional rewriting

Condition can be defined to determine whether to rewrite symbol or not. If the expression in condition (after keyword where) is true (non-zero) then the rewrite rule is applied. Otherwise is rewrite skipped and rewrite engine will try to find another rewrite rule for symbol.

Input

1
2
3
4
5
6
7
8
lsystem RewriteRuleExample12 {
set iterations = 3;
set interpretEveryIteration = true;
set symbols axiom = A(1) A(2) A(3) A(4) A(5);
rewrite A(x) where x % 3 == 0 to X;
rewrite A(x) to A(x + 1);
}
process all with SymbolPrinter;

Output

  1. A(1) A(2) A(3) A(4) A(5)
  2. A(2) A(3) X A(5) A(6)
  3. A(3) X X A(6) X
  4. X X X X X

Local constant definition and condition can be used together (first must be constant definition).

Input

1
2
3
4
5
6
7
lsystem RewriteRuleExample13 {
set iterations = 1;
set interpretEveryIteration = false;
set symbols axiom = A(1) A(2) A(-1) A(3) A(1);
rewrite A(x) with a = x*x where a == abs(x) to X;
}
process all with SymbolPrinter;

Output

X A(2) X A(3) X

Context with condition works as expected.

Input

1
2
3
4
5
6
7
8
lsystem RewriteRuleExample14 {
set iterations = 1;
set interpretEveryIteration = false;
set symbols axiom = A(1) A(2) A(-1) A(3) A(1);
rewrite {
A(a1) } A(a2) where a1 < a2 to X;
}
process all with SymbolPrinter;

Output

A(1) X A(-1) X A(1)

Stochastic rewriting

In rewrite rule can be defined more replacements than one. Then will be picked one replacement by random. In following examples is set randomSeed to keep examples deterministic (but still randomized). If randomSeed is set the result will be always the same. If you want to experiment with stochastic rewrite rules just delete definition of randomSeed, it will be generated seed by random. If you use stochastic rewrite rule and you randomly created output you especially like you can save random seed and use it to reproduce the output.

Input

1
2
3
4
5
6
7
8
lsystem RewriteRuleExample15 {
set iterations = 7;
set interpretEveryIteration = true;
set symbols axiom = A;
set randomSeed = 1;
rewrite A to B A or to C A;
}
process all with SymbolPrinter;

Output

  1. A
  2. B A
  3. B B A
  4. B B B A
  5. B B B C A
  6. B B B C C A
  7. B B B C C B A
  8. B B B C C B B A

Probability weight can be specified after each replacement to affect probability of individual replacements. Keyword or can be omitted.

Input

1
2
3
4
5
6
7
8
9
lsystem RewriteRuleExample16 {
set iterations = 7;
set interpretEveryIteration = true;
set symbols axiom = I I I I I I I I;
set randomSeed = 1;
rewrite I to I weight 4
to X weight 1;
}
process all with SymbolPrinter;

Output

  1. I I I I I I I I
  2. I I I I I I I X
  3. I I I I I X I X
  4. I I I I I X X X
  5. I I I I I X X X
  6. I I X X I X X X
  7. I I X X I X X X
  8. X X X X X X X X

Probability weight value can be expression (not only constant). If weight is less or equal to zero there is no chance to rewrite.

Input

1
2
3
4
5
6
7
8
9
lsystem RewriteRuleExample17 {
set iterations = 7;
set interpretEveryIteration = true;
set symbols axiom = I(-1) I(0) I(1) I(2);
set randomSeed = 1;
rewrite I(x) to I(x+1) weight 4
to X(0) weight x;
}
process all with SymbolPrinter;

Output

  1. I(-1) I(0) I(1) I(2)
  2. I(0) I(1) I(2) X(0)
  3. I(1) I(2) I(3) X(0)
  4. X(0) I(3) X(0) X(0)
  5. X(0) I(4) X(0) X(0)
  6. X(0) I(5) X(0) X(0)
  7. X(0) I(6) X(0) X(0)
  8. X(0) X(0) X(0) X(0)

Inheritance of rewrite rules

Basic rule which is applied in inheritance (and also in single L-system definition) is that newer definitions will replaces new ones. This is problem because rewrite rules can not be redefined. Even if rewrite rules are defined for symbol older can not be replaced by newer because they can rewrite under different conditions (like context or condition in rewrite rule). Order of rewrite rules is inverted by inheritance to allow redefine rewrite rules from base class, first are defined rewrite rules from derived L-system then r-rules from base class.

Input

1
2
3
4
5
6
7
8
9
10
abstract lsystem Base {
rewrite A to X;
rewrite B to X;
}
lsystem RewriteRuleExample18 extends Base {
set symbols axiom = A B;
set iterations = 1;
rewrite A to C;
}
process all with SymbolPrinter;

Output

C X

Everything at once

Every feature described on this page can be used in any combination. TODO

Formal grammar

Rewrite rule

1
rewrite_rule = 'rewrite' rr_pattern rr_consts? rr_condition? 'to' rr_replacement ';'

Rewrite rule pattern

1
2
3
4
5
6
7
rr_pattern = rr_context? symbol_opt_params rr_context?
 
symbol_opt_params = SYMBOL symbol_params?
symbol_params = '(' params_list? ')'
params_list = ID (',' ID)*
 
rr_context = '{' symbol_opt_params* '}'

Rewrite rule constants definition

1
2
3
rr_consts = 'with' rr_cost_defs_list
 
rr_cost_defs_list = ID '=' expression (',' rr_cost_defs_list)?

Rewrite rule condition

1
rr_condition = 'where' expression

Rewrite rule replacement

1
2
3
4
5
rr_replacements =
| symbol_expr_params* rr_weight? ('or'? 'to' rr_replacements)?
| 'nothing'
 
rr_weight = 'weight' expression