Wed, 24 Oct 2001 10:36:22 +0200
On Mon, Oct 08, 2001 at 07:38:09PM +0000, Marcin 'Qrczak' Kowalczyk wrote:
> Mon, 8 Oct 2001 11:35:48 +0200, Hannah Schroeter <firstname.lastname@example.org> 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.
I don't think so. Why not create a dictionary record while compiling
the associated instance (which may, by the H'98 definition, occur
only once in the program)? Then the instance is associated with one
symbol (in the C linker sense), which you refer at all times you must
conjure up a dictionary to pass it into functions. The symbol
is resolved to the same address on every reference by the linker,
voilą, there's the identity based dictionary identification.
And hashing (void*)'s isn't too difficult, either.
And I think just referring to the same dictionary record over and over
is also cheaper than creating new dictionary records from time to time.
instance Num Int where
-> code for the methods, and
(some tag that it's a dictionary which is static and must
never be touched by the GC)
reference to method for (+)
reference to method for (-)
foo :: Num a => a -> a
foo x = x + 1
foo_impl(struct dict_num* num_dict, HS_OBJ* x, Continuation* c)
HS_OBJ* one = num_dict->fromInteger(INTEGER_SMALL_LIT(1));
HS_OBJ* result = num_dict->plus(x, one);
bar :: Int -> Int
bar x = foo x
bar_impl(HS_OBJ* x, Continuation* c)
// as a tail call
foo_impl(dict_num_int, x, c);
And here, you use the same dictionary address as on every other call site
that has to pass a Num a => a argument from a monomorphic Int value.
> >> 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.
It would fit, one just would have to give up the "one-source-at-a-time-
and-produce-only-traditional-object-code" compilation model.
> > 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).
Yes, of course. It's a similar problem like in Cayenne, where type checking
could take infinite time, too. (And what about current ghc Haskell,
with multiple parameter type classes, overlapping instances, perhaps
> >> 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
> str = show x
Oh... Good example, thanks.