Subreal
Paradigm(s)  Imperative 

Designed by  User:RocketRace 
Appeared in  2020 
Memory system  Stackbased 
Computational class  Turing complete 
Reference implementation  Unimplemented 
File extension(s)  .sbr or .subreal 
Subreal is a Turing complete stackbased 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.
Contents
About
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 singlecharacter 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 1indexed 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 settheoretic 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:
 0 (equivalent to
{}
, or the nil value)  1 (equivalent to
{{}}
, or the "simplest" surreal number greater than 0)  All integers:
2
,5
,124
, etc.  All decimal forms of dyadic fractions:
0.5
,0.75
,0.375
, etc. Note that.
in literals binds stronger than the.
operation.  All dyadic fractions
±a / 2 ^ b
:1/2
,15/64
,2/256
,2/1
, etc.  All terminating decimal forms of rational numbers:
0.1
,0.85
,10.722
, etc.  All recurring decimal forms of rational numbers:
0.`1`
,9.`9`
,12.34`56`
, etc.  All rational numbers
±a / b
for nonzerob
:1/2
,12/5
,0/1
, etc. ω
(oro
), the simplest limit ordinalε
(ore
), the simplest infinitesimal All values
aω ± b ± cε
(orao ± b ± ce
) such thata
andc
represent dyadic fractions, andb
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.  All mixtures of set literals and numeric literals:
{0}
,{{01}3/4}
,{ω{ω}}
, etc.
Any instances of integers may also be interpreted in base32, 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 superTuring 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.
 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.