rewriteString stream variant of a lindenmayer system
An initial stream, the axiom, is recursively rewritten, using a set
of production rules. In a classic lindenmayer system (L-system),
each level of rewriting is done at once, rewriting the whole string.
This can be also done in a depth-first traversal through all levels, taking in a stream and resulting in a stream.
The L-system's restrictions to a general generative grammar is a fixed order in which the
rules are applied, and no principal distinction between terminal and nonterminal symbols.
If one of the two special characters "<" and ">" appear in a set of rules,
they are interpreted as context in order to form a context-sensitive generative grammar. Everything that falls outside the closure suc as A and B in A<X>B are not rewritten - X is rewritten only if AXB match.
The class Prewrite by James McCartney does a similar thing with objects, whereby their
identity is used as a lookup. This is more efficient, but does not allow for the combinatorics
that a pure string rewriting system does.
Julian Rohrhuber, 2005.
// stream a string as axiom. 1 level of rewiting
(
var axiom, rules;
axiom = "hello Aristide".iter; // create a stream from a string
rules = [
"r" -> "rr",
"i" -> "ou",
"u" -> "i"
];
z = axiom.rewriteString(rules);
z.all.join; // stream all characters into one string
)
// the same doing the rewriting all at once:
(
var rules;
rules = [
"r" -> "rr",
"i" -> "ou",
"u" -> "i"
];
"hello Aristide".rewriteString(rules);
)
// cantor set
"_".rewriteString(["_" -> "_ _", " " -> " "], 4);
// fibonacci numbers
(
var r;
r = "A";
10.do {
r = r.rewriteString(["A" -> "B", "B" -> "AB"]);
r.postln;
r.size.postln;
}
)
// thue-morse L-system
(
var r;
r = "a";
6.do {
r = r.rewriteString(["a" -> "ab", "b" -> "ba"]);
r.postln;
}
)
// streaming the 45th..50th generation of an l-system
(
var z;
(45..50).do { arg i;
z = Pseq("aaa", 1).asStream.rewriteString(["a" -> "bb", "b" -> "abb"], i);
z.nextN(40).reject(_.isNil).join.postln;
}
)
// using a stream as axiom has certain advantages,
// because it does not have to be known from the beginning.
// it would be even possible to make the axiom dependent on the productions.
// using a random stream of letters as axiom
(
k = Prout { 50.do { "abcde".choose.yield } };
c = [
"a" ->"aa", "b" -> "bb", "c" -> "dd", "d" -> "dxx", "x" -> "y"
];
)
// 1 level of rewriting
(
z = k.asStream.rewriteString(c);
z.all.join;
)
// 5 levels of rewriting
(
z = k.asStream.rewriteString(c, 5); // 5 x rewriting
z.all.join;
)
// if the input stream returns nil, the output stream finishes and returns nil asl well.
// it can be resumend if the input stream resumes.
(
a = "abc";
k = Prout { 100.do { a.yield } };
z = k.asStream.rewriteString(c, 5); // 5 x rewriting
z.nextN(20).join.postln;
a = nil;
z.nextN(50).join.postln;
a = "c";
z.nextN(50).join.postln;
""
)
// increasing the level of rewriting by reusing the same stream
(
r = "hello aristide".iter;
c = [
"r" -> "ri",
"i" -> "ou",
"u" -> "i"
];
z = r.rewriteString(c,8);
)
// calculate the first 8 characters
z.nextN(5).join;
// now add a next level and continue streaming:
(
z = z.rewriteString(c);
z.nextN(8).join;
)
// take the rest
z.all.join;
// the rules can contain functions as values. The function is evaluated passing in
// the current string cache, the rewriting level (generation) and the rules themselves.
(
k = Prout { 3.do { "abcd".choose.yield } };
c = [
"a" -> "xaa",
"b" -> "x",
"d" -> "dxx",
"c" -> { arg count, level, rules; if(level.even) {"Z"} {"P"} },
]
)
// post 5 variations
(
5.do {
var z;
z = k.asStream.rewriteString(c, 6);
z.all.join.postcs;
"\n".post;
}
)
// a stochastic thue-morse L-system.
// systems like this resemble markov chains
(
var r;
r = "a";
8.do {
r = r.rewriteString([
"a" -> { ["ab", "b"].choose },
"b" -> { ["ba", "a"].choose }
]);
r.postln;
}
)
// context-sensitive chomsky-grammar:
// "X<A>Y", where X,A,Y is any number of characters.
(
var rules;
r = "xuabcyyyyxcccxx";
rules = [
"a<b>c" -> "Z",
"xx" -> "?",
"y<xcc" -> "P",
"x>u" -> "...",
"." -> "_.",
"Zcc" -> "abc"
];
r.rewriteString(rules, 1).postcs;
r.rewriteString(rules, 2).postcs;
r.rewriteString(rules, 3).postcs;
r.rewriteString(rules, 4).postcs;
r.rewriteString(rules, 5).postcs;
""
)
/* returns:
"...uaZccyyyyPc?"
"_._._.uaabcyyyyPc?"
"__.__.__.uaaZccyyyyPc?"
"___.___.___.uaaabcyyyyPc?"
"____.____.____.uaaaZccyyyyPc?"
*/
// classical context-sensitive l-system for modeling movement along an axis
(
var r, rules;
r = "aa......aa......";
rules = [
"a<." -> "a",
"a>a" -> "."
];
15.do { |i|
r.postcs;
r = r.rewriteString(rules, 1);
};
)
// Penrose tile (without screen graphics)
(
var angle = 36 / 360 * 2pi;
var r = "[X]++[X]++[X]++[X]++[X]";
var rules = [
"W" -> "YF++ZF----XF[-YF----WF]++ ",
"X" -> "+YF--ZF[---WF--XF]+",
"Y" -> "-WF++XF[+++YF++ZF]-",
"Z" -> "--YF++++WF[+ZF++++XF]--XF",
"F" -> ""
];
2.do {
r = r.rewriteString(rules).postln
}
)
// sound examples ////////////////////////////////////////////////////////
(
SynthDef("sinegrain",
{ arg out=0, freq=440, dur=0.05;
var env;
env = EnvGen.kr(Env.perc(0.01, dur, 0.2), doneAction:2);
Out.ar(out, SinOsc.ar(freq, 0, env))
}).memStore;
)
// translating characters in melody
(
k = Pseq("ab");
c = [
"a" -> "ba",
"b" -> "ca"
];
d = Dictionary[
$a -> 0,
$b -> 5,
$c -> 3
];
z = Pdict(d, // apply homomorphism (final translation)
k.asStream.rewriteString(c, 5)
);
Pbind(
\instrument, \sinegrain,
\degree, z,
\dur, 0.1
).play;
)
// which is the same as:
(
k = Pseq([0, 5]);
c = IdentityDictionary[
0 -> [5, 0],
5 -> [3, 0]
];
z = Prewrite(k, c, 5);
Pbind(
\instrument, \sinegrain,
\degree, z,
\dur, 0.1
).play;
)
// the following would be hard with Prewrite, because
// the new string is a combination of previous ones
// ("aa" -> "_", "ab" -> "c")
(
k = Pseq("abx");
c = [
"aa" -> "_",
"ab" -> "c",
"a" -> "ba",
"b" -> "ca",
"c" -> "ac"
];
d = Dictionary[
$a -> 0,
$b -> 5,
$c -> 3,
$_ -> 8,
$x -> [5, 7]
];
k.asStream.rewriteString(c, 10).all.join.postln;
z = Pdict(d, k.asStream.rewriteString(c, 10));
Pbind(
\instrument, \sinegrain,
\degree, z,
\octave, 5,
\dur, 0.1
).play;
)
// two levels in parallel:
(
k = Pseq("abx");
c = [
"aa" -> "_",
"a" -> "ba",
"b" -> "ca",
"c" -> "ac"
];
d = Dictionary[
$a -> 0,
$b -> 5,
$c -> 3,
$_ -> 9,
$x -> Pseq((0..15), 2) // end phrase
];
z = Ptuple([
Pdict(d, k.asStream.rewriteString(c, 8)),
Pdict(d, k.asStream.rewriteString(c, 9)) + 2 // modal transpose
]).trace;
Pbind(
\instrument, \sinegrain,
\degree, z,
\dur, 0.1
).play;
)
// rule order tests /////////////////////////////////////////////////////////
// the rules are applied in order. The first match is used to translate
// the current string.
(
k = Pseq("ba");
c = [
"ab" -> "c",
"a" -> "ba"
];
k.asStream.rewriteString(c, 6).all.join.postcs; // "bbbbbbba"
)
(
k = Pseq("ab");
c = [
"ab" -> "c",
"a" -> "ba"
];
k.asStream.rewriteString(c, 6).all.join.postcs; // "c"
)
(
k = Pseq("ab");
c = [
"a" -> "ba",
"ab" -> "c"
];
k.asStream.rewriteString(c, 6).all.join.postcs; // "bbbbbbab"
)
// Links on the net:
http://www.math.okstate.edu/mathdept/dynamics/lecnotes/node15.html
http://en.wikipedia.org/wiki/Lindenmayer_system
http://en.wikipedia.org/wiki/Chomsky_grammar
http://swiki.hfbk-hamburg.de:8888/MusicTechnology/279
http://www.avatar.com.au/courses/Lsystems/
//////////////////////////////////////////
(
var w, b, u, f, z, level=0;
w = SCWindow("test", Rect(40, 240, 200, 200)).front;
w.view.decorator = FlowLayout(w.bounds.copy.left_(30).top_(30));
b = { |i| { |j|
var c = ({ "abcd".choose } ! 3).join;
SCButton(w, Rect(0,0, 30,25))
.states_([[c, Color.black]])
.action_({ f.(c) })
.font_(Font(\Georgia, 11))
} ! 4; w.view.decorator.nextLine } ! 4;
w.view.decorator.nextLine;
SCButton(w, Rect(0,0, 30,25))
.states_({ |i| [i.asString, Color.black]} ! 16)
.action_({ |b| level = b.value });
r = [
"aa" -> "aba.b",
"ba" -> "....aa",
"c" -> "ddba",
"." -> "b.",
"dd" -> { #[".c", "c.", "ld"].choose }
];
(
SynthDef(\p, { |out = 0, freq=400, amp=0.4, sustain=0.04|
OffsetOut.ar(out,
SinOsc.ar(freq)
* XLine.ar(amp, amp * 0.001, sustain, doneAction: 2)
);
}).memStore;
);
u = { |str|
fork {
var m = str.iter.rewriteString(r, level);
var b;
Char.nl.post;
loop {
b = m.next;
if(a.notNil and: b.isNil) { "\n".post };
(b ? "").post;
if(b.isNil) { nil.yield };
Synth.grain(\p, [\freq, b.ascii - 97 * 200 + 300]);
0.04.wait;
}
}
};
f = { |c| u.(c); };
w.onClose = { u.stop };
)