Browse thread
Efficency of varient types
-
Michael D. Adams
- Stefan Monnier
- Nicolas Cannasse
- Jon Harrop
-
Lukasz Stafiniak
- Lukasz Stafiniak
- Christophe Raffalli
- David Baelde
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2005-11-28 (08:13) |
From: | Christophe Raffalli <raffalli@u...> |
Subject: | Re: [Caml-list] Efficency of varient types |
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