Type-Based Uncurrying for Unknown Function Calls

In strict functional languages, a left-to-right evaluation of an application of a curried function to n arguments generally requires creating n - 1 intermediate closures and making n function calls. A type-based optimization can reduce the number of calls by consistently uncurrying function definitions and calls to them, and by inserting implicit currying coercions when functions receive too few arguments. However, it only uncurries calls to known (let-bound) functions. Naively uncurrying calls to unknown (λ -bound) functions generally fails, since the implicit uncurrying coercions do not preserve the semantics of programs with side effects. We propose a characterization of when calls to unknown (λ -bound) functions can be uncurried. We describe it as a type-based translation and outline an algorithm that implements the translation. We demonstrate that programs with side effect preserve their meaning across this translation, even when they require uncurrying coercions.