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 th