Sat, 6 Oct 2001 22:22:24 -0700, Juan Carlos Arévalo Baeza
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
Hello! On Sun, Oct 07, 2001 at 11:29:09AM +0000, Marcin 'Qrczak' Kowalczyk wrote:
[...]
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.
Now, with the typical dictionary implementation of type classes, this wouldn't really be too difficult. foo :: Num a => a foo = 2*3*5*7 creates a hash map, where the key is the dictionary argument and the value is the deferred (call by need) calculation of 2*3*5*7 for that particular Num instance, so it could be transformed to sth like createHashMap :: (Hashable key) => value -> IO HashMap key value createHashMap defaultValue = ... gethash :: HashMap key value -> key -> value puthash :: HashMap key value -> key -> value -> IO () foo_internal :: HashMap ... foo_internal = createHashMap foo_impl foo :: NumDict a -> a foo dict = (gethash foo_internal dict) dict -- foo_impl gets called only once per dict, as it replaces its entry -- in foo_internal by the lazy value of foo for that particular -- instance and returns that. foo_impl :: NumDict a -> a foo_impl dict = let value = (*) dict (fromInteger dict 2) ... hashSlot _ = value in unsafePerformIO $ do puthash foo_internal dict hashSlot return value Yes, it creates some burden, but for fast hash maps, that shouldn't be completely unfeasible. Other programming languages use hash lookups for every function call and get performance by dynamic code generation techniques or other means. And "we" could still specialize cases where foo is applied in known type contexts (e.g. when the context of one particular usage definitely suggests "Integer", the compiler could even statically evaluate the whole of foo).
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.
No. The standard specifies "export"ed templates. It's only that nearly no implementation supports that part of the ISO standard. With exported templates, you specify only signatures in the headers, together with appropriate placement of the keyword "export". The implementation is in .cc files, just like for non-template methods.
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.
Isn't there some experimental thing that implements type classes by complete specialization of all code that uses polymorphic values?
It works because Haskell's rules of overloading are defined more "semantically". C++ templates are closer to syntactic macros.
Yep. C++ templates are a castrated version of Lisp macros :-) But at least, C++ templates have pattern matching ([partial] specialization!) and are Turing complete, albeit in a very strange way of expression.
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?
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).
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.
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.
Seems so, at least when language extensions come into play.
[...]
Kind regards, Hannah.
participants (2)
-
Hannah Schroeter -
Marcin 'Qrczak' Kowalczyk