Esolang Concepts: The Counterinterpreter

Let's define the following instruction set for a stack-based calculator:

• neg negate that top of the stack
• add pop two items, add them, then push result
• sub pop two items, subtract them, then push result
• mul pop two items, multiply them, then push result
• div pop two items, divide them, then push result
• srt pop one itme, computer square root, then push result
• swp swap top two items
• dup duplicate top item
• jmp jump to address specified by top of stack
• nop no operation

A typical interpreter preforms instructions as stated in sequence. Each instruction is interpreted as some action. And, each instruction corresponsed to only a single action. With a normal interpreter dup mul swp dup mul add srt, defines a square root.

A counterinterpreter preforms everything but the stated action. dup would represent the following set of instructions: {neg add sub mul div srt swp jmp nop}. A counterinterpreter could choose a random instruction for the underlying interpreter to run. In this model, a counterinterpeter is an unpredictable stochastic machine.

Alternatively, it could fork into multiple interpreters each running one instruction. When the next instruction is read, the threads are permuted into further sub-interpreters. Thus, the number of active programs rapidly explodes.

Constraints Programming

A counterinterpreter could also be implemented using constraints. For example, the square program could be expressed as the following sequence:

wont neg add sub mul div srt swp jmp nop
wont neg add sub div srt swp dup jmp nop
wont neg add sub mul div srt dup jmp nop
wont neg add sub mul div srt swp jmp nop
wont neg add sub div srt swp dup jmp nop
wont neg sub mul div srt swp dup jmp nop
wont neg add sub mul div swp dup jmp nop
wont add sub mul div swp dup jmp

This is the same program from the interpreter encoded into the counterinterpreter. Take note of the last instruction. It represents the possible actions of {nop neg}, in a counterinterpreter with forking instructions, it could compute both the positive and negative square roots simultaniously. In a stochastic counterinterpreter, the result will be random.

The Jump Instruction

Thus, every program in a counterinterpreter forces the programmer to beg its code to not do something unexpected. Especially when it comes to jmp. Jump in a counterinterpreter goes to everywhere but the address given. This makes flow control logic incredibly difficult.

For a forking counterinterpreter, it could mean creating thousands, millions, or billions of interpreters who's instruction pointer has been jumped to every location in program memory. For a stochastic counterinterpreter, this means jumping to a random location in program memory.

This would make jmp an impossible to use operation without filling the program memory with noop. However, a constraint approach could be used to mark locations as "invalid". For example, lets change the instruction set to just jmp (jump), inc(increment cell), and shn (show number). The following program prints a stream of numbers:

( define a no-operation that can be jumped to )
    wont jump, wont show number, wont increment
( increment the counter )
    wont jump, wont show number, cant jump here
( show the number )
    wont jump, wont increment, cant jump here
( jump to the only valid spot )
    wont show number, wont increment, cant jump here

The counterprogram declares lines 2, 3, and 4 cannot be selected by jmp. Line 1, declares a no-op that can be targeted. Then, the program proceeds to run inc shn jmp.

Literal Values

Literals are another challenge with counterinterpreters. A counter-lit instruction produce any or all values unspecified. Lets strip the instruction set to just lit and add. In a constraint-based approach, the counterprogram to lit 2 lit 3 add could be:

( summon the number 2 )
    wont add, isnt less than 2, isnt more than 3
( summon the number 3 )
    wont add, isnt less than 3, inst more than 4
( add the number together )
    wont be

Implementations

A possible candidate for an implementation of a counterinterpreter is DOESNT. Rules in DOESNT specify shouldn't be consumed rather than what should be consumed. The fizzbuzz example shows how the number of undesired states rapidly grows.