Making a fast curry: push/enter vs. eval/apply for higher-order languages

✨ Summary

Overview

The paper compares two implementation models for curried function application when the function being called is not statically known. In push/enter, arguments are placed on the stack and the function is entered; the callee determines the function’s arity and consumes, returns, or retains arguments as appropriate. In eval/apply, the caller evaluates the function to a value and then applies the appropriate number of arguments, using runtime information about arity and partial applications.

The authors present a common operational framework for both models and describe how each maps onto a real implementation of Haskell. The analysis covers function closures, partial applications, thunks, update frames, call continuations, stack layouts, garbage collection, and the treatment of over-saturated and under-saturated calls. Push/enter can avoid some intermediate closure creation, but it requires an unusual stack representation containing pending arguments. This complicates accurate stack walking, garbage collection, runtime-system design, and compilation through portable intermediate languages such as C. Eval/apply instead places more responsibility on the caller and uses explicit call continuations, yielding a more conventional runtime structure.

Measurements using the Glasgow Haskell Compiler found that the execution costs of the two models were broadly similar across a substantial benchmark suite. The expected performance advantage of push/enter did not provide a consistent overall benefit. Because eval/apply was substantially simpler in its interaction with stack management, garbage collection, code generation, and runtime support, the authors concluded that compiled implementations should use eval/apply. The paper reports that GHC adopted eval/apply as a consequence of this evaluation.

Subsequent influence

The paper became a recurring reference point in discussions of higher-order calling conventions and currying. Later work on verified higher-order uncurrying explicitly contrasts native multi-argument calling, push/enter, and eval/apply, citing this paper when discussing the runtime costs of partial applications and higher-arity calls. (researchgate.net)

It is also cited by later research on functional-language implementation, including Making a Faster Curry with Extensional Types, which revisits efficient treatment of curried functions and lists the paper as prior work. (simon.peytonjones.org) The implementation model described by Marlow and Peyton Jones is referenced in research on GHC’s runtime behavior, where GHC is characterized as using eval/apply for unknown function application. (readkong.com)

Outside academic research, the paper has been used as implementation guidance in language projects such as Elm, whose documentation cites it while describing optimizations that combine known curried arguments into fewer runtime calls. (elm-lang.org) Current GHC bytecode infrastructure also contains specialized apply instructions and partial-application allocation operations, indicating that the implementation issues studied by the paper remain relevant to functional-language runtimes. (ghc.gitlab.haskell.org)