SUB

SUB

Paradigm(s)	Declarative
Designed by	User:Hakerh400
Appeared in	2021
Computational class	Unknown
Major implementations	Unimplemented
File extension(s)	.txt

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.