Recipe Book

: 🍂 🎉 🎉 > 🍂💕 ;
: 🌻 > 🍂 ;
: 🍂 > ❄️ ;
: ❄️ > 🌱 🎉 ;
: 🌱 > 🌻 ;

🍂

Recipe Book is a small multiset rewriting system written in Lua. It's hopefully small enough to be easy to modify, learn from, and expand upon.

It's worth noting that it's not the most robust engine. It has few peculiar edge cases such as empty rules (: > run-forever ;) and being space delimited (:> whoops this isn't a rule ; / : uh oh > this rule isn't actually closed;).

To run a program use the following command:

cat recipes/<program> | lua main.lua

Alternatively, you can enter a program from the command line and use ctrl-d to end your session.

Multisets

A multiset is an unordered collection of items. This collection allows for duplicate items to exist. Each duplicate encodes how much of that item is available in the set. A small example could be food you might have in your kitchen:

sugar oranges apples cherries flour apples

Rewriting

On its own, this doesn't do much of anything. However, a rewriting system allows us to define rules which modify our multiset. Let's call these recipes. Maybe we have a simple recipe book with the following:

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

Multiset Rewriting

Combining our ingredients and our recipes, we now have a program that can construct a fruit cake:

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

sugar oranges apples cherries flour apples

Looping

A rewriting engine will continue to rearrange your program as long as any rule matches. This allows you to construct loops and iterate over your multiset indefinitely. For example, a loop that counts to the 4th year one season at a time:

: spring year^4 > four-years-have-passed ;
: spring > summer ;
: summer > autumn ;
: autumn > winter ;
: winter > spring year ;

spring

Looping with a catalyst

A common pattern is to have a token that dictates what work to do:

: move-a cycle^10 > too-may-cycles ;


: move-a a > move-a b ;
: move-a > move-b ;

: move-b b > move-b a ;
: move-b > cycle move-a ;

a^10 move-a

Without : move-a cycle^10 >, this program would endlessly loop back and forth. However, with that rule, the catalyist for : move-a a > is removed. Thus, the process of turning a into b is no longer able to activate.

Iterating on Math

From here, you can build up various mathematical operations. Each operation iterates the tokens in your multiset to compute math in a form known as "unary". The four basic mathematical operations are adding two counters, subtracting two counters, dividing a counter by a constant, and multiplying a counter by a constant:

: a+b a > a+b c ;
: a+b b > a+b c ;
: a+b ;

: a-b a b > a-b   ;
: a-b a   > a-b c ;
: a-b b ;
: a-b   ;

: a*3 a > c c c ;
: a*3 ;

: a/3 a a a > c ;
: a/3 a ;
: a/3 ;

Ascending the Tower

From here, you can combine these principles into more and more general computing. This process of moving coins between cups is capable of expressing any computer program (give enough effort, cups, and coins). For example, using just the above ideas, you can compute the fibbonaci sequence:

: fib n > fib.shift ;

: fib.shift n1 > fib.shift N2 ;
: fib.shift n2  > fib.shift N1 N2 ;
: fib.shift      > fib.move ;

: fib.move N1 > fib.move n1 ;
: fib.move N2 > fib.move n2 ;
: fib.move   > fib ;

: last ; 
: fib  ; 

n^5 n1 n2 fib

Implementation originally by Devine Lu Linvega in their fractran article. That article is another great exploration of multiset rewriting through the lens of John Conway's Fractran.

Into the Great Unknown

Since I'm not looking to write a book (yet), I'll leave things here. There is much more to explore. Not just in multiset rewriting, but in rewriting systems in general. Consider for a moment if we extended recipe book with the ability to trigger Lua code? How much more would you be able to do with a system like that? What if tokens weren't all the same shape and color? What if they held messages and meaning? How could that add another layer of computational power?

If you do make something interesting, don't be shy about sending an email to the Horadric mailing list!