Poly: a specialization helper function

[rrnewton]

@pkoronkevich, this is the warm-up task we described today, after L0 is functional. The idea is to design a function specializer that takes:

• a top-level function definition,
• a call site, i.e., with a concrete set of argument expressions

And produce as output:

• a new function definition,
• a function that transforms a call-site

Here, a "call site" is defined an application of a curried function to any number of arguments, e.g. ((f x) y). The specializer can assume a monomorphic program (as this happens after monomorphization).

Example: Specialize of map (\x -> x+1) ls should return the map' definition and transform the call-site to map' ls. All constant arguments should go away, so f 1 2 3 x turns into f' x (in the future we may want to back down from that if we find a reason not to greedily specialize, e.g. to preserve some sharing).

Step 2: Reuse Optimization

This can be saved for after the basic specializer works.

In the above input/output specification, the idea with returning a function instead of just a new call site, is for reuse. For example, if ((f x) y) is the input, then the output "call site optimizer" function, should transform it, e.g. into non-curried f(x,y). But that function should also work on other call sites, which can optionally use the same specialized function. I.e. it would transform ((f a) b) just as well. It can return a Maybe to indicate whether it worked or failed.

Specializing to the number of arguments (uncurrying) is a simple example, but it applies to other specializations too. If we specialize expt x 2, then the function we create as a result should also be shared if we later see expt y 2. (Of course in that example the specialized function should be inlined too, but we can for the moment leave that to the C compiler or LLVM...)

[rrnewton]

@pkoronkevich - what's the status on this issue? Is it fair to say that the specialization helper function is done? (Which commit?) I think what you have left is at the level of the whole monorphization/defunctionalization process, not at the level of the single helper function that this issue is concerned with.

[pkoronkevich]

commit 9d2827f3701ef6d755f39df5953ca188d9b0c1bf