Bunk bed

Bunk bed is a programming language that works with mappings of values.
== Overview ==
A mapping in this language maps values to other values. Values are also mappings.
The are variables. All uninitialized variables are the same and they represent mappings that map each value to the value itself. For example, if we have uninitialized variable x and we try to access property y, we will get y as the result.
If we assign one variable to another, modifying any of them will not modify the other. All values (values are mappings) are copied by value, not by reference.
== Syntax ==
There are instructions and labels. A label starts with an identifier, followed by a colon.
All instruction names are case-insensitive. Also, they are not reserved as keywords, so any instruction name can be used as a variable. Multiple instructions can appear in a single line (no new lines are required).
=== Assignment ===
Assigns a value to a variable. It has three different forms.
==== Another variable ====
Assign variable y to variable x
 x = y
==== Property ====
Get property z from the mapping stored in the variable y and assign it to x
 x = GET y z
==== Map to a single value ====
Create a new mapping that maps all values to y and assign it to x
 x = ALL y
Note: the right side is evaluated first, so x = ALL x would not create a recursion, but simply create a new mapping that maps to old value of x.
=== Set property ===
Update variable x so that y now maps to z
 SET x y z
=== Compare ===
If variables x and y have different values (how mappings are compared is explained below in paragraph "Comparing mappings"), then skip the next instruction:
 CMP x y
=== Jump ===
Jump to label lab
 JMP lab
=== Input ===
If the next input bit is 0 or the end of the input is reached, skip the next instruction.
 INP
=== Check end of input ===
If there are more bits in the input, skip the next instruction.
 EOF
=== Output ===
Output a bit.
 OUT 0 // Output bit 0
 OUT 1 // Output bit 1
=== No operation ===
Does nothing.
 NOP
== Comparing mappings ==
Given the following sample code:
 y = ALL x
In this example, x is uninitialized (maps all values to themselves), while y maps all values to x.
Any two mappings are compared in the following way:
# If one of them is x and the other is y (from the example above), they are not equal
# If there is at least one property that differs among them, they are not equal.
# Otherwise, they are equal.
Here is an example:
 A = A
 B = ALL A
 C = ALL B
 D = GET C D
We want to answer the following:
* Is A equal to B?
* Is A equal to C?
* Is A equal to D?
* Is B equal to C?
* Is B equal to D?
* Is C equal to D?
First, we see that A is assigned to itself. Assigning a variable to itself has no effects, so A is still "uninitialized", so it maps each value to the value itself. We can also see that x from the example above also maps each value to the value itself, so A and x are identical (they are exactly the same mapping).
Variable B is a mapping that maps all values to A. If we compare to our example above, we can see that y is also a mapping that maps all values to x. Since A is x, we conclude that B is y. Given that, by definition, x is not equal to y, we conclude that A is not equal to B.
Variable C maps all values to B. We want to check whether A is equal to C. In order to prove that they are not equal, we need to find at least one property (one mapping, because properties are mappings) such that A and C map it to different values. Let the property be A itself. A maps A to itself (because A maps each value to the value itself), while C maps A to B (because C maps everything to B). Since A is not equal to B, we conclude that A is also not equal to C.
Variable D is equal to the value into which C maps D. Variable D was unitialized before the assignment, but it does not matter, because C maps everything to B, so GET C D results in B. Therefore D is equal to B. We know that A is not B, so A is also not D.
At the end, we want to compare B (or D) with C. Let the property we want to test be A. Since B maps A to A and C maps A to B and since A and B are not equal, we conclude that C and D are also not equal.
== I/O format ==
Stream of bits.
== Examples ==
We demonstrate all examples on sample input string 1011 for simplicity.
=== Cat ===
Code:
 read:
 EOF
 JMP end
 INP
 JMP 1
 OUT 0
 JMP read
 1:
 OUT 1
 JMP read
 end:
 NOP
Input: 1011
Output: 1011
Explanation: No variables are used. It is simpy to demonstrate control flow.
=== Reverse bits ===
Code:
 b = ALL a
 c = ALL b
 d = c
 read:
 EOF
 JMP print
 e = d
 SET e b c
 c = e
 INP
 JMP read
 SET c a a
 JMP read
 print:
 CMP c d
 JMP end
 e = GET c a
 c = GET c b
 CMP e b
 JMP 1
 OUT 0
 JMP print
 1:
 OUT 1
 JMP print
 end:
 NOP
Input: 1011
Output: 1101
Explanation: variable a is used as bit 0, variable b is used as bit 1, variable c is used as a LIFO linked list (stack), variable d is used as a template (prototype) for a list element and e is auxiliary variable. Basically, we push all bits to the list, then pop all bits and output them (which results in the reversed order).
== Computational class ==
We have seen in the example with reversing bits that we can implement a stack using a single variable. We can also implement two stacks and thus we can simulate a Turing machine.
== Interpreters ==
Interpreter
Category:Languages
Category:Turing complete
Category:Implemented
Category:2020