I am playing with a simple implicitly typed functional language and have implemented type checking using a Hindley Milner style system. In order to guide code generation, I want to tag each term with its type during type inference.
Of course my language uses lambda expressions and the implicit typing should enable nice polymorphic use of those lambdas. Unfortunately, this goal clashes with the static type tagging as each lambda can be tagged only once which specializes it for a particular set of argument and closure types. It is also not possible to statically copy lambdas on each use, as this requires dynamic knowledge.
I thought about dynamically copying and tagging lambdas at runtime but this would involve quite some work and possibly overhead. Is there a standard solution for this kind of problem?
Update 1 The following example might help to clarify my point.
add := func (a, b) begin a + b end a := add(2, 3) b := add('hello', 'world')
add has polymorphic type
(T1, T1) -> T1 and during type checking
add is first instantiated to
(Int, Int) -> Int and then to
(Str, Str) -> Str, everything fine so far. But, during compilation, I want to have the tree representing
add to be annotated with conrete types. Unfortunately,
add is a single tree and that tree is either tagged with the first or the second type instantiation.
I could create copies of the
add tree for each application but it seems to me that this is only possible at runtime, when the actual target of a call is available. On the other hand, maybe I could somehow
let bind copies of the lambda for each instantiation and mangle the type variant into the name? That would entail updating references and I'm not sure whether this is actually possible in general? What about lambda return values, conditionals and so forth?
Update 2 I still feel like I did not describe my problem sufficiently. My language is really rather simple and I would like to stick with a simple typing solution. I found an article series that exactly details my problem and even explores the approaches that I envisioned: type spacialization per application and selecting specialized trees using a structured ler naming scheme.