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

[oleg at okmij.org]

Lennart Augustsson wrote:
> I was just pointing out that the mechanism for doing the OO thing
> exists in Haskell too, albeit looking a little different.

Indeed there is a mechanism for doing OO in Haskell -- several of
them. Most of them have nothing to do with Existentials. In the 
OHaskell paper,

	http://homepages.cwi.nl/~ralf/OOHaskell/

Ralf Laemmel has collected all known to us methods of doing OO in
Haskell. Incidentally, three years ago Lennart Augustsson described a
simple, Haskell98 method of emulating OO, without existentials. We
give him credit in footnote 4.

The OOHaskell paper then goes to demonstrate how to do *all* of the
known OO in Haskell, with all its inherent complexity: depth and width
subtyping, upcasting and safe downcasting, nominal and structural
subtyping, and the whole issue about covariant methods.

Derek Elkins wrote:
> In general, to encode OO you need quite a bit more than existentials.
> As you are probably aware, there was a cottage industry in the mid to
> late '90s working on encodings of OO languages into System F + foo
> calculi.  They just about gave up on a complete encoding until someone
> figured one out.  'turns out all you needed was recursive bounded
> existential quantification.

Not necessarily. Again, please see the OOHaskell paper. The full story
is that there are several encodings of objects -- using closures and
using existentials. The former are *far* simpler. ML-ART (which later
evolved in the 'O' of OCaml) chose the more complex encoding -- and
hence had to add equi-recursive types, existentials and universals to
Caml -- only because of a potential safety issue with closures. A
constructor of an object may invoke methods that may access fields
that are not initialized yet. This problem is present in all OO
languages, and the common `solution' is an admonition ``not to do
that''. Clearly Didier Remy has higher standards, and he went into
considerable pain to solve the problem. Incidentally, Haskell can
solve this problem in a simpler way. We critically rely on the fact
that all effects must be done in a monad. Therefore, in OOHaskell we
can safely use the simpler encoding for objects.

Regarding existentials, the web page
	http://okmij.org/ftp/Computation/Existentials.html

demonstrates how to systematically eliminate existentials. In fact,
the object encoding via existentials can be easily transformed into
the encoding that uses only simple, first-order types. The web page
begs a question if there is ever any real need for existentials.