Wanda

Wanda is a Forth-like, "concatenative" programming language that's arguably not concatenative at all, nor even "stack-based", because it's based on a string-rewriting semantics.

The remainder of this document will describe the language and will attempt to justify the above statement.

Basics

-> Tests for functionality "Run Wanda program"

A Wanda program is a string of symbols. Each symbol consists of one or more non-whitespace characters. In the string, symbols are separated by whitespace.

Here is a legal Wanda program. (The ===> is not part of the program; it only shows the expected result of running it.)

$ 2 3 + 4 *
===> 20 $

Evaluation happens by successively rewriting parts of this string of symbols. For example, in the above,

• $ 2 is rewritten into 2 $
• $ 3 is then rewritten into 3 $
• 2 3 $ + is then rewritten into 5 $
• $ 4 is then rewritten into 4 $
• finally, 5 4 $ * is rewritten into 20 $.

Rewrites occur when parts of the string match the pattern of one of the rewrite rules in effect. For instance, the rule for + has the pattern X Y $ +, where X and Y will match any integer symbols; the part of the string that matches this pattern is replaced by a single integer symbol which is the sum of X and Y, followed by a $.

You can think of $ as a symbol that delineates the stack (on the left) from the program (on the right). When constants are encountered in the program, they are pushed onto the stack.

But if you do think of it this way, bear in mind that it is only a convenient illusion. For, despite looking like and evaluating like a Forth program, there is no "stack" that is distinct from the program — it's all just a string that gets rewritten. 2 is neither an element on the stack, nor an instruction that pushes the value 2 onto the stack; it's just a 2.

Indeed, observe that, if no patterns match anywhere in the string, the expression remains unchanged and evaluation terminates:

2 $ +
===> 2 $ +

Some other builtins

We've seen + and *, which are built-in functions (or rules). There are a handful of other built-in functions (or rules).

$ 7 sgn 0 sgn -14 sgn
===> 1 0 -1 $

5 4 $ pop
===> 5 $

4 $ dup
===> 4 4 $

Defining functions

Wanda supports a special form for defining functions, which is very similar to Forth's : ... ; block. The main difference is that there is a -> symbol inside it, which you can think of as a way to making it explicit where the function naming ends and the function definition begins.

4 10 $
: $ perim -> $ + 2 * ;
perim
===> 28 $

You can in fact think of this special form as something that gets rewritten into nothingness (a zero-length string) and which introduces a new rule as a side effect. The new rule matches the function naming (in this case $ perim) and replaces it with its definition (in this case $ + 2 *), like so:

4 10 $ + 2 *

(And then evaluation continues as usual to obtain the final result.)

Some things to note:

This special form only gets rewritten when it appears immediately to the right of a $.

: $ foo -> $ ; $ 1 2 +
===> : $ foo -> $ ; 3 $

So, you can think of this special form as something that is "executed" in the same way the builtins we've described above are.

Rules defined this way are applied in the order in which they were defined. You can think of this as functions being redefined.

$
: $ ten -> $ 10 ;
ten
: $ ten -> $ 11 ;
ten
===> 10 11 $

Derivable operations

We can define functions for some common operations seen in other Forth-like languages, by deriving them from the built-in operations.

$
: $ abs -> $ dup sgn * ;
7 abs 0 abs -14 abs
===> 7 0 14 $

$
: $ abs -> $ dup sgn * ;
: $ not -> $ sgn abs 1 - abs ;
0 not 1 not -1 not 999 not -999 not
===> 1 0 0 0 0 $

$
: $ abs -> $ dup sgn * ;
: $ not -> $ sgn abs 1 - abs ;
: $ eq? -> $ - not ;
14 14 eq? 9 8 eq? -100 100 eq?
===> 1 0 0 $

$
: $ abs -> $ dup sgn * ;
: $ not -> $ sgn abs 1 - abs ;
: $ eq? -> $ - not ;
: $ gt? -> $ - sgn 1 eq? ;
5 4 gt? 5 5 gt? 5 6 gt?
===> 1 0 0 $

Recursion

If we include the name of the function in its own definition, recursion ought to happen. And indeed, it does. For example if we said

: $ fact -> $ dup 1 - fact * ;

then

3 $ fact

would rewrite to

3 $ dup 1 - fact *

which is fine, the next fact will get rewritten the same way in due course, all fine except for the troublesome matter of it never terminating because we haven't given a base case. Viewing the trace of execution for the first few steps makes this clear:

-> Tests for functionality "Trace Wanda program"

3 $
: $ fact -> $ dup 1 - fact * ;
fact
===> 3 $ fact
===> 3 $ dup 1 - fact *
===> 3 3 $ 1 - fact *
===> 3 3 1 $ - fact *
===> 3 2 $ fact *
===> 3 2 $ dup 1 - fact * *
===> 3 2 2 $ 1 - fact * *
===> 3 2 2 1 $ - fact * *
===> 3 2 1 $ fact * *
===> 3 2 1 $ dup 1 - fact * * *
===> 3 2 1 1 $ 1 - fact * * *
===> 3 2 1 1 1 $ - fact * * *
===> 3 2 1 0 $ fact * * *
===> 3 2 1 0 $ dup 1 - fact * * * *
===> 3 2 1 0 0 $ 1 - fact * * * *

-> Tests for functionality "Run Wanda program"

What would be great would be some way for 0 fact to be immediately rewritten into 1 instead of recursing.

Well, this is what the extra -> is for in a : ... ; block — so that we can specify both the pattern and the replacement. So, if we say

: 0 $ fact -> $ 1 ;

we have defined a rule which matches 0 $ fact and replaces it with $ 1 (which will immediately be rewritten to 1 $). Thus the recursion will now terminate.

$
: 0 $ fact -> $ 1 ;
: $ fact -> $ dup 1 - fact * ;
5 fact
===> 120 $

At first blush it may seem like the order of rule application matters in the above, but in fact it does not:

$
: $ fact -> $ dup 1 - fact * ;
: 0 $ fact -> $ 1 ;
5 fact
===> 120 $

This is because the string is searched left-to-right for the first match, and if the string contains 0 fact, this will always match a pattern of 0 fact before we're even in a position to check the parts of the string to the right of the 0 that would match the pattern fact.

Computational class

We can ask ourselves: if we stop here, what kinds of things can we compute with what we have so far?

Well, we have a first-in-first-out stack discipline, and it's well-known that if you have a strict stack discipline you have a push-down automaton, not a Turing machine.

If we had unbounded integers, and a division operation or swap, we might be able to make a 1- or 2-counter Minsky machine. But we don't have those operations, and I haven't said anything about the boundedness of integers yet.

And anyway, that all assumes this is a traditional stack-based language, which it's not! It's a string-rewriting language, and it naturally has access to the deep parts of the stack, because it goes and looks for patterns in them.

In fact, from this viewpoint, the language looks a lot like a deterministic version of Thue. Every time we define a function like

: $ not -> $ sgn abs 1 - abs ;

it's not unlike defining a rule in Thue like

$N::=$SA1-A

And Thue is Turing-complete, and the additional determinism isn't an impediment to what it can compute — a program which is written to accomodate an unspecified rewriting order (as Thue programs generally are) can be written to work the same way when the order is specified and fixed.

So, if we were to leave the language as it is so far, we could conclude it's Turing-complete. Which is great, but also somewhat unsatisfying. I'd like for Wanda to be more than just a Thue-in-Forth's-clothing.

So to make it more interesting, let's intentionally restrict the language so that we can't easily map programs to Thue programs.

We could say we have unbounded integers, but I don't think that helps (at least not without some other twist(s) that I don't see offhand) because you can just embed a finite alphabet a la Thue in your unbounded alphabet of integers.

But what if we place restrictions on the function definitions?

Specifically, let's say every rewrite rule must contain exactly one $ on the left and exactly one $ on the right.

This might seem to do the trick: you can now rewrite the string in only one place: around the leftmost $. That's a pretty big impediment.

Concretely, let's say that if you actually violate this constraint when defining a function, the Wanda implementation may flag up some kind of warning, but at any rate, it will erase the special form, but it not introduce any new rules.

$
: $ ten -> 10 ;
ten
===> $ ten

$
: ten -> $ 10 ;
ten
===> $ ten

$
: ten -> 10 ;
ten
===> $ ten

$
: $ $ ten -> $ 10 ;
ten
===> $ ten

$
: $ ten -> $ $ 10 ;
ten
===> $ ten

But this isn't quite enough, because you can add rules that move the $ around in the string. If you want to rewrite some other part of the string, you can just add some rules that move the $ there first.

So we'll make the restriction even stronger: on the right-hand side (but not necessarily the left-hand side), the single $ must always appear as the leftmost symbol.

$
: $ ten -> dix $ ;
ten
===> $ ten

$
: 10 $ ten -> $ dix ;
10 ten
===> $ dix

Anyway, the point is, this prevents us from ever writing a rule that moves the $ to the right. And so this prevents us from arbitrarily moving the $ around, which prevents us from being able to rewrite arbitrary parts of the string, which prevents it being Turing-complete in the way Thue is. But it continues to be able to express all the functions we've shown so far.

But what of the built-in functions? It's true that they allow us to move some information from the right of the $ in the string to the left. $ 10, for example, rewrites to 10 $. But each of these can only move a bounded amount of information, and this prevents us from getting to arbitrary parts of the string and rewriting them.

In fact, I think that this limits the kinds of rewrites that can be undertaken in exactly the same way a strict stack discipline does, i.e. it can only compute what a push-down automaton can compute.

But I have not got a proof of that. It may turn out, in fact, that even with these restrictions, the language is Turing-complete, due to something I've missed.

So, I'll hedge a bit, and I'll describe the feature that will be added in the next section like so: it makes Wanda Turing-complete, even if the language we've described so far already is.

Concrete Shoes

Let's introduce some built-in rules that allow us to manipulate values at the left end of the string, i.e. deep in the "stack".

In fact, since we're imagining part of this string is a "stack" anyway, we might as well go further and imagine it's a body of water.

To store a value on the left end of the string, what we'll do is "tie a weight" to it and let it "sink" to the bottom.

We should make "the bottom" explicit, as well. It will be the ) symbol.

) 1 2 3 4 5 $ 99 sink
===> ) 99 1 2 3 4 5 $

It might be illustrative to show the trace of this.

-> Tests for functionality "Trace Wanda program"

) 1 2 3 4 5 $ 99 sink
===> ) 1 2 3 4 $ 99 sink 5
===> ) 1 2 3 $ 99 sink 4 5
===> ) 1 2 $ 99 sink 3 4 5
===> ) 1 $ 99 sink 2 3 4 5
===> ) $ 99 sink 1 2 3 4 5
===> ) $ 99 1 2 3 4 5
===> ) 99 $ 1 2 3 4 5
===> ) 99 1 $ 2 3 4 5
===> ) 99 1 2 $ 3 4 5
===> ) 99 1 2 3 $ 4 5
===> ) 99 1 2 3 4 $ 5
===> ) 99 1 2 3 4 5 $

Note that after the value has "sunk", the $ will "bubble up" all by itself, assuming the values on the stack are integers.

It should now be straightforward to construct a Tag system in Wanda, by matching patterns at the top (i.e. at the right edge of the string), and, upon a successful match, "sinking" new values to the bottom (the left edge of string). And because Tag systems are Turing-complete and Wanda can simulate any Tag system, Wanda is Turing-complete.

History

Wanda was originally conceived in 2009 (I distinctly remember implementing the idea, in Haskell, on a laptop in a laundromat in Seattle), but it wasn't as developed as what you see here; the idea that a Forth-like language could be defined using string-rewriting semantics was there, but it didn't really carry through with it.

There are probably several reasons for this.

One is that I thought it should have a right-to-left rewriting order. I don't remember my reason for that (if I actually had one). It did not have the distinguished $ symbol, so this would have resulted in an odd (or at least unintuitive) order of evaluation, and I never really worked out the full implications of that.

Another is that, the way I was implementing it in Haskell, it would have been most natural to describe the reduction function with an infinite type. Discovering that Haskell did not support that "out of the box" was somewhat discouraging. Now, of course, I realize that you can fake that sort of thing with Haskell's newtype, but at the time it wasn't obvious.

Did it also seem like already-explored territory to me? Perhaps; it feels like I felt that way at some point. I don't think I had encountered Enchilada back then (I don't think I had even heard of "concatenative" languages at that time), but a year or two later, when I did learn there was already a stack-based rewriting-based language out there, it may have discouraged me further.

But Enchilada is really not all that similar to Wanda, and the idea and the desire to turn Wanda into a real (toy) language never really went away. So here we are.

Further Work

There may be more features that might be productively added to the language, if we wanted more from it than just showing that it's Turing-complete.

One logical extension would be, since we are able to sink values to the bottom of the stack, also be able to float them up from the bottom again. This would let the bottom of the stack be usable as a temporary storage area, rather than just as a way to use the string as a queue.

Another thing that seems attractive is the possibility for creating new rules that are not written statically in the initial program. (And possibly retracting existing rules too, but this seems less exciting.) But I haven't worked out a way to do this yet that I really like.

Happy nonconcatenativeing!
Chris Pressey
London, England
Feb 27, 2019