Static and Dynamic Partitioning of Pointers as Links and Threads

Abstract

Identifying some pointers as invisible threads, for the purposes of storage management, is a generalization from several widely used programming conventions, like threaded trees. The necessary invariant is that nodes that are accessible (without threads) emit threads only to other accessible nodes. Dynamic tagging or static typing of threads ameliorates storage recycling both in functional and imperative languages. We have seen the distinction between threads and links sharpen both hardware- and software-supported storage management in Scheme, and also in C. Certainly, therefore, implementations of languages that already have abstract management and concrete typing, should detect and use this as a new static type. Categories and subject descriptors: D.3.3 [Programming Languages]: Language Constructs and Features---data types and structures, dynamic storage management, abstract data types; E.2 [Data Storage Representations ]: Linked representations; B.3.2 [Memory Structures]: Design S...