12 Hustle: heaps and lists
A little and a little, collected together, become a great deal; the heap in the barn consists of single grains, and drop and drop makes an inundation.
12.1 Inductive data
So far all of the data we have considered can fit in a single machine word (64-bits). Well, integers can’t, but we truncated them and only consider, by fiat, those integers that fit into a register.
In the Hustle language, we will add two inductively defined data types, boxes and pairs, which will require us to relax this restriction.
Boxes are like unary pairs, they simply hold a value, which can be projected out. Pairs hold two values which each can be projected out.
The new operations include constructors (box e) and (cons e0 e1) and projections (unbox e), (car e), and (cdr e).
Usually boxes are mutable data structures, like OCaml’s ref type, but we will examine this aspect later. For now, we treat boxes as immutable data structures.
12.2 Empty lists can be all and end all
Inductive data types are useful for creating a wide variety of data structures. Their practicality can be somewhat limited when their structure is unknown: Is the second element in a cons important? Or is it there because something has to be there? For this reason, many languages that provide inductive data types also have an empty or nil value (this should not be confused with null in languages like C!). In Racket, and in our languages, we write this value as '().
Using cons and '() in a structured way we can form proper list, among other useful data structures.
We use the following grammar for Hustle:
We can model this as an AST data type:
#lang racket ;; type Expr = ... ;; | (Empty) ;; type Op1 = ... ;; | 'box | 'car | 'cdr | 'unbox ;; type Op2 = ... ;; | 'cons
12.3 Meaning of Hustle programs, implicitly
The meaning of Hustle programs is just a slight update to Grift programs, namely we add a few new primitives.
The update to the semantics is just an extension of the semantics of primitives:
The interpreter similarly has an update to the interp-prims module:
#lang racket (require "ast.rkt") (provide interp-prim1 interp-prim2) ;; Op1 Value -> Answer (define (interp-prim1 p1 v) (match (list p1 v) [(list 'add1 (? integer?)) (add1 v)] [(list 'sub1 (? integer?)) (sub1 v)] [(list 'zero? (? integer?)) (zero? v)] [(list 'char? v) (char? v)] [(list 'char->integer (? char?)) (char->integer v)] [(list 'integer->char (? codepoint?)) (integer->char v)] [(list 'eof-object? v) (eof-object? v)] [(list 'write-byte (? byte?)) (write-byte v)] [(list 'box v) (box v)] [(list 'unbox (? box?)) (unbox v)] [(list 'car (? pair?)) (car v)] [(list 'cdr (? pair?)) (cdr v)] [(list 'empty? v) (empty? v)] [_ 'err])) ;; Op2 Value Value -> Answer (define (interp-prim2 p v1 v2) (match (list p v1 v2) [(list '+ (? integer?) (? integer?)) (+ v1 v2)] [(list '- (? integer?) (? integer?)) (- v1 v2)] [(list 'eq? v1 v2) (eqv? v1 v2)] [(list 'cons v1 v2) (cons v1 v2)] [_ 'err])) ;; Any -> Boolean (define (codepoint? v) (and (integer? v) (or (<= 0 v 55295) (<= 57344 v 1114111))))
Inductively defined data is easy to model in the semantics and interpreter because we can rely on inductively defined data at the meta-level in math or Racket, respectively.
In some sense, the semantics and interpreter don’t shed light on how constructing inductive data works because they simply use the mechanism of the defining language to construct inductive data. Let’s try to address that.
12.4 Meaning of Hustle programs, explicitly
Let’s develop an alternative semantics and interpreter that describes constructing inductive data without itself constructing inductive data.
The key here is to describe explicitly the mechanisms of memory allocation and dereference. Abstractly, memory can be thought of as association between memory addresses and values stored in those addresses. As programs run, there is a current state of the memory, which can be used to look up values (i.e. dereference memory) or to extend by making a new association between an available address and a value (i.e. allocating memory). Memory will be assumed to be limited to some finite association, but we’ll always assume programs are given a sufficiently large memory to run to completion.
In the semantics, we can model memory as a finite function from addresses to values. The datatype of addresses is left abstract. All that matters is we can compare them for equality.
We now change our definition of values to make it non-recursive:
We define an alternative semantic relation equivalent to 𝑯 called 𝑯′:
Like 𝑯, it is defined in terms of another relation. Instead of 𝑯-𝒆𝒏𝒗, we define a similar relation 𝑯-𝒎𝒆𝒎-𝒆𝒏𝒗 that has an added memory component both as input and out:
For most of the relation, the given memory σ is simply threaded through the judgment. When interpreting a primitive operation, we also thread the memory through a relation analagous to 𝑯-𝒑𝒓𝒊𝒎 called 𝑯-𝒎𝒆𝒎-𝒑𝒓𝒊𝒎. The key difference for 𝑯-𝒎𝒆𝒎-𝒑𝒓𝒊𝒎 is that cons and box operations allocate memory by extending the given memory σ and the car, cdr, and unbox operations dereference memory by looking up an association in the given memory σ:
There are only two unexplained bits at this point:
the metafunction
which consumes a memory
and a list of values. It produces a memory and an address
such that 
is
like 
except it has a new association for
some 
and 
is fresh, i.e. it does not appear in the domain of
.the metafunction
used
in the conclusion of 
. This function does
a final unloading of the answer and memory to obtain a answer
in the style of 𝑯.
The definition of 
is
omitted, since it depends on the particular representation
chosen for 
, but however you choose to
represent addresses, it will be easy to define appropriately.
The definition of 
just traces
through the memory to reconstruct an inductive piece of data:
With the semantics of explicit memory allocation and dereference in place, we can write an interepreter to match it closely.
We could define something very similar to the semantics by threading through some representation of a finite function serving as the memory, just like the semantics. Or we could do something that will produce the same result but using a more concrete mechanism that is like the actual memory on a computer. Let’s consider the latter approach.
We can use a Racket list to model the memory.
#lang racket (provide interp interp-env-heap) (require "heap.rkt" "env.rkt" "unload.rkt" "interp-prims-heap.rkt" "ast.rkt") ;; type Answer* = ;; | (cons Heap Value*) ;; | 'err ;; type Value* = ;; | Integer ;; | Boolean ;; | Character ;; | Eof ;; | Void ;; | '() ;; | (list 'box Address) ;; | (list 'cons Address) ;; type Heap = (Listof Value*) ;; type REnv = (Listof (List Id Value*)) ;; Expr -> Answer (define (interp e) (unload (interp-env-heap e '() '()))) ;; Expr REnv Heap -> Answer* (define (interp-env-heap e r h) (match e [(Int i) (cons h i)] [(Bool b) (cons h b)] [(Char c) (cons h c)] [(Eof) (cons h eof)] [(Empty) (cons h '())] [(Var x) (cons h (lookup r x))] [(Prim0 'void) (cons h (void))] [(Prim0 'peek-byte) (cons h (peek-byte))] [(Prim0 'read-byte) (cons h (read-byte))] [(Prim1 p e) (match (interp-env-heap e r h) ['err 'err] [(cons h v) (interp-prim1 p v h)])] [(Prim2 p e1 e2) (match (interp-env-heap e1 r h) ['err 'err] [(cons h v1) (match (interp-env-heap e2 r h) ['err 'err] [(cons h v2) (interp-prim2 p v1 v2 h)])])] [(If p e1 e2) (match (interp-env-heap p r h) ['err 'err] [(cons h v) (if v (interp-env-heap e1 r h) (interp-env-heap e2 r h))])] [(Begin e1 e2) (match (interp-env-heap e1 r h) ['err 'err] [(cons h _) (interp-env-heap e2 r h)])] [(Let x e1 e2) (match (interp-env-heap e1 r h) ['err 'err] [(cons h v) (interp-env-heap e2 (ext r x v) h)])]))
The real trickiness comes when we want to model such data in an impoverished setting that doesn’t have such things, which of course is the case in assembly.
The problem is that a value such as (box v) has a value inside it. Pairs are even worse: (cons v0 v1) has two values inside it. If each value is represented with 64 bits, it would seem a pair takes at a minimum 128-bits to represent (plus we need some bits to indicate this value is a pair). What’s worse, those v0 and v1 may themselves be pairs or boxes. The great power of inductive data is that an arbitrarily large piece of data can be constructed. But it would seem impossible to represent each piece of data with a fixed set of bits.
The solution is to allocate such data in memory, which can in principle be arbitrarily large, and use a pointer to refer to the place in memory that contains the data.
12.5 Representing Hustle values
The first thing do is make another distinction in the kind of values in our language. Up until now, each value could be represented in a register. We now call such values immediate values.
We introduce a new category of values which are pointer values. We will (for now) have two types of pointer values: boxes and pairs.
So we now have a kind of hierarchy of values:
- values |
+ pointers (non-zero in last 3 bits) |
* boxes |
* pairs |
+ immediates (zero in last three bits) |
* integers |
* characters |
* booleans |
* ... |
We will represent this hierarchy by shifting all the immediates over 3 bits and using the lower 3 bits to tag things as either being immediate (tagged #b000) or a box or pair. To recover an immediate value, we just shift back to the right 3 bits.
The pointer types will be tagged in the lowest three bits. A box value is tagged #b001 and a pair is tagged #b010. The remaining 61 bits will hold a pointer, i.e. an integer denoting an address in memory.
The idea is that the values contained within a box or pair will be located in memory at this address. If the pointer is a box pointer, reading 64 bits from that location in memory will produce the boxed value. If the pointer is a pair pointer, reading the first 64 bits from that location in memory will produce one of the value in the pair and reading the next 64 bits will produce the other. In other words, constructors allocate and initialize memory. Projections dereference memory.
The representation of pointers will follow a slightly different scheme than that used for immediates. Let’s first talk a bit about memory and addresses.
A memory location is represented (of course, it’s all we have!) as a number. The number refers to some address in memory. On an x86 machine, memory is byte-addressable, which means each address refers to a 1-byte (8-bit) segment of memory. If you have an address and you add 1 to it, you are refering to memory starting 8-bits from the original address.
We will make a simplifying assumption and always store things in memory in multiples of 64-bit chunks. So to go from one memory address to the next word of memory, we need to add 8 (1-byte times 8 = 64 bits) to the address.
What is 8 in binary? #b1000
What’s nice about this is that if we start from a memory location that is “word-aligned,” i.e. it ends in #b000, then every 64-bit index also ends in #b000.
What this means is that every address we’d like to represent has #b000 in its least signficant bits. We can therefore freely uses these three bits to tag the type of the pointer without needing to shift the address around. If we have a box pointer, we can simply zero out the box type tag to obtain the address of the boxes content. Likewise with pairs.
So for example the following creates a box containing the value 7:
(seq (Mov 'rax (arithmetic-shift 7 imm-shift)) (Mov (Offset 'rbx 0) 'rax) ; write '7' into address held by rbx (Mov 'rax 'rbx) ; copy pointer into return register (Or 'rax type-box) ; tag pointer as a box (Add 'rbx 8)) ; advance rbx one word
If 'rax holds a box value, we can “unbox” it by erasing the box tag, leaving just the address of the box contents, then dereferencing the memory:
(seq (Xor 'rax type-box) ; erase the box tag (Mov 'rax (Offset 'rax 0))) ; load memory into rax
Pairs are similar. Suppose we want to make (cons 3 4):
(seq (Mov 'rax (arithmetic-shift 3 imm-shift)) (Mov (Offset 'rbx 0) 'rax) ; write '3' into address held by rbx (Mov 'rax (arithmetic-shift 4 imm-shift)) (Mov (Offset 'rbx 1) 'rax) ; write '4' into word after address held by rbx (Mov 'rax rbx) ; copy pointer into return register (Or 'rax type-pair) ; tag pointer as a pair (Add 'rbx 16)) ; advance rbx 2 words
If 'rax holds a pair value, we can project out the elements by erasing the pair tag, leaving just the address of the pair contents, then dereferencing either the first or second word of memory:
(seq (Xor 'rax type-pair) ; erase the pair tag (Mov 'rax (Offset 'rax 0)) ; load car into rax (Mov 'rax (Offset 'rax 1))) ; or... load cdr into rax
From here, writing the compiler for box, unbox, cons, car, and cdr is just a matter of putting together pieces we’ve already seen such as evaluating multiple subexpressions and type tag checking before doing projections.
12.6 Allocating Hustle values
We use a register, 'rbx, to hold the address of the next free memory location in memory. To allocate memory, we simply increment the content of 'rbx by a multiple of 8. To initialize the memory, we just write into the memory at that location. To contruct a pair or box value, we just tag the unused bits of the address.
... will have to coordinate with the run-time system to initialize 'rbx appropriately. A Run-Time for Hustle
12.7 A Compiler for Hustle
The complete compiler is given below.
#lang racket (provide (all-defined-out)) (require "ast.rkt" "types.rkt" a86/ast) ;; Registers used (define rax 'rax) ; return (define rbx 'rbx) ; heap (define r8 'r8) ; scratch in +, - (define r9 'r9) ; scratch in assert-type (define rsp 'rsp) ; stack (define rdi 'rdi) ; arg ;; type CEnv = [Listof Variable] ;; Expr -> Asm (define (compile e) (prog (Extern 'peek_byte) (Extern 'read_byte) (Extern 'write_byte) (Extern 'raise_error) (Label 'entry) (Mov rbx rdi) ; recv heap pointer (compile-e e '()) (Ret))) ;; Expr CEnv -> Asm (define (compile-e e c) (match e [(Int i) (compile-value i)] [(Bool b) (compile-value b)] [(Char c) (compile-value c)] [(Eof) (compile-value eof)] [(Empty) (compile-value '())] [(Var x) (compile-variable x c)] [(Prim0 p) (compile-prim0 p c)] [(Prim1 p e) (compile-prim1 p e c)] [(Prim2 p e1 e2) (compile-prim2 p e1 e2 c)] [(If e1 e2 e3) (compile-if e1 e2 e3 c)] [(Begin e1 e2) (compile-begin e1 e2 c)] [(Let x e1 e2) (compile-let x e1 e2 c)])) ;; Value -> Asm (define (compile-value v) (seq (Mov rax (imm->bits v)))) ;; Id CEnv -> Asm (define (compile-variable x c) (let ((i (lookup x c))) (seq (Mov rax (Offset rsp i))))) ;; Op0 CEnv -> Asm (define (compile-prim0 p c) (match p ['void (seq (Mov rax val-void))] ['read-byte (seq (pad-stack c) (Call 'read_byte) (unpad-stack c))] ['peek-byte (seq (pad-stack c) (Call 'peek_byte) (unpad-stack c))])) ;; Op1 Expr CEnv -> Asm (define (compile-prim1 p e c) (seq (compile-e e c) (match p ['add1 (seq (assert-integer rax) (Add rax (imm->bits 1)))] ['sub1 (seq (assert-integer rax) (Sub rax (imm->bits 1)))] ['zero? (let ((l1 (gensym))) (seq (assert-integer rax) (Cmp rax 0) (Mov rax val-true) (Je l1) (Mov rax val-false) (Label l1)))] ['char? (let ((l1 (gensym))) (seq (And rax mask-char) (Xor rax type-char) (Cmp rax 0) (Mov rax val-true) (Je l1) (Mov rax val-false) (Label l1)))] ['char->integer (seq (assert-char rax) (Sar rax char-shift) (Sal rax int-shift))] ['integer->char (seq assert-codepoint (Sar rax int-shift) (Sal rax char-shift) (Xor rax type-char))] ['eof-object? (eq-imm val-eof)] ['write-byte (seq assert-byte (pad-stack c) (Mov rdi rax) (Call 'write_byte) (unpad-stack c) (Mov rax val-void))] ['box (seq (Mov (Offset rbx 0) rax) (Mov rax rbx) (Or rax type-box) (Add rbx 8))] ['unbox (seq (assert-box rax) (Xor rax type-box) (Mov rax (Offset rax 0)))] ['car (seq (assert-cons rax) (Xor rax type-cons) (Mov rax (Offset rax 8)))] ['cdr (seq (assert-cons rax) (Xor rax type-cons) (Mov rax (Offset rax 0)))] ['empty? (eq-imm val-empty)]))) ;; Op2 Expr Expr CEnv -> Asm (define (compile-prim2 p e1 e2 c) (seq (compile-e e1 c) (Push rax) (compile-e e2 (cons #f c)) (match p ['+ (seq (Pop r8) (assert-integer r8) (assert-integer rax) (Add rax r8))] ['- (seq (Pop r8) (assert-integer r8) (assert-integer rax) (Sub r8 rax) (Mov rax r8))] ['eq? (let ((l (gensym))) (seq (Cmp rax (Offset rsp 0)) (Sub rsp 8) (Mov rax val-true) (Je l) (Mov rax val-false) (Label l)))] ['cons (seq (Mov (Offset rbx 0) rax) (Pop rax) (Mov (Offset rbx 8) rax) (Mov rax rbx) (Or rax type-cons) (Add rbx 16))]))) ;; Imm -> Asm (define (eq-imm imm) (let ((l1 (gensym))) (seq (Cmp rax imm) (Mov rax val-true) (Je l1) (Mov rax val-false) (Label l1)))) ;; Expr Expr Expr CEnv -> Asm (define (compile-if e1 e2 e3 c) (let ((l1 (gensym 'if)) (l2 (gensym 'if))) (seq (compile-e e1 c) (Cmp rax val-false) (Je l1) (compile-e e2 c) (Jmp l2) (Label l1) (compile-e e3 c) (Label l2)))) ;; Expr Expr CEnv -> Asm (define (compile-begin e1 e2 c) (seq (compile-e e1 c) (compile-e e2 c))) ;; Id Expr Expr CEnv -> Asm (define (compile-let x e1 e2 c) (seq (compile-e e1 c) (Push rax) (compile-e e2 (cons x c)) (Add rsp 8))) ;; CEnv -> Asm ;; Pad the stack to be aligned for a call (define (pad-stack c) (match (even? (length c)) [#t (seq (Sub rsp 8))] [#f (seq)])) ;; CEnv -> Asm ;; Undo the stack alignment after a call (define (unpad-stack c) (match (even? (length c)) [#t (seq (Add rsp 8))] [#f (seq)])) ;; Id CEnv -> Integer (define (lookup x cenv) (match cenv ['() (error "undefined variable:" x)] [(cons y rest) (match (eq? x y) [#t 0] [#f (+ 8 (lookup x rest))])])) (define (assert-type mask type) (λ (arg) (seq (Mov r9 arg) (And r9 mask) (Cmp r9 type) (Jne 'raise_error)))) (define (type-pred mask type) (let ((l (gensym))) (seq (And rax mask) (Cmp rax type) (Mov rax (imm->bits #t)) (Je l) (Mov rax (imm->bits #f)) (Label l)))) (define assert-integer (assert-type mask-int type-int)) (define assert-char (assert-type mask-char type-char)) (define assert-box (assert-type ptr-mask type-box)) (define assert-cons (assert-type ptr-mask type-cons)) (define assert-codepoint (let ((ok (gensym))) (seq (assert-integer rax) (Cmp rax (imm->bits 0)) (Jl 'raise_error) (Cmp rax (imm->bits 1114111)) (Jg 'raise_error) (Cmp rax (imm->bits 55295)) (Jl ok) (Cmp rax (imm->bits 57344)) (Jg ok) (Jmp 'raise_error) (Label ok)))) (define assert-byte (seq (assert-integer rax) (Cmp rax (imm->bits 0)) (Jl 'raise_error) (Cmp rax (imm->bits 255)) (Jg 'raise_error)))
12.8 A Run-Time for Hustle
The run-time system for Hustle is more involved for two main reasons:
The first is that the compiler relies on a pointer to free memory residing in 'rbx. The run-time system will be responsible for allocating this memory and initializing the 'rdi register. To allocate memory, it uses malloc. It passes the pointer returned by malloc to the entry function. The protocol for calling functions in C says that the first argument will be passed in the 'rdi register. Since malloc produces 16-byte aligned addresses on 64-bit machines, 'rdi is initialized with an address that ends in #b000, satisfying our assumption about addresses.
Once the runtime system has provide the heap address in 'rdi it become our responsibility to keep track of that value. Because 'rdi is used to pass arguments to C functions, we can’t keep our heap pointer in 'rdi and expect it to be saved. This leaves us with two options:
We can ensure that we save 'rdi somewhere safe whenever we might call a C function
We can move the value away from 'rdi as soon as possible and never have to worry about 'rdi being clobbered during a call to a C function (as long as we pick a good place!)
We’ve decided to use the second option, which leaves the choice of where to move the value once we receive it from the runtime system. As usual, we will consult the System V Calling Convention, which tells us that 'rbx is a callee save register, which means that any C function we might call is responsible for ensuring that the value in the register is saved and restored. In other words: we, the caller, don’t have to worry about it! Because of this we’re going to use 'rbx to store our heap pointer. You can see that we do this in the compiler with (Mov ’rbx ’rdi) as part of our entry code.
The second complication comes from printing. Now that values include inductively defined data, the printer must recursively traverse these values to print them.
The complete run-time system is below.
#include <stdio.h> #include <inttypes.h> #include <stdlib.h> #include "types.h" #include "runtime.h" FILE* in; FILE* out; void (*error_handler)(); int64_t *heap; void print_result(int64_t); void error_exit() { printf("err\n"); exit(1); } void raise_error() { return error_handler(); } int main(int argc, char** argv) { in = stdin; out = stdout; error_handler = &error_exit; heap = malloc(8 * heap_size); // 8-byte words * number of words we want // `heap` gets passed in `rdi` // (defined by the calling convention, not up to us!) int64_t result = entry(heap); // See if we need to print the initial tick if (cons_type_tag == (ptr_type_mask & result)) printf("'"); print_result(result); if (result != val_void) printf("\n"); free(heap); // good memory hygiene return 0; } void print_char(int64_t); void print_cons(int64_t); void print_result(int64_t result) { if (cons_type_tag == (ptr_type_mask & result)) { printf("("); print_cons(result); printf(")"); } else if (box_type_tag == (ptr_type_mask & result)) { printf("#&"); print_result (*((int64_t *)(result ^ box_type_tag))); } else if (int_type_tag == (int_type_mask & result)) { printf("%" PRId64, result >> int_shift); } else if (char_type_tag == (char_type_mask & result)) { print_char(result); } else { switch (result) { case val_true: printf("#t"); break; case val_false: printf("#f"); break; case val_eof: printf("#<eof>"); break; case val_empty: printf("()"); break; case val_void: /* nothing */ break; } } } void print_cons(int64_t a) { int64_t car = *((int64_t *)((a + 8) ^ cons_type_tag)); int64_t cdr = *((int64_t *)((a + 0) ^ cons_type_tag)); print_result(car); if (cdr == val_empty) { // nothing } else if (cons_type_tag == (ptr_type_mask & cdr)) { printf(" "); print_cons(cdr); } else { printf(" . "); print_result(cdr); } }