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.

REFERENCES

• 1: Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
• 2: A. W. Appel & Z. Shao. An empirical and analytic study of stack vs. heap cost for languages with closures. J. Funct. Programming (to appear).
• 3: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 4: Henry G. Baker, Lively linear Lisp: “look ma, no garbage!”, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992 [doi>10.1145/142137.142162]
• 5: D. W. Clark and C. C. Green. A note on shared structure in LmP. Inform. Proc. Ltrs. 7, 6 (October 1978), 312-314.
• 6: Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
• 7: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 8: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 9: D. P. Friedman and D. S. Wise. Reference counting can manage the circular environments of mutual recursion. Inform. Proc. Ltrs. 8, i (January 1979), 41-44.
• 10: W. Goldman. The Princess Bride, (screenplay). Nelson Entertainment & Twentieth-Century Fox Film Corp. (1987), Miracle Max scene.
• 11: Ellis Horowitz , Sartaj Sahni, Fundamentals of data structures in PASCAL, Computer Science Press, Inc., New York, NY, 1984
• 12: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 13: Harry R. Lewis , Larry Denenberg, Data Structures and Their Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 14: D. Liles, P. Mamnami, R. Sinclair, J. Walgenbach, & S. Williams. ROD User's Guide. Class notes for Software Development, Computer Science Dept., New Mexico State Univ. (Spring 1994).
• 15: J. S. Miller. MultiScheme: a Parallel Processing System Based on MIT Scheme, Ph.D. dissertation, Mass. institute of Tech. (1987).
• 16: Moon, David A. MA CLISP Reference Manual, Project MAC, Mass. Institute of Tech. (April 1974).
• 17: Young Park , Benjamin Goldberg, Static analysis for optimizing reference counting, Information Processing Letters, v.55 n.4, p.229-234, Aug. 25, 1995 [doi>10.1016/0020-0190(95)00096-U]
• 18: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 19: A. J. Perlis , Charles Thornton, Symbol manipulation by threaded lists, Communications of the ACM, v.3 n.4, p.195-204, April 1960 [doi>10.1145/367177.367202]
• 20: Thomas A. Standish, Data Structure Techniques, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1980
• 21: R. Tarjan. Finding dominators in directed graphs. SIAM J. Comput. 3, I (March 1974), 62-89.
• 22: David N. Turner , Philip Wadler , Christian Mossin, Once upon a type, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.1-11, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224168]
• 23: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 24: J. Weizenbaum, More on the reference counter method of erasing list structures, Communications of the ACM, v.7 n.1, p.38, Jan. 1964 [doi>10.1145/363872.363881]
• 25: David S. Wise, Referencing lists by an edge, Communications of the ACM, v.19 n.6, p.338-342, June 1976 [doi>10.1145/360238.360244]
• 26: David S. Wise, Design for a multiprocessing heap with on-board reference counting, Proc. of a conference on Functional programming languages and computer architecture, p.289-304, January 1985, Nancy, France
• 27: David S. Wise, Stop-and-copy and one-bit reference counting, Information Processing Letters, v.46 n.5, p.243-249, July 9, 1993 [doi>10.1016/0020-0190(93)90103-G]
• 28: D. S. Wise, B. Heck, C. Hess, W. Hunt, and E. Ost. Uniprocessor performance of reference-counting hardware heap. Technical Report 401, Computer Science Dept., Indiana Univ. (June 1994).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Primary memory

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management; Abstract data types

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

General Terms:
Languages

Keywords:
garbage collection, reference counting, storage management, tags