vm.md

Virtual Machine Semantics

The uFork virtual machine is designed to support machine-level actors. All instructions execute within the context of an actor handling a message-event. There is no support for procedure/function call/return. Instead actors are used to implement procedure/function abstractions. There is no support for address arithmetic or load/store of arbitrary memory. Mutation is always local to an actor's private state. Immutable values are passed between actors via message-events. External events (such as "interrupts") are turned into message-events.

Representation

The quad-cell is the primary internal data-structure in uFork. It consists of four integers (current compile options are 16, 32, and 64 bits).

t	x	y	z
type/proc	head/car	tail/cdr	link/next

The integers in each field carry a type tag in their 2 most-significant bits (MSBs). The 1st MSB is {0=indirect-reference, 1=direct-value}. The 2nd MSB is {0=transparent, 1=opaque}. The resulting type-heirarchy looks like this:

                    any-value
                   0 /     \ 1
               indirect   direct (fixnum)
              0 /    \ 1
(quad) transparent  opaque (ocap)

Direct values (fixnums) are stored in 2's-complement representation, where the 2nd MSB is the sign bit of the integer value.

Indirect values (references) desigate quad-cells (with fields {t, x, y, z}).

Opaque values (object-capabilities) cannot be dereferenced except by the virtual-processor (to implement actor primitive operations).

Transparent values designate quad that may be written as well as read.

Data Structures

Quad-cells are used to encode most of the important data-structures in uFork.

Structure	Description
{t:Event_T, x:target, y:msg, z:next}	actor event queue entry
{t:IP, x:SP, y:EP, z:next}	continuation queue entry
{t:Instr_T, x:opcode, y:data, z:next}	machine instruction (typical)
{t:Symbol_T, x:hash, y:string, z:value}	immutable symbolic-name
{t:Pair_T, x:head, y:tail}	pair-lists of user data (cons)
{t:Pair_T, x:item, y:rest}	stack entry holding item
{t:Actor_T, x:beh, y:sp, z:?}	idle actor
{t:Actor_T, x:beh', y:sp', z:events}	busy actor, intially {z:()}
{t:Fexpr_T, x:actor, y:?, z:?}	interpreter (cust ast env)
{t:Fexpr_T, x:self, y:msgs, z:beh}	meta-actor transaction
{t:Dict_T, x:key, y:value, z:next }	dictionary binding entry
{t:Free_T, z:next}	cell in the free-list

Instructions

The uFork instruction execution engine implements a linked-stack machine, however the stack is only used for local state in a computation. The input for each instruction is taken from the stack and the output is placed back onto the stack. Instructions all have a t field containing Instr_T type marker. The operation code is carried in the x field of the instruction. Many instructions also have an immediate value, usually carried in the y field of the instruction. For the typical case of a instruction with a single continuation, the "next instruction" is carried in the z field of the instruction.

Input	Instruction	Output	Description
v	{x:VM_typeq, y:T, z:K}	bool	TRUE if v has type T, otherwise FALSE
T	{x:VM_cell, y:1, z:K}	cell	create cell {t:T}
T X	{x:VM_cell, y:2, z:K}	cell	create cell {t:T, x:X}
T X Y	{x:VM_cell, y:3, z:K}	cell	create cell {t:T, x:X, y:Y}
T X Y Z	{x:VM_cell, y:4, z:K}	cell	create cell {t:T, x:X, y:Y, z:Z}
cell	{x:VM_get, y:T, z:K}	t	get t from cell
cell	{x:VM_get, y:X, z:K}	x	get x from cell
cell	{x:VM_get, y:Y, z:K}	y	get y from cell
cell	{x:VM_get, y:Z, z:K}	z	get z from cell
cell T	{x:VM_set, y:T, z:K}	cell'	set t to T in cell
cell X	{x:VM_set, y:X, z:K}	cell'	set x to X in cell
cell Y	{x:VM_set, y:Y, z:K}	cell'	set y to Y in cell
cell Z	{x:VM_set, y:Z, z:K}	cell'	set z to Z in cell
... tail head	{x:VM_pair, y:n, z:K}	pair	create {t:Pair_T, x:head, y:tail} (n times)
pair	{x:VM_part, y:n, z:K}	... tail head	split pair into head and tail (n times)
pair	{x:VM_nth, y:n, z:K}	itemn	extract item n from a pair list
pair	{x:VM_nth, y:-n, z:K}	tailn	extract tail n from a pair list
—	{x:VM_push, y:value, z:K}	value	push literal value on stack
vn ... v1	{x:VM_depth, z:K}	vn ... v1 n	count items on stack
vn ... v1	{x:VM_drop, y:n, z:K}	—	remove n items from stack
vn ... v1	{x:VM_pick, y:n, z:K}	vn ... v1 vn	copy item n to top of stack
vn ... v1	{x:VM_dup, y:n, z:K}	vn ... v1 vn ... v1	duplicate top n items on stack
vn ... v1	{x:VM_roll, y:n, z:K}	vn-1 ... v1 vn	roll item n to top of stack
vn ... v1	{x:VM_roll, y:-n, z:K}	v1 vn ... v2	roll top of stack to item n
n	{x:VM_alu, y:NOT, z:K}	~n	bitwise not n
n m	{x:VM_alu, y:AND, z:K}	n&m	bitwise n and m
n m	{x:VM_alu, y:OR, z:K}	n|m	bitwise n or m
n m	{x:VM_alu, y:XOR, z:K}	n^m	bitwise n exclusive-or m
n m	{x:VM_alu, y:ADD, z:K}	n+m	sum of n and m
n m	{x:VM_alu, y:SUB, z:K}	n-m	difference of n and m
n m	{x:VM_alu, y:MUL, z:K}	n*m	product of n and m
m	{x:VM_eq, y:n, z:K}	bool	TRUE if n == m, otherwise FALSE
n m	{x:VM_cmp, y:EQ, z:K}	bool	TRUE if n == m, otherwise FALSE
n m	{x:VM_cmp, y:GE, z:K}	bool	TRUE if n >= m, otherwise FALSE
n m	{x:VM_cmp, y:GT, z:K}	bool	TRUE if n > m, otherwise FALSE
n m	{x:VM_cmp, y:LT, z:K}	bool	TRUE if n < m, otherwise FALSE
n m	{x:VM_cmp, y:LE, z:K}	bool	TRUE if n <= m, otherwise FALSE
n m	{x:VM_cmp, y:NE, z:K}	bool	TRUE if n != m, otherwise FALSE
n c	{x:VM_cmp, y:CLS, z:K}	bool	TRUE if n in c, otherwise FALSE
bool	{x:VM_if, y:T, z:F}	—	continue F if "falsy", otherwise continue T
—	{x:VM_msg, y:0, z:K}	msg	copy event message to stack
—	{x:VM_msg, y:n, z:K}	msgn	copy message item n to stack
—	{x:VM_msg, y:-n, z:K}	tailn	copy message tail n to stack
—	{x:VM_my, y:SELF, z:K}	actor	push current actor address on stack
—	{x:VM_my, y:BEH, z:K}	beh	push current actor behavior on stack
—	{x:VM_my, y:STATE, z:K}	v1 ... vn	push current actor state on stack
msg actor	{x:VM_send, y:0, z:K}	—	send msg to actor
mn ... m1 actor	{x:VM_send, y:n, z:K}	—	send (m1 ... mn) to actor
beh	{x:VM_new, y:0, z:K}	actor	create new actor with behavior beh
v1 ... vn beh	{x:VM_new, y:n, z:K}	actor	create new actor with (v1 ... vn . beh)
beh	{x:VM_beh, y:0, z:K}	—	replace behavior with beh
v1 ... vn beh	{x:VM_beh, y:n, z:K}	—	replace behavior with (v1 ... vn . beh)
reason	{x:VM_end, y:ABORT}	—	abort actor transaction with reason
—	{x:VM_end, y:STOP}	—	stop current continuation (thread)
—	{x:VM_end, y:COMMIT}	—	commit actor transaction
—	{x:VM_end, y:RELEASE}	—	commit transaction and free actor
chars	{x:VM_cvt, y:LST_NUM, z:K}	fixnum	convert chars to fixnum
chars	{x:VM_cvt, y:LST_SYM, z:K}	symbol	convert chars to symbol
char	{x:VM_putc, z:K}	—	write char to console
—	{x:VM_getc, z:K}	char	read char from console
value	{x:VM_debug, y:tag, z:K}	—	debug_print tag: value to console

Object Graph

The diagram below shows a typical graph of quad-cells representing the contents of the e_queue (event queue) and the k_queue (continuation queue). These two queues, plus the global symbol table, and the interrupt-handling actors, form the root-set of objects for garbage-collection.

e_queue: [head,tail]--------------------------+
          |                                   V
          +-->[Event,to,msg,next]---> ... -->[Event,to,msg,NIL]
                     |   |
                     |   +--> actor message content
                     V
                    [Actor,beh,sp,?]
                            |  |
                            |  +--> actor state (initial SP)
                            |
                            +--> actor behavior (initial IP)

k_queue: [head,tail]--------------------+
          |                             V
          +-->[ip,sp,ep,kp]---> ... -->[ip,sp,ep,NIL]
               |  |  |
               |  |  +-->[Event,to,msg,NIL]
               |  |             |   |
               |  |             |   +--> ...
               |  |             V
               |  |            [Actor,beh',sp',events]---> ... -->[Event,to,msg,NIL]
               |  V
               | [Pair,car,cdr,?]
               |        |   |
               |        |   +--> ... -->[Pair,car,NIL,?]
               |        V
               |       item
               V
              [Op,EQ,0,k]
                       |
                       +--> [Op,IF,t,f]
                                   | |
                                   | +--> ...
                                   V
                                   ...

Pair-List Indexing

Instructions like VM_nth and VM_msg have an immediate index argument (n) to succinctly designate parts of a pair-list.

• Positive n designates elements of the list, starting at 1.
• Negative n designates list tails, starting at -1.
• Zero designates the whole list/value (for messages).

  0            -1            -2            -3
---->[car,cdr]---->[car,cdr]---->[car,cdr]---->...
    +1 |          +2 |          +3 |
       V             V             V

...or more compactly...

0-->[1,-1]-->[2,-2]-->[3,-3]--> ...
     |        |        |
     V        V        V

If the index is out-of-bounds, the result is ? (undefined).

Character Classes

The {x:VM_cmp, y:CLS} instruction produces TRUE if a character value is part of the specified class, or FALSE otherwise. The class is defined as a union of the named classes:

• CTL Control Character
• DGT Decimal Digit
• UPR Uppercase Letter
• LWR Lowercase Letter
• DLM Delimiter
• SYM Name Symbol
• HEX Hexadecimal Digit
• WSP Whitespace

The tables below define which characters are included in each class.

ch	dec	hex	CTL	DGT	UPR	LWR	DLM	SYM	HEX	WSP
^@	0	00	x
^A	1	01	x
^B	2	02	x
^C	3	03	x
^D	4	04	x
^E	5	05	x
^F	6	06	x
^G	7	07	x
^H	8	08	x
^I	9	09	x							x
^J	10	0a	x							x
^K	11	0b	x							x
^L	12	0c	x							x
^M	13	0d	x							x
^N	14	0e	x
^O	15	0f	x
^P	16	10	x
^Q	17	11	x
^R	18	12	x
^S	19	13	x
^T	20	14	x
^U	21	15	x
^V	22	16	x
^W	23	17	x
^X	24	18	x
^Y	25	19	x
^Z	26	1a	x
^[	27	1b	x
^\	28	1c	x
^]	29	1d	x
^^	30	1e	x
^_	31	1f	x

ch	dec	hex	CTL	DGT	UPR	LWR	DLM	SYM	HEX	WSP
	32	20								x
!	33	21						x
"	34	22					x
#	35	23						x
$	36	24						x
%	37	25						x
&	38	26						x
'	39	27					x
(	40	28					x
)	41	29					x
*	42	2a						x
+	43	2b						x
,	44	2c					x
-	45	2d						x
.	46	2e						x
/	47	2f						x
0	48	30		x					x
1	49	31		x					x
2	50	32		x					x
3	51	33		x					x
4	52	34		x					x
5	53	35		x					x
6	54	36		x					x
7	55	37		x					x
8	56	38		x					x
9	57	39		x					x
:	58	3a						x
;	59	3b					x
<	60	3c						x
=	61	3d						x
>	62	3e						x
?	63	3f						x

ch	dec	hex	CTL	DGT	UPR	LWR	DLM	SYM	HEX	WSP
@	64	40						x
A	65	41			x				x
B	66	42			x				x
C	67	43			x				x
D	68	44			x				x
E	69	45			x				x
F	70	46			x				x
G	71	47			x
H	72	48			x
I	73	49			x
J	74	4a			x
K	75	4b			x
L	76	4c			x
M	77	4d			x
N	78	4e			x
O	79	4f			x
P	80	50			x
Q	81	51			x
R	82	52			x
S	83	53			x
T	84	54			x
U	85	55			x
V	86	56			x
W	87	57			x
X	88	58			x
Y	89	59			x
Z	90	5a			x
[	91	5b					x
\	92	5c						x
]	93	5d					x
^	94	5e						x
_	95	5f						x

ch	dec	hex	CTL	DGT	UPR	LWR	DLM	SYM	HEX	WSP
`	96	60					x
a	97	61				x			x
b	98	62				x			x
c	99	63				x			x
d	100	64				x			x
e	101	65				x			x
f	102	66				x			x
g	103	67				x
h	104	68				x
i	105	69				x
j	106	6a				x
k	107	6b				x
l	108	6c				x
m	109	6d				x
n	110	6e				x
o	111	6f				x
p	112	70				x
q	113	71				x
r	114	72				x
s	115	73				x
t	116	74				x
u	117	75				x
v	118	76				x
w	119	77				x
x	120	78				x
y	121	79				x
z	122	7a				x
{	123	7b					x
|	124	7c					x
}	125	7d					x
~	126	7e						x
^?	127	7f	x

Common Code Structures

Many instruction streams end with a common suffix. These immutable continuation sequences are available to be shared by many behaviors.

K_CALL:     [MSG,+0,k]---+
                         |
                         |
RESEND:     [MSG,+0,k]   |    RV_ZERO:    [PUSH,+0,k]-----+
                    |    |                                |
                    v    |                                |
            [SELF,?,k]---+    RV_NIL:     [PUSH,NIL,k]----+
                         |                                |
                         |                                |
RV_SELF:    [SELF,?,k]   |    RV_UNDEF:   [PUSH,UNDEF,k]--+
                    |    |                                |
                    v    |                                |
CUST_SEND:  [MSG,+1,k]<--|--------------------------------+
                    |    |
                    v    |
SEND_0:     [SEND,0,k]<--+    RELEASE_0:  [SEND,0,k]
                    |                             |
                    v                             v
COMMIT:     [END,+1,?]        RELEASE:    [END,+2,?]