Carleton University
Technical Report TR-20
March 1983
Not-Quite-Linear Random Access Memories
Jim des Rivieres & Wilf R. LaLonde
Abstract
Not-quite-linear random access memories (NQL-RAMs) are an alternative to conventional linear RAMs, that are better suited to list processing applications, such as LISP systems. Some of their advantageous characteristics are:
General-Purpose.
Like conventional memories, NQL-RAMs are quite simple and flexible. They do not impose severe constraints on the shapes of objects that may be represented. All words within a multi-word object have addresses.
Compact Representations.
NQL-RAMs are well-suited to applications involving a large number of small objects. Tagged pointers, tagged words, “immediate” pointers, “invisible” words, and compact list representations (“CDR-coding”) are all supported with memory system overhead as little as three bits per word.
Memory level garbage collection.
Sufficient information is encoded in an NQL-RAM to support application independent garbage collection and compaction, with linearization of sequence-like multi-word structures.
Implementable.
All primitive operations of NQL-RAMs can be efficiently implemented either in microcode or with special-purpose hardware. Conventional memory technologies can be used at the implementation level.
The general structure of NQL-RAMs, their use in list processing, and their implementation are all discussed in this paper.