Luigi

Luigi is an esoteric programming language invented by Nathan van Doorn, which is based on L-systems, which are a kind of parallel string rewriting. (That is, they rewrite strings in parallel, not that they rewrite parallel strings.)

Background

The L-System was originally developed by not a computer scientist, but Hungarian botanist Aristid Lindenmayer, after whom it is named (the L is short for Lindenmayer), originally for documenting the growth of algae.

Structure

An L-system consists of two parts:

• The axiom, or initial state
• A set of production rules, consisting of two strings: the predecessor and the successor. If a character is not used on the left hand side of any production rule, it is assumed to have the Identity Rule, n->n.

These parts may contain any character, other than ';' (semicolon), '<' (less than) and '>' (more than). These symbols have special meanings. Newlines are ignored.

In Luigi, rules may not be ambiguous. However, context-sensitive rules (see below) take priority over normal rules. The structure of the program is as follows, with a semicolon at the beginning and the end, and between everything:

;axiom;predecessor;successor;predecessor;successor;etc.;

Context-sensitive rules

Context-sensitive rules are only activated if the predecessor part of a rule is after what is called the "left part", and before the "right part". This is expressed in the following format, where content in square brackets is optional:

 ;[left-part<]predecessor[>right-part];successor;

A rule with both a left part and a right part takes priority over a rule with just one, which in turn takes priority over a rule with none.

Computational class

Luigi is Turing-Complete, as it is possible to translate arbitrary Turing machines into it. For instance, the two-state five-colour universal Turing machine given at http://mathworld.wolfram.com/UniversalTuringMachine.html becomes:

;{initial-state}; a^;^b ;^b a; a^a;^b b; a^b;^b c; a^c;^b d; a^d;^b e; a^e;^c a;
 a^a;^c b; a^b;^c c; a^c;^c d; a^d;^c e; a^e;^d a; eva;^d b; evb;^d c; evc;^d d;
 evd;^d e; eve; e^;vd ; av;^c ;vb a; a^a;vb b; a^b;vb c; a^c;vb d; a^d;vb e; a^e
;vc a; e^a;vc b; e^b;vc c; e^c;vc d; e^d;vc e; e^e;vd a; eva;vd b; evb;vd c; evc
;vd d; evd;vd e; eve; ev;vc ;{;{a;};a};

Examples

Fibonacci Numbers

;a;a;b;b;ab;

The length of the data string in each iteration is a successive fibonacci number.

Thue-Morse sequence

;0;0;01;1;10;

Each iteration doubles the computed digits,.