[Scrap] Rewriting Systems and Concatenative Languages
Some meandering thoughts on these approaches to programing. This article was initially written in November 2024. I don't usually date my wikithing pages but this one feels worth pinning its place in time.
Concatenative langauges (hereafter called "Catlangs") and rewriting systems (henceforth called "Rewriting") have been two topics of interst. Catlangs and rewriting are inheriently connected. The connection between the two has been on my mind as of late. There is a tension in my mind despite catlangs being a subset of rewriting systems. This page serves as my means of moving through them.
Concatenative Programming
From the very start, catlangs have been analyzed through the lens of rewriting rules. Brent Kerby used a notation similiar to rewriting rules found in Modal.
[B] [A] swap == [A] [B]
[A] dup == [A] [A]
[A] zap ==
The items left of == will be consumed and replaced by the
items on the right. This notation is derived from the syntax used by
Joy,
a programming langauge by the late Manfred von Thun. Manfred himself
even explored the relationship of
catlangs
and rewriting.
A core tenet of catlangs is the idea of "juxtaposition is composition". If you take two programs, and concatenate them, the result is another valid program. Functions and there definitions are freely exchange able. To achieve thise catlangs are inherently point-free.
"points" are a jargon term for "variables" and their creation. A point-free language means you can write code without the need of binding data to names
The "point-free" nature is most easily and directly expressed using
a stack. For example, the following is a point-free implementation of
pythagorean theorem: dup * swap dup * + sqrt. This is
generally the form catlangs have taken. One advantage of RPN is that
it's trivial to get started with implementing. You'll have a language
up and running in a few hours.
The down side to this is there is an inherient limitation here. Data often needs to get move out of the way. Additionally, a machine with *only* one stack is not turing complete. This is why languages such as Forth, uxn, Factor, and other stack-langs implicitly or explicity rely on multiple stacks.
But there is still a problem here. Catlangs typically have ordered access to data. This can restrict you in numerous ways. Many catlangs employ the usage of local bindings. However, this breaks many properties of concatenation. Values are now dependent on their local context making code hard to refactor and more tightly bound.
This is where we must look outwards from our small island and to the broader world of rewriting.
Rewriting Systems
Rewriting systems are an approach to programming that can be summarized in a very sussinct way: find and replace. Rules define how your state is shaped on ever iteration of the rule book. Take the following program:
: {hello #42} > {the meaning of life} :
: {hello $thing} > {goodbye $thing} :
{hello "sheep"} {hello #42} {hello "lizar"} {hello "sheep"}
This program describes the process of moving data from
{hello *} to {goodbye *}, with the exception of
{hello #42}. However, notce how at no point did I actually
describe the follow of information here. The only thing this program has
is rules and data. The rules will be applied to the data repeatedly
until there are no more rules to be applied.
I'm free to reach across my state and pluck data from various places. This may seem similiar to how you are used to programing via the applications of functions and methods to data. But, like catlangs, the data is implicitly shared between all the rules.
This freedom to reach across the ailse makes rewriting systems uniquely suited for modeling interactions. Additionally, it means programs are fully composeable. You take two rule sets and join to gether and they will form a fully valid program.