Impera

From Esolang
Jump to: navigation, search

Impera is an esoteric programming language that takes the imperative programming to its absolute minimum. It was created by User:Plugnburn on August 5, 2013 for 140byt.es contest with the goal to create an imperative language interpreter as small as possible in JS while keeping it Turing-complete.

Language structure and program flow

Impera implements a virtual machine with unbounded number of registers, all initially set to 0. All registers can get non-negative integer values.

Impera code starts with [ (opening square bracket), consists of the instructions separated with a comma, and ends with ] (closing square bracket). Each instruction, in turn, starts with [ (opening square bracket), consists of three values separated with a comma, and ends with ] (closing square bracket).

Any instruction has the following structure: [opcode,reg,addr].

opcode can be either 0, in which case it means JZDEC instruction, or any non-zero value (including non-integers), in which case it means INCJ instruction. Yes, there are no other instructions in Impera.

reg is a register index (it may be non-integer, so consider it a variable name) that references the memory cell for current operation.

addr must be a non-negative integer value specifying where to jump (or not to jump, depending on the opcode) after performing current operation.

Given that, let us explain the instruction semantics (for simplicity sake, INCJ instruction will be 1, although it can be any non-zero value in real code):

  • INCJ instruction: [1,reg,addr] - increment the register at the reg index and unconditionally jump to instruction addr;
  • JZDEC instruction: [0,reg,addr] - if the value of the reg register is zero, jump to instruction addr, else decrement the reg register.

Instruction pointer numeration starts from 0. The program continues to run until the instruction pointer doesn't meet a valid instruction. That can occur either when all instructions are exhausted in the code, or a jump to a non-existent instruction is performed (e.g. [1,0,8] will effectively halt a 8-instruction program, as well as [1,0,99]).

Examples

Add two numbers 5+7 (note that reference implementation has a trick that allows commenting but this possibility is not in the language specification so don't rely on it):

[
	[1,1,1],[1,1,2],[1,1,3],[1,1,4],[1,1,5], //set the register 1 to 5
	[1,2,6],[1,2,7],[1,2,8],[1,2,9],[1,2,10],[1,2,11],[1,2,12], //set the register 2 to 7
	[0,2,14],//while we can decrement the second number...
	[1,1,12],//...increment the first (the previous instruction has the index 12)
	[0,1,15],[1,1,16] //finalization
]

Other examples are coming soon. ;)

Implementation

Impera reference implementation in JavaScript is only 120 bytes long:

function(i,p,s,u,m){for(i=eval(i),p={},s=0;u=i[s++];)m=+p[u[1]]||0,+u[0]?(m++,s=+u[2]):m?m--:s=+u[2],p[u[1]]=m;return m}

It takes the string with Impera code as the input and returns the last accessed register as the output.

Turing completeness

Impera implements a variant of Minsky machine with unbounded storage, so it's Turing complete.

See also