Equipage
Equipage is a concatenative programming language designed by Chris Pressey in early May 2018. Like Carriage, it is the result of trying to devise a "pure" concatenative language, i.e. one where the rule "concatenation = function composition" is taken to be strictly literal and universal (with no exceptions such as allowing nested quoted programs.) It is more successful than Carriage at achieving this goal.
In this context, "purely concatenative programming language" means:
- Every symbol in the language is associated with a function that takes stacks to stacks.
- The meaning of a program text is the sequential composition of the functions associated with those symbols.
Thus, the meaning of a program is a function that takes stacks to stacks. Since the program generally only deals with one stack at a time, it is also possible to think of this as a single stack ("the" stack) which gets modified over time.
The stack contains zero or more elements, and each element may be one of two kinds of values: unbounded integers, and functions which take stacks to stacks. The stack is generally accessed in a LIFO fashion, with a few strategic exceptions.
Here is a table mapping the legal Equipage symbols to functions.
! apply ; push *apply* onto the stack . push *compose* onto the stack $ push *pop* onto the stack \ push *swap* onto the stack + push *add* onto the stack - push *sub* onto the stack % push *sign* onto the stack ~ push *pick* onto the stack 1 push *one* onto the stack <space> nop
(where `<space>` represents any whitespace character.)
And here is an informal description of the functions named in the above table.
apply: pop a function off the stack and apply it to the rest of the stack
compose: pop a function g, then a function h, off the stack, then push g∘h
pop: pop a value off the stack and discard it
swap: pop a value a, then a value b, off the stack, then push a, then push b
add: pop a value a, then a value b, off the stack, then push a + b
sub: pop a value a, then a value b, off the stack, then push b - a
sign: pop a value off the stack, then push 1, 0, or -1, depending on its sign
pick: pop a value n off the stack, then copy the n'th element on the stack
and push it onto the stack. If n is negative, work from bottom of stack.
one: push the value 1 onto the stack
nop: do nothing to the stack. (identity function.)
Here is an example program text:
1!$!
Given the above table, this program maps to the function
push(one) ∘ apply ∘ push(pop) ∘ apply
which can be thought of operationally as doing the following when run:
- pushes the function `one` onto the stack
- pops the function `one` off the stack and applies it, which pushes the integer 1 onto the stack
- pushes the function `pop` onto the stack
- pops the function `pop` off the stack and applies it, which pops the integer 1 off the stack and discards it
Computational class
Equipage is Turing-complete; there are various possible constructions, but one of the simplest and easiest to understand is to simulate a two-counter Minsky machine. We'll use a specific construction in which there's an "active counter" and "inactive counter", with a command to change which counter is active, and with increments/decrements/zero-tests affecting the active counter. At all times after initial initialisation, the stack consists of a number of functions at the bottom, with the inactive counter above them and the active counter above that (and possibly a temporary or two above those).
The construction starts by placing a number of Minsky machine commands (which correspond to Equipage functions) onto the stack. For example, the Minsky machine command that increments the active counter requires running a composition of "one" and "add", so we want that composition on the stack. The functions will be listed below as the Equipage commands that push the function in question (rather than the commands that execute it, which can be different).
Each of the fragments at the bottom of the stack consists of two parts, a counter-changing part composed with a control-flow part. The counter-changing parts are pushed as follows (and multiple such parts can be composed together with .! to form a larger fragment):
- Increment:
1+.! - Decrement:
1\.!-.! - Swap counters:
\ - No-op:
\\.!
For control flow, each command effectively ends with a goto, specifying the command to run next. This starts by specifying the stack index of the command to run next (the stack has a known size at this point – it doesn't have any temporaries above the two counters – so the position of the next command to run will be known). This is a positive integer and is pushed by starting with 1 for 1, and 1+.!.! for successor (e.g. 3 would be encoded as 11+.!.!1+.!.!). If the command does not contain a zero test, then we finish off by composing the integer in question with a pick and apply, i.e. ~.!;.!. (Then one final .! composes the counter-changing part with the control-flow part, leaving us with a command that's ready to run; we just leave that on the stack and push the next such command.) Alternatively, if the program is meant to halt (i.e. there is no next command), we don't compose a control-flow portion.
In the case of a zero test, there are two possible "next commands", one that runs when the active counter is zero, the other when the active counter is positive (and the active counter being negative at this point is undefined behaviour). We require the commands in question to be in consecutive stack slots, with the is-zero command being numbered one less than the is-positive command (the existence of an unconditional goto means that this restriction has no effect on the power of the program). We start by pushing the stack index of the is-zero command as the "next command to run", but before composing the pick and apply with it, we run 1.!1.!+.!~.!%.!+.!, i.e. we're composing "push 1+1, pick, sign, add", i.e. we copy the active counter (the second stack element at this point), take its sign, and add it to the stack index we're going to run. When the ~.!;.! is added on, it'll run the command at the resulting stack index, i.e. the stack index we originally pushed (that of the is-zero command) if the active counter is zero, but the stack index below (that of the is-positive command) if the active counter is positive.
Finally, once we've set up the commands, we push initial values for the two counters (using 1! and +!), then the stack index of the first command (the same way), and pick with ~! and apply with ;!. Then the entire program will run, with each command running the appropriate next command in a tail-recursive way, until program execution finishes.