RCEM
Jump to navigation
Jump to search
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))))
(read-integer ()
(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)
(let ((number-of-steps (read-integer)))
(declare (type integer number-of-steps))
(incf pointer number-of-steps)))
(#\l (incf position)
(let ((number-of-steps (read-integer)))
(declare (type integer number-of-steps))
(decf pointer number-of-steps)))
(#\s (incf position)
(let ((new-cell-value (read-integer)))
(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_")
(let ((input (read)))
(declare (type T input))
(setf (current-cell) input)))
(#\x (expect-token "x_")
(setf (current-cell) (random 3)))
(#\^ (incf position)
(let ((pointer-offset (read-integer)))
(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)
(let ((pointer-offset (read-integer)))
(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)
(let ((new-cell-value (read-integer)))
(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))
(setf start-cell-index (read-integer))
(expect-token "::")
(setf end-cell-index (read-integer))
(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))
(setf start-cell-index (read-integer))
(expect-token "::")
(setf end-cell-index (read-integer))
(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")