Improving the lazy Krivine machine |
| |
Authors: | Daniel P. Friedman Abdulaziz Ghuloum Jeremy G. Siek Onnie Lynn Winebarger |
| |
Affiliation: | (1) Indiana University, Bloomington, IN, USA;(2) University of Colorado at Boulder, Boulder, CO, USA |
| |
Abstract: | Krivine presents the machine, which produces weak head normal form results. Sestoft introduces several call-by-need variants of the machine that implement result sharing via pushing update markers on the stack in a way similar to the TIM and the STG machine. When a sequence of consecutive markers appears on the stack, all but the first cause redundant updates. Improvements related to these sequences have dealt with either the consumption of the markers or the removal of the markers once they appear. Here we present an improvement that eliminates the production of marker sequences of length greater than one. This improvement results in the machine, a more space and time efficient variant of . We then apply the classic optimization of short-circuiting operand variable dereferences to create the call-by-need machine. Finally, we combine the two improvements in the machine. On our benchmarks this machine uses half the stack space, performs one quarter as many updates, and executes between 27% faster and 17% slower than our ℒ variant of Sestoft’s lazy Krivine machine. More interesting is that on one benchmark ℒ, , and consume unbounded space, but consumes constant space. Our comparisons to Sestoft’s Mark 2 machine are not exact, however, since we restrict ourselves to unpreprocessed closed lambda terms. Our variant of his machine does no environment trimming, conversion to deBruijn-style variable access, and does not provide basic constants, data type constructors, or the recursive let. (The Y combinator is used instead.) |
| |
Keywords: | Lambda calculus Abstract machine Call by need Lazy evaluation |
本文献已被 SpringerLink 等数据库收录! |
|