Equipage
========
<!--
SPDX-FileCopyrightText: Chris Pressey, the original author of this work, has dedicated it to the public domain.
For more information, please refer to <https://unlicense.org/>
SPDX-License-Identifier: Unlicense
-->
_Try it online_ [@ catseye.tc](https://catseye.tc/installation/Equipage)
| _Wiki entry_ [@ esolangs.org](https://esolangs.org/wiki/Equipage)
| _See also:_ [Carriage](https://codeberg.org/catseye/Carriage#carriage)
∘ [Wagon](https://codeberg.org/catseye/Wagon#wagon)
∘ [Oxcart](https://codeberg.org/catseye/Oxcart#oxcart)
- - - -
Equipage is the language that [Carriage][] might have been had I not been
so concerned about quoting. (See "[Discussion: Quoting][]", below.)
Equipage is a purely concatenative programming language. In this context,
that 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.)
So. 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
The remainder of this document gives some examples of Equipage programs,
which also serve as test cases, and then discusses some aspects of the
language's design.
[Carriage]: http://esolangs.org/wiki/Carriage
[Discussion: Quoting]: #discussion-quoting
Equipage Tests
--------------
-> Tests for functionality "Interpret Equipage Program"
-> Functionality "Interpret Equipage Program" is implemented by
-> shell command "bin/equipage %(test-body-file)"
-> Functionality "Interpret Equipage Program" is implemented by
-> shell command
-> "python3 impl/equipage.py/equipage.py %(test-body-file)"
one, apply
----------
Pushing numbers on the stack. Note stacks are outputted top-to-bottom.
1!
===> [1]
1!1!
===> [1,1]
apply (deferred)
----------------
apply, as a function which is pushed onto the stack.
1;!
===> [1]
add
---
Pop two values, then push their sum.
1!1!+!
===> [2]
nop
---
Space and newline are both whitespace is nop.
1! 1!1!+!
1!1!+!1!+!
===> [3,2,1]
swap, pop
---------
Test `\` (swap) and `$` (pop).
1! 1!1!+! 1!1!+!1!+! \!$!
===> [3,1]
sub
---
Test `-`.
1! 1!1!+! 1!1!+!1!+! +!+! 1!-!
===> [5]
sign
----
Test `%` (sign).
1!1!+!1!+! %!
===> [1]
1!1!-!1!-! %!
===> [-1]
1!1!-! %!
===> [0]
pick
----
pick with a positive index picks from the top of the stack.
1! 1!1!+! 1!1!+!1!+! 1! ~!
===> [3,3,2,1]
1! 1!1!+! 1!1!+!1!+! 1!1!+! ~!
===> [2,3,2,1]
Picking from the very top of the stack has the effect of
duplicating the top stack element, so the idiom for `dup`
found in some other languages is `1!~!`.
pick with a negative index picks from the bottom of the stack.
1! 1!1!+! 1!1!+!1!+! 1!1!-!1!-! ~!
===> [1,3,2,1]
1! 1!1!+! 1!1!+!1!+! 1!1!-!1!-!1!-! ~!
===> [2,3,2,1]
pick with a zero index is zero, always.
1! 1!1!+! 1!1!+!1!+! 1!1!-! ~!
===> [0,3,2,1]
compose
-------
Compose pop and swap into a single function, and apply it.
1! 1!1!+! 1!1!+!1!+! \$.! !
===> [3,1]
idiom: compose + pick + apply = call
------------------------------------
One idiom we forsee being used in Equipage is creating re-usable
functions using composition (on primitives and other functions)
and storing them at the bottom of the stack. When one wishes to
use one of these functions, one would pick it using its known
(negative!) index, and apply it.
Create a function which pushes 2 onto the stack, and apply it
several times.
11+.!.!
1!1!-!1!-!~!;!
1!1!-!1!-!~!;!
1!1!-!1!-!~!;!
===> [2,2,2,<fn>]
(Yes, the code to fetch and apply the function, is longer than
the function itself. So it goes.)
Create a function which doubles the value on the stack, and
apply it to 1 several times.
1~+.!.!
1!
1!1!-!1!-!~!;!
1!1!-!1!-!~!;!
1!1!-!1!-!~!;!
===> [8,<fn>]
idiom: sign + pick = if
-----------------------
If we push a onto the stack, then b, then take the sign of a value,
then add one, then perform a pick, we will get a if the value was
positive and b if the value was zero. If a and b are functions,
we can then apply the one we get.
In this example, a is 2, b is 3, and the value is zero.
1!1!+! 1!1!+!1!+!
1!1!-!
%!1!+!~!
===> [3,3,2]
In this example, a is 2, b is 3, and the value is 4.
1!1!+! 1!1!+!1!+!
1!1!+!1!1!+!+!
%!1!+!~!
===> [2,3,2]
It's possible to do a variant of this that picks from the bottom
of the stack. We'll see how to do that in a more exhaustive test
below.
idiom: pick self + apply = loop
-------------------------------
'self' could be provided any number of ways, but if the function
that's currently executing is one of the common utility functions
from the bottom of the stack (first idiom), it's simplest to
just pick it like that.
This is an infinite loop. For that reason, it's not written as a
Falderal test.
11-1-~;.!.!.!.!.!.!
1!1!-!1!-!~!;!
finally: if + loop = while loop
-------------------------------
Let's pop all values off the stack until we hit a zero, and then stop.
Pseudocode:
def f1:
duplicate value on stack
if it is zero,
stop
else,
pop it off
f1
push 2, 0, 2, 1
f1
The result should be `[0,2,<functions>]`.
Working out the pseudocode a bit:
def f1:
duplicate value on stack
take the sign
if it is zero,
f3 (i.e. -3, pick, apply)
else,
f2 (i.e. -2, pick, apply)
def f2:
pop a value off the stack
f1
def f3:
do nothing
push 2, 0, 2, 1
f1
Translating the pseudocode to Equipage:
1~%1-1-1-~;
.!.!.!.!.!.!.!.!.!.!
$11-1-~;
.!.!.!.!.!.!.!
1$
.!
11+11-11+1
.!.!.!.!.!.!.!.!.!
!
11-1-~;
.!.!.!.!.!.!
!
Let's test these parts in isolation a bit maybe.
Initial stack:
11+11-11+1
.!.!.!.!.!.!.!.!.!
!
===> [1,2,0,2]
Nop:
1$
.!
!
===> []
Run f1 initially (here, f1 is nop):
1$
.!
11-1-~;
.!.!.!.!.!.!
!
===> [<fn>]
Everything but run.
1~%1-1-1-~;
.!.!.!.!.!.!.!.!.!.!
$11-1-~;
.!.!.!.!.!.!.!
1$
.!
11+11-11+1
.!.!.!.!.!.!.!.!.!
!
11-1-~;
.!.!.!.!.!.!
===> [<fn>,1,2,0,2,<fn>,<fn>,<fn>]
The final result:
1~%1-1-1-~;
.!.!.!.!.!.!.!.!.!.!
$11-1-~;
.!.!.!.!.!.!.!
1$
.!
11+11-11+1
.!.!.!.!.!.!.!.!.!
!
11-1-~;
.!.!.!.!.!.!
!
===> [0,2,<fn>,<fn>,<fn>]
Discussion: Computational Class
-------------------------------
Equipage stores data on a LIFO stack; thus there is reason to suspect that
it might not be Turing-complete, as it cannot access data arbitrarily.
However, we should consider the following:
* The `swap` function allows us to access the top two elements on the
stack arbitrarily, and an element can be an integer value, with no
bounds imposed on its size. Equipage can increment, decrement, and
branch if the value is zero. Therefore it seems plausible that one
could implement a 2-counter [Minsky machine][] in Equipage.
* The `pick` function allows us to read from the bottom of the stack
(but not write to it.) Careful manipulation of the index from which
values are being picked might allow one to simulate a queue in the
upper portion of an ever-growing stack, and it seems plausible that
this queue could be used to implement a [Tag system][].
* Finally, Equipage allows the construction of new functions from
existing functions through composition; data and data structures can
be encoded in these functions in the manner of [Church numerals][];
and it seems plausible that, given a Turing machine, one could
construct an Equipage function which, when applied, simulates one
step (or many steps) of that machine, simply by evaluating to a
suitably modified version of itself.
[Minsky machine]: http://esolangs.org/wiki/Minsky_machine
[Tag system]: http://esolangs.org/wiki/Tag_system
[Church numerals]: http://esolangs.org/wiki/Church_numeral
Discussion: Quoting
-------------------
Purely concatenative languages are almost embarassingly easy to interpret,
in a functional language:
* **map** each symbol to a function
* **compose** all those functions into a single function, in a **fold**
* **apply** that single funciton
They are correspondingly easy to parse. While most programming languages
require a context-free (or even context-sensitive) grammar to describe
their syntax, a purely concatenative language can be parsed with a regular
expression. (And in Equipage's case, not even a complex one.)
But many, probably most, concatenative languages are not purely so; that is,
when specifying the program they incorporate some operations over and above
function composition.
One such useful thing is quoting — being able to nest subprograms within
a program, basically. This seems to be how many of them deal with function
definitions.
But this nesting is exactly what requires the grammar to be context-free.
Carriage dealt with the issue of quoting by providing two interpretations
of the program text: one where it is all quoted, another where it is all
composed into a single function. This is very esolang. But was, I must
admit, somewhat unsatisfying (otherwise why would I be writing this.)
Equipage's approach is to have almost every instruction "already quoted".
That is, every symbol except `!` simply pushes a function onto the stack.
If you need to actually apply it, you have to do that "manually", by
following it with `!`.
This results in long chains of `x!y!z!` for some instructions x, y, and z,
and when you want to compose functions out of existing functions
especially, long chains of `.!.!.!` whose length must match the number of
composition operations involved in composing the constituent functions.
But if we're willing to add somewhat more complexity to the language,
we can make something that is virtually the equivalent of syntactic
quoting.
### EquipageQ ###
-> Tests for functionality "Interpret EquipageQ Program"
-> Functionality "Interpret EquipageQ Program" is implemented by
-> shell command "bin/equipage -Q %(test-body-file)"
-> Functionality "Interpret EquipageQ Program" is implemented by
-> shell command
-> "python3 impl/equipage.py/equipage.py -Q %(test-body-file)"
We can define a minor dialect of Equipage, which we will call EquipageQ,
which lets us handle quoting in a syntactically nicer way.
EquipageQ adds a special value, MARKER, which can appear on the stack.
It also adds two new symbols to the vocabulary:
( push *mark* onto the stack
) push *define* onto the stack
(Note that, by having these symbols push functions onto the stack, we
are following the Equipage approach. We will need to apply these with
`!` when we want to use them.)
The definition of those functions being
mark: push a MARKER onto the stack
define: keep popping functions off the stack, composing them,
until a MARKER is popped; then push the resulting function
onto the stack
That lets us write `wxyz.!.!.!` as `(!wxyz)!`, which is simpler,
because we don't need to be careful that the number of compose
operations matches the number of functions being composed.
And that lets us write the above program like:
(! 1~%1-1-1-~; )!
(! $11-1-~; )!
(! 1$ )!
(! 11+11-11+1 )!!
(! 11-1-~; )!!
===> [0,2,<fn>,<fn>,<fn>]
We can further say that if `define` exhausts the stack without seeing
a MARKER it acts as if there was a MARKER at the very bottom of the
stack. This permits us to say what the meaning of an Equipage program
is, even if it contains unbalanced parentheses. This is of course not
a full compensation for not having them as a syntactic construct, which,
for the price of having a parsing phase, buys you things like being
able to detect unbalanced parentheses without running the program.
Happy concatenating!
Chris Pressey
London, UK
June 12th, 2018