Bind

Bind is an esoteric programming language created by User:D, which supports a stack and a tape.

Data Structures

Bind has an unbounded tape of nonnegative integers, with the tape head initially pointing to the first cell.

It also has an unbounded stack of nonnegative integers.

Commands

Command	Behavior
@	Push the current tape item onto the stack.
;	Drop TOS of the stack.
<	Move tape head to the left.
>	Move tape head to the right.
Z	Zero the current tape item.
S	Increment current tape item.
[ ... ]	Do ... while tape item + 1 != TOS. (The stack is not modified.)

Examples

Copy

Replace > with moving to the destination cell.

@ > Z[S]S ;

Infinite loop

Z@[]

Implementation of primitive recursive functions/operators

Pick

Move the tape head to the desired item, then push it with @.

Next, use the copying algorithm above to set the TOS value to a cell.

Composition

Functions in primitive recursion are basically composed of picking, successor, and zero functions.

A copy of the definition of composition, copied here for explanation purposes:

C[g, h1, h2, ..., hn] (a1, a2, ... ak) =
  g(h1(a1, a2, ... ak), h2(a1, a2, ... ak), ..., hn(a1, a2, ... ak))

Since both the arguments and the number of hn functions is finite, we can use the pick algorithm to generate copies of the arguments, then apply g on it (which basically means calling the appropriate functions on the selected arguments).

Primitive Recursion

Primitive recursion is a little more complicated. Say, we have the following tape configuration:

 a1 a2 ... an g 0 <sc>
              ^

The base case of primitive recursion would mean to assign g(a1, a2, ... an) to the g cell. This is basically done by calling the appropriate functions, so that the cell is set to the return value of calling g(...).

To do the recursive case, we use the cell to the right as a counter. Say, we want to loop 3 times.

We first set a scratchpad to the value of 3, then push it onto the stack, and finally go back to the counter:

>>SSS@<

In the [ ... ] loop:

• First, , clear our scratchpad so that <sc> may be set to h(a1, ..., an).

[ >Z

• Then, call the appropriate functions so that <sc> is set to h(a1, ..., an).

• This is basically done by using the cells a1 .. an, g, and the counter as a target for calling the functions.

• Then, we copy the scratchpad to the position of g, so that the next iteration of the [ ... ] loop will use the same tape configuration.

@<<Z[S]S;

• Finally, bump our looping counter.

>S ]

At the end of the loop, the g cell stores the final value of the primitive recursion.

<

Minimization

Minimization can also be implemented with the [ ... ] instruction.

Assuming that the tape configuration is like this:

a1 ... an 0 <sc>
          ^

To run ... while f(a1, ... an, x) != 0, we first store a 1 onto the stack:

S@

Next, we start counting from zero:

Z>[

The body of this loop just sets <sc> to the return value of applying f.

Lastly, we bump the counter.

<S>]

If the value in the cell <sc> is 0, the [ ... ] loop is exited.

The cell to the left of <sc> is the return value of minimization:

<

Computational class

Bind is Turing complete. One way to demonstrate this is by compiling μ-recursive functions into this language (demonstrated above).

Another way is to use counter machines; the instruction set {INC r; CLR r; JE rj, rk, z} is Turing-complete. INC r maps to S, CLR r maps to Z, switching counters is < and >.

Lines can be implemented with a series of if-equal blocks (checking the Instruction Counter) enclosed with an outer infinite loop. JE is basically setting the IC to a different value, if the condition is met.

External links

• Official interpreter