1.11 Data types: Structured Data and Heap Allocation

1.11.1 Preface: What’s wrong with Exprs-Lang v7

Exprs-lang v7 gained proper data types, which is a huge step forward in expressivity and high-level reasoning. However, it still does not allow us to express structured data. Real languages require structured heap-allocated data—such as strings, vectors, and linked lists—to express interesting programs over data larger than a single word. Functional languages use procedures, a data structure, to provide functions as first-class values.

To express data larger than a single word, we need support from the low-level languages to get access to locations larger than a single word in size. All our locations so far, registers and frame locations, are only a single word in size. We need access to the heap—arbitrary unstructured and unrestricted memory locations.

Once we have the ability to allocate arbitrary space in heap memory, and pointers to that memory, we can add structured data types. We’ll use the same tagging approach introduced in the last chapter to tag pointers, so we can distinguish pointers to vectors vs pointers to lists, perform dynamic checking, etc.

Since our low-level languages don’t have any operations on memory address except frame variables, we’ll need to introduce new low-level abstraction. Our run-time system will also need to provide access to the heap memory in some way.

1.11.2 Implementing Structured Data

These two are interesting, since one has a statically known size, while one has a dynamically determined size. Each of these properties requires attention in our compiler. We could add more, but these two are enough to demonstrate the general approach to compiling structured data.

To add immediate data, we needed three operations: tagging, untagging, and tag checking. We need all of these to implement structured data types and follow the same pattern as Data types: Immediates for them, but we also need three additional operations: memory allocation, dynamically computed memory assignment, and dynamically computed memory dereference.

First, to implement constructors, we need the ability to allocate memory. For now, we’ll assume the existence of some abstraction alloc that can do this (which we become responsible for implementing later). cons creates a pair, so it should allocate two words of space by producing `(alloc ,(current-pair-size)). make-vector allocates one word for the length, and then one word for every element of the vector. That is, it should allocate n+1 words for a vector of length n.

Second, to initialize and mutate structured data, we need the ability to assign to a memory location that is dynamically computed. With frame variables, we added displacement mode operands, which could statically offset from the frame base pointer (whose location is statically known), and we could use this as an operand to a set! instruction. However, for structured data, we need something more general. We want the ability to (1) use an arbitrary location storing the base address, since we are dynamically allocating structured data, and passing that pointer around as a value, so the address itself could end up in any register or frame variable and (2) a dynamically determined offset from that base address, since we may want pass as an argument the index into vector. This is quite different from the abstractions we used to add frame variables.

We’ll assume a new abstraction, (mset! value value value), where the first operand is an arbitrary expression that evaluates to a base pointer (and is assumed to be produced from alloc), the second operand is an expression that evaluates to an offset in bytes from that base pointer, and the third operand evaluates to the value to be stored in the memory location computed by adding the offset to the base. As usual, we become responsible for implementing this abstraction at some pointer further down the compiler pipeline.

However, we must also tag the pointer as a pair, to create a ptr. Previously, we used a combination of shifting and bitwise-and to tag data. This limited the range of our immediate data. To tag pointers, we need to similar limit the range of addresses that we get pointers to, to ensure some bits are available as tags. This is relatively easy to achieve—most operating systems enable requesting aligned pointers, ensuring the 3 low-order bits are 0. We could also over-allocate, then find an address in the allocated range that is aligned properly to consider our base. We’ll assume the run-time system is capable of giving us aligned pointers, so we avoid wasting memory through over allocation. However, this method means we get pointers whose high-order bits contain part of the address, and low-order bits are already zero—we do not need to shift the pointer. Instead, to tag, we combine the pointer with the tag bits using bitwise-ior and untag by using the bitwise-xor on the tagged pointer and the tag, which resets only the tag bits to 0.

Finally, we need some way to actually access memory locations to implement the destructors for our data types. This requires similar functionality to mset!—it needs to take dynamically computed pointers and offsets in order to access a dynamically computed memory address. We’ll assume some abstraction (mref value value), where the first operand is the pointer and the second operand is the offset, and which returns the value stored at the pointer plus the offset. Using this we could implement (car value_1) as (mref value_1 -1), using the previous optimization to avoid the explicit untagging.

In summary, our strategy is to add three intermediate abstractions that can be used to easily create new data structures for its surface language.

To implement these new memory operations, or mops (pronounced em ops), we need to expose additional features from x64 and from the run-time system. Namely, we need low-level pointer operations that are different from those for frame variables, and we need run-time support for getting aligned addresses from the operating system to enable tagging pointers efficiently.

We then reuse our object tagging approach from the previous chapter to tag, untag, and tag check pointers to our new structured data types.

1.11.3 Memory Allocation and Access in x64

To implement the memory allocation and access abstractions we’ve just introduced, we need additional support from x64 and from the run-time system.

To access memory, we expose the index-mode operand from x64. It is written QWORD [reg_base + reg_offset], and refers to the memory location whose base pointer is stored in the register reg_base and whose index is stored in the register reg_offset. Unlike displacement-mode operands, both components of this operand are registers, so both the base and offset can be computed dynamically. We also enable a generalization of the displacement-mode operand, so we can access statically known offsets from base pointers other than the frame base pointer. This generalized operand, QWORD [reg_base + int32], adds some static offset to a base pointer to compute an address. Note that unlike the version used to implement frame variables, we add to (rather than subtract from) the base pointer, and the index is not restricted to a multiple of 8.

To implement allocation, we need some strategy for managing memory. Our run-time system or compiler needs to know what memory is in use, how to allocate (mark free memory as in use), and how to deallocate memory (return in-use memory to the pool of free memory and ultimately to the system). There are many strategies for this, such as "let the user deal with it", "add a process to the run-time system that dynamically manages memory", or "make the type system so complex that the compiler can statically manage memory". Each of these has merits.

To implement our allocation-only strategy, we need the run-time system to provide an initial base pointer from which we can start allocating. We reserve another register, the current-heap-base-pointer-register (abbreviated hbp). The run-time system initializes this register to point to the base of the heap, with all positive-integer indexes after this base as free memory. Allocation is implemented by copying the current value of this pointer, and incrementing it by the number of bytes we wish to allocate. The pointer must only be incremented by word-size multiples of bytes, to ensure the 3 low-order bits are 0 and the pointer can be tagged. Any other access to this register is now undefined behaviour, similar to accesses to fbp that do not obey the stack of frames discipline.

1.11.4 Implementing Structured Data

We design Exprs-lang v8 below. The language is large, as we include several new structured data types and their primitives.

Since the number of primitive operations is growing, we simplify the syntax to only give primops, rather than distinguishing unops, binops, and so on, so we can easily group like primops with like.

As usual, we first task is to uniquify. Below we define the target language, Exprs-unique-lang v8.

procedure (uniquify p) → exprs-unique-lang-v8

p : exprs-lang-v8

Resolves top-level lexical identifiers into unique labels, and all other lexical identifiers into unique abstract locations.

Next, we implement new safe primitive operations. All the accessors for the new data types can result in undefined behaviour if used on the wrong ptr. Similarly, vector reference can access undefined values if the vector is constructed but never initialized. We fix this by wrapping each primitive to perform dynamic checks and remove undefined behaviour.

We design the target language, Exprs-unsafe-data-lang v8, below.

Note that in this language, we add expose effect context and begin. In the source, we have an effect procedure, namely vector-set!. The user must manually call impure functions and bind the result. The result of an effectful function is either void, or an error. The unsafe variant, unsafe-vector-set!, does not need to produce a value, so we expose effect context.

Introducing this contextual distinction, we requrie primops to respect contexts. Only primops that produce values can appear in value context, while only imperative primops (only unsafe-vector-set! so far) can be directly called in effect context. Otherwise, we’d need to supprot values in effect context sometime later, which we haven’t considered how to do yet.

To implement the safe language, we wrap all accessors to perform dynamic tag checking before using the unsafe operations. We also wrap unsafe-make-vector to initialize all elements to 0.

Finally, we must extend specify-representation to implement the new data structures and primitives. We design the target Exprs-bits-lang v8 below.