Rewriting ReQ style

Last time I spent a while drawing little diagrams indicating what the old ReQ interpreter dynamics were like, in preparation for writing a new updated version with some improvements.

I realized something interesting, as I did about the seventeenth revision of what should have been a “simple example”.

As you’ll recall, the dynamics of ReQ centers around the dynamics of a queue, and specifically the functional application of some items to other items in that queue. That is, we (1) remove the function currently at the head of the queue, (2) look through the queue for the first item that can act as any of its arguments, (3) remove the first argument we find (if it exists), and (4) enqueue the result of partially applying the function to that argument. If we don’t find an argument, but the function does want one, we simply enqueue it, as it was, at the tail of the queue.

Function application as rewriting

As I wrote one of the previous examples out, I stumbled dozens of times along the way. I kept wanting to skip steps: specifically, I wanted the swap example involving non-default energies to work out faster, so I kept skipping intermediate steps and stages of the eternally cycling arguments around the queue.

This one:

[swap₂(Any,Any) 1₂ 2₂ 3₂ 4₂]
[2₂ 3₂ 4₂ swap₁(Any,Any) swap₁(1₂,Any)]
[3₂ 4₂ swap₁(Any,Any) swap₁(1₂,Any) 2₁]
[4₂ swap₁(Any,Any) swap₁(1₂,Any) 2₁ 3₁]
[swap₁(Any,Any) swap₁(1₂,Any) 2₁ 3₁ 4₁]
[2₁ 3₁ 4₁ swap₁(swap₁(1₂,Any),Any)]
[3₁ 4₁ swap₁(swap₁(1₂,Any),Any) 2₁]
[4₁ swap₁(swap₁(1₂,Any),Any) 2₁ 3₁]
[3₁ 4₁ 2₁ swap₁(1₂,Any)]
[4₁ 2₁ swap₁(1₂,Any) 3₁]
[2₁ swap₁(1₂,Any) 3₁ 4₁]
[swap₁(1₂,Any) 3₁ 4₁ 2₁]
[4₁ 2₁ 3₁ 1₂]
[2₁ 3₁ 1₂ 4₁]
[3₁ 1₂ 4₁ 2₁]
[4₁ 2₁ 3₁ 1₁]
...

I’m still not sure it’s correct. I made mistakes at least a dozen times as I worked it out by hand. Probably because of that swap₁(swap₁(1₂,Any),Any) that crops up in the middle.

Anyway, the repetition of the exercise until I finally got it right made me daydream a little. Or maybe the daydreaming made me repeat it because I was getting distracted. Whatever. The idea happened, is what I’m saying.

Let me propose a little abstract thing for exploration.

Same dynamics as the basic ReQ interpreter, but instead of familiar scalar constants and intention-communicating function names, let me use just plain letters.

These letters will still represent functions, just as in ReQ, but they will be abstract functions. Some of them will take no arguments, some will take one or more arguments. If they take no arguments, then they will be executed (producing their results) as soon as they’re at the head of the queue. If they take arguments, then they will consume the first argument they encounter, if one exists, and then enqueue the result of consuming that argument at the tail.

One additional quirk, though: There can be some of these functions which have multiple signatures. For example, b() -> c is a function that takes no arguments and produces a c, while b(b) -> a is one that takes a single argument b and produces a new a. If both of these two “rules” (or “signatures”, if you prefer) are listed in the grammar I am about to show you, then the first rule is checked first against all items in the queue, and then the second one, and so on.

Ready?

Here’s a simple grammar I’ve been playing with in some sketches:

a()  -> b
b(c) -> c b a
b()  -> a c
c(c) -> d a

What happens when I “run the ReQ program” containing a single a, under these rules? Let’s see if I can do it without fucking it up again.

[a]
[b]
[a c]
[c b]
[b c]
[c b a]
[b a c]
[a c b a]
[c b a b]
[b a b c]
[a b c b a]
[b c b a b]
[b a b c b a]
[a b b a c b a]
[b b a c b a b]
[b a b a b c b a]
[a b a b b a c b a]
[b a b b a c b a b]
[a b b a b a b c b a]
[b b a b a b c b a b]
[b a b a b b a b c b a]
[a b a b b a b b a c b a]
[b a b b a b b a c b a b]
[a b b a b b a b a b c b a]
[b a b b a b a b b a b c b a]
[a b b a b a b b a b b a c b a]
[b b a b a b b a b b a c b a b]
[b a b a b b a b b a b a b c b a]
(and so on)

That’s interesting, if a little dry. Is it all that happens? Not under all starting conditions, no:

a()  -> b
b(c) -> c b a
b()  -> a c
c(c) -> d a

[c c c c]
[c c d a]
[d a d a]
[a d a d]
[d a d b]
[a d b d]
[d b d b]
[b d b d]
[d b d a c]
[d a d c b a]
[a d c b a d]
[d c b a d b]
[a d b d c b a]
[d b d c b a b]
[b d c b a b d]
[d b a b d c b a]
(and so on)

So apparently not. This little term-rewriting system based on a queue does some different things under different circumstances. It makes me wonder what language it defines, in the sense of being a relatively simple automaton following deterministic rules.

Oh but wait, it doesn’t have to follow deterministic rules, does it? If these are indeed algorithmic functions of the arguments, they could just as readily be probabilistic functions of those arguments. They could return samples from some distribution. Or whole distributions. They could return other partially-applied functions not present in the left hand sides of the grammar, even; for instance, I might consider a rule like c(b) -> (x(d) -> (c c)), which would replace c(b) with a new function x(d) that would produce a (c c) when and if a d comes into its hands.

Those grammar rules look a lot like the type signatures of functions, don’t they?

But I’ve been thinking of grammars, not type systems (ahem). I wonder what sort of traditional automaton one could use to capture the sort of (deterministic, term-rewriting) dynamics in my little sketch examples.

I also wonder what sort of effect the ReQ rules about partial application of functions will have, and how quickly that might expand the state space of the underlying automata.

For example, what if we had some rules in the “grammar” like these?

...
c(a,b) -> b a c
c(b,a) -> c a b
c(c)   -> a a
...

Based on the ReQ rule of greedy, order-independent argument capture, that first rule would grab either an a or b, whichever appears first in the queue, and produce a partial function result like c(a,«b») or c(«a»,b). Here, I’m using the notation f(«x») to indicate a missing argument that is supposed to be x, as if it were an item missing from a type signature I suppose.

Would that second rule, c(b,a) -> c a b, ever fire at all? I don’t think so, but I could be wrong. I’m quite sure that under the assumption that every rule is checked in toto over the entire queue, before the next rule is examined, it cannot possibly fire, because the first rule would consume any a or b it found, and the second rule also wants the same arguments and no others. As a result, the first rule would “silence” the second.

That said, the third rule could still be triggered if there are no a or b characters in the queue. So maybe it is the empty intersection—or if you prefer, the total overlap—between the set of arguments {a,b} in c(a,b) and c(b,a) that is causing the first to overshadow of the second?

If—and I am not suggesting this, just musing—the rule for function application was to look for the first missing argument only, and to fail if it is not found, then there would be a very different relationship between these two rules. The first rule would only look for a, and then fail over to the second, which would look for b. They would not be mutually exclusive, there.

As a counterexample, under the (regular ReQ) dynamics, these two rules do not interfere with one another all the time:

...
c(a,b)   -> b a c
c(b,a,c) -> c a b
c(c)     -> a a
...

The second rule, in this case, could be triggered and partially applied first if there were no a or b arguments in the queue, but there was a c. For example:

...
[c c d c d]
[d c d c(«b»,«a»,c)]
...

But of course, the third rule is now silenced and overshadowed by the second, which will eat all the c arguments before the third rule is considered.

In any case, this is just a note to myself, jotting down some pokes at what I’ve been pondering a bit today. It’s an interesting variant on familiar grammar schemes, especially when the partial application stuff kicks in.

Well, and also it might be interesting when combinators and higher-order functions show up, like swap and map.

But leave that for another day.