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