Melvin E. Conway’s proposal for an UNCOL

This is an abstract machine described in a letter in 1958 as a compilation target for programming languages. The idea is that each of its instructions expects arguments at predetermined locations in memory, and there is a single special instruction for copying memory. Consider this program:

(G:a, A:1)
(G:b, A:2)
X(sum)
(R:1, G:c)

The first two instructions copy the values of variables a and b from the G-general storage to the A-argument storage. The instruction sum assumes two items in the A storage and puts the result to the R-result storage to be put into the variable c.

There is special syntax for copying constants: mark the origin with an asterisk. Beyond this general idea, the letter doesn’t elaborate on instructions for other tasks such as control flow or indexing of data structures, it’s assumed that the needed instructions can be specified according to the needs for a language that is to be compiled.

I find this model interesting because it shares an idea with Forth: an instruction expects its arguments to be initalised before its invokation, and after its execution, the caller is responsible for handling the returned data. This is what you come up with if you attempt to make Forth work without a stack. I also see a similarity with regular machine code, except that an instruction’s parameters, instead of being fields, are taken out and encased in their own kind of instruction. I like the implication that the arguments to the transfer instruction are completely static.

I couldn’t help myself but make an interpreter. Source code in Forth is below with example programs.

Example: addition

variable Va
variable Vb
create program
(* 2 ->G Va );
(* 3 ->G Vb );
(G Va ->A 1 );
(G Vb ->A 2 );
X( sum );
(R 1 ->A 1 );
X( writenum );
end.
program run cr

Example: loop

create program
(* 1 ->T 1 );
(* 6 ->T 2 );
(* 0 ->T 3 );
begin; ( loop )
(T 1 ->A 1 );
(T 2 ->A 2 );
X( less );
(R 1 ->A 1 );
cond; ( while )
	(T 3 ->A 1 );
	(T 1 ->A 2 );
	X( sum );
	(R 1 ->T 3 );
	(T 1 ->A 1 );
	(* 1 ->A 2 );
	X( sum );
	(R 1 ->T 1 );
endloop;
(T 3 ->A 1 );
X( writenum );
end.
program run cr

Source

( mode )
0 constant MX ( execute )
1 constant MA
2 constant MR
3 constant MT
4 constant MG
5 constant MC ( constant )

( interpreter )

variable IP

: >storage ( index mode -- addr )
	1- 5 lshift + cells here + ;

: load ( parameter mode -- x )
	dup MC = if drop
	else dup MG = if drop @
	else >storage @
	then then ;

: store ( x parameter mode -- )
	dup MG = if drop else >storage then ! ;

: transfer ( -- )
	IP @ dup cell+ @ over @ load
	swap cell+ cell+ dup cell+ @ swap @ store
	4 cells IP +! ;

: instruction ( -- )
	IP @ 2 cells IP +! cell+ @ execute ;

: run ( addr -- )
	IP ! begin IP @ while
	IP @ @ if transfer else instruction then repeat ;


( instructions )

: finish
	0 IP ! ;

: jump ( IP <- A1 )
	1 MA load IP ! ;

: cond ( IP <- A2 if A1 = 0 )
	1 MA load 0= if 2 MA load IP ! then ;

: writenum ( A1 )
	1 MA load . ;

: sum ( R1 <- A1 + A2 )
	1 MA load 2 MA load + 1 MR store ;

: less ( R1 <- A1 < A2 )
	1 MA load 2 MA load < 1 MR store ;


( assembler )

: begin; ( -- addr ) here ;
: (G ( -- mode ) MG ;
: (A ( -- mode ) MA ;
: (R ( -- mode ) MR ;
: (T ( -- mode ) MT ;
: (* ( -- mode ) MC ;
: -> ( mode parameter -- ) swap , , ;
: ->G -> MG ;
: ->A -> MA ;
: ->R -> MR ;
: ->T -> MT ;
: X( ( -- mode parameter ) MX ' ;
: [X]' ( word -- ) MX , , ;
: [X] ( -- ) ' postpone literal ['] [X]' compile, ; immediate
: ); ( mode parameter -- ) -> ;
: end. ( -- ) [X] finish ;

: cond; ( -- addr )
	here (* 0 ->A 2 );
	[X] cond ;

: endcond; ( addr -- )
	here swap cell+ ! ;

: again; ( addr -- )
	(* swap ->A 1 );
	[X] jump ;

: endloop; ( addr addr -- )
	swap again; endcond; ;