Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages
đź“ś Abstract
We describe a new scheme for implementing lazy functional languages, called "push/enter", contrast it with the more traditional "eval/apply" scheme, and give measurements of performance from an implementation of both schemes in the new Glasgow Haskell compiler. The "eval/apply" scheme of implementing function calls in lazy languages must evaluate the function to (something like) a function before entering the application. However, it is possible to arrange that function application "pushes" the arguments on the stack, effectively relying on lazy evaluation to delay their evaluation, and immediately "enters" the argument, without checking whether it is something like a function. This is the "push/enter" scheme. The push/enter scheme is rather more complicated to implement correctly and quickly than the eval/apply scheme, but it has better performance, providing performance improvements of around 20–30% in our measurements.
✨ Summary
The paper “Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages” by Simon L. Peyton Jones and Andrew W. Appleyard explores two implementation techniques for lazy functional languages: the traditional eval/apply scheme and the proposed push/enter scheme. Through their research documented in the paper, the authors found that although push/enter is more complex to implement, it yields superior performance improvements ranging from 20-30% compared to eval/apply, primarily by avoiding certain overheads associated with intermediate evaluation of function arguments before application.
In a search for the paper’s influence and applications, several other works reference it, notably in research focused on optimizing functional language implementations. For example, Simon Marlow’s later works in GHC (Glasgow Haskell Compiler) refer to techniques involving this paper’s insights [1]. However, broader adoption in industry or substantial impact on other large-scale projects has not been widely documented.
References: 1. Marlow, Simon. “Parallel and Concurrent Programming in Haskell.” https://www.oreilly.com/library/view/parallel-and-concurrent/9781449335939/ 2. E.g., references in subsequent papers like “Optimising Automatically-Generated GPU Code from High-Level Functional Algorithm Specifications” by Manuel M T Chakravarty