Universal stack operations using Uxn primitives

I wanted to know if the `Uxntal` primitives are complete, in the sense that they allow access to all elements on the stack (what I call “covering the stack”). And if so, what the minimum set of Uxntal primitives is required to move an element to or from any location on the working stack.

The proof of these claims is by construction of a recursive algorithm, so it is a proof by induction. I have written this in Haskell notation because I think it is most clear. For completeness, I also looked at duplication and deletion. As the set of primitives is Uxn-specific, I assume the presence of a return stack.

tl;dr:

• The Uxn primitives are complete (no surprise there)
• The instructions `SWP`, `ROT`, `STH` and `STHr` are sufficient to cover the entire stack.
• Adding `DUP`, we can replicate arbitrary sequences.
• Adding `POP` we can remove arbitrary sequences.

Uxntal and Uxn

`Uxntal` is the programming language for the `Uxn` virtual machine. As Uxn is a stack machine, Uxntal is a stack language, similar to e.g. Forth or Joy in that it uses reverse Polish notation (postfix). It is an assembly language with opcodes for 8-bit and 16-bit operations on the stack and memory. To get the most out of this article, it is best if you have basic knowledge of Uxntal, either from the above resources or for example the great tutorial at Compudanzas.

A brief overview of used Haskell syntax

In Haskell, for example a function `f` of `x` and `y` is written as `f x y`, so no parentheses. Parentheses are only used to enforce precedence, for example `f (x+1)`

Also, a recursive function can be defined as

``````    f 1 = ...
f n = ... f (n-1) ...
``````

So there is no need for an `if` or `case` or similar constructs. Also, if a function argument is used in final position on both sides of the definition, it can be omitted, for example

``````    f x = id x
``````

can be written as

``````    f = id
``````

(In this example, `id` is the identity function, which returns its argument)

Finally, composing functions is done using the `.` operators. For example, `f1 (f2 (f3 x))` can be written as `(f1 . f2 . f3) x`. Combining both features, we can write for example

``````    f = f1 . f2 . f3
``````

Minimal set of primitives

The type for all primitives is

``````    prim :: ([Byte],[Byte]) -> ([Byte],[Byte])
``````

The primitive `prim` takes a tuple (pair) of two lists of bytes and returns a tuple of two lists of bytes. (You can read the arrow as “from … to”.) For this discussion, the stacks don’t have to be of fixed size, so using lists is fine.

The notation `x:xs` means that `x` is the first element of a list and `xs` is the rest of the list.

``````        swp (x:y:wst',rst) = (y:x:wst',rst) -- swap in Forth
rot (x:y:z:wst',rst) = (z:x:y:wst',rst)
sth (x:wst',rst) = (wst',x:rst)
sthr (wst,x:rst') = (x:wst,rst')
``````
• For replication and deletion, we also need
``````        dup (x:wst',rst) = (x:x:wst',rst)
pop (x:wst',rst) = (wst',rst) -- drop in Forth
``````

Accessing the stack

I define two functions, one to move the kth element on the stack to the 1st position, the other its inverse.

Put the kth element of the stack at position 1

In Forth terminology this is called `roll`.

``````    -- ( x a b -- a b x )

k_to_top 1 = id
k_to_top 2 = swp
k_to_top 3 = rot
k_to_top k = swp . sthr . (k_to_top (k-1)) . sth
``````

Put the 1st element of the stack at position k

Somewhat to my surprise, Forth does not define an inverse for `roll`. Of course it is not necessary, as we can apply `roll k` k-1 times. But that means quadratic complexity; and I like to have an inverse for every primitive.

``````    -- ( a b x -- x a b )

top_to_k 1 = id -- k==1, do nothing
top_to_k 2 = swp
top_to_k 3 = rot . rot
top_to_k k = sthr . (top_to_k (k-1)) . sth . swp

id = (top_to_k k) .  (k_to_top k)
``````

With these two functions, any element on the stack can be moved between two arbitrary position k1 and k2:

``````    (top_to_k k2) .  (k_to_top k1)
``````

This proves that the four primitives are sufficient to cover the entire stack.

Growing the stack

Variants that keep the original element in place and so grow the stack are easily defined based on these two:

Put the kth element of the stack at position 1, keep the original element

This function grows the stack by duplication of the element. In Forth terms, this is called `pick`.

``````    -- ( x a b -- x a b x )

k_to_top_keep 1 = dup
k_to_top_keep k = swp . sthr . (k_to_top_keep (k-1)) . sth
``````

The inverse of this is simply `pop` (`drop` in Forth).

``````    id = pop . (k_to_top_keep k)
``````

Put the 1st element of the stack at position k, keep the original element

This function also grows the stack by duplication of the element:

``````    -- ( a b x -- x a b x )

top_to_k_keep 1 = id
top_to_k_keep k = sthr . (top_to_k k) . sth . dup
``````

The inverse of this requires the ability to delete a value at a given position of the stack:

Shrinking the stack

This function deletes an element from an arbitrary position on the stack.

``````    -- ( x a b -- a b )

delete_k 1 = pop
delete_k k = sthr . (delete_k (k-1)) . sth
``````

With this function, the inverse of `top_to_k_keep` is `delete_k (k+1)`:

``````    id = (delete_k (k+1)) . (top_to_k_keep k)
``````

The Haskell code shows these functions at work and demonstrates the inverses. It is straightforward to implement the above functions in Uxntal, I leave that to the reader as an exercise.

Updated