ObCode

ObCode is a stack-based, Turing complete esoteric programming language created by User:Challenger5. It can be considered a Turing Tarpit.

It is based on "Objects", which are lists of zero or more other objects.

Syntax

The ObCode parser only recognizes two characters, ( and ). All others are ignored. Oftentimes ; or , will be used for clarity.

Ignoring unused characters, ObCode programs must conform to the following grammar:

obj     ::= "()" || "(" + objList + ")"
objList ::= obj || obj + objList
program ::= obj

So this is a valid object:

(((())()())(()()()))

But these are not:

)(
((())()((())(()))

Execution Model

ObCode uses an unbounded stack of stacks for memory, as well as one register. All data is in the form of ObCode objects. Most stack operations operate on the top stack.

ObCode programs are parsed into a single ObCode object. Each element of the object is then interpreted as an instruction:

Instruction  Alias   Action

()           NOP     No-op (Does nothing)
(())         PUSH    The next item in the list should be interpreted as data and pushed onto the current stack.
(()())       STORE   Pop an object from the current stack and store it in the register.
((())())     LOAD    Push the object currently held in the register.
(()(()))     WHILE   Pop an object and execute it as code until the current stack is empty.
((())(()))   USING   Pop an object from the current stack and push the object as a new stack.
((()))       END     Pop the entire current stack as an object and push it onto the stack underneath it.
((()()))     SWAP    Swap the top two objects on the current stack.
(()()())     OUT     Pop an object, take the length, and print the ASCII character corresponding to that number.
((())()())   IN      Read a character from input and push an object containing as many empty objects as the ASCII value of that character.
(()()(()))   CAT     Pop two objects and concatenate them.
((()())())   DEF     Pop a, pop b. Redefine b as an instruction that does a.

Example Program

Hello World program:

((())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())(())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()))

Output in ObCode is generally very cumbersome.

Cat Program (1 character):

(
	((())()())
	(()()())
)

Cat Program (Forever):

(
	(()) ()
	(()) (((())(()))((())()())(()()())((())))
	(()(()))
)

Cat Program (Until EOF):

(
	Input once
	((())()())
	Put the input onto a new stack
	((())(()))
	While the stack is nonempty, output and input.
	(())(
		((()))
		(()()())
		((())()())
		((())(()))
	)(()(()))
)

Truth-machine:

((())((()())((())())((())())(()()(())))(())()((()())())(())(()()())()()()()(()())((())())((())())((())()())(()())((())())((())())(()()())((()()))((())(()))(())((()())((()))((()()))((())(())))()(()(()))((()))(()())((()()))(())(())(()()(()))((())(()))((()()))(())(((()))((()()))(()())((())())((())())(()()())((()()))((())(())))(()(())))

Computational Class

This language has the standard commands seen in stack-based languages. It is possible to simulate two stacks by having the root stack contain two objects which are repeatedly turned into new stacks. It should be possible to compute on the lengths of the objects, so a representation of numbers can be created. All of this evidence pointed to ObCode being Turing Complete, and indeed it has been proven now:

Every brainfuck program can be converted to ObCode with this translation table (BEGIN and END means the corresponding code must be put at the beginning/end of every program):

 brainfuck -> ObCode
 BEGIN        ( (())() (())(()) ((())(()))
 +            (())(()) (()()(()))
 -            ((())(())) (()()) ((()))
 .            (()()) ((())()) ((())()) (()()())
 ,            (()()) ((())()())
 <            ((())) ((()())) (())(()) ((()())) (()()(())) ((())(())) (()()) ((())) ((()())) ((())(())) ((())())
 >            (()()) ((())) ((()())) ((())(())) ((())()) ((())) ((()())) (())(()) ((()())) (()()(())) ((())(()))
 [            ((())(())) (())( ((()))
 ]            ((())(())) )(()(())) ((()))
 END          )

ObCode does almost certainly classify as a Turing Tarpit. However, there are several unnecessary instructions. NOP is obviously not necessary. PUSH could be eliminated through heavy use of the register if the stack started out with an empty object on it, or if USING was simply used at the beginning to produce an empty object. CAT could be avoided through usage of USING and END, and DEF is not necessary. If all these changes were implemented, the language could be reduced down to 8 instructions. Not only does it have very few instructions, the language only has two unique characters, and programming in it leads to very large programs.

Binary ObCode

Because ObCode only has two characters, it can be trivially converted into binary. Let's use our Cat Program as an example:

((())()(())(((())(()))((())()())(()()())((())))(()(())))

Because the program will always start with (, it is natural to replace ( with 1 and ) with 0:

((())()(())(((())(()))((())()())(()()())((())))(()(())))
11100101100111100110001110010100110101001110000110110000

We then convert it to hexadecimal:

E5 9E 63 94 D4 E1 B0

To interpret Binary ObCode, convert the hex to binary (removing any leading 0s) and turn it into parenthesis, then interpret it as ObCode.

External resources

• Interpreter in Python. Supports a more efficient variant of Binary ObCode.