Tuesday, December 22, 2009

On Generalizations

The bootstrap compiler has a more restrictive typechecker, basically because I implemented some cases better. Parts of the bootstrap compiler are therefore not accepted. Two problems, which basically boil down to generalization errors.

First -yeah I read the papers,- it assumed, mostly, that generalization is 'good' because of the following example:
let f = [x -> x] in (f 3, f 'a')

If we wouldn't generalize the type of f, it must be the identity on int and char, which fails to typecheck. The only problem: The example is not general, it never happens. Functions which are polymorphic are usually written as definitions, and almost never occur in function bodies.

What does happen is that we want to know in local functions what argument types to expect, such that subsequently we can optimize better, i.e.:
let g = [y -> print y] in g 3
If y has type int, then the generic function print may be optimized to print_int.

Moreover, and this seems to be a source of 'features,' it is hard to generalize in the right order. In the example below, it should be derived that z is a printable value.
f z = let x = [x -> x] in let g = [y -> print y] in g (f z)

Which fails, at the moment.

Which leaves me with two choices. After thinking it through, I derived that linear order solving handles almost all cases, so that's no problem. So, get rid of generalizations is one choice, get rid of the bug the other. Guess I'll stick with generalizations, even if problematic. (Can only generalize over local variables, pattern matching and generalization are a hard mix.)

I guess I forgot an equality somewhere, or forgot assigning some variables monomorphic...

12/23/09: A substitution on a set of monomorphic variables is the set of free-variables after substitution.

No comments:

Post a Comment