Bunk bed

Bunk bed

Paradigm(s)	Imperative
Designed by	Hakerh400
Appeared in	2020
Computational class	Turing complete
Major implementations	Interpreter
File extension(s)	.txt

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:

1. If one of them is x and the other is y (from the example above), they are not equal
2. If there is at least one property that differs among them, they are not equal.
3. 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