# Hello today I am a unicorn

Paradigm(s) Imperative Hakerh400 2020 Turing complete Interpreter `.txt`

Hello today I am a unicorn is a Turing-complete programming language that has only two variables.

## Overview

There are only two variables: `x` and `y`. Both are non-negative integers of unlimited size.

Source code consists of zero or more instructions. Any instruction can be prefixed by a label.

Each instruction begins with the variable name it uses (`x` or `y`), then operator that is applied and operands.

### Operator Xor

Denoted by `~`. No operands. Inverts the lowest bit of the variable. Example:

```x~
```

Value of `x` before: `123`
Value of `x` after: `122`

### Operator Shift left

Denoted by `+`. No operands. Performs binary shift to the left. Example:

```y+
```

Value of `y` before: `5`
Value of `y` after: `10`

### Operator Shift right

Denoted by `-`. No operands. Performs binary shift to the right. Example:

```x-
```

Value of `x` before: `15`
Value of `x` after: `7`

### Operator If

Denoted by `?`. Two operands (and they are labels). If the lowest bit is `1` jump to the first label, otherwise jump to the second label. Example:

```y? label1 label2
label1: x+
label2: x-
```

If `y` is odd, `x` will be shifted left and then shifted right. If `y` is even, `x` will only be shifted right.

Note: all instructions except this simply increment instruction pointer.

## I/O format

Input is a non-negative number. It is written in the `x` variable before program starts, while `y` is initially `0`. When program terminates, `y` contains the output.

## Examples

### Cat

Note: assuming the same I/O format as described here for converting from/to ASCII strings.

```      x? copy exit
copy: x- y+ y~ y+
x? flip next
flip: y~
next: x- x? copy exit
exit: x~
```

## Computational class

The variables `x` and `y` effectively implement two stacks of bits; you can push to these via a left-shift (possibly followed by an xor), pop them via a right-shift, and test the bottom bit via the if operator. Because the language also allows arbitrary control flow, this allows two-stack machines to be implemented more or less directly (a two-counter machine can also be implemented via treating the counter as a stack of multiple 0 bits above a single 1 bit), making the language Turing complete.