1.10 Data types: Immediates

1.10.1 Preface: What’s wrong with Exprs-lang v6.5

Exprs-lang v6.5 gained the ability to nest expressions pretty much arbitrarily. However, our functions are still limited to work on machine integers. A realistic language would allow us to express programs over more interesting data types than mere machine integers.

Unfortunately, once we add data types, we have a problem distinguishing between any two data types. Everything is eventually represented as 64-bit integers in x64. We need some way to distinguish a collection of 64 bits as an integer, from a boolean, from the empty list, from a pointer to a procedure. Otherwise, we will have serious problems: undefined behaviours, unsafe casts, and/or memory safety errors.

This is not only a problem for ruling out unsafe behaviour in the source language. A static type system could take care to prevent the user from calling an integer as a procedure, for example. However, the language itself may need to distinguish different kinds of data at run time. For example, a garbage collector may need to traverse data structures, but not immediate data like integers; a pretty printer may want to print different data differently.

To enable the language to distinguish different kinds of data, we can steal a few of our 64 bits to represent a data type tag. This limits the range of machine integers, but allows us to us to distinguish data dynamically, enabling safety and abstractions that must differentiate data dynamically.

Our goal in this assignment is to implement the following language, Exprs-lang v7.

We want to allow Exprs-lang v7 programs to return any of these values, which requires additional support from the run-time system. The run-time system must be able to distinguish these different values in order to pretty print or otherwise return them to the user (such as via an exit code in the case of the error value). This means our run-time representation of values cannot just be 64-bit machine integers; we need some way for the run-time system to differentiate values dynamically.

The support libraries include an implementation of this new run-time system in cpsc411/ptr-run-time, which supports pretty printing all the new values. cpsc411/compiler-lib also contains parsers for the values. execute takes a new optional second parameter, which can be used to change your view of the result. By default, it parsers the printed value as a Racket value. You can pass nasm-run/print-string to get back the string representation of the result, which will be handy to view the result of (void) correctly. You can pass nasm-run/exit-code to get the exit code, which is helpful for viewing the result of (error uint8), which sets the exit code to uint8.

We also add new primitive operations, primarily predicates on our new data types. The interpretation of several operations will also change to add dynamic type checking. This will prevent those operations from being a source of undefined behaviour.

With proper booleans, we can finally allow an arbitrary value in the predicate position of an if expression in the surface language.

1.10.2 Introduction to Tagged Object Representation

The key challenge we need to solve in adding data types to our language is how to implement data-type checking. That is, given some value triv, branch on whether it is a particular type data type such as a boolean or a number: (if (fixnum? triv) value_1 value_2) and (if (boolean? triv) value_1 value_2) should be supported. Ideally, each data type is unique: (boolean? triv) and (fixnum? triv) should never both be true.

These don’t necessarily need to be dynamic checks, as long as they are somehow expressible by the compiler, whether as expressions that dynamically check or meta-data that is statically checked. However, even in a statically typed language, we may need some ability for the run-time system to distinguish different kinds of data dynamically.

Depending on how these type checks are implement, this alone is enough to let us implement different data types safely. We could use procedural abstraction to wrap existing binary operations to ensure, e.g., that + is only operating on numbers, and not booleans. We could expand if to check that the value in predicate position is both a boolean (that is, that (boolean? triv) is equal to some value using a relop), and that the value is equal to some representation of true.

Each data type in our language will now be represented by a ptr (pronounced like footer). A ptr is a machine word whose n least-significant bits represent the primary tag, and whose upper (- (* 8 (current-word-size-bytes)) n) bits represent the data.

In our setting, we have 64-bit words and will use the 3 least-significant bits for primary tags. With 3 bits, we can represent 8 primary data types in a ptr. We want to reserve these for the most common and most performance critical data that can fit in a ptr, but we have additional constraints. This will limit the size of data we can represent, but gives us additional data types—probably a good trade off.

If we want more than 8 data types, which most languages support, we must reserve one tag for "everything else" (a pointer to memory). The structure in memory has infinite space in which to store additional tags. This seems to leave us only 7 possible data types without going to memory.

Some data types require fewer than 64 bits, and we can exploit this fact to gain a few extra data types. For example, booleans really only require 1 bit. The empty list and the void object only require a tag, since they do not contain any data. ASCII characters only require 8 bits. We can make all of these share a single primary tag, and steal some of the unnecessary high-order bits for a secondary tag. This gives us 4 data types for the price of only 1 primary tag—what a bargain!

This leaves us 6 primary tags. One obvious choice is to use one for fixed sized integers; these will now be 61-bit integers, which we call fixnums. Integer operations are fast, and we don’t want to slow them down by making them go through heap allocation and pointer indirection. If we wanted to support graphics and scientific operations, we would reserve one for floating-point numbers too.

We reserve the remaining primary tags for tagged pointers, pointers to common heap-allocated structures. Storing the tag on the pointer instead of in memory avoids the expense of an additional memory access to check a tag and the additional memory overhead of storing the tag in memory. We’ll address the implementation of tagged pointers and heap-allocated structured data in the next chapter.

The integer 7 is #b111 in base 2, and would be represented, in base 2, as the ptr #b111000. The three low-order bits are the tag #b000, and the high-order bits are the data #b111 (implicitly padded with 0 to 64-bits).

A handy fact about the choice of tag for fixnums is that any number n is represented as (* 8 n). This fact allows for implementing fast fixnum operations on the ptr representation directly. That is, we can implement binary operations on fixnums without detagging followed by tagging, by relying on some algebraic facts about operations on integers.

The representation of booleans is a bit tricky. We can think of booleans either as the 61-bit values 0 and 1, with tag #b110, or as two separate secondary tags (with no payload) #b00001110 and #b00000110. I typically think in the the latter interpretation, where we represent #t and #f as separate data types, whose tags are #b110 (6) and #b1110 (14).

The representation of error, which represents an exit code, is inefficient. We only require 8 bits of data for the error code, so 24 bits are wasted. But we’re not adding more data types with secondary tags, so it is not worth over-engineering. Besides, a better error data type would use at least a string payload, which requires allocating space on the heap anyway.

The particular choice of tags is not important for correctness, although clever choices like above can help us implement common operations more efficiently. We therefore should introduce abstractions to keep the compiler abstract with respect to particular tag choices, so we can change our minds later if a better representation occurs to us.

To implement ptrs, we need bitwise operations such as arithmetic-shift so that we can implement tag checking, tagging, and untagging. This means we need to expose bitwise operations from x64, all the way through the compiler pipeline. This is not very interesting, so we begin by implementing tagged objects in terms of these, and then extending the rest of the compiler to expose bitwise operations.

1.10.3 Extending the source and front-end passes

We start by discussing the design of Exprs-lang v7.

We could distinguish procedure calls from primitive operations, and implement primitive operations by expanding to expressions, but this risks duplicating code (although, not much code). But, at some point, primitive operations will need to be wrapped as procedures if we want to use them with functional abstractions, so we might as well do it now, and leave some other pass to implement procedure inlining.

These choices mean we can change our validator, check-exprs-lang. We no longer need to type check the arguments (previously, operands) to primitive operations, except to call, which still must call a statically known procedure (since we don’t have a tagged representation of procedures, yet). Instead, we statically allow expressions like (call * #f #\y), but expect this to raise a dynamic error.

procedure (check-exprs-lang p) → exprs-lang-v7

p : any/c

Checks that a Exprs-lang v7 program is well typed (only that procedures are called with the right number of arguments), and well scoped.

We extend uniquify as usual. Below, we design Exprs-unique-lang v7.

As usual, we transform names into either abstract locations or labels. Data types do not complicate this.

procedure (uniquify p) → exprs-unique-lang-v7?

p : exprs-lang-v7?

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

And now, we figure out where to place our new passes.

As we saw in Introduction to Tagged Object Representation, many of the operations we want to perform on ptrs are easily expressed as algebraic expressions. For example, the expression (call fixnum? 7) is compiled to as (= (bitwise-and 7 7) 0).

Thankfully, we just added algebraic expressions. If we position our new passes above remove-complex-opera*, we don’t need to manually introduce auxiliary variables, or generate code with additional let-bindings. The compiler will do this for us, and allow us to write the code we want to write.

1.10.4 Specifying Data Type Representation

First we design Exprs-unsafe-data-lang v7. In this language, we compile our dynamically typed safe primitive procedures into lower level primitive operations on data types.

To make clear the distinction between the source and target implementations of these operations, we prefix the unsafe operators that require a dynamic check with unsafe-. call is still unsafe, since we do not know how to tag procedures yet.

Each safe procedure should produce some error code indicating that kind of error that occurred. Be sure to document your error codes. For now, we have enough error codes that we can encode which operation and which argument caused the error.

Design digression:

To avoid producing unnecessary definitions, you may consider how to design this pass so that a definition for a primitive procedure is only added to the module if that procedure is actually used.

You may also consider an alternative implementation of this pass that avoids inserting dynamic checks at all. Note that the the language definitions allow this behaviour for all well-typed programs.

Next we design Exprs-bits-lang v7, a language with all values represented as 64 bits and only primitive bitwise operations, but that allows algebraic expressions in most positions. The predicate position of if is again restricted to the predicate sublanguage.