Re: [Caml-list] Efficency of varient types

[Christophe Raffalli <raffalli@univ-savoie.fr>]

Lukasz Stafiniak a écrit :

>2005/11/26, Michael D. Adams <mdmkolbe@gmail.com>:
>  
>
>>I have recently learned about OCaml and have been impressed by how
>>fast it is in the benchmarks.  However I have discovered that variant
>>types can slow down a program quite a bit.
>>    
>>
>[...]
>  
>
>>I am working on a program that translates code from scheme into ocaml.
>> (Later I will try python into ocaml.)  Because it is a dynamicly
>>typed language, the most natural translation would make everything a
>>function of a large variant type like:
>>
>>type value = Int of int
>> | Char of char
>> | String of string
>> (* etc. *)
>>
>>    
>>

I would suggest that you run a typing algorithm on your scheme program 
with an extra type "top" for
polymorphic function where object are boxed as proposed above.

Then, when typing fails, you insert in your code the proper conversion 
which are defined by induction over types:


(from int to top) : fun x -> Int x
(from char to top) : fun x -> Char x
...

(from top to int) : function Int x -> x | _ -> failwith "bad scheme program"
...

(from a to a) : identity (needed for optimization bellow)

(from a -> b to a' -> b') : fun f x -> (from b to b') f ((from a' to a) x)

(from a list to b list) : fun l -> List.map (from a to b) l

The pb here is to try to avoid as much as possible the composed function 
(the two latest, especially the latest, the one for
function is not that bad, it does not allocate a lot of memory at 
runtime) ... a possible way to do this is the following:

in the typing algorithm, do not solve the unification constraint 
immediately, just collect them as triple

(a,b,p) where a and b are the type that should be equal and p is the 
position in the code where to insert the (from to ...) function.

Then, consider the smallest relation on type variable with a < b if 
something like (b, list a, p) or (list a, b) appear (idem for arrow and
type constructor ...

there may be cycle in this relation, but do your best to propagate 
unification constraint from the "maximum" type for this relation ...
the solution being not unique, this is not a trivial task.

Moreover, if you compile a library, you may get a very nice solution for 
the library ... that require a lot of translation when you
finally use the library. But then, the only solution is probably to ask 
a little help from the programmer ...

This is the hardness of this problem that makes statically typed 
language better than dynamically typed language.

For lisp, there is one more specific pb, you use "cons" both for pairs 
and lists so for each "cons" there is a choice to translate it as (,) or 
(::)
... exploring all the possibility will probably increase a lot the 
complexity of the algorithm... but feaseable solution may be possible by 
trying
to delay the problem again chosing the order in which you solve 
unification constraint (you try to make "pertinent" information 
propagate before
doing compromising choices) ...

But I am sure this is an active field of reasearch in the lisp compiler 
community ...

I hope this helps.

Christophe