Memory allocation and higher-order functions

• Main Author: Danvy, O.
• Format: Conference Proceeding
• Language: English
• Subjects: Applied computing > Life and medical sciences > Computational biology; Applied computing > Life and medical sciences > Genetics; Applied computing > Life and medical sciences > Systems biology; Computing methodologies > Artificial intelligence > Knowledge representation and reasoning > Cognitive robotics; Computing methodologies > Artificial intelligence > Philosophical/theoretical foundations of artificial intelligence > Cognitive science; Hardware > Integrated circuits > Semiconductor memory; Information systems > Information storage systems > Storage management; Software and its engineering > Software notations and tools > General programming languages > Language types; Software and its engineering > Software organization and properties > Contextual software domains > Operating systems > File systems management; Software and its engineering > Software organization and properties > Contextual software domains > Operating systems > Memory management
• ISSN: 0362-1340
• DOI: 10.1145/29650.29676

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.