[Haskell-cafe] Object-oriented programming, Haskell and existentials

[oleg at okmij.org]

Lennart Augustsson wrote:
> We don't need them [existentials] from a theoretical perspective, 
> but in practice I'd rather use existentials than encodinging them 
> in some tricky way.

If the claim that we don't need existentials theoretically is obvious,
I don't have the argument. Still, existentials are the recurrent topic
on the OCaml list; quite a few people perceive them as a needed
feature and their perceived absence as a drawback of OCaml. 

The principle of encoding existentials is straightforward: represent
the existential datatype by a set of its possible
observations. Existentials demonstrate once again what I sloppily call
initial-final dichotomy: initial encodings are easier to think of
upfront, yet require fancier type systems (second-order types,
dependent types, GADTs). Final encodings are elementary, yet take
(far) longer to imagine. That difficulty may be just the matter of
habit.

BTW, wasn't hbc the first Haskell compiler to introduce existentials?


The performance grounds for existentials are justified, for example,
by the following paper

Yasuhiko Minamide, J. Gregory Morrisett and Robert Harper
Typed Closure Conversion, POPL 1996, pp. 271--283.
http://www.cs.cmu.edu/~rwh/papers/closures/popl96.ps

Many object encodings may be considered instances of the type closure
conversion. On the other hand, existential elimination may be seen as
an inverse process.