Is there a standard way of dealing with the interaction between separate compilation and different kinds of closure conversion when compiling higher-order function calls?
I know of three function-like constructs that are distinctly compiled in most programming languages: closures, (top-level) functions, and C++-style function objects. Syntactically they are called the same way, but a compiler would optimally generate distinctly-shaped call sites:
Syntax: | clo(args) | func(args) | obj(args)
--------------------------------------------------------------------------------
Codegen: | clo.fnc(&clo.env, args) | func(args) | cls_call(&obj, args)
^ ^ ^ ^ ^
fn ptr | +--"top level" fn --+ |
+--- "extra" param, compared to source type -----+
(In C++, cls_call
would be T::operator()
for obj
's class T
. C++ also allows virtual functors, but that's essentially the closure case with an extra indirection.)
At this point, calls to map (x => x > 3) lst
and map (x => x > y) lst
should invoke different map
functions, because the first is a simple function pointer after hoisting, and the second is a closure.
I can think of four ways of dealing with this issue:
The C++ (98) approach, which forces the callee to either pick a call-site shape (via formal parameter type: virtual functor, function pointer, or non-virtual functor) or drop separate compilation by using a template, effectively specifying solution #2 below.
Overloading: the compiler could do multiple instantiation of
map
, and all other higher-order functions, with appropriate name-mangling. In effect, there is a separate internal function type per call site shape, and overload resolution picks the right one.Mandate a globally uniform call-site shape. This means that all top-level functions take an explicit
env
argument, even if they don't need it, and that "extra" closures must be introduced to wrap non-closure arguments.Retain the "natural" signature for top-level functions, but mandate that all handling of higher-order function params be done through closures. The "extra" closures for already-closed functions call a wrapper trampoline function to discard the unused
env
parameter. This seems more elegant than option 3, but harder to implement efficiently. Either the compiler generates a multitude of calling-convention-indepedent wrappers, or it uses a small number of calling-convention-sensitive thunks...
Having an optimized closure-conversion/lambda lifting hybrid scheme, with a per-function choice of whether to stick a given closure argument in the env or the parameter list, seems like it would make the issue more acute.
Anyways, questions:
- Does this issue have an explicit name in the literature?
- Are there other approaches besides the four above?
- Are there well-known tradeoffs between approaches?