Monomorphism, monomorphism...

[Marcin 'Qrczak' Kowalczyk]

Sat, 6 Oct 2001 22:22:24 -0700, Juan Carlos Arévalo Baeza <jcab@roningames.com> pisze:

>>A pattern which is something other than an identifier.
> 
>    Like defining a function, as opposed to defining a constant?

No: a pattern, e.g. (x,y), Just y, (x:_) etc. A function definition
looks like an identifier applied to patterns, which usually doesn't
look like a pattern. These are two forms of lhs of =.

These yntaxes collide only for identifiers alone. They could be
treated like degenerate patterns (which match anything) or like
functions with no arguments.

>>- isNil (or any value with a non-empty context in its type) doesn't
>> really behave like a constant, but as a function taking a dictionary
>> of 'IsNil a' as an implicit argument, so it's recomputed each time
>> it it used...
> 
>    Ok... This is an angle I hadn't even approached yet. We're talking
>    about the internal implementation of the compiler here. Hmmm...

The difference is visible for the programmer not only in speed, but
also by typing rules: pattern bindings are monomorphic, functions
can be polymorphic.

With monomorphic restriction a lhs looking like an identifier is
treated as something between pattern and function: type variables with
class constraints are monomorphic, type variables without conatraints
are polymorphic. And it can be promoted to a fully polymorphic version
by giving a type signature.

>    Shouldn't the compiler be able to limit the recomputations to
>    one per instance of the class?

It would require very unusual implementation. Currently the compiler
doesn't need to build dictionaries indexed by types at runtime and
even doesn't need to recognize which types are "the same" at runtime.

>    I guess I'm biased here by my knowledge of templates in C++,
>    which can be used to implement something very similar to type
>    classes in Haskell.

C++ templates require having source available in each place a template
is used. I agree that it would be useful for Haskell compilers to
compile some instances that way when optimization is turned on,
but the traditional way to implement classes uses a single compiled
version which is passed various dictionaries at runtime.

It works because Haskell's rules of overloading are defined more
"semantically". C++ templates are closer to syntactic macros.

The C++ way wouldn't work for Haskell in general because sometimes
the depth of instances created is not bounded statically, unlike C++
templates which are instantiated at compile time. And it doesn't
work with extensions like existential quantification, where types
which differ in instance dictionaries can be packed into values of
a single type, so the instance to use *must* be chosen dynamically
(data flow can't be statically determined in general).

It can be only an optimization (and perhaps it's sometimes more code
bloat than optimization), it doesn't fit as the primary model IMHO.

> class Num a where
>   n :: a
>   n = 7*11*13
> 
>    'n' here has that type 'Num a => a', doesn't it? Don't tell me
>    compilers will compute it twice if we use it twice, as in:
> 
> n1 = n
> n2 = n

It will probably recognize that the same instance is needed in both
places. But it will almost certainly recompute when n1 and n2 are
defined in separate modules.

It can't perform the multiplication until the type is known.

>>- When a pattern binds several variables, it can happen that their
>> types need different sets of class constraints. Using such a variable
>> doesn't fully determine the type to perform the computation in.
>> It's thus ambiguous and an error.
> 
>    You're talking about the case '(var1, var2) = expr', right? That's
>    because var1 and var2 cannot have different contexts?

They can, caused by different sets of type variables present in types
of var1 and var2:

    (x, y) = let z = read "[10,20]" in (z, show z)

Here x :: Read a => a,
     y :: String.

It makes no sense to give y yhe type 'Read a => String'. This type
would be ambiguous because 'a' is absent in the main part of the type.

With monomorphism restriction uses of x determine the way y is
computed. Without monomorphism restriction all uses of x and y have
individually instantiated types, so there is no way to compute y at
all: you don't know on which type it should be done, as in
    show (read "[10,20]")
which is ambiguous.

>    So it is. I just tried, with Hugs:

Hugs implements this incorrectly. AFAIK it doesn't let usages of
global variables contribute to disambiguation of their types.

>>2. Define a possibly polymorphic function and perform the given
>> computation when it is applied (function binding).
> 
>    In case 2 we wouldn't need the restriction, right?

Yes. Functions are defined one at a time, not by matching patterns;
and their recomputation is expected.

>>It might happen that by choosing this instance now it will be OK when
>>f is used. The other possibility of the type for f would take away
>>some freedom: we can't use this instance later with different choices
>>for types of list elements, because both uses of g must make the same
>>choices for type variables with class constraints. It's not visible yet
>>(before choosing the instance) that the single type 'IsNil a => a'
>>will expand into something containing quantified type variables without
>>class constraints which can be instantiated independently!
> 
>    Hmmm... As in typing '2+2' in Hugs and having it say 'ambiguous
>    type: Num a => a'? Is this the kind of problem that you're
>    talking about?

Not quite: the Karl's example is more subtle. Even if the overloading
is resolved by the surrounding code, choosing an instance early may
give extra opportunities to instantiate the resulting type several
times with slightly different types.

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