Equipage

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

★ 8 Open GitHub ↗

MIRROR of https://codeberg.org/catseye/Equipage : The purely concatenative language that Carriage might've been

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

Equipage
========

_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

Equipage

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README