Monomorphism, monomorphism...

[Hannah Schroeter]

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.