Rewriting languages are usually a series of rules that transform strings in a given alphabet, nodes in a tree or cells in a cellular automata.

A string rewriting system is based on an alphabet which is just a set of symbols. Strings over a given alphabet are arbitrary sequences of symbols, each taken from the alphabet. The empty sequence or null string is included. A string rewriting system consists of an alphabet and a relation ->, a set of such pairs or rules.

swap x y -> y x

These languages have multiple, distinct phases with different syntactic and semantic rules. There are often two phases; the first gives a set of rules, and the second provides objects on which those rules are to be applied.

swap foo bar ; bar foo

Fractran is a computer architecture based entirely on the multiplication of fractions.

A prime is a number that can only be divided by itself one, since these numbers can't be divided, they can considered the DNA of other numbers. The factoring of a number into prime numbers, for example: 18 = 2 × 3², exposes values which Fractran utilizes as registers. There are two parts to a Fractran program:

1. The Accumulator
2. The Fractions

The Accumulator

The Accumulator is a single number whose prime factorization holds the value of registers(2, 3, 5, 7, 11, 13, 17, ..). For example, if the state of the accumulator is 1008(2⁴ × 3² × 7), r2 has the value 4, r3 has the value 2, r7 has the value 1, and all other registers are unassigned.

The Fraction

A Fraction represents an instruction that tests one or more registers by the prime factors of its numerator and denominator. To evaluate the result of a rule we take the the accumulator, if multiplying it by this fraction will give us an integer, we will update the accumulator with the result.

if(r3 >= 1){ 
	r3 -= 1;
	r2 += 1;
	return;
}

if(r2 >= 6){ 
	r2 -= 6;
	r3 += 1;
	r5 += 1;
	return;
}

if(r2 >= 2 && r5 >= 1){ 
	r2 -= 2; 
	r5 -= 1; 
	r3 += 1; 
	r7 += 1;
	return;
}

Operations become more readable when broken down into their primes. We can think of every prime number as having a register which can take on non-negative integer values. Each fraction is an instruction that operates on some of the registers.

A Notation

While Fractran is commonly reduced to just another opaque esoteric language, portraying it as such is doing a disservice to the relatively simple idea at its core and to the researchers who might otherwise benefit by venturing deeper into a relatively unexplored field of computation.

Wryl, who created Modal, demonstrated to me an interesting connection between Fractran and rewriting languages. We need only to compile our rules and point the prime registers to symbols in a dictionary to see this relationship more clearly.

:: left side > right side (compiled: 15/6 left.2 side.3 > side.3 right.5)

AC 6 left side (initial state)
00 6 × 15/6 = 15, side right (result state)

This documentation will represent registers with names(x, y, foo-bar, baz, ..). Fractions will be written as rewrite rules starting with ::, a left-side, a spacer(>) and a right-side. The notation indicates which registers to replace on the left-side, and what to replace them with on the right-side.

Programming In Fractran

In a rule definition, we find symbols to the left-side of the spacer(>) to be rewritten by what is found on the right-side. Each new symbol is added to the dictionary and represented internally as a prime number.

:: flour sugar apples > apple-cake
:: apples oranges cherries > fruit-salad
:: fruit-salad apple-cake > fruit-cake

sugar oranges apples cherries flour apples

Rules are tested in a sequence from the first to the last, when a valid rewrite rule is encountered, the accumulator is updated, and the PC moved back at the first rule. In other words, it helps to visualize the fractions in a program as a list of rewrite rules that tests the accumulator against its left-side, and starts back at the top of the list after updating the accumulator when it is a match, or keep going when it does not.

AC 21450 flour sugar apples apples oranges cherries 
00 21450 × 7/30 = 5005, apples apple-cake oranges cherries 
01 5005 × 17/715 = 119, apple-cake fruit-salad 
02 119 × 19/119 = 19, fruit-cake 

• For each rule in the list for which the multiplication of the accumulator and the fraction is an integer, replace the accumulator by the result of that multiplication.
• Repeat this rule until no fraction in the list produces an integer when multiplied by the accumulator, then halt.

Logic & Arithmetic

Logic in rewrite rules is typically implemented as multiple rules, where each one is a potential combination, here is logical and as example:

:: x y and > true
:: x and > false
:: y and > false

AC 30 x y and 
00 30 × 7/30 = 7, true

You can get the sum of two registers by moving the value of one register into the other. The naming of the x register in advance ensures that the highest number will be stored in the lowest register:

:: x (Naming)
:: y > x

x x x x y y

You can get the difference between two registers by consuming the value of two registers at once, and moving the remains to the first:

:: x y >
:: y > x

AC 576 x x x x x x y y 
00 576 × 1/6 = 96, x x x x x y 
00 96 × 1/6 = 16, x x x x

You can get the product of two registers by keeping an intermediate result and state register. Keeping the resulting product, by naming the first register, prevents the accumulator grow too much in size:

:: r acc x y (Naming)
:: iter acc > x iter
:: iter >
:: x y > r acc y 
:: y > iter
:: x > 

AC 8575 x x y y y 
02 8575 × 42/35 = 10290, r acc x y y y 
02 10290 × 42/35 = 12348, r r acc acc y y y 
03 12348 × 11/7 = 19404, r r acc acc y y iter 
00 19404 × 55/33 = 32340, r r acc x y y iter 
00 32340 × 55/33 = 53900, r r x x y y iter 
01 53900 × 1/11 = 4900, r r x x y y 
02 4900 × 42/35 = 5880, r r r acc x y y 
02 5880 × 42/35 = 7056, r r r r acc acc y y 
03 7056 × 11/7 = 11088, r r r r acc acc y iter 
00 11088 × 55/33 = 18480, r r r r acc x y iter 
00 18480 × 55/33 = 30800, r r r r x x y iter 
01 30800 × 1/11 = 2800, r r r r x x y 
02 2800 × 42/35 = 3360, r r r r r acc x y 
02 3360 × 42/35 = 4032, r r r r r r acc acc y 
03 4032 × 11/7 = 6336, r r r r r r acc acc iter 
00 6336 × 55/33 = 10560, r r r r r r acc x iter 
00 10560 × 55/33 = 17600, r r r r r r x x iter 
01 17600 × 1/11 = 1600, r r r r r r x x 
04 1600 × 1/5 = 320, r r r r r r x 
04 320 × 1/5 = 64, r r r r r r

I/O

John Conway has not specified any way for the program to interface with the outside world, but others have offered schemes like assigning an alphabet to a series of registers. The advantage with symbolic rewriting is that registers are already assigned whole tokens, so we shall use those instead.

:: print foobar > hello world >

AC 6 print foobar 
00 6 × 35/6 = 35, hello world

>> hello world

This rule has a second spacer(>) which tells our interpreter to print the registers present in the accumulator after the application of the rule. For a more complete example, see fizzbuzz.

That's all!

Implementation

The rewriting implementation of the runtime can be implemented in about 200 lines.

cc fractran.c -o fractran view raw

• Fractran Interpreter(C89)
• Fractran Interpreter(Web)
• Intro to Fractran
• Article on Esolang
• Collatz function
• Remembering John Conway

Interaction nets are a graphical model of computation.

Interaction nets can capture all computable functions with rewriting rules, no external machinery such as copying a chunk of memory, or a garbage collector, is needed. Unlike models such as Turing machines, Lambda calculus, cellular automata, or combinators, an interaction net computational step can be defined as a constant time operation, and the model allows for parallelism in which many steps can take place at the same time.

1. Agents

An agent(a) is a cell that has one principal port and a number of auxiliary ports(n). A pair of agents connected together on their principal ports is called an active pair. Graphically, principal ports are distinguished by arrows.

The examples on this page will make use of four agents: Successor(increments a natural number), Zero, Add & Mul.

2. Interaction Nets

A net is an undirected graph of agents where each port is connected to another one by means of a wire. The following net has three free ports, x, y, and z. Note that a wire may connect two ports of the same agent. A rewriting of a net is performed only on an active pair according to an interaction rule.

3. Rewriting Rules

Here, rewriting is just a convenient word to express a very concrete notion of interaction, which we shall make precise by requiring some properties of rules:

• Agents interact only through their principal port.
• Each variable in a rule occurs exactly twice, once on each side.
• There is at most one rule for each pair of distinct symbols.

In an agent definition, the first port is the principal port, the rest of the ports are listed in the order obtained by moving anticlockwise round the agent. The following definition follows the interaction net at the left side of the rule 2 figure.

Net:
	Add(u,y,z), S(u,x)

Rule 1	Rule 2

In the following notation, an interaction rule consists of a pair of net descriptions separated by an arrow. Agents are capitalized, and free ports are lowercase.

Rules:
	Add(u,y,z), Z(u)   --> z-y
	Add(u,y,z), S(u,x) --> S(z,w), Add(x,y,w)

An interaction net to compute the result of 1 + 1 with the rules defined above, is shown below, where one active pair has been generated. We then show two reductions, which use the previous two rules. The final net, on the right-hand side, is of course the representation of 2, which is the expected answer.

Programming

From now on, we will use Inpla's notation for rules in which the principal ports are taken out of the brackets and their equivalent connection written as ><. When an agent has an arity of 0, the brackets are removed altogether. Thus, we can write the entire addition program as:

Rules:
	add(y, z) >< Z => y~z;
	add(y, z) >< S(x) => add(y, S(z))~x;
Exec:
	add(res,S(Z))~S(S(Z)); 1 + 2
	res; 
Result:
	S(S(S(Z))), or 3

When defining multiplication, note that the argument y is used twice in the first equation, and it is not used at all in the second one. For that reason, two extra symbols are needed duplicate and erase.

sx * y = (x + y) + y               0 * y = 0

The idea is that a net representing a natural number should be duplicated when it is connected to the principal port of a duplicate, and it should be erased when it is connected to the principal port of an erase.

The system of interaction combinators consists of three symbols, called combinators: y(constructor), d(duplicator), and e(eraser). The six interaction rules below are of two kinds: commutation when the two cells carry different symbols (yd, ye, de) and annihilation when they carry the same symbol (yy, dd, ee).

Note that the annihilations for y and d are not the same. Furthermore, if one numbers the auxiliary ports, one realizes that it is yy, not dd, which exchanges the ports:

• Interaction Nets
• Interaction Combinators
• Implementation of a low-level language for interaction nets, Shinya Sato
• Inpla, Interaction Nets as Programming Language
• Towards a Programming Language for Interaction Nets, Ian Mackie
• An Implementation Model for Interaction Nets
• Interaction Nets Playground
• Bologna Optimal Higher-Order Machine

Thue is a matrioshka esoteric computer based on string rewriting rules.

A Thue program consists of two parts: a list of substitution rules, which is terminated with a line having both sides of the operator empty, followed by a string representing the initial program state.

#::=Unused rules are comments
a::=~Hello Thue!
::=
[a] []

Execution consists of picking, from the list of rules, an arbitrary rule whose original string exists as a substring somewhere in the program state, and replacing that substring by the rule's replacement string. This process repeats until there are no rules that can be applied, at which point, the program ends.

#::=Increment binary number
1_::=1++
0_::=1
01++::=10
11++::=1++0
_0::=_
_1++::=10
::=
_10010011_ _10010100

Thue represents one of the simplest possible constraint-based programming language. It is to the constraint-based paradigm what languages like OISC are to the imperative paradigm.

Input

Added to this simple system are two strings which are used to permit Thue to communicate with the outside world. The first of these is the input symbol (":::"). The input symbol is actually the lhs of an implicit rule of which the user (or system's "input stream") is a component. The input symbol, therefore, is replaced by a line of text received from the "input stream."

Output

As a counterpart of input, the output symbol ("~") is supplied. Like the input symbol, the output symbol triggers an implicit rule which, in this case, encompasses the "output stream." The specific effect is that all text to the right of the output symbol in the rhs of a production is sent to the output stream.

Note that either (or both) of these implicit rules may be overridden by providing explicit rules that perform some other task.

#::=Sierpinski's triangle, backticks are linebreaks
X::=~_
Y::=~*
Z::=~`
_.::=._X
_*::=*_Y
._|::=.Z-|
*_|::=Z
..-::=.-.
**-::=*-.
*.-::=*-*
.*-::=.-*
@.-::=@_.
@*-::=@_*
::=
@_*...............................|

• On Esolangs
• Interpreter, written in Uxntal. Video
• Wanda, concatenative language meets string rewriting.

Modal is a programming language based on string rewriting.

Modal programs are represented as a series of substitution rules, applied to a given tree which gets continually modified until no rules match any given part of the tree. The principale elements of modal are:

• Rules: <> left right
• Registers: ?x, ?y, ?z
• Trees: word, (a tuple), a (cons (list))

The documentation below displays the examples as a series of rules, followed by the rewriting steps in the following format:

<> A rule

.. The input program
04 The result of applying rule #4
-1 The result of applying a lambda

Modal's evaluation model is based on scanning from left-to-right across a string that represents a serialized tree. We only match from the start of the string, and if we can't find a rule that matches, we move one token or subtree forward. All rules match against the start of the string, and if one matches, the matched pattern is erased, and the right-hand side of the rule is written to the end of the string.

Rules

To define a new rule, start with <>, followed by a left and a right statement, which is either a word, or a tree. The program evaluation starts at the first character of the string and walks through to the end trying to match a transformation rule from that location:

<> hello (good bye)  This is a rule

.. hello world       This is program data
00 good bye world    This is the result

Rules can be also be undefined using the >< operation that will try matching a previously declared rule's left statement:

<> cat owl
<> owl bat
<> owl rat
>< owl

.. cat 
00 owl 
02 rat

Modal is homoiconic, meaning that any string is a potential program and new rules can be composed directly during the evaluation. For instance, here is a rule that defines a new rules definition infix syntax:

<> (?x -> ?y) (<> ?x ?y)
fruit_a -> apple
fruit_b -> banana
(apple banana) -> fruit-salad

.. fruit_a fruit_b
01 apple fruit_b
02 apple banana
03 fruit-salad

Registers

Registers are single-character identifiers bound to an address in a pattern used in rewriting:

<> (copy ?a) (?a ?a)

.. copy cat
00 cat cat

When a register is used in a pattern, and when we try to match a given tree with a pattern, each register is bound to a corresponding an address to the left of a rule, and referenced to the right:

<> (swap ?x ?y) (?y ?x)

.. (swap fox rat)
00 (rat fox)

When a register appears more than once in a rule, each instance is bound to the first address, but differently named registers can still match on the same pattern:

<> ((?x ?x ?x)) match3
<> ((?x ?y)) match2

.. (fox fox fox) (bat bat) (bat cat)
00 match3 (bat bat) (bat cat)
01 match3 match2 (bat cat)
01 match3 match2 match2

Trees

Trees can be found in rules and program data, they include words, registers and nested trees. Rules can match specific trees and rewrite their content in a new sequence.

<> (rotate ?x (?y) ?z) (?y (?z) ?x)

.. rotate foo (bar) baz
00 bar (baz) foo

An efficient way to represent an array is to store information in nested lists, it allows for rules to target specific segments of the list, similarly to Lisp's car and cdr primitives. To print each element of such a structure, we can use the following recursive rules:

<> (putrec (?: ?x)) (putrec ?: ?x)
<> ((putrec (?:))) (?:)

.. (putrec (a (b (c (d (e))))))
00 (putrec (b (c (d (e)))))
00 (putrec (c (d (e))))
00 (putrec (d (e)))
00 (putrec (e))
01 

> abcde

Logic

Let us build a logic system, starting by comparing two registers:

<> (eq ?x ?x) (#t)
<> (eq ?x ?y) (#f)

.. (eq fox bat)
01 (#f)

We can implement the truth tables by defining each case:

<> (and #t #t) #t <> (or #t #t) #t 
<> (and #t #f) #f <> (or #t #f) #t
<> (and #f #t) #f <> (or #f #t) #t 
<> (and #f #f) #f <> (or #f #f) #f
<> (not #t) #f    <> (not #f) #t

.. (or #f #t)
08 (#t)

Building on the comparison rule above, we can write conditionals with a ternary statement:

<> (ife #t ?t ?f) (?t)
<> (ife #f ?t ?f) (?f)
<> (print ?:) (?:)

.. ife #f (print True!) (print False!)
13 (print False!)
14 ()

Types

Understanding how to use typeguard to reach a specific evaluation order is important to become proficient with Modal. Creating a type system is merely a matter of creating stricter rules expecting a specific grammar. Notice in the example below, how join-strings expects to match two String typed words. Without typed inputs, the rule is not matched.

<> (join-strings (String ?x) (String ?y)) (?x?y)

.. join-strings (String foo) (String bar)
00 foobar

Lambdas

A lambda is created by using the ?(body) special register. Rules created that way exist only for the length of one rewrite and must match what is found immediately after:

.. ?((?x ?y) (?y ?x)) foo bar
-1 bar foo

Outgoing Events

Sending a message is done with the ?: special register, it sends a word or a tree to be handled by a device:

<> (print ?:) (?:)

.. print (hello world\n)

hello world

Incoming Events

Similarly, listening to incoming messages is done with the ?~ special register:

<> (?: print) (?:)
<> (READ ?~) ((You said: ?~ \n) print)

.. (READ stdin)

You said: 

Special Registers Reference

The ?* special register explodes a token or tuple into a nested list, and the ?^ register to join it back into a single word. Notice how the following program makes use the List type to ensure a specific evaluation order:

<> (reverse List () ?^) (?^)
<> (reverse (?*)) (reverse List (?*) ())
<> (reverse List (?x ?y) ?z) (reverse List ?y (?x ?z))

.. (reverse (modal))
01 (reverse List (m (o (d (a (l ()))))) ())
02 (reverse List (o (d (a (l ())))) (m ()))
02 (reverse List (d (a (l ()))) (o (m ())))
02 (reverse List (a (l ())) (d (o (m ()))))
02 (reverse List (l ()) (a (d (o (m ())))))
02 (reverse List () (l (a (d (o (m ()))))))
00 (ladom)

sierpiński.modal

To review everything documented above, here is a small program that prints the Sierpiński triangle fractal:

?(?-) (Rules)

<> (* (. > (. ?x))) (* (. (. > ?x))) 
<> (. (. > (* ?x))) (* (. (* > ?x))) 

?(?-) (Physics)

<> (Tri > (?x ?y)) (Tri (?x > ?y))
<> (Tri (?x > (?y ?z))) (Tri (?x (?y > ?z)))
<> (?x (?y > (?z ?n))) (. (?y (?z > ?n)))
<> ((?x > ())) (< ())
<> (Tri < (* ?^)) (?(?: ?:) (*?^ \n))
<> ((?x < ?y)) (< (?x ?y))

?(?-) (Print)

<> (Tri.join ?x ?:) (Tri > ?x ?:)
<> (Tri.dup ?x ?^) (Tri.join ?x ?^)
<> (Tri < ?x) (Tri.dup (. ?x) (?x \n))

?(?* (Tri < (?*))) ...............*...............

Implementation

The language runtime can be implemented in about 300 lines.

cc modal.c -o modal view raw

• view sources, ANSI C.
• discord channel, in the concatenative server.
• Levels of Dynamic behavior in Modal
• This language is an original creation of wryl from 2018, who has courteously spent countless hours to help me progress with the language, much of the code above is derived from their research and merely made available here as to give this fantastic system a home on the internet.

incoming parade logic two dimensional fractran