# Subreal

Paradigm(s) Imperative User:RocketRace 2020 Stack-based Turing complete Unimplemented `.sbr` or `.subreal`

Subreal is a Turing complete stack-based esoteric programming language based on one of John Conway's famous works, the surreal numbers. Subreal programs operate on three stacks containing surreal numbers, with a focus on recursion.

Subreal uses three stacks: L, R, and X. The first two are used to construct surreal numbers, and X is a general purpose stack. Subreal programs consist of single-character operations separated into lines. The program halts at EoF. Anything within square brackets (`[like this]`) is considered a comment and ignored.

A list of operations is provided below. Operations followed by `N` take in a numeric argument as a nonnegative integer. Whenever N = 0, N is assumed to be as large as possible instead.

Note that if a stack is empty and a pop is executed on it, the offending instruction is ignored instead.

### Stack operations

Operation Effect
`<` Pop a value from X and push it to L.
`>` Pop a value from X and push it to R.
`/` Pop a value from L and push it to X.
`\` Pop a value from R and push it to X.
`& N` Duplicate the last `N` values in X.
`- N` Discard the last `N` values from X.

### Surreal operations

Operation Effect
`=` Construct a surreal number `{ L | R }` using the contents of L and R for the left and right sets respectively, and push the resulting value to X.
`x` Pop one value `x` from X and push the smallest sets `L` and `R` such that `{ L | R } = x`, to L and R respectively. This is equivalent to splitting a surreal number into its left and right sets.
`+ [literal]` Push a surreal literal to X. Rather than an integer, this operation takes in a surreal literal as an argument.
`# N` Pop `N` values from X and print their numeric literal representations to STDOUT.
`@ N` Read and push `N` surreal literals from STDIN to X.

### Control flow operations

Line numbers are 1-indexed for convenience.

Operation Effect
`. N` Jump to line `N`.
`, N` Pop a value `x` from X. If that value is equivalent to 0, i.e. `x = {|}`, jump to the start of line `N` in the program and continue execution.
`: N` Jump into a subprocess starting at line `N` in the program. Push the subprocess' return value to X.
`( instructions )` Execute the instructions inside the parentheses as a subfinite loop. Evaluate its return value, and push that to X.
`!` If this is executed by a subprocess, pop a value from X and return that value to the parent process.

Otherwise, halt the program.

## Subprocesses

Subprocesses are a means of recursion. When a subprocess is spawned, the parent process gives the child process a copy of the L and R stacks, but not the X stack. A subprocess executes instructions like the parent process.

If a subprocess executes a `!` instruction, instead of halting the whole program, will return to the parent process. The subprocess will pop one value from its own X stack and return that value to the parent process. This return value is pushed onto the parent process' X stack.

If a subprocess reaches EoF, the entire program halts.

## Subfinite loops

Subfinite loops are a way to handle infinitely long, or infinitely nested data using only finite time. Any instructions surrounded by parentheses `(like so)` will be treated as a subfinite loop. Once a process enters a subfinite loop, it determines the "final" state of the loop (even if the loop does not halt, or does not "converge" conventionally), and exits the loop assuming that state.

For example, the following loop will compute `ω` and push it onto L: `(=<)`. In each iteration of the loop, the L and R stacks are evaluated, and the result is pushed to L, effectively incrementing the result by one. After an infinite amount of iterations, this yields `ω` (the first infinite ordinal).

Certain instructions are ignored while inside a subfinite loop: `#`, `@`, `,`, and `:`.

Parentheses may not be nested.

## Surreal literals

Surreal literals are mathematical representations of surreal numbers. There are two types of representations of surreal numbers: set literals and numeric literals.

Set literals are a raw representation of surreal numbers, using only the `{|}` syntax. Examples of set literals are: `{|}`, `{|{|}}` and `{{{|}|}|{|}}`. They are akin to the set-theoretic definition of the natural numbers.

Numeric literals are a more flexible representation of surreal literals. They are an abstraction over the set literals, much in the same way that the natural numbers are an abstraction over the Von Neumann or Zermelo ordinals. Most written numbers are numeric literals in this regard. The following are examples of numeric literals:

1. 0 (equivalent to `{|}`, or the nil value)
2. 1 (equivalent to `{{|}|}`, or the "simplest" surreal number greater than 0)
3. All integers: `2`, `-5`, `124`, etc.
4. All decimal forms of dyadic fractions: `0.5`, `-0.75`, `0.375`, etc. Note that `.` in literals binds stronger than the `.` operation.
5. All dyadic fractions `±a / 2 ^ b`: `1/2`, `-15/64`, `2/256`, `2/1`, etc.
6. All terminating decimal forms of rational numbers: `0.1`, `0.85`, `-10.722`, etc.
7. All recurring decimal forms of rational numbers: `0.`1``, `9.`9``, `12.34`56``, etc.
8. All rational numbers `±a / b` for nonzero `b`: `1/2`, `-12/5`, `0/1`, etc.
9. `ω` (or `o`), the simplest limit ordinal
10. `ε` (or `e`), the simplest infinitesimal
11. All values `aω ± b ± cε` (or `ao ± b ± ce`) such that `a` and `c` represent dyadic fractions, and `b` is a rational number: `-ω + 0.1 + 2ε`, `3/7 - 0.0625ε`, `1/2ω - 5`, `15ω`, etc. Note that `+` and `-` in literals binds stronger than the `+ N` and `- N` instructions.
12. All mixtures of set literals and numeric literals: `{0|}`, `{{0|1}|3/4}`, `{ω|{ω|}}`, etc.

Any instances of integers may also be interpreted in base-32, hexadecimal, octal, quaternary or binary by prefixing `0z`, `0x`, `0o`, `0q` and `0b`, respectively.

## Computational class

Subreal is Turing complete, by reduction to a Minsky machine with two registers. Here, each register machine instruction is on its own line.

```INC A, N      := +0<:N
INC B, N      := +0>:N
JZDEC A, N, M := /,M:N
JZDEC B, N, M := \,M:N
```

It is not super-Turing complete, regardless of the subfinite loops, which are similar to supertasks. That is because subfinite loops only operate on a subset of instructions that is not Turing complete, and therefore cannot solve the halting problem.

## Examples

Since most arithmetic on surreal numbers is defined recursively, programs written using it are bound to have large time complexity.

### Fibonacci numbers

```+0+1>>:2&1#1\\-1<>/>+0,1
\&1,3\&1,4&2xx/>>:2/>>:2=!
\!
>!
```

Explanation:

• Push 0 and 1 to the R stack.
• Forever:
• Evaluate R0 + R1, the sum of the two values, using the "add" subprocess.
• Print the result.
• Replace the smallest value with the result.
• Evaluate the predecessors R0' and R1' using the `x` instruction. (For positive integers, it yields the values' predecessors.
• Return `{R0 + R1', R1 + R0'|}`, using this recursive addition subprocess.