Address/memory management for a gigantic LISP environment or, GC considered harmful

ABSTRACT

The possibility of incredibly cheap, fantastically large media for storage gives rise to a realistic LISP memory management scheme under which GC may be postponed for days, or even indefinitely; the idea is encapsulated in the acronym “DDI”—“GC? Don't Do It!”. Tertiary memory is used to archive pages of the LISP environment which are perhaps reclaimable, but which have not been proven so; whereas the standard technique of “paging” is used to swap active data from the main memory to a secondary store such as magnetic disk. Some scenarios are presented considering a variety of currently-available technologies, and of one speculative possibility—videodisc—by which a requisite compactifying GC would be done “overnight”, or over the weekend. With enough tertiary available, one design could last for over 12 years without a GC. “Write-once” memories, probably unusable for most applications, would not be at a disadvantage here.

REFERENCES

• 1: 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]
• 2: Bishop, P. B.; Garbage Collection in a Very Large Address Space: Technical Report TR-178, MIT Laboratory for Computer Science.
• 3: Daniel G. Bobrow , Douglas W. Clark, Compact Encodings of List Structure, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.266-286, Oct. 1979 [doi>10.1145/357073.357081]
• 4: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 5: L. Peter Deutsch, Experience with a microprogrammed Interlisp system, Proceedings of the 11th annual workshop on Microprogramming, p.128-129, November 19-22, 1978, Pacific Grove, California, United States
• 6: Doyle, J.; "A Truth Maintenance System"; Artificial Intelligence 12, 3 (Nov 1979), Pp. 231-272.
• 7: Daniel J. Edwards, Secondary Storage in LISP, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 8: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 9: Greenblatt, R.; "The LISP Machine"; Working Paper No. 79, M.I.T. Artificial Intelligence Lab, Cambridge MA (Nov 1974).
• 10: Greenblatt, R., et. al.; "LISP Machine Progress Report"; A.I. Memo 444, M.I.T. Artificial Intelligence Lab, Cambridge MA (Aug 1977).
• 11: Daniel H. H. Ingalls, The Smalltalk-76 programming system design and implementation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.9-16, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512762]
• 12: Lieberman, Henry, and Hewitt, Carl; "A Real Time Garbage Collector That Can Recover Temporary Storage Quickly"; A.I. Memo 569, M.I.T. Artificial Intelligence Lab, Cambridge MA (Apr 1980); (also submitted for publication)
• 13: Marti, J., Hearn, A., Griss, M., and Griss, C.; Standard LISP Report; UCP-60, University of Utah (Jan 1978).
• 14: McWilliams, T.M., Widdoes, L.C., Jr., and Wood, L.L.; The S-1 Project; Lawrence Livermore Laboratory, Livermore CA (Sep 1977)
• 15: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 16: Nadan, J.S. "Optical Information Storage and Retrieval Systems"; in Archival Memory Technology, Proc. of a Workshop Held at Carnegie-Mellon Univ. (Sep 28, 1978), Pp. 28-30.
• 17: Steele, G.L. Jr.; "Data Representations in PDP-10 Maclisp", A.I. Memo 420, M.I.T. Artificial Intelligence Lab, Cambridge MA (Sep 1977).
• 18: White, JonL; "NIL—A Perspective"; in Proc. of 1979 MACSYMA Users Conference (June 1979), Pp. 190-199.
• 19: Jon L White, LISP/370: a short technical description of the implementation, ACM SIGSAM Bulletin, v.12 n.4, p.23-27, November 1978 [doi>10.1145/1088276.1088280]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP

General Terms:
Languages, Management, Performance