© 1992 by Oxford University Press
Original Articles |
Compile-Time Garbage Collection for Higher-Order Functional Languages
Dr C. L.Department of Computer Science, Imperial College of Science, Technology and Medicine 180 Queen's Gate, London SW7 2BZ, UK
Functional languages suffer from problems associated with inefficient use of store. In this paper we present a compile-time garbage collection optimization for a strict higher-order functional language to mitigate these problems. Compile-time garbage collection involves the determination, at compile-time, of points in a program's execution at which garbage collection will take place and of the parts of store to be garbage collected. Actual collection still takes place at run-time. The compile-time garbage collection optimization is validated by two static (compile-time) analyses. Generation analysis gives us sharing information about a given list while inheritance analysis essentially tells us which parts of lists evaluated during the application of a function are part of the result of the application.
Correctness of the analyses and optimizations is considered, using a denotational store semantics as a reference. We apply the analyses and optimizations to an example quicksort program and quantify the improvement. We find that the program is significantly improved to the extent that its consumption of store is optimal after optimization.