Unleash

Paradigm(s) String-rewriting, Stack-based User:Hakerh400 2020 Turing complete Interpreter `.txt`

Unleash is an esoteric programming language inspired by Unlambda and Underload. It can be viewed either as stack-based or string-rewriting language.

Overview

Element is either a list or an instruction

List is denoted by a pair of parentheses and contains zero or more elements.

Instruction can be one of: `+-~*.%`

Source code consists of an array of elements. We keep track of the source code (array of elements) and we also keep track of the stack (a single stack, which initially contains infinitely many empty lists). Since the stack always contains infinitely many elements, we represent it as an array of elements where the top element is the element with index ${\displaystyle 0}$, the second top element is the element with index ${\displaystyle 1}$, and so on. When we push an element to the stack, the element that we push will have index ${\displaystyle 0}$ and all other elements will be shifted to the right. Similar happens when we pop an element.

I/O format

Input and output are arrays of bits. Before program starts, each bit of the input is prepended with an extra ${\displaystyle 1}$ bit. Reading after the last input bit returns ${\displaystyle 0}$.

Computation step

If the source code is empty, then halt the program. Otherwise, pop the top element from the source code (the leftmost element). If the element is a list, push it to the stack. Otherwise execute it, because it must be an instruction.

Instructions

Instructions may take arguments. Arguments are non-negative integers, separated by `|` characters. Arguments can be omitted and for each instruction we describe what the default arguments are. Arguments appear immediately after the instruction. If descriptions of these instructions are not clear enough, see the reference implementation for details.

Instruction +

Takes up to 3 arguments: `+x|y|z`
If no arguments are provided, it is equivalent to `+0|1|0`
If one argument `x` is provided, it is equivalent to `+x|1|0`
If two arguments `x y` are provided, it is equivalent to `+x|1|y`

Create a copy of `y` consecutive elements from the stack starting at index `x` and insert it to the stack at index `z`.

Instruction -

Takes up to 2 arguments: `-x|y`
If no arguments are provided, it is equivalent to `-0|1`
If one argument `x` is provided, it is equivalent to `-x|1`

Remove `y` consecutive elements from the stack starting at index `x`.

Instruction ~

Takes up to 3 arguments: `~x|y|z`
If no arguments are provided, it is equivalent to `~0|1|1`
If one argument `x` is provided, it is equivalent to `~x|1|0`
If two arguments `x y` are provided, it is equivalent to `~x|1|y`

Remove `y` consecutive elements from the stack starting at index `x` and then insert them at index `z`.

Instruction *

Takes up to 2 arguments: `*x|y`
If no arguments are provided, it is equivalent to `*0|1`
If one argument `x` is provided, it is equivalent to `*0|x`

Create a list containing `y` consecutive elements from the stack starting at index `x` (also remove those elements from the stack) and insert the list to the stack at index `x`.

Instruction .

Takes up to 1 argument: `.x`
If no arguments are provided, it is equivalent to `.0`

Let `e` be the element from the stack at index `x` (also remove it from the stack). If `e` is a list, insert its elements to the stack at index `x`. Otherwise, read the next bit from the input stream and if the bit is ${\displaystyle 1}$ then put `e` back to index `x`.

Instruction %

Takes up to 1 argument: `%x`
If no arguments are provided, it is equivalent to `%0`

Let `e` be the element from the stack at index `x` (also remove it from the stack). If `e` is a list, insert its elements to the source code at index `0`. Otherwise, if `e` is one of `+-~` output bit ${\displaystyle 0}$, and if `e` is one of `*.%` output bit ${\displaystyle 1}$.

Examples

```(
~((
((+)-1)
((.)-1|2)
(+)..%1.%+%
)-1|2)
(+)..%1%
)+%
```

```(
~((
((.)-1)
((+)-1|2)
(+)..%1.%+%
)-1|2)
(+)..%1%
)+%
```

```(
((%)-1)((
(.%%).
((+)-1)
((.)-1|2)
(+)..%1
*0|4~
+%
)-1|2)
(+)..%1%
)+%
```

Increment a binary number

```(-)(((-)-1)((-1)-1|2)(+)..%1)((-0|2)(+1%(-1)~0|2|2+%)+3%%%)+%((-))(-1)((-()((-1)+*3)%2%)((((-))(-1(-
)~(-1))+3%%)(((-1))((-))+3%%)%5%(-1)~0|2|2*2|3+%)%5%)+%(~.()(((+).%)((*).%)%2%~+%)%2%)+%
```

Decrement a binary number

```(-)(((-)-1)((-1)-1|2)(+)..%1)((-0|2)(+1%(-1)~0|2|2+%)+3%%%)+%((-))(-1)((-0|2)((((-))((-1))+3%%)(((-1
))(-1(-)~(-))+3%%)%5%(-1)~0|2|2*2|3+%)%5%)+%(~.(-((-1)(-)((-))))((~+%)((-1)+*3)%2%)%2%)+%(~.()(((+).
%)((*).%)%2%~+%)%2%)+%
```