Monomorphism, monomorphism...

Marcin 'Qrczak' Kowalczyk qrczak@knm.org.pl
8 Oct 2001 19:38:09 GMT


Mon, 8 Oct 2001 11:35:48 +0200, Hannah Schroeter <uk1o@rz.uni-karlsruhe.de> pisze:

> Now, with the typical dictionary implementation of type classes,
> this wouldn't really be too difficult.

Dictionaries would have to be make hashable and comparable. For a sane
semantics you can't compare their identities, because dictionaries
of instances of the same type might be created independently in
separate modules and would be treated as different. So we would either
need to extend the representation of each dictionary to include a
runtime identification of the type, or somehow guarantee to share
the representation of equal dictionaries.

>> C++ templates require having source available in each place a template
>> is used.
> 
> No. The standard specifies "export"ed templates. It's only that
> nearly no implementation supports that part of the ISO standard.

Ok, I was talking about the traditional model of compilation of C++.
That's why nobody fully implemented 'export' yet: it doesn't fit it.

> Isn't there some experimental thing that implements type classes
> by complete specialization of all code that uses polymorphic
> values?

I'm not sure. I argued for a kind of pragma between INLINE and
SPECIALIZE, which would tell the compiler to export the unfolding for
making specializations in modules which need them, but don't bother
with inlining each call. SimonPJ agreed that it's a good idea and is
perhaps working on this.

I was only able to change ghc to mark internal instance functions as
inline. The effect isn't exactly right.

> But at least, C++ templates have pattern matching ([partial]
> specialization!) and are Turing complete, albeit in a very
> strange way of expression.

That's why they have a limited depth of recursion (I think 31 is the
required minimum).

>> The C++ way wouldn't work for Haskell in general because sometimes
>> the depth of instances created is not bounded statically,
> 
> Can you name such a case in standard H'98?

Polymorphic recursion:

f :: Show a => Int -> a -> String
f n x | null (drop n str) = f n (x,x)
      | otherwise         = str
  where
    str = show x

> Right. A collection of existentially typed values is similar to
> abstract class Base ... class Derived1 : Base ... class Derived2 : Base,
> Collection[Base] with values of the different derived classes in
> typical OO languages.

Except that there are no downcasts (neither checked with a Maybe
result nor unchecked unsafe).

Since OO languages often use subtypes to emulate constructors of
algebraic types, they need downcasts. In Haskell it's perhaps less
needed but it's a pity that it's impossible to translate an OO scheme
which makes use of downcasts into Haskell in an extensible way
(algebraic types are "closed").

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK