Rewriting Systems

A rewriting system is an approach to programming where you combine two things: rules and state.

Rules

Rules are what define how you transform your state. Rules are made of two parts: conditions and results. conditions are a set of patterns which define the what a rule needs for it to fire. The results are what happen when that rules runs. They translate to a very simple mode of logic. For example take these rules:

: sock-on-ground > picking-up-sock ;
: picking-up-sock > holding-sock ;
: holding-sock drawer-empty > put-sock-away ;

These rules define the process of seeing a sock on the ground and putting it away. These rules are run in a loop until no rule is able to be applied. In this case, out sock program will run until all the socks of the ground.

State

State is the information at hand. There are many ways to structure this information. You can use sets, bags, queues, trees, stacks, etc. For example, Modal uses a queue that holds a tree of nested strings:

<> ((hello ?what)) ((goodbye ?what))

(hello raven) (hello sheep) (hello lizar)

The sock program uses what's known as a "multiset". A multiset is an unordered collection of items that allow multiples of those items in itself. Real life examples of multisets include a the inventory of a store, a recipe, and a mancala board.

: autumn year year year year > second-autumn ;
: summer > autumn ;
: autumn > winter ;
: winter > sprint year ;
: sprint > summer ;

autumn

Thue, the esoteric turing tarpit, represents its state as a plain string. It's rules are additionally applied in a random order to this string. Despite these seemingly restricted and unmanagable features, Thue is turing complete. Here is an example of Thue generating the Sierpinski trangle pattern:

#::=Sierpinski's triangle, HTML version
#::=By Nikita Ayzikovsky
X::=~ 
Y::=~*
Z::=~<br>
_.::=._X
_*::=*_Y
._|::=.Z-|
*_|::=Z
..-::=.-.
**-::=*-.
*.-::=*-*
.*-::=.-*
@.-::=@_.
@*-::=@_*
::=
@_*...............................|

Applications

Rewriting is a rich space to explore. A lot of the academic literature focuses on term writing and formal verfication. Two topics outside my realm of understanding. However, there are some folks exploring how to apply these systems to graphical applications, real-time programming, and the wider software crisis at hand. Further more these systems naturally lend themselves to being expressed in visual means:

🫴 🍂 🎉 🎉 🫳 🍂💕 🤲
🫴 🌻 🫳 🍂 🤲
🫴 🍂 🫳 ❄️ 🤲
🫴 ❄️ 🫳 🌱 🎉 🤲
🫴 🌱 🫳 🌻 🤲

🍂

If you are interested in taking the dive, You can find some of us on the Horadric mailing list.

"The software winter is always bountiful when the computing is weird."
— Capital