[1] We could represent memory as lists of items. However, the access time would then not be independent of the index, since accessing the $n$th element of a list requires $n-1$ tail operations.
[2] For completeness, we should specify a make_vector operation that constructs vectors. However, in the present application we will use vectors only to model fixed divisions of the computer memory.
[3] This is precisely the same tagged data idea we introduced in chapter 2 for dealing with generic operations. Here, however, the data types are included at the primitive machine level rather than constructed through the use of lists.
[4] Type information may be encoded in a variety of ways, depending on the details of the machine on which the JavaScript system is to be implemented. The execution efficiency of JavaScript programs will be strongly dependent on how cleverly this choice is made, but it is difficult to formulate general design rules for good choices. The most straightforward way to implement typed pointers is to allocate a fixed set of bits in each pointer to be a type field that encodes the data type. Important questions to be addressed in designing such a representation include the following: How many type bits are required? How large must the vector indices be? How efficiently can the primitive machine instructions be used to manipulate the type fields of pointers? Machines that include special hardware for the efficient handling of type fields are said to have tagged architectures.
[5] This decision on the representation of numbers determines whether ===, which tests equality of pointers, can be used to test for equality of numbers. If the pointer contains the number itself, then equal numbers will have the same pointer. But if the pointer contains the index of a location where the number is stored, equal numbers will be guaranteed to have equal pointers only if we are careful never to store the same number in more than one location.
[6] This is just like writing a number as a sequence of digits, except that each digit is a number between 0 and the largest number that can be stored in a single pointer.
[7] There are other ways of finding free storage. For example, we could link together all the unused pairs into a free list. Our free locations are consecutive (and hence can be accessed by incrementing a pointer) because we are using a compacting garbage collector, as we will see in section 5.3.2.
[8] This is essentially the implementation of pair in terms of set_head and set_tail, as described in section 3.3.1. The operation get_new_pair used in that implementation is realized here by the free pointer.
5.3.1 Memory as Vectors