UM-32

UM-32 "Universal Machine" is a virtual machine used in the 2006 ICFP Programming Contest. It was supposedly created by an ancient secret society, the Cult of the Bound Variable, in 200 BC. The machine had eight registers, a replaceable codespace, and dynamic memory allocation. The opcodes could refer three registers (indexed A, B, C). The 14 opcodes:

0: if C, A = B
1: A = B[C]  indirect memory load
2: A[B] = C  indirect memory store
3: A = B + C
4: A = B * C
5: A = B / C
6: A = B nand C
7: halt
8: B = allocate C words
9: deallocate C
10: putchar(C)
11: C = getchar()
12: program load: duplicate memory in B into code space, and set instruction pointer to C 
13: A = load immediate (25-bit quantity)

The UM-32 Universal Machine is a virtual machine with simple instructions, each instruction encoded in a 32-byte integer. The machine has 8 general-purpose registers and a segmented memory model. The program can dynamically allocate and free segments ("arrays") of any size. The memory can then be addressed as an array of 32-bit words ("platters"), using a combination of the segment id and the index, both in registers. The memory stores both data and code: each instruction stored as a 32-byte word. There are 14 instructions, consisting of literal load, simple arithmetic on the registers, memory access, indirect jump, allocation and deallocation of segments, and byte input/output. The specification describes how the machine is initialized by reading a single segment from a source file.

If you don't count the limit of the address space (at most 2**32 segments, 2**32 words in each segments), the language is Turing complete.

About the contest

Even more amazing, once the virtual machine was implemented, the remainder of the contest unfolded, uncovering an entire Unix-like operating system (UMIX) containing even more esoteric languages:

QBASIC

The first language encountered was a relatively mundane version of BASIC, but with one evil twist.

All line numbers and numeric literals had to be Roman numerals! One had to extend a corrupted QBASIC program to advance.

2-D

This language was a combination of list processing, Peano numbers, and two-dimensional code.

Given an example that added two Peano numbers, The contest asked you to provide multiplication, list reversal, and a ray tracer.

Peano Addition in 2-D

,....|.............................,
:add v               +----+        :
:*==================*|    v        :
:!send [(N,S),(N,E)]!+  *=====*    :
:*==================* +>!use a!+   :
:++   *==============*| *=====*|   :
-#--->!case W of E, S!+        |   :
:|    *==============*         v   :
:|      |        *================*:
:|      v        !send [(Inl N,E)]!-
:| *============**================*:
:+>!send [(W,E)]!-------------------
:  *============*                  :
,..................................,

External resources

• Main contest site
• Virtual machine specification
• The "Codex", which UM-32 is meant to decode to obtain documents to submit to the contest.

See also

• Intcode, another interpreted language used in a programming competition to give machine readable descriptions of how to verify solutions.

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.