Rewriting languages are typically made of rules and a starting state.

These languages often have two phases; the first gives a set of rules, and the second provides an accumulator on which those rules are to be applied. For example, a program for a string rewriting system with wildcards begins with a series of rules which define strings to match, a relation(->), and the resulting transformation.

rule            swap ?x ?y -> ?y ?x
accumulator     swap foo bar
transformation  bar foo

When a rule consumes a specific token during the application, we'll call this token the reagent. When a rule utilizes a specific token that survives the rewrite, we'll call it the catalyst.

dup a   -> a a  dup is a reagent
sub a b -> sub  sub is a catalyst

Bestiary

a ->

a b ->

b c -> a

a a -> a

a -> b

a -> b
b -> a

a -> b
b -> c
c -> a

a -> a a

a -> b b

a -> b c

• Pocket Rewriting, a multiset rewriting zine.
• Horadric, a rewriting mailing list.

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 >= 8){ 
	r2 -= 8;
	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 to venture deeper into a relatively unexplored field of computation.

Wryl, who created Modal, demonstrated to me an interesting connection between Fractran and rewriting languages which is made clearer by using a notation where prime registers are automatically assigned names, and fractions are defined in terms of transformations of these names:

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

AC 6 left side  accumulator
00 6 × 15/6 = 15, side right  result

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 denominator left-side, and what to replace them with on the numerator right-side. Unlike John Conway's original specification of Fractran, fractions are not reduced.

Programming In Fractran

In a rule definition, which is a fraction where prime factorization is written as names, we find names to the left-side of the spacer(>) to be rewritten by names found on the right-side. Each new name is added to the dictionary and represented internally as a prime number.

:: > A rule with no left-side is a comment.
:: 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 rewrite rule gives us an integer when when multiplied by the accumulator, the accumulator is updated by the product of that multiplication, and search for the next rule starts back again from the beginning.

:: 7/30 flour.2 sugar.3 apples.5 > apple-cake.7 
:: 17/715 apples.5 oranges.11 cherries.13 > fruit-salad.17 
:: 19/119 apple-cake.7 fruit-salad.17 > fruit-cake.19 

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 

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.

• For each fraction in a 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.

That's all!

Loops

Loops are a useful and common construct in programming, here is an example program in the imperative style that cycles through the four seasons until it reaches the autumn of the year two:

while(year++) {
	for(season = 0; season < 4; season++) {
		if(year == 2 && season == 3)
			return print("Reached!");
	}
}

To create a loop, a rewriting program relies on cycling back onto a term and the boundary of a loop is done by catching the ending case. Now, if we translate the above program into rewrite rules:

:: year year autumn > Reached!
:: spring > summer > autumn > winter > spring year

spring

Looking at the trace of the evaluation, we can see the following transformations:

AC 7, spring 
01 7 × 11/7 = 11, summer 
02 11 × 3/11 = 3, autumn 
03 3 × 13/3 = 13, winter 
04 13 × 14/13 = 14, year spring 
01 14 × 11/7 = 22, year summer 
02 22 × 3/11 = 6, year autumn 
03 6 × 13/3 = 26, year winter 
04 26 × 14/13 = 28, year^2 spring 
01 28 × 11/7 = 44, year^2 summer 
02 44 × 3/11 = 12, year^2 autumn 
00 12 × 5/12 = 5, Reached!

Logic

Binary logic is typically implemented as multiple rules, where each is a potential location in the truth table:

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

:: x y or > true
:: x   or > true
::   y or > true
::     or > false

:: x y xor > false
:: x   xor > true
::   y xor > true
::     xor > false

:: true  not > false
:: false not > true

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

The comparison operations are implemented using a loop that drains the registers until only the offset remains:

:: x y gth > gth
:: x   gth > true
::     gth > false

:: x y lth > lth
::   y lth > true
::     lth > false

:: x y equ > equ
:: x   equ > false
::   y equ > false
::     equ > true

:: x y neq > neq
:: x   neq > true
::   y neq > true
::     neq > false

AC 2160, x^4 y^3 gth 
00 2160 × 5/30 = 360, x^3 y^2 gth 
00 360 × 5/30 = 60, x^2 y gth 
00 60 × 5/30 = 10, x gth 
01 10 × 7/10 = 7, true 

Arithmetic

The sum of two registers(x+y) can be reached by writing the result in a third register(sum):

:: x   add > add sum
::   y add > add sum
::     add >

AC 2352, x^4 add y^2 
00 2352 × 15/6 = 5880, x^3 add sum y^2 
00 5880 × 15/6 = 14700, x^2 add sum^2 y^2 
00 14700 × 15/6 = 36750, x add sum^3 y^2 
00 36750 × 15/6 = 91875, add sum^4 y^2 
01 91875 × 15/21 = 65625, add sum^5 y 
01 65625 × 15/21 = 46875, add sum^6 
02 46875 × 1/3 = 15625, sum^6

Alternatively, the result can also be reached by moving the value of one register into the other:

:: y > x

AC 144 x^4 y^2
00 144 × 2/3 = 96, x^5 y
00 96 × 2/3 = 64, x^6

The difference between two registers(x-y) can be reached by consuming the value of two registers at once, and moving the remains into a third(pos) and fourth(neg) to get the signed result:

:: x y sub > sub
:: x   sub > sub pos
::   y sub > sub neg
::     sub >

AC 58320, x^4 y^6 sub 
00 58320 × 5/30 = 9720, x^3 y^5 sub 
00 9720 × 5/30 = 1620, x^2 y^4 sub 
00 1620 × 5/30 = 270, x y^3 sub 
00 270 × 5/30 = 45, y^2 sub 
02 45 × 55/15 = 165, y sub neg 
02 165 × 55/15 = 605, sub neg^2 
03 605 × 1/5 = 121, neg^2 

Alternatively, the result can also be reached by consuming the value of two registers at once, and moving the remains to the first if we want the result inside x:

:: x y >
::   y > x

AC 576 x^6 y^2
00 576 × 1/6 = 96, x^5 y 
00 96 × 1/6 = 16, x^4

The doubling of a register(x*2) is a matter of incrementing an output register twice for each input register values:

:: x double > res res double
::   double >

AC 48, x^4 double 
00 48 × 75/6 = 600, x^3 double res^2 
00 600 × 75/6 = 7500, x^2 double res^4 
00 7500 × 75/6 = 93750, x double res^6 
00 93750 × 75/6 = 1171875, double res^8 
01 1171875 × 1/3 = 390625, res^8

The halving of a register(x/2) is a matter of decrementing an input register twice for each output register value:

:: x x half > res half
::     half > 

AC 48, x^4 half 
00 48 × 15/12 = 60, x^2 half res 
00 60 × 15/12 = 75, half res^2 
01 75 × 1/3 = 25, res^2

To find the result of x*(y+z), in which a sequence of operation is needed to find the correct answer, the operator precedence, or order in which operators will be evaluated, is dictated by the rules order:

:: add z      > add y 

:: mul x y    > mul x acc res
:: mul        > mulrec
:: mulrec acc > mulrec y
:: mulrec x   > mul

x^2 y^3 z^4 add mul
x^2 y^7 mul
res^14

Example: Fibonacci

Let's have a look at a real program to generate the Fibonacci Sequence(1, 1, 2, 3, 5, 8, 13, 21, 34..). This program uses catalysts(fib, fib.shift, fib.move) to keep the program state which has 3 phases(shift, move and back to fib) and ensures the correct evaluation order:

:: > Shift the scrolling window to show two numbers

:: fib n last > fib n B
:: fib n res  > fib n A B
:: fib n      > fibrec

:: > Move the temporary registers back by one number

:: fibrec A > fibrec last
:: fibrec B > fibrec res
:: fibrec   > fib

:: > Cleanup temporary registers at the end of the program

:: last > 
:: fib  > 

:: > Find the fib number equal to the value in n register

AC 6240, n^5 last res fib
..
08 15869140625 × 1/13 = 1220703125, res^13 

Example: Tic-Tac-Toe

Fractran's output capability is limited to the resulting accumulator at the end of an evaluation. The advantage of symbolic rewriting is that registers are already assigned names, so we shall print those instead. As for input, we can type in new symbol tokens and appending their value to the accumulator between evaluations. We can implement a tic-tac-toe in a mere 16 rules:

:: > Reserve the first registers for the player moves

:: x#a o#a x#b o#b x#c o#c
:: x#d o#d x#e o#e x#f o#f
:: x#g o#g x#h o#h x#i o#i

:: > This register remains active until the game ends

game

:: > A symbol to draw the value of registers in a grid

"

  Set move in the format x#a, o#b, x#c, etc:

  a b c  |  {x#a o#a .} {x#b o#b .} {x#c o#c .}
  d e f  |  {x#d o#d .} {x#e o#e .} {x#f o#f .}
  g h i  |  {x#g o#g .} {x#h o#h .} {x#i o#i .}

 "

:: > Rules for each possible victory states

:: game x#a x#b x#c > x#a x#b x#c "Player X wins!" 
:: game o#a o#b o#c > o#a o#b o#c "Player O wins!"
:: game x#d x#e x#f > x#d x#e x#f "Player X wins!" 
:: game o#d o#e o#f > o#d o#e o#f "Player O wins!"
:: game x#g x#h x#i > x#g x#h x#i "Player X wins!" 
:: game o#g o#h o#i > o#g o#h o#i "Player O wins!"
:: game x#a x#e x#i > x#a x#e x#i "Player X wins!" 
:: game o#a o#e o#i > o#a o#e o#i "Player O wins!"
:: game x#g x#e x#c > x#g x#e x#c "Player X wins!" 
:: game o#g o#e o#c > o#g o#e o#c "Player O wins!"
:: game x#a x#d x#g > x#a x#d x#g "Player X wins!" 
:: game o#a o#d o#g > o#a o#d o#g "Player O wins!"
:: game x#b x#e x#h > x#b x#e x#h "Player X wins!" 
:: game o#b o#e o#h > o#b o#e o#h "Player O wins!"
:: game x#c x#f x#i > x#c x#f x#i "Player X wins!" 
:: game o#c o#f o#i > o#c o#f o#i "Player O wins!"

Program don't need to specify anything other than these 16 rules, as players can already input their moves in the format of its register names: x#a, o#b, x#c, etc.

  Set move in the format x#a, o#b, x#c, etc:

  a b c  |  x o o
  d e f  |  . x .
  g h i  |  . . x

  Player X wins!

A Fractran program specifies the wiring and logic of an interactive application, registers point to symbols in memory and so the bytecode itself is never localized as these strings reside in the application's front-end far from its logic.

Example: Fizzbuzz

Alternatively to getting the resulting program state at the end of an evaluation, we can emit the accumulator at a specific rate during the evaluation by checking if a register is active or not.

:: > Reserve the first registers for the increments and base-10

:: +5 +3
:: 1# 2# 3# 4# 5# 6# 7# 8# 9# 0
:: 1  2  3  4  5  6  7  8  9

:: > Leave the printing register for no more than one rewrite

:: print: fizz >
:: print: buzz >
:: print: fizzbuzz >
:: print: "{1# 2# 3# 4# 5# 6# 7# 8# 9# 0}{1 2 3 4 5 6 7 8 9}" > 

:: > Fizzbuzz logic

:: eval +3 +3 +3 +5 +5 +5 +5 +5 > print: fizzbuzz
:: eval +3 +3 +3 > print: fizz
:: eval +5 +5 +5 +5 +5 > print: buzz
:: eval > print: "{1# 2# 3# 4# 5# 6# 7# 8# 9# 0}{1 2 3 4 5 6 7 8 9}"

:: > Base-10 numbers

:: 1# 9 > 2# 0 +3 +5 eval
:: 2# 9 > 3# 0 +3 +5 eval
:: 3# 9 > 4# 0 +3 +5 eval
:: 4# 9 > 5# 0 +3 +5 eval
:: 5# 9 > 6# 0 +3 +5 eval
:: 6# 9 > 7# 0 +3 +5 eval
:: 7# 9 > 8# 0 +3 +5 eval
:: 8# 9 > 9# 0 +3 +5 eval
:: 9# 9 > 

:: 0 > 1 +3 +5 eval
:: 1 > 2 +3 +5 eval
:: 2 > 3 +3 +5 eval
:: 3 > 4 +3 +5 eval
:: 4 > 5 +3 +5 eval
:: 5 > 6 +3 +5 eval
:: 6 > 7 +3 +5 eval
:: 7 > 8 +3 +5 eval
:: 8 > 9 +3 +5 eval
:: 9 > 1# 0 +3 +5 eval

:: > The initial state

0

During the evaluation, these 27 fractions will toggle r79(print:) giving us a trigger when the accumulator state might be read. This is demonstrated here as an alternative approach for emitting programs and debugging where the runtime is masking lower registers to the printing register.

07 25338 × 7979/103 = 1962834      01 
07 159444 × 7979/103 = 12351492    02 
05 1045656 × 6557/2781 = 2465432   fizz 
07 262032 × 7979/103 = 20298576    04 
06 1750176 × 7031/3296 = 3733461   buzz 
05 339282 × 6557/2781 = 799954     fizz 
07 82812 × 7979/103 = 6415116      07 
07 526536 × 7979/103 = 40788648    08 
05 3248208 × 6557/2781 = 7658576   fizz 
06 1829280 × 7031/3296 = 3902205   buzz 
07 380070 × 7979/103 = 29442510    11 
05 2391660 × 6557/2781 = 5639020   fizz 
07 580920 × 7979/103 = 45001560    13 
07 3930480 × 7979/103 = 304478640  14 
04 26252640 × 7663/88992 = 2260585 fizzbuzz 
07 188490 × 7979/103 = 14601570    16 
07 1242180 × 7979/103 = 96226740   17 
05 7898040 × 6557/2781 = 18621880  fizz
..

Example: Stack Machines

A stack-machine can be implemented in Fractran, but it's not for the faint of heart. This computation model keeps an entire program state in a single number, and the following stack machine allocates a whole stack into a single register of that number. The theory is that it is possible to keep a stack of zeros and ones in a single register using a binary encoding for that number.

• Pushing a 0 onto the stack is equivalent to doubling the number.
• Pushing a 1 is equivalent to doubling and adding 1.
• Popping is equivalent to dividing by 2, where the remainder is the number.

If we begin with push, we can see that we are doubling the x register, same as demonstrated above. After the evaluation, our LIFO stack has a value of 30, and is equal to 1 1 1 0, where the right-most one is the item on top. Now, for pop, we can halve the x register, again, same as demonstrated above, and keeping the result of the value in a register for 0, and a register for 1.

:: push 1 x > A A push 1
:: push 1 > x
:: push 0 x > A A push 0
:: push 0 >

:: pop x x > A pop
:: pop x   > 1
:: pop     > 0

:: A A > x x
:: A > x

x    push 1 = x^3
x^3  push 1 = x^7
x^7  push 1 = x^15
x^13 push 0 = x^30

x^30 pop : 0 x^15
x^15 pop : 1 x^7
x^7  pop : 1 x^3
x^3  pop : 1 x

We can build on these two primitives and define temporary register to keep the result of popping, extra stack operations dup and swap, and a little state-machine to input some of these commands:

:: ?#a 0 > 0#a :: ?#a 1 > 1#a
:: ?#b 0 > 0#b :: ?#b 1 > 1#b

:: dup > pop ?#a dup-next
:: dup-next 0#a > 0#a 0#a push-a push-a 
:: dup-next 1#a > 1#a 1#a push-a push-a 

:: swap > swap-next pop ?#a 
:: swap-next > swap-last pop ?#b push-a
:: swap-last > push-b

:: push-a 0#a > push 0
:: push-a 1#a > push 1
:: push-b 0#b > push 0
:: push-b 1#b > push 1

:: 1) > push 1 2) 1
:: 2) > push 1 3) 1 1
:: 3) > push 1 4) 1 1 1
:: 4) > push 0 5) 1 1 1 0
:: 5) > swap   6) 1 1 0 1
:: 6) > dup       1 1 0 1 1

1) x 

To explore further, try running these examples yourself:

• Conway's Game Of Life in Conway's Fractran(video)
• The Collatz Sequence
• Divide

Reduction & Catalysts

Conway's Fractran traditionally compared the accumulator against reduced fractions, but computationally-speaking, getting to the gcd of a fraction does little more than getting rid of otherwise valuable information used during comparison to match against a restricted set of fractions. The support for catalysts, symbols found on both sides of a rewrite rule, makes for a simpler implementation and a more usable runtime.

:: 15/6 red green > green blue
:: 5/2 red > blue

red green

These two fractions are not equal and reducing the first into the second, eliminates the capability to match against it only when the catalyst green is present in the accumulator:

Deadcode Elimination

An unreachable rule is created when a rule's left-hand side is part of the left-hand side of a rule below it:

:: foo > baz
:: foo bar > baz

foo bar

For a rule to be reachable, all the symbols in the left-hand side must be present in either the right-hand side of an other valid rule, or in the accumulator.

:: violet > red
:: purple > violet

violet

Rules that are unreachable are considered comments and should not be part of the ruleset during evaluation.

Exhaustive Rules

When moving values between registers, each move takes one rewriting and thus can quickly become computationally expensive:

:: a > res
:: b > res

AC 1000, a^3 b^3 
00 1000 × 3/2 = 1500, a^2 res b^3 
00 1500 × 3/2 = 2250, a res^2 b^3 
00 2250 × 3/2 = 3375, res^3 b^3 
01 3375 × 3/5 = 2025, res^4 b^2 
01 2025 × 3/5 = 1215, res^5 b 
01 1215 × 3/5 = 729, res^6 

Completed in 6 steps.

A rule with a right-hand side that does not include symbols present in any of the left-hand sides of the rules above it can be run exhaustively and perform many applications without having to look for the next applicable rule:

AC 1000, a^3 b^3 
00 1000 × 3/2 = 3375, res^3 b^3 
01 3375 × 3/5 = 729, res^6 

Completed in 2 steps.

Reversibility

Fractran operators are reversible, meaning that a some programs can run backward to their original state. Evaluation is undone by applying rules and inverting their numerator and denominator, or right and left sides.

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

For a program to be reversible, two rules may not share identical numerators or denominators. The implementation of a reversible CNOT logic gate differs from the non-reversible logic gates in that we cannot rely on the absence of registers, rules must contain symbols for their absence:

:: c+ t+ cnot > c+ t- cnot
:: c+ t- cnot > c+ t+ cnot
:: c- t+ cnot > c- t+ cnot
:: c- t- cnot > c- t- cnot

Implementation

A basic implementation of the runtime core is a mere 20 lines:

cc framin.c -o framin view raw

An implementation of the full symbolic runtime is about 300 lines:

cc fractran.c -o fractran view raw

• Fractran Interpreter(C89), used for this documentation.
• Fractran Interpreter(Web)
• Intro to Fractran
• Remembering John Conway
• On Esolang

Vera is a multiset rewriting system.

Vera is a multiset rewriting system designed to converse with computers, created by the same author as Modal. A program is made entirely of facts and rules:

|| The first character in a file assigns a spacer glyph.
|| A program is made of rules and facts.

|| Two spacers indicate the creation of facts
|| Facts are separated by commas, a matchbox, a log, paper

| A rule has a left side | And a right side.
| Facts on the left side | are replaced by facts in the right side

| a flame, a log | a warm fire
| a matchbox | a match, a match, a box
| a match, paper | a flame

Spacer

The first character in a file assigns a spacer glyph to be used to indicate rules and facts, the pipe character | is most commonly used:

| this is a rule |
|| this is a fact, this is another fact

Facts

A fact is the name for an item in the bag, the bag is the collection of all existing facts. A line starting with two spacing characters(also called an empty rule) will add facts to the bag, facts are comma separated:

|| a fact, another fact
|| one more fact,
	yet another,
	a last fact

Whitespace only exists to separate the words in a fact, but are not significant when matching facts. These 3 facts are equal:

|| a new fact, a   new fact, a new   fact

Multiple instances of the same facts can be created by using the colon character. There are same amount of instances of these two facts:

|| a, a, a, a, b:4

Rules

A rule is made of a left and often a right side, and indicate facts to remove and replace in the bag.

| a fact, another fact | the result
| another rule | another result
| a rule may not have a right side | 

Evaluation

In turn, each rule is matched against the existing facts found in the bag, starting from the first rule, when a rule's left-hand side is found in the bag, these facts are replaced by the rule's right-hand side, and matching is started again from the top.

|flour, sugar, apples| apple cake
|apples, oranges, cherries| fruit salad
|fruit salad, apple cake| fruit cake

|| sugar, oranges, apples, apples, cherries, flour

Vera will match any amount found in the left-hand side, the following two rules are equivalent in Vera:

| an apple, hunger | a core
| an apple, an apple, an apple, hunger | a core

Comments

Vera will discard a rule when all the facts found in its left-hand side are not present in any rule's right-hand side or declared as facts.

| yellow | This is a comment.
| purple | This is not a comment.
| # | This is also a comment.
|| purple

Implementation

The language runtime can be implemented in about 200 lines.

cc vera.c -o vera view raw

• Vera Interpreter(C89), used for this documentation.
• A Raven's Flyby, tutorial.
• Vera Wiki

Thue is a string-rewriting system.

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

I/O

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

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.

Interaction nets are a graph rewriting system.

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(triangles).

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
• ia2d, haskell.
• Interaction Nets Playground
• Bologna Optimal Higher-Order Machine

Modal is a tree rewriting system.

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 (nested (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 pocket rewriting tote parade logic two dimensional fractran fractran thue interaction nets