SUB

SUB is an esolang invented by User:Hakerh400 in 2021.
== Overview ==
Each line in the source code consists of a directive. Each directive consists of the name and arguments. There are 5 directives:
* VAR
* CMP
* NIL
* PAR
* SUB
== Directives ==
=== VAR ===
Takes one argument. For example VAR myVariable. The argument represents the variable name. This example declares a variable named myVariable. We can declare the same variable multiple times. Each variable has a value, which we do not define explicitly, but the interpreter figures out what the value can be. A value is either NIL, or an ordered pair of two values. Each value has finite depth.
=== CMP ===
Takes two arguments. For example CMP x y. The x and y represent line numbers in the source code (1-indexed). They must be strictly smaller than the current line index. It is an error if either x or y contain a CMP directive.
This directive asserts that the values defined at lines x and y are equal. Each value is equal to itself. Each two NILs are equal. Two pairs are equal iff their corresponding elements are equal. No pair is equal to NIL. If two variables have the same name, they are equal.
=== NIL ===
Takes no arguments. Defines NIL. There can be multiple NIL directives in a program, but there is no point of doing so. If you need NIL, just define it once and reference the line afterwards.
=== PAR ===
Takes two arguments. For example PAR x y. The x and y represent line numbers in the source code (1-indexed). They must be strictly smaller than the current line index. It is an error if either x or y contain a CMP directive.
This directive creates a pair of values from lines x and y.
=== SUB ===
Takes three arguments. For example SUB x y z. The x and y and z represent line numbers in the source code (1-indexed). They must be strictly smaller than the current line index. It is an error if either x or y or z contain a CMP directive.
This directive defines a value that is obtained by replacing each occurrence of the value from y with the value from z inside the value from x.
More formally, if a, b and c are values, to replace b with c inside a apply the first of these three cases that can be applied:
* If a is equal to b, the result is c
* If a is NIL, the result is NIL
* If a is a pair of d and e, the result is a pair of replacing b with c inside d and replacing b with c inside e
Here are some corollaries that can be derived from the definition above:
* SUB a a b is equal to b for any a and b
* SUB a b b is equal to a for any a and b
* If c is a pair of b and NIL, and if SUB a b c is not equal to a, then a not being equal to b implies that SUB b a x is equal to b for any x
== Result ==
The result of executing a program is any assignment of variables that satisfy all the CMP directives. If there is no such assignment, the program does not halt.
== I/O format ==
Implementation dependent. There can be one specific variable that represents the input (implicitly asserted to be equal to the input value) and also one variable for output.
== Examples ==
Warning: the examples are written by hand and not tested on a real interpreter. There may be mistakes.
=== Example 1 ===
 NIL
 VAR A
 CMP 2 1
The value of A is NIL.
=== Example 2 ===
 VAR A
 CMP 1 1
The value of A can be anything.
=== Example 3 ===
 VAR A
 VAR B
 NIL
 PAR 2 2
 CMP 2 3
 CMP 1 4
The value of A is a pair of two NILs, and the value of B is NIL.
=== Example 4 ===
Empty program. It halts, but the output is an empty set of assignments, since there are no variables.
=== Example 5 ===
 NIL
 PAR 1 1
 CMP 1 2
Does not halt, because NIL cannot be equal to a pair.
=== Example 6 ===
 VAR A
 NIL
 PAR 2 2
 CMP 1 2
 CMP 1 3
Does not halt, because A cannot be NIL and a pair at the same time.
=== Example 7 ===
 VAR A
 PAR 1 1
 CMP 1 2
Does not halt, because A cannot be a finite value.
=== Example 8 ===
 NIL
 PAR 1 1
 VAR A
 VAR B
 CMP 3 2
 SUB 3 1 3
 CMP 4 6
A is a pair of two NILs, and B is a pair of a pair of two NILs and a pair of two NILs.
== Computational class ==
Unknown.
== Interpreters ==
Unimplemented.
Category:Languages
Category:Unknown_computational_class
Category:2021
Category:Unimplemented