Re: [Caml-list] polymorphic lists, existential types and asorted other hattery

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: Peng Zang <peng.zang@gmail.com>

> I've come across a way to do this in haskell using what they call
> "existential types".
> 
>   http://www.haskell.org/haskellwiki/Existential_type
> 
> I don't really understand existential types however and don't know if
> OCaml has them nor how to use them.

Notwithstanding your reluctance to use them, objects in ocaml are
really what amounts to Haskell's existential types, particularly
those for which a type class is specified. Put the other way round,
most examples of constrained existential types (i.e. where there is a
type class specifiying the existential) are just encodings for
objects. The encoding of objects through existentials has been known
for a long time. OCaml doesn't need this encoding because it has
primitive objects.

>From an implementation point of view, constrained existentials need to
be accompanied by their dictionaries, which is exactly the same thing
as the method table in an object, so even the implementation is very
similar.

Method calls on arbitrary objects can be slow. This is because, due to
subtyping, in some situations there is no way to know where the method
will be in the table, and a binary search has to be done. However,
this overhead can be avoided if all objects used in a specific method
call have the same methods. That is, they should have the same
interface, without using subtyping. That way, the method will be at
the same position in all objects, and this position is cached (for
native code).
(Note that this also means that any benchmark on the performance of
objects shall consider the impact of cacheing, which can be hard to
evaluate in micro-benchmarks.)

Dmitri's example had this property, so it should display good
performance (as good as explicit existential encodings.)

Jacques Garrigue