Subreal

Subreal

Paradigm(s)	Imperative
Designed by	User:RocketRace
Appeared in	2020
Memory system	Stack-based
Computational class	Turing complete
Reference implementation	Unimplemented
Major implementations	Online interpreter
File extension(s)	.sbr or .subreal

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

Execution model

Subreal uses three stacks: L, R, and X, containing surreal numbers. The first two are used to construct surreal numbers, and X is a general purpose stack. Subreal programs consist of sequences of single-character operations separated into lines, executed linearly. The program halts upon reaching the end of the program.

The use of whitespace in the program, outside of line feeds to separate lines and to disambiguate numbers, is optional. Additionally, text within square brackets ([like this]) is considered a comment and ignored.

Elements of L, R and X must be valid numeric forms of surreal numbers. (A form is a pair {A | B} of sets A and B containing surreal numbers.) A form {A | B} is numeric if and only if every element a of A is strictly less than each element b of B. The ordering in question is defined recursively for surreal numbers. If two equivalent numeric forms are pushed to the stacks through any means, the two forms will become indistinguishable, being of the same equivalence class.

A list of imperative operations is provided below. Operations followed by N take in an optional numeric argument as a nonnegative integer. If an argument is not given, N is assumed to be as large as possible -- that is, the largest N (possibly infinite) that doesn't fault from the operation.

Operations may fault, whenever it reaches an invalid state. By default, the program should ignore faults and roll back any actions taken by the faulting operation, but implementations may define other additional behavior.

Stack operations

Operation	Effect	Faults
<	Pop a value from X and push it to L.	X is empty.
>	Pop a value from X and push it to R.	X is empty.
/	Pop a value from L and push it to X.	L is empty.
\	Pop a value from R and push it to X.	R is empty.
& N	Duplicate the last N values in X.	N is greater than the number of elements in X.
- N	Discard the last N values from X.	N is greater than the number of elements in X.

Surreal operations

Operation	Effect	Faults
=	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.	The form constructed from L and R is not numeric.
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.	X is empty.
+ [literal]	Push a surreal literal to X. Rather than an integer, this operation takes in a surreal literal as an argument. This argument cannot be omitted.	The literal is not numeric.
# N	Pop N values from X and print their numeric literal representations to STDOUT. The specific format for outputting literals is defined by the implementation, but it is recommended to separate each literal with a line feed.	N is greater than the number of elements in X.
@ N	Read and push N surreal literals from STDIN to X. The specific format for inputting these literals is defined by the implementation, but it is recommended to separate each literal with a line feed.	Any of the literals were not numeric, or STDIN was closed before N elements could be read.

Control flow operations

Line numbers are 1-indexed for convenience, meaning line 1 is the first line in the program. A line number of 0 corresponds with no jump, i.e. "keep executing the current line".

Operation	Effect	Faults
. N	Jump to the start of line N.	N is beyond the last line of the program.
, 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.	X is empty, or N is beyond the last line of the program.
~ N	Prepare the program for a fault. If the next operation executed faults, continue execution at the start of line N. Otherwise, program flow continues unaffected.	N is beyond the last line of the program.
: N	Jump into a subprocess starting at line N in the program. Push the subprocess' return value to X.	N is beyond the last line of the program.
( instructions )	Execute the operations inside the parentheses as a subfinite loop. Evaluate its return value, and push that to X.	The operations inside the parentheses are invalid for a subfinite loop (see below).
!	If this is executed by a subprocess, pop a value from X and return that value to the parent process. Otherwise, halt the program.	X is empty.

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 ! operation, 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, it behaves as if it executed a ! operation. It will thus return to the parent process and let execution continue.

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 converge "conventionally"), and exits the loop assuming that state. This is equivalent to taking the limit as this sequence of instructions is taken to infinity.

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).

Similarly, the following loop will compute the rational number 2/3, which cannot otherwise be reached in a finite number of constructions: ==<(=><\&>=<>/&<). The stacks are initialized with a zero in X and L. The loop starts by computing a surreal number, pushing it to R. The remaining element of X is pushed to L, and the value in R is duplicated into X. This entire process is then repeated with L swapped with R.

Caveats

Certain instructions are invalid and will fault the entire loop if executed while inside a subfinite loop. These include interactions with the outside world, as well as conditional branches: #, @, ,, and ~. As a result of this, the final state of the subfinite loop is decidable, meaning an implementation of Subreal can exist in the real world. In addition, if an implementation deems that the resulting state of a subfinite loop is too difficult to compute, it should fault.

Parentheses may not be nested. As a result of this, a Subreal program is only able to compute a surreal number within the set S_ω*n for integers n. As a result, it is impossible to compute higher powers of ω.

In addition, as the instructions inside a subfinite loop must be finite and are executed repeatedly, arbitrary real numbers cannot be computed either, despite being in S_ω. This is due to the requirement that real computers cannot consume infinite memory.

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. A set literal can have zero or more comma-separated literals in its left and right sets. Examples of set literals are: {|}, {|{|}} and {{|}, {{|}|}|}.

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 oldest surreal number)
2. 1 (equivalent to {0|}, or the oldest surreal number above 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, {0|1}|3/4}, {ω, ω + 1|}, etc.

Any instances of integers within literals may also be interpreted as base32hex, hexadecimal, octal, quaternary or binary by prefixing 0z, 0x, 0o, 0q or 0b, and using the appropriate ranges of digits.

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

Note: These were written for an earlier version of Subreal. They may not function properly.

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.
• The "add" subprocess:
  • If either of the two values is 0, return the other value.
  • 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.