Runt: a proposed virtual machine specfication

2016-10-14

In my recent efforts working with Polysporth, I found myself battling the scheme Garbage Collector when trying to implement callbacks. After many no-go efforts, I began scheming up a system that could persitently hold procedures and call C functions. What came out was a creation I call Runt. While no lines of actual C code have been written, I have thought out much of system in the writeup below.

Description

Runt is a stack-based, static memory, virtual machine to be written in ANSI C.

Some of the features may include:

Macros and typedefs

 enum {
     RUNT_NOT_OK = 0,
     RUNT_OK = 1,
     RUNT_NIL = 0,
     RUNT_FLOAT,
     RUNT_STRING,
     RUNT_CELL
 };

Data structures

Pointer

 typedef struct {
     runt_type type;
     void *ud;
 } runt_ptr;

Procedure

 typedef runt_int runt_proc (runt_vm *, runt_ptr);

Here is an example of a procedure.

 static runt_int runt_add(runt_vm *vm, runt_ptr p)
 {
     if(runt_check_stack(rd, 2, "ff") =! OK) return RUNT_NOT_OK;
     runt_stacklet *v1 = runt_pop(rd);
     runt_stacklet *v2 = runt_pop(rd);
     runt_stacklet *v3 = runt_push(rd);
     runt_float v1f = v1->p.f;
     runt_float v2f = v2->p.f;
     v3->f = v1f + v2f;
     return RUNT_OK;
 }

Cell

 typedef struct {
     runt_proc proc;
     runt_ptr data;
     runt_uint psize;
 } runt_cell;

Stacklet

 typedef struct {
     runt_ptr p;
     runt_float f;
 } runt_stacklet;

Stack

 typedef struct {
     stacklet stack[MAX_SIZE];
     runt_int pos;
     runt_int size;
 } runt_stack;

List

A runt_entry is a single link for a linked list. The init function is called every time a new cell is added. 

 typdef struct runt_list {
     runt_cell *cell;
     runt_proc init;
     struct runt_list *next;
 } runt_entry;
 typedef struct {
     runt_int size;
     runt_entry root;
     runt_entry *last;
 } runt_list;

Dictionary

 typedef struct {
     runt_int size;
     runt_list list[128];
 } runt_dict;

Pool

 typedef struct {
     unsigned char *data;
     runt_uint size;
     runt_uint used;
 }

Main Data struct

VM functions

Pools

Before Runt can call anything, the various memory pools must manually be created and initialized. There are two memory pools in Runt: the cell pool and the memory pool. The cell pool is space where procedures are stored, and the memory pool is where cells can allocate data without having to worry about freeing it.

runtcellpool_set sets the cell memory pool

 runt_int runt_cell_pool_set(runt_vm *vm, runt_cell *cell, runt_uint size);

runtcellpool_init after setting the cell pool, zeros out the cell pool (sets thing to nil)

 runt_int runt_cell_pool_init(runt_vm *vm, runt_cell *cell);

runtmemorypool_set sets the memory pool 

 runt_int runt_memory_pool_set(runt_vm *vm, unsinged char *buf, runt_uint size);

runt_malloc allocates memory from the pool. Returns (N + 1), the position in the memory pool

 runt_uint runt_malloc(runt_vm *vm, size_t size, void **ud);

Cell operations

Cells are the atomic unit in Runt. Inside every cell is a function and user data associated with that cell.

runtnewcell gets a new cell from the cell pool.

 runt_uint runt_new_cell(runt_vm *vm, runt_cell \*\*cell);

runtlinkcell links a cell to another cell. used to call procedures 

 runt_int runt_link_cell(runt_vm *vm, runt_cell *src, runt_cell *dest);

runt_bind binds function + pointer data to cell

 runt_uint runt_bind(runt_cell *cell, runt_proc proc, runt_ptr data);

runt_call executes a single cell

 int runt_call(runt_vm *vm, runt_cell *cell);

runt_exec iterates through a contiguous group of cells determined of size cell->psize

 int runt_exec(runt_vm *vm, runt_cell *cell);

Stack operations

runt_pop and runt_push pop and push stacklet pointsers on the stack. These can then be read and written to. 

 runt_stacklet * runt_pop(runt_vm *vm);
 runt_stacklet * runt_push(runt_vm *vm);

Pointers

runtmkpointer turns a void pointer into a runt pointer

 runt_ptr runt_mk_pointer(runt_type type, void *ud);

runtrefto_cptr takes an integer and gets the actual block of memory, filled into ud. Returns RUNTOK on sucess, RUNTNOT_OK on failure.

 runt_int runt_ref_to_cptr(runt_vm *vm, runt_uint ref, void **ud);

Dictionary

Procedures added to Runt can be associated with a string keyword in something called a dictionary. To make a word in a dictionary, you create an entry with the C function and optional init function for allocation, then add this table to the hash table.

runtentrycreate allocates memory for a new entry from the memory pool, then assigns the variables. What is returned is the reference. A value of zero indicates failure.

 runt_uint runt_entry_create(runt_vm *vm, runt_cell *cell, runt_proc init, 
     runt_entry **entry);

runt_word adds a new word to the dictionary which points to an entry

 runt_int runt_word(runt_vm *vm, 
     const char *name, 
     runt_int size, 
     runt_entry *entry);

runtwordsearch looks for an entry in the dictionary

 runt_int runt_word_search(runt_vm *vm, 
     const char *name, runt_int size, runt_entry **entry);

Lexing and parsing

In addition to the VM, Runt has a Forth-like language built around it. These are the functions needed.

runt_compile compiles a string to cells

 runt_int runt_compile(runt_vm *vm, const char *str);

runt_lex is called repeatedly. It parses each word in the string and returns the type of the word. pos is updated to the position of the next word.

 runt_type runt_lex(runt_vm *vm, const char *str, 
    runt_int size, runt_int *pos);

Procedures

Procedures int Runt do things. In Runt, every cell is a procedure, but cells can also be grouped together as a procedure.

runtprocbegin starts a procedure. cells added to the cell pool will be included in this procedure until runtprocend is called.

 runt_int runt_proc_begin(runt_vm *vm, runt_cell *proc);

runtprocend closes a procedure being made.

 runt_int runt_proc_end(runt_vm *vm);

runtproczero Is a dummy function that does nothing. It is the default function in all cells, as well as the function you should pass 

 runt_int runt_proc_zero(rung_vm *vm, runt_ptr p);