# Intramodular Transaction

Paradigm(s) Declarative User:Hakerh400 2019 Turing-complete Interpreter `.txt`

Intramodular Transaction operates on infinite sequences of bits.

## Syntax

Source code consists of one or more operator definitions. Each definition contains exactly one equals sign `=` and ends with semicolon `;`. On the left side of the equals sign one or more identifiers can appear (the first one is operator name, others are formal argument names), and on the right side of the equals sign operators and identifiers can appear. Each operator has fixed arity (number of operands it takes). All operators are in prefix notation and all operands are sequences of bits.

Built-in operators are:

• `0` - Takes a sequence of bits, returns the sequence with bit 0 prepended
• `1` - Takes a sequence of bits, returns the sequence with bit 1 prepended
• `.` - Takes a sequence of bits, returns the sequence without the first bit
• `?` - Takes three sequences, if the first bit of the first sequence is 1, returns the second sequence, otherwise returns the third sequence

Identifiers can contain letters and digits, but cannot start with a digit. Example of a definition:

```operator sequence = ? sequence 0 operator . sequence 1 operator . sequence;
```

The above example defines operator `operator` that takes one operand `sequence` and then if the first bit of the sequence is 1, apply the operator to remaining bits and prepend 0, otherwise apply the operator to remaining bits and prepend 1. In other words, this operator inverts all bits. Space can be omitted after builtin operators (including 0 and 1).

Here is another example:

```op1 = 0 op2;
op2 = 1 op1;
```

In this example, operator `op1` generates sequence `01010101...`, while operator `op2` generates sequence `10101010...`.

Comments start with `--` and end with a new line or the end of the source code.

## Execution

The main operator is the operator from the first definition in the source code. The arity of the main operator must be 1. The output sequence is the result of the main operator applied to the input sequence.

If a finite sequence is needed, one may convert finite sequence of bits to infinite by prepending 1 before each bit and appending infinitely many zeros after the sequence. For example, finite sequence

```10011100
```

can be converted to infinite sequence:

```11101011111110100000000000000000...
```

Similarly, infinite sequence can be converted to a finite one by removing all bits after the first 0 on an even position (0-indexed) and removing redundant 1s from even positions. When working with ASCII strings, input (array of bytes) can be converted to finite sequence of bits, then to infinite sequence of bits, then apply the main operator and convert back to finite sequence of bits and then to the ASCII string. Therefore, a program in this language can operate on ASCII strings as well.

## Examples

### Cat

Output the input string unchanged:

```main str = str;
```

### Reverse all bits

Reverse all bits at odd positions up to the first 0 bit at even position.

```main input = reverse input;
p a b = ? a 1 b 0 b;

reverse str = ? str
1 p lastBit str
reverse dropLastBit str
str;

lastBit str = ? ..str
lastBit ..str
.str;

dropLastBit str = ? ..str
1 p .str dropLastBit ..str
..str;
```

## Computational class

Given that User:Qpliu has implemented Brainfuck interpreter in this language, it proves that this language is Turing-complete.