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
Marcin 'Qrczak' Kowalczyk writes: : | 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"). Hi. I'm curious about this impossibility. - Is it well known? If so, would someone please refer me to a paper or posting which explains it? - Does it just affect Haskell 98, or does it have deep implications for any future language extensions? - How does it relate to the alternative record mechanism idea you mentioned a while ago? http://haskell.org/pipermail/haskell/2000-December/000213.html Regards, Tom
Hello! On Mon, Oct 08, 2001 at 07:38:09PM +0000, Marcin 'Qrczak' Kowalczyk wrote:
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.
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. I.e. compile instance Num Int where ... -> code for the methods, and dict_num_int: (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); TAIL_CALL_CONTINUATION(c, result); } 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 even -fallow-undecidable-...?!)
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
Oh... Good example, thanks.
[...]
Kind regards, Hannah.
Hannah Schroeter wrote:
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)?
One problem is that certain Haskell programs need an unbounded number of instances. -- Lennart
participants (4)
-
Hannah Schroeter -
Lennart Augustsson -
Marcin 'Qrczak' Kowalczyk -
Tom Pledger