[Caml-list] Expansion of type-constructors in ctype.ml

["Christoph Höger" <christoph.hoeger@tu-berlin.de>]

Dear all,

as a followup to [1], I figured out what causes both the massive
unnecessary work and the huge output files.

The fundamental problem is as follows:

In case you have a type constructor in your implementation, say

val x : 'a -> 'a foo

the compiler will, among other things, try to match the implementation
with its (inferred) interface. During this process, the routines eqtype,
morgen and unify2 in ctype.ml are used.

In all of these routines, however, the first step is to do an
expand_head, which will replace the Tconstr with whatever is on its
right-hand-side.

If you happen to have a large rhs (as I do from a compiler), this
process kills the compiler performance. I will try to write a script
that autogenerates an example to demonstrate the issue later, but
consider the form of:

class ['a] c_n (a : 'a) = object
  method m = (new c_<n-1>) a
  method n = (new c_<n-1>) a
end

for an arbitrary n.
Instead of checking e.g. the equality of a c_n with b c_n, by comparing
a and b first, c_n is unfolded to an object. Then that object's fields
are compared (and instead of comparing a c_<n-1> with b c_<n-1> ... you
get the idea).

So I intend to patch the compiler to try to avoid these expansions, when
possible. But to do that, I need some more information:

1. In the case of equality, it seems fairly simple. Iff the path of two
constructors is the same and both argument lists are equal, the types
are equal, right?

2. In the case of unification, if both paths are the same, the argument
lists are of the same length, we can directly unify the arguments, right?

3. In the case of moregen, I am a little bit lost. Trying to just move
up the Tconstr {..} case before the expansion made bootstrapping fail
with inconsistent assumptions in the hashtbl module. So it seems
something relies on the expansion's side-effect. Does anyone know why?

Maybe in all these cases above, I'll have to do expansion in case the
result is negative (non-equal, unification not possible etc.), would
that be acceptable?

And besides all this: Is there some clever trick that would let me avoid
compiler patching at all? (Note that there is currently no way to
autogenerate interfaces, I only have the implementations).

regards,

Christoph

[1]: https://sympa.inria.fr/sympa/arc/caml-list/2015-08/msg00132.html
-- 
Christoph Höger

Technische Universität Berlin
Fakultät IV - Elektrotechnik und Informatik
Übersetzerbau und Programmiersprachen

Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin

Tel.: +49 (30) 314-24890
E-Mail: christoph.hoeger@tu-berlin.de