Runtime
Irken's runtime is a static tagged runtime, which does not perform parametric instantiation. This makes it a mixture of what you normally see in static and dynamic runtimes.
Like a static runtime, Irken emits efficient static code for non-polymorphic operations, such as integer arithmetic, or field access to non-polymorphic record fields.
Like a dynamic runtime, every machine-word in Irken's runtime is tagged. This means all Irken immediate types take up a full machine word in Irken, even boolean and char values. This allows the garbage collector to look at any machine-word value and determine if it is a pointer or not. In addition, boxed allocations (like records and boxed variants) also contain a type-header. This allows lookup_field to perform dynamic record field lookups by looking at the type tag (see below). The fact that every piece of data is tagged simplifies debugging enormously, and allows the runtime to print out objects in a useful manner.
Irken's runtime is similar to OCaml's runtime, which tags values to distinguish between immediates and pointers, and uses runtime polymorphic dispatch for objects.
Records in Irken are structurally typed, meaning when we write the function (define (fun a) a.x), it works for any record which contains a .x field. However, all records don't put their .x field in the same place. How does Irken deal with this?
If a record field is only used in a single record type in the whole program, then it can only be at a single offset, and there is no runtime polymorphism for that field. In this case, the Irken compiler emits static offsets for that field lookup.
If a record field is used in more than one record type, such as .x in the record types {x=1 b=1} and {foo=1 x=1}, then there may be runtime polymorphism on that record type, because the .x field can be found at different offsets depending on which record is handed to a function {x=int ...}. In this case Irken emits dynamic lookups for accesses to the .x field. These lookups call a single generated loopup_field(record_ptr,field_id) implementation which examines the runtime type tag of the record, and looks up the offset of the corresponding field_id.
(For the code, see emit-record-get and guess-record-type)
Unfortunately, this means that the performance of field lookups is slower if field names are re-used in multiple types, even if those types are never used polymorphically. In the future this could be fixed with a combination of parametric instantiation in the c-backend, and JIT and Polymorphic Inline Caching in the VM.
Because the Irken C-backend is currently a whole-program compiler only, lookup_field() is implemented as a nested-switch dispatch table, which a C compiler will optimize into a jump table or linked branch (binary search).
Currently, the bytecode backend performs the same optimization, encoding unambigious field lookups as static tupref instructions, and potentially polymorphic ones as dynamic lookup rref instructions.
After typing and optimization, the program is transformed into a Continuation Passing Style register-machine language before the final output. This allows Irken to support continuations, and heap-allocated stack frames. As a result, user-space threading is extremely lightweight and memory efficient, as pre-allocated stacks are not required.
This chart illustrates tagging on 32bit binary words:
xxxx xxxx xxxx xxxx | xxxx xxxx xxxx xxx1 integer
xxxx xxxx xxxx xxxx | xxxx xxxx xxxx xx00 pointer
xxxx xxxx xxxx xxxx | xxxx xxxx tttt tt10 char, bool, undefined,
immediate variants
Boxed object header:
nnnn nnnn nnnn nnnn | nnnn nnnn tttt tttt t = tag,
n = number of words in boxed object
It's important to note that tags are not all globally unique type tags. Immediates, Records, and Polymorphic variants receive global type tags, while static variants share tags.
Integers are tagged with a single bit, the least significant. This allows the runtime to distinguish an integer by looking only at this bit. Any odd value is an integer. This means our int datatype loses one bit of information. In the 16-bit days, this was horribly painful. In the 32-bit days, it was a mild inconvenience. Today, with 64 bits, I would claim that it hardly matters at all.
Characters, Booleans(#t, #f), Undefined (#u) list:nil, variant types, etc... are all represented with the second bit set and lowest bit cleared (i.e., multiples of 2, but not 4). A datatype declaration with an empty variant constructor is also represented from this code space. This allows all these values to be stored in a single word, and thus in a register.
Pointer types have their two least significant bits cleared - in other words, they are always 32-bit aligned. They point to a boxed type.
All boxed types stored in the heap have a one-word header. The lowest byte of this header gives a type code (allowing the runtime to distinguish between the variants of datatypes, and between builtin types). The remainder of the word gives the number of words to follow.
The garbage collector is a very simple Cheney two-space copying collector. It consists of 153 lines of C. Someday, someone will write a generational collector for Irken.
In the future, Irken could have a static untagged runtime with parametric instantiation, like CLR (with or without the JIT).
This would mean storing headers on records, indicating their type, and telling the GC where pointers are located - instead of tagging every value.
Functions used in different places with different concrete types could be emit separately for each type, while functions used polymorphically on existential types would perform dynamic field lookups at runtime, similar to CLR interface lookups, or Objective-C method calls.
The copying collector enables Irken to have a dump/load facility. An image of the running system can be dumped to disk and reloaded later very quickly. This would be useful for things like moving or distributing a computation, checkpointing, or to get a CGI to load quickly.
This requires disabling Address Space Layout Randomization, and assumes the code is not holding any foreign C-pointer references.
Next: History