Existential Typing (was Multi-parameter OOP)

Leon Smith lps@po.cwru.edu
Wed, 24 Oct 2001 10:38:48 -0400


--------------Boundary-00=_OOSPHRC6ZUFBFMMTYGYD
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 8bit

On Friday 19 October 2001 11:02, George Russell wrote:
> Recently I've been experimenting with a sort of OOP with GHC, [...]

I find your discussion rather intriguing, but I'm not sure I fully understand 
what you are trying to do.

Existential typing allows for what I would call "dynamic dispatch", which 
allows for the dynamic lookup of class members (i.e. methods).  What you 
appear to be trying is something resembling dynamic typing.  Dynamic typing 
can be "emulated" using dynamic dispatch.  

If GHC had true existential typing, as opposed to just existential datatypes, 
you could reasonably code what I think you want like this:

class A a where
    basicA :: Bool
    nextA  :: a -> (EX a'. A a' => a')
    basicA = True
    nextA  = id

data WrappedA = forall a. A a => WrappedA a

instance A WrappedA where
    basicA = False
    nextA (WrappedA a) = a

data A1 = A1

instance A A1

--... similarly for B ...

class AB a b where
   toBool :: a -> b -> Bool

instance (A a, B b) => AB a b where
   toBool a b 
      | (basicA :: a) && (basicB :: b) = True
      | (basicA :: a) || (basicB :: b) = False
      | otherwise = toBool (nextA a) (nextB b)


In this new setting, class AB seems a little silly.  You could simply get rid 
of it.  

Of course, GHC doesn't work this way.  Instead, you have to introduce a 
datatype "StupidA" to wrap your existential type in.   For the benefit of 
this new stupid datatype, you'll also need to change the type of basicA from 
(:: Bool) to (:: a -> Bool).  This datatype also introduces unnecessary 
overhead, as you end up having chains of StupidA constructors that do 
essentially nothing.

You could look at my attached code if you really want to.  It has been beaten 
throughly with an ugly stick. 

From the purely denotational point of view of semantics,  I love existential 
typing.   I think this example really drives the point across that 
existential datatypes are not nearly as useful as existential typing.   I can 
think of several similar situations in actual code of mine.  However, using 
existential datatypes was overkill for the situation, and thus I opted for a 
different solution altogether.  

I don't understand all the implementation consequences of existential typing. 
Most importantly, how does existential typing effect the operational 
semantics?  Mercury has existential typing,  but then again, Mercury is newer 
and its design philosophy is far more ambitious.
		
best,
leon
--------------Boundary-00=_OOSPHRC6ZUFBFMMTYGYD
Content-Type: text/plain;
  charset="iso-8859-1";
  name="ExClass.hs"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="ExClass.hs"

Y2xhc3MgQSBhIHdoZXJlCiAgIGJhc2ljQSA6OiBhIC0+IEJvb2wKICAgbmV4dEEgIDo6IGEgLT4g
U3R1cGlkQQogICBiYXNpY0EgXyA9IFRydWUgCiAgIG5leHRBICBhID0gU3R1cGlkQSBhCgpkYXRh
IFN0dXBpZEEgPSBmb3JhbGwgYSAuIEEgYSA9PiBTdHVwaWRBIGEKCmluc3RhbmNlIEEgU3R1cGlk
QSB3aGVyZQogICBiYXNpY0EgKFN0dXBpZEEgYSkgPSBiYXNpY0EgYSAKICAgbmV4dEEgIChTdHVw
aWRBIGEpID0gU3R1cGlkQSAobmV4dEEgYSkKCmRhdGEgV3JhcHBlZEEgPSBmb3JhbGwgYSAuIEEg
YSA9PiBXcmFwcGVkQSBhIAoKaW5zdGFuY2UgQSBXcmFwcGVkQSB3aGVyZQogICBiYXNpY0EgXyAg
ICAgICAgICAgPSBGYWxzZQogICBuZXh0QSAoV3JhcHBlZEEgYSkgPSBTdHVwaWRBIGEgCgpkYXRh
IEExID0gQTEKCmluc3RhbmNlIEEgQTEgCgpjbGFzcyBCIGIgd2hlcmUKICAgYmFzaWNCIDo6IGIg
LT4gQm9vbAogICBuZXh0QiAgOjogYiAtPiBTdHVwaWRCCiAgIGJhc2ljQiBfID0gVHJ1ZSAKICAg
bmV4dEIgIGIgPSBTdHVwaWRCIGIKCmRhdGEgU3R1cGlkQiA9IGZvcmFsbCBiIC4gQiBiID0+IFN0
dXBpZEIgYgoKaW5zdGFuY2UgQiBTdHVwaWRCIHdoZXJlCiAgIGJhc2ljQiAoU3R1cGlkQiBiKSA9
IGJhc2ljQiBiCiAgIG5leHRCICAoU3R1cGlkQiBiKSA9IFN0dXBpZEIgKG5leHRCIGIpCgpkYXRh
IFdyYXBwZWRCID0gZm9yYWxsIGIgLiBCIGIgPT4gV3JhcHBlZEIgYgoKaW5zdGFuY2UgQiBXcmFw
cGVkQiB3aGVyZQogICBiYXNpY0IgXyAgICAgICAgICAgPSBGYWxzZQogICBuZXh0QiAoV3JhcHBl
ZEIgYikgPSBTdHVwaWRCIGIKCmRhdGEgQjEgPSBCMQoKaW5zdGFuY2UgQiBCMSAKCgp0b0Jvb2wg
OjogKEEgYSwgQiBiKSA9PiBhIC0+IGIgLT4gQm9vbAp0b0Jvb2wgYSBiIAogIHwgYmFzaWNBIGEg
JiYgYmFzaWNCIGIgPSBUcnVlCiAgfCBiYXNpY0EgYSB8fCBiYXNpY0IgYiA9IEZhbHNlCiAgfCBv
dGhlcndpc2UgICAgICAgICAgICA9IHRvQm9vbCAobmV4dEEgYSkgKG5leHRCIGIpCgkJCgkJCgoK
CgoKCgptYWluID0gcmV0dXJuICgp

--------------Boundary-00=_OOSPHRC6ZUFBFMMTYGYD--