[Caml-list] Avoiding type unfolding

[Caml-list] Avoiding type unfolding

[Christoph Höger]

Dear all,

I asked about this back in August but only now I had the time to get
back at the issue. Consider the following script:

#!/usr/bin/bash
echo "class ['t] c_0 (t:'t) = object method child = t end" > c_0.ml
for x in {1..15}; do
    ((y = $x - 1)) ;
    echo "class ['t] c_$x (t:'t) = object method child_2 = ((new
C_$y.c_$y) t) method child_1 = (new C_$y.c_$y) t end" > c_$x.ml

    /usr/bin/time ocamlc.opt -c c_$x.ml
done

It demonstrates that type unfolding during the check of
implementation/interfaces generates an exponential runtime. The problem
is that each constructor is parametric and has to be expanded in order
to access the normal form of its rhs. This is done for each element in
the hierarchy.

Is there any trick, hack or encoding that enables compilation of the
same (or equivalent) classes in constant time?

thanks,

Christoph

-- 
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