Memory allocation and higher-order functions

ABSTRACT

This paper presents a constant-time marking-collecting algorithm to efficiently implement recursion with a general heap memory rather than with a vectorial stack, in a context of frequent captures of continuations. It has been seen to reduce the 80% garbage collection overhead to less than 5% on average.The algorithm has been built into a virtual machine to efficiently implement at the assembly level the Actor language PLASMA, an Actor-oriented version of PROLOG and a variant of SCHEME, currently in use on 8086, 68000 and Vax.The rationale to use the heap memory is that continuations are available via a single pointer in a unified memory and can be shared optimally when recurrently captured, which is simply impossible using a strategy based on stack recopy. Further, non-captured continuations can be incrementally garbage collected on the fly.Part I describes the elementary recursive instructions of the virtual machine. Part II presents and proves the marking-collecting strategy. Part III safely generalizes the transformation "call + return = branch" in a way compatible with the possible capture of the current continuation. An appendix relates its integration in the Virtual Scheme Machine supporting Scheme 84.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 2: David H. Bartley , John C. Jensen, The implementation of PC Scheme, Proceedings of the 1986 ACM conference on LISP and functional programming, p.86-93, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319852]
• 3: Françoise Carré: ALOG: acteurs et programmation en logique, ENSEEIHT, Thèse de docteur-ingénieur, Toulouse, France (June 1984).
• 4: Olivier Danvy: [Danvy 86a] LILA: a Virtual Machine for Functional and Declarative Languages, Workshop on Future Directions in Computer Science and Software, Seabrock Island, LITP 86-38, South Caroline (May 1986).
• 5: [Danvy 86b] Agir avec LILA: le manuel de référence, LITP 86-40, Paris (May 1986).
• 6: [Danvy 86c] Machines virtuelles pour Langages Applicatifs et Langages Acteur: réalisations et programmation , thèse (nouveau régime) de l'Université Paris VI, LITP 86-57, Paris (June 1986).
• 7: [Danvy 87a] Memory Allocation and Higher-Order Functions: capture, sharing and incremental recovery, an alternative to the stack strategy using a heap memory, DIKU 87-1, Copenhagen (January 1987).
• 8: [Danvy 87b] Getting Liberated from the Free List, INRIA Technical Report (to appear), submitted to the Journal LISP and Symbolic Computation.
• 9: Olivier Danvy, Danielle Julien: Langage d'Implémentation pour Langages Applicatifs: contribution à l'étude d'une réalisation informatique, Bigre+Globule No. 48, 3e journées d'étude sur les Langages Orientés Objet, LITP 86- 23, Paris, France (January 1986).
• 10: Olivier Danvy, Jean-Louis Durieux, Patrick Sallé: Self-reflections and implementations: the virtual Actor-Machine LILA, LITP 86-56, Paris, France (August 1986).
• 11: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 12: Jean-Louis Durieux: [Durieux 81] Sémantique des liaisons nom-valeur: application à l'implémentation des ¿-langages, thèse d'état, Université Paul Sabatier, Toulouse, France (September 1981).
• 13: [Durieux 82] La Sémantique des Liaisons Nom-Valeur: un calcul permettant la vérification des techniques d'implémentation, journées GRECOGROPLAN sur la Programmation, Rapport UPSLSI No. 171, Bergerac, France (March 1982).
• 14: [Durieux 83] Interprétation du langage PLASMA, Actes de la 10e Ecole de Printemps Compilation et Interprétation, LITP 83-17, Barèges, France (March 1982).
• 15: Jean-Louis Durieux, Danielle Julien, Françoise Carré, Patrick Sallé: Langage d'Implémentation pour Logique et Acteurs, Bigre+Globule, 2e journées d'étude sur les L.O.O., Brest, France (November 1984).
• 16: Daniel P. Friedman, Christopher Haynes, Eugene Kohlbecker: Programming with continuations, from Program Transformation and Programming Environments, P. Pepper (ed.), Springer-Verlag pp. 263-274 (1984).
• 17: Daniel P. Friedman , Christopher T. Haynes, Constraining control, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.245-254, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318654]
• 18: Daniel Friedman, Christopher Haynes, Eugene Kohlbecker, Mitchell Wand: Scheme 84 Interim Reference Manual, Technical Report No. 153, Indiana University, Bloomington, (June 1983).
• 19: Patrick Greussay: Contribution à la définition interprétative et à l'implémentation des ¿-langages, thèse d'état, LITP 78-2, Paris, France (November 1977).
• 20: Eichi Goto: Monocopy and associative algorithms in an extended LISP, Technical Report 74.03, Information Science Laboratories, Faculty of Science, University of Tokyo (May 1974).
• 21: Christopher T. Haynes , Daniel P. Friedman, Engines build process abstractions, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.18-24, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802018]
• 22: Christopher T Haynes, Logic continuations, Proceedings on Third international conference on logic programming, p.671-685, September 1986, London, United Kingdom
• 23: Carl Hewitt: Control structures as patterns of passing messages , from Artificial Intelligence: an MIT perspective , Vol. 2, pp. 433-465, MIT Press, Cambridge, Massachusetts (1979).
• 24: Carl Hewitt , Peter Bishop , Richard Steiger , Irene Greif , Brian Smith , Todd Matson , Roger Hale, Behavioral semantics of nonrecursive control structures, Programming Symposium, Proceedings Colloque sur la Programmation, p.385-407, April 09-11, 1974
• 25: Jack Holloway, Guy L. Steele Jr., Gerald Jay Sussman, Alan Bell: The SCHEME-79 Chip, MIT AI Lab., AI Memo No. 559, Cambridge, Massachusetts (January 1980).
• 26: John B. Johnston, The contour model of block structured processes, ACM SIGPLAN Notices, v.6 n.2, February 1971 [doi>10.1145/1115880.1115883]
• 27: Danielle Julien: Etude et réalisation de la machine virtuelle LILA, adaptée à l'écriture d'interprètes, thèse de 3e cycle, Université Paul Sabatier, Toulouse, France (December 1985).
• 28: Drew McDermott, An efficient environment allocation scheme in an interpreter for a lexically-scoped LISP, Proceedings of the 1980 ACM conference on LISP and functional programming, p.154-162, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802801]
• 29: Robert Milne , C. Strachey, A Theory of Programming Language Semantics, Halsted Press, New York, NY, 1977
• 30: Jonathan Rees, William Clinger (editors): Revised^3 report on the algorithmic language Scheme, Joint Technical Report Indiana University and MIT Laboratory for Computer Science (1986).
• 31: Emmanuel Saint-James: [Saint-James 82] Fonctionnalité et filtrage: nouveaux algorithmes en Logique Combinatoire typée, thèse de 3e cycle, LITP 84.39, Paris, France (June 1982).
• 32: Emmanuel Saint-James, Recursion is more efficient than iteration, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.228-234, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802039]
• 33: Patrick Sallé [Sallé 84] Syntaxe et sémantique de PLASMA et ALOG, Technical Report, LSI-ENSEEIHT, Toulouse, France (1984).
• 34: [Sallé 85] Le bon usage de la machine virtuelle LILA (version UNIX_C), Technical Report, LSIENSEEIHT, Toulouse, France (November 1985).
• 35: [Sallé 86] Manuel de présentation des langages PLASMA et ALOG, Technical Report, LSIENSEEIHT, Toulouse, France (1986).
• 36: Brian Smith, Carl Hewitt: A PLASMA Primer, Rough draft 13:17, MIT AIL, Cambridge, Massachusetts (1975).
• 37: Richard M. Stallman: Phantom stacks: if you look too hard, they aren't there, MIT AIL, AI Memo No. 556, Cambridge, Massachusetts (July 1980).
• 38: Guy L. Steele Jr., Gerald Jay Sussman: Lambda, the ultimate imperative, MIT AIL, AI Memo No. 353, Cambridge, Massachusetts (March 1976).
• 39: Guy L Steele, LAMBDA: The Ultimate Declarative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 40: Henry M. Wu: Scheme86: an architecture for microcoding a Scheme interpreter, thesis, Departement of Electrical Engineering and Computer Science, MIT, Cambridge, Massachusetts (May 1986).

INDEX TERMS

Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

  D. Software
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Languages, Verification