# RCEM

Random Code Executation Machine (RCEM) is an esoteric computer language invented in March 2008 by User:Feuermonster. Data is stored on an infinite tape. In addition, there exists a cell (called I-Cell), which can store numbers. Every cell can have one of the following values: 0 (false), 1 (true), or 2 (maybe).

## Basics

RCEM is based on the idea of a tape, infinite in size and populated by cells capable of storing ternary digits, also known as trits. Partaking of this threefold nature, the following digits are allowed per cell:

• 0 (false)
• 1 (true)
• 2 (maybe)

The current cell on this tape is referenced by a movable pointer. An additional cell, not physically bound to the tape and named the I-Cell, permits the maintenance of an integer number of arbitrary size and sign. Data can be communicated to and fro between the tape, interpreted as binary in such a context, and the I-Cell.

## Instructions

RCEM defines commands to operate on the current cell, the I-Cell, and the communication betwixt these. A command might accept zero, one or two arguments.

Command Meaning
`rx` Moves the pointer `x` steps to the right.
`lx` Moves the pointer `x` steps to the left.
`sx` Sets the current cell to `x`, where `x` might be 0, 1, or 2.
`o_` Prints out the value which is stored at the current cell.
`i_` Reads a value from the input and stores it in the current cell.
`x_` Sets the value of the current cell to a random value which might be 0, 1, or 2.
`^x` Changes the current cell by XOR-combining it with the cell at `cells[current + x]`.
`+x` Changes the current cell by AND-combining it with the cell at `cells[current + x]`.
`c_` Switches the current cell value from 0 to 1 or from 1 to 0.
`++` Adds 1 to the current cell.
`--` Subtracts 1 from the current cell.
`2x` If the current cell has the value 2, its value is replaced by `x`.
`m+` Adds 1 to the I-Cell.
`m-` Subtracts 1 from the I-Cell.
`mp` Prints out the I-Cell as a number.
`mo` Prints out the I-Cell as a character.
`mi` Reads a value from the input and stores it in the I-Cell.
`m::x::y` Reads the cells from `cells[x]` to `cells[y]` as binary digits, concatenates them, and stores their represented decimal value into the I-Cell. E.g., `m::0::8` would read the cells 0 to 8. See the examples below.
`z::x::y` Reads the decimal number from the I-Cell, converts it into its binary representation, and stores the bits into the cells `cells[x]` to `cells[y]`.

If the value n of a cell would be >=3, the value will instead be set to n % 3.

## Loops

RCEM defines the following loops as control structures. Each variant is discriminated by its own activation condition; however, if the current cell equals 2, every loop will be executed, even if relying upon a certain cell configuration.

Loop Condition
`(…)` The code will be executed if the current cell has the value 0.
`{…}` The code will be executed if the current cell has the value 1
`<…>` The code will be executed if the I-Cell value is not 0.
`/…\` The code will be executed if the current cell has the value 2.
`[…]` The code will be executed if `Rnd(2)` yields 1, giving a chance of 50%.

## Examples

`s2[r1s2]` Infinite loop.
`s2o_` This will print 2.
`x_[r1x_]` Random loop.
`x_r9([r1][l2]x_)` An other random based loop.
`r65s1l65(m+r1)mo` This will Print 'A'.
`s0r1s1r1s0r1s1l3m::0::3mp` This will print '5'.
`m+m+m+m+m+z::0::2o_r1o_r1o_` This will print '101'.
`x_/x_\o_` Prints out '1' or '0'
`<m->` Sets the I-Cell to 0.

## Implementations

The following Common Lisp implementation of an interpreter models the infinite tape as a hash table. Each tape cell is represented by an entry in the hash table, the key of which assumes the cell index, associated with the cell value as a ternary digit (trit).

``` (deftype trit ()
'(integer 0 2))

(defun parse-rcem (code)
"Parses and interprets the RCEM CODE and returns NIL."
(declare (type string code))
(let ((position 0)
(memory   (make-hash-table :test #'eql)) ;; Maps: [integer] -> [trit].
(pointer  0)
(i-cell   0))
(declare (type fixnum position) (type hash-table memory) (type integer pointer i-cell))
(flet
((expect-token (token)
(declare (type string token))
(loop
for token-character of-type character across token
for code-character  of-type character = (char code position)
do  (if (char= token-character code-character)
(incf position)
(error "Invalid character ~s, instead of ~s."
token-character code-character))))
(peek-next-character ()
(the character (char code (1+ position))))
(let ((end (or (position-if-not #'digit-char-p code :start position)
(length code))))
(declare (type fixnum end))
(the integer
(prog1
(parse-integer code :start position :end end)
(setf position end)))))
(move-past-section-terminator (initiator terminator)
(declare (type character initiator terminator))
(let ((nesting-level 0))
(declare (type (integer 0 *) nesting-level))
(loop do
(incf position)
(let ((current-character (char code position)))
(declare (type character current-character))
(cond
((char= current-character terminator)
(if (zerop nesting-level)
(loop-finish)
(decf nesting-level)))
((char= current-character initiator)
(incf nesting-level))))))
(the fixnum (incf position)))
(move-to-section-initiator (initiator terminator)
(declare (type character initiator terminator))
(let ((nesting-level 0))
(declare (type (integer 0 *) nesting-level))
(loop do
(decf position)
(let ((current-character (char code position)))
(declare (type character current-character))
(cond
((char= current-character initiator)
(if (zerop nesting-level)
(loop-finish)
(decf nesting-level)))
((char= current-character terminator)
(incf nesting-level))))))
(the fixnum position))
(check-cell-indices (start-cell-index end-cell-index)
(declare (type integer start-cell-index end-cell-index))
(when (> start-cell-index end-cell-index)
(error "Start index ~d > end index ~d." start-cell-index end-cell-index)))
(current-cell ()
(the trit (gethash pointer memory 0)))
((setf current-cell) (new-value)
(declare (type integer new-value))
(the trit (setf (gethash pointer memory 0) (mod new-value 3))))
(cell-at (index)
(declare (type integer index))
(the trit (gethash index memory 0)))
((setf cell-at) (new-value index)
(declare (type integer new-value index))
(the trit (setf (gethash index memory 0) (mod new-value 3)))))

(loop
while (< position (length code))
for   character of-type character = (char code position)
do
(case character
(#\r  (incf position)
(declare (type integer number-of-steps))
(incf pointer number-of-steps)))

(#\l  (incf position)
(declare (type integer number-of-steps))
(decf pointer number-of-steps)))

(#\s  (incf position)
(declare (type integer new-cell-value))
(setf (current-cell) new-cell-value)))

(#\o  (expect-token "o_")
(format T "~a" (current-cell)))

(#\i  (expect-token "i_")
(declare (type T input))
(setf (current-cell) input)))

(#\x  (expect-token "x_")
(setf (current-cell) (random 3)))

(#\^  (incf position)
(declare (type integer pointer-offset))
(setf (current-cell)
(logxor (current-cell)
(cell-at (+ pointer pointer-offset))))))

(#\+  (let ((next-character (peek-next-character)))
(declare (type character next-character))
(case next-character
((#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)
(incf position)
(declare (type integer pointer-offset))
(setf (current-cell)
(logand (current-cell)
(cell-at (+ pointer pointer-offset))))))
(#\+  (expect-token "++")
(incf (current-cell) 1))
(otherwise
(error "Invalid command: +~c." next-character)))))

(#\-  (expect-token "--")
(decf (current-cell) 1))

(#\c  (expect-token "c_")
(case (current-cell)
(0 (setf (current-cell) 1))
(1 (setf (current-cell) 0))
(T NIL)))

(#\2  (incf position)
(declare (type integer new-cell-value) (ignorable new-cell-value))
(when (= (current-cell) 2)
(setf (current-cell) new-cell-value))))

(#\m  (incf position)
(let ((next-character (char code position)))
(declare (type character next-character))
(case next-character
(#\+  (incf i-cell 1)
(incf position))
(#\-  (decf i-cell 1)
(incf position))
(#\p  (format T "~d" i-cell)
(incf position))
(#\o  (format T "~c" (code-char I-cell))
(incf position))
(#\i  (let ((input (read)))
(declare (type T input))
(setf i-cell input)
(incf position)))
(#\:  (expect-token "::")
(let ((start-cell-index 0)
(end-cell-index   0)
(new-i-cell-value 0))
(declare (type integer start-cell-index end-cell-index)
(type integer new-i-cell-value))
(expect-token "::")
(check-cell-indices start-cell-index end-cell-index)
(loop
for cell-index of-type integer from end-cell-index downto start-cell-index
for cell-value of-type trit    = (cell-at cell-index)
for bit-index  from 0 by 1
do  (case cell-value
(0 (setf (ldb (byte 1 bit-index) new-i-cell-value) 0))
(1 (setf (ldb (byte 1 bit-index) new-i-cell-value) 1))
(2 (setf (ldb (byte 1 bit-index) new-i-cell-value) 1))
(T (error "Invalid cell value in cell ~d: ~d." cell-index cell-value))))
(setf i-cell new-i-cell-value)))
(otherwise
(error "Invalid command: 'm~c'." next-character)))))

(#\z  (incf position)
(expect-token "::")
(let ((start-cell-index 0)
(end-cell-index   0))
(declare (type integer start-cell-index end-cell-index))
(expect-token "::")
(check-cell-indices start-cell-index end-cell-index)
(loop
for cell-index       of-type integer from start-cell-index to end-cell-index
for i-cell-bit-index of-type unsigned-byte from 0 by 1
do  (setf (cell-at cell-index)
(if (logbitp i-cell-bit-index i-cell) 1 0)))))

(#\(  (if (zerop (current-cell))
(incf position)
(move-past-section-terminator #\( #\))))

(#\)  (move-to-section-initiator #\( #\)))

(#\<  (if (not (zerop i-cell))
(incf position)
(move-past-section-terminator #\< #\>)))

(#\>  (move-to-section-initiator #\< #\>))

(#\/  (if (= (current-cell) 2)
(incf position)
(move-past-section-terminator #\/ #\\)))

(#\\  (move-to-section-initiator #\/ #\\))

(#\[  (if (or (= (current-cell) 2)
(= (random 2) 1))
(incf position)
(move-past-section-terminator #\[ #\])))

(#\]  (move-to-section-initiator #\[ #\]))

(otherwise
(error "Invalid command: ~s at position ~d." character position)))))))
```

An exemplary invocation is:

``` ;; Prints the character 'A' to the standard output.
(parse-rcem "r65s1l65(m+r1)mo")
```