Intcode

Intcode is an esoteric programming language created purely to annoy programmers competing in the Advent of Code 2019. It was featured on days 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 and 25. 
== Program Structure ==
An Intcode program is a list of integers (positive and negative) seperated by commas. In other words, programs will look something like this:
 1, 3, 4, 2, 99
Intcode implements a von Neumann architecture with unbounded memory consisting of unbounded integer cells indexed starting from 0.
The program is copied to the beginning of the memory before execution starts; the remaining cells are initialized to 0.
The Intcode virtual machine has two registers, an instruction pointer which points to the current instruction, and a relative base pointer used for relative addressing.
Initially, both registers are 0.
== Advent of Code ==
Day	Program 	Link
02 	Gravity Assist 	Day 2
05 	Thermal Environment Supervision Terminal (TEST) 	Day 5
07 	Amplification Circuit 	Day 7
09 	Basic Operation Of System Test (BOOST) 	Day 9
11 	Emergency Hull Painting Robot 	Day 11
13 	Arcade Cabinet 	Day 13
15 	Repair Droid 	Day 15
17 	Aft Scaffolding Control and Information Interface (ASCII)	Day 17
19 	Tractor Beam Testing Drone 	Day 19
21 	Springscript For A Springdroid 	Day 21
23 	Network Interface Controller (NIC) 	Day 23
25 	Cryostasis 	Day 25
== Instruction Format ==
The value pointed to by the instruction pointer is read as a decimal value with digits ABCDE.
The lower digits DE define the opcode, whereas C, B, A define the parameter mode of the first, second, and third parameter of the instruction, respectively (if any).
=== Opcodes ===
Op	Params	Description
01	3 	Adds the first two arguments and stores the result in the third argument.
02	3 	Like 1, but for multiplication.
03	1 	Inputs a single integer and stores it in the first argument.
04	1 	Outputs the first argument.
05	2 	If the first argument is non-zero, sets the instruction pointer to second argument.
06	2 	Like 5, but jumps if the first argument is zero.
07	3 	If the first argument is less than the second argument, writes 1 to the third argument. Otherwise, writes 0.
08	3 	Like 7, but check equality instead.
09	1 	Adds the first argument to the relative base register.
99	N/A 	Halts the program.
Except after jumps, the instruction pointer is advanced to the next instruction after the completion of the current one.
=== Parameter Modes ===
Parameter modes impact how arguments are read or written. Three parameter modes are defined.
* Mode 0, position mode: the parameter is the address of a cell to be read or written.
* Mode 1, immediate mode: the parameter is the value read. (This mode is never used for writing.)
* Mode 2, relative mode: the parameter is added to the relative base register to obtain the address of the cell to be read or written.
=== Evolution ===
The features were introduced incrementally over time.
* Day 2, part 1 defined only opcodes 01, 02 and 99, and had no parameter modes (all parameters were treated in position mode).
* Day 5, part 1 added opcodes 03 and 04, and immediate mode.
* Day 5, part 2 added opcodes 05 to 08.
* Day 9, part 1 added opcode 09 and relative mode.
=== Proposed Assembly Syntax ===
The most basic syntax that supports labels could look as follows (in EBNF).
 input ::= { line '\n' } ;
 
 line ::= [ identifier ':' ] [ instr | directive ] ;
 
 directive ::= 'DATA' { expr [','] } ;
 
 instr ::= op { param [','] } ;
 
 op ::= 'ADD' (* 01 *) | 'MUL' (* 02 *) | 'IN' (* 03 *) | 'OUT' (* 04 *) | 'JZ' (* 05 *)
 | 'JNZ' (* 06 *) | 'SLT' (* 07 *) | 'SEQ' (* 08 *) | 'INCB' (* 09 *) | 'HALT' (* 99 *) ;
 
 param ::= [ '#' (* mode 1 *) | '@' (* mode 2 *) ] expr ;
 
 expr ::= expr '+' expr | expr '-' expr
 | expr '*' expr | expr '/' expr
 | '+' expr | '-' expr
 | '(' expr ')' | identifier | number ; (* with the usual precedence resolution *)
Many extensions are possible. One interesting idea is to add labels to parameters. This would facilitate patching instructions (for example, to implement indirect addressing).
 param ::= ... | [ '#' | '@' ] '[' identifier ':' expr ']' ;
.ints could be a good standard file extension for Intcode assembly.
== Example Programs == 
=== Hello, World! ===
Outputs are interpreted as ASCII characters.
 4,3,101,72,14,3,101,1,4,4,5,3,16,99,29,7,0,3,-67,-12,87,-8,3,-6,-8,-67,-23,-10
=== Count from 1 to 10 ===
 4,17,4,19,1001,17,1,17,8,17,18,16,1006,16,0,99,-1,1,11,32
=== Calculate factorial for a given number ===
The following program calculates the factorial of a number, including zero factorial
 3, 34, 1007, 34, 1, 35, 1005, 35, 30, 1001, 34, 0, 33, 1001, 33, -1, 33, 1006, 33, 27, 2, 34, 33, 34, 1005, 33, 13, 4, 34, 99, 104, 1, 99
=== Langton's ant ===
This works for the hull painting robot introduced on day 11.
 1101,0,11111,0,3,1,102,-1,1,1,101,1,1,1,4,1,4,1,101,-1,2,2,1005,2,4,99
== Interpreters == 
Each contestant had to write their own interpreter, so many interpreters exist. Some examples are collected here.
* Intcode/Interpreters: Python
* Starwort's interpreter: Python
== Computational Class ==
With the addition of control flow on day 5, Intcode is powerful enough to be Turing-complete.
It may be interesting to study minimal Turing-complete subsets of Intcode.
For example, the subset consisting of instructions 01 (addition) and 05 (jump if equal to zero) and only position mode is Turing-complete.
If we add 03 and 04 for I/O, 07 (set if less than) for better performance, and 99 for termination, we should be able to write a decently efficient full Intcode interpreter.
== See also ==
* UM-32, another interpreted language used in a programming competition to give machine readable descriptions of how to verify solutions.
Category:2019
Category:Implemented
Category:Languages
Category:Self-modifying
Category:Turing complete