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))))
 (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")
== References ==
* Wikipedia:Ternary numeral system
Category:Turing tarpits 
Category:Cell-based 
Category:Implemented 
Category:Languages
Category:2008
Category:Turing complete