# Bunk bed

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.

## Contents

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