Notes: Stack Operations for String Rewriting

This is a very brief notecard about something I've been working on. This kinda serves as a means of documenting my thoughts and what lead to this synthesis. Skip to Synthesis if you just want the thingy and not the rambling story of getting there. Also, since these are notes, expect them to be pretty messy.

Fusion of Ideas

Relational Machine Calculus

Jon Purdy introduce me to "Relational Machine Calculus". Apparently, AGAIN reminded them of this concept. In the paper it describes a stack machine with multiple named stacks and prolog-style variables that unify with values.

[X]foo foo<3>

I don't fully grasp the ideas here. I only really understand the machine presented. The examples don't really illustrate much for me (I feel like I'm missing prior experience / knowledge). They also don't really give an idea of how unification will work mechanically. For me, mechanics matter more than theory-based description. So, I just kinda let it mull about in the back of my mind.

Rejoice (and uxn)

For a while now, I've been mulling over a sequential, stack-based assembly language for Nova. More generally, I've been really trying to describe string rewriting in general using an assembly language for a stack machine. Every attempt has resisted my efforts. Until, Devine release Rejoice which had me thinking about this idea again.

( The forge contains 3 ingots of lead )
lead^3

( Double the amount of ingots, add the philosopher's stone )
lead^lead stone

( The philosopher stone turns four ingots into gold )
'gold/[stone lead^4]

( Inspect the result )
take ."It's " [True Fool]/[take gold]

@Fool  .pyrite.. End
@True  .gold! @End

It's a concatenative-flavored assembly language for multiset rewriting. "Fractions" like a/x describe a rewriting operation: given x, I'll give you a. I've been struggling to write a clean parser for the language. I tend to prefer LL(k) parsers. Ideally, LL(1) with no need to look ahead. Rejoice's fraction syntax makes that rather hard as you have to scan until you find a / or space before knowing what else to parse.

My frustration with Rejoice syntax eventually lead me to the thought of making the denominator of fractions independent. uxn has this syntax for anonymous "unless blocks": ?{ ( only runs if the top-of-stack is 0 ) }. So, I thought, why not borrow this, invert the condition, and make my machine "signal failure". So, something like a/x becomes /x { a }. "Attempt to take x. If that succeeded, give a". That immediately resolved my parsing issues, but also lead to synthesizing a new idea.

Synthesis

Move and Unify, or Fail

The core of the idea was a multistack machine based on symbol unification. Unification would be described by the following actions:

• Pop from current stack.
• If target stack is empty, move popped value to target
• If target stack is non-empty:
• If top of stack matches, discard value and flag success
• Otherwise, return value and flag failure

The Operations

The core operations are as followed using a notation I came up with.

$foo

Push value from current stack, to foo

!foo

Pop value from foo to current stack

&foo

Peek value from foo to current stack

~foo

Unify top of current stack with foo using above method

Each of these operations can fail. When they do, the interpreter shall set a flag that conditional blocks can observe. Additionally, these are the only push, pop, peek, and unify can fail. Everything else always succeeds.

Well, unless I find reason for something else to fail. This is all notes

A Contrived Example

Lets give this language some additional pieces of syntax: the aforementioned {}, @Label to mark an address to jump to, \Label to preform an unconditional jump, and %add for an addition operation. We can describe a loop that counts up to ten as followed:

10 $stop-at 0 @Count
    ~stop-at { \Done }
    1 %add \Count
@Done

First, we move 10 onto the target stack. Then we push 0 to the current stack. Next we mark the start of our loop (@Count). ~target { |Done } attempts to unify the top of the current stack with target this will only succeed once we've counted to ten. 1 %add \Count begines the next iteration of this loop.

I think this gives me the basis of a stack-machine that can describe string rewriting nicely. Currently working on implementing small assembly and interpreter. It's current named Squirm just cause I couldn't think of anything better.