Suppose I have the following function definition: app :: (?ys :: [a]) => [a] -> [a] app xs = case ?ys of [] -> xs (y:ys') -> y : (app xs with ?ys = ys') This function appends its argument to its implicit argument, by recursively changing the implicit argument. For example: Hugs> app [1,2] with ?ys = [3,4] [3,4,1,2] So far so good! Now, since Haskell has type inference, we can leave out the type signature: -- app :: (?ys :: [a]) => [a] -> [a] app xs = case ?ys of [] -> xs (y:ys') -> y : (app xs with ?ys = ys') Let us check if it still works again: Hugs> app [1,2] with ?ys = [3,4] [3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,{Interrupted!} And, stunningly, it doesn't! Why doesn't this work? That is because type inference assumes that the body of `app' is monomorphic, i.e. has no context in its type. Therefore, the recursive call to app where ?ys is changed, had no effect at all. It works with the type signature there, because in order to implement type checking (note: not type inference) with polymorphic recursion demands to use the stated type in checking the body of the function. Mark Shields, Simon Peyton-Jones, and I, and also Jörgen Gustavsson have been discussing several modest solutions to this (we believe it is not needed to do full type inference that can deal with polymorphic recursion to solve this problem). Not so fast! Proposing a "solution" means this is regarded as a "problem"! But what is to say that the first behaviour is "right" in any general sense? The important thing is that the language semantics is clear, and this is a semantic question. The static semantics of Haskell *is* clear: recursive calls are monomorphic unless a type signature is given; this is the basis for understanding the behaviour above. When implicit parameters are used, it's very important to be aware whether a binding is monomorphic or not (can't resist plugging := again!). Will your "solution" make understanding when a binding is monomorphic simpler? If not, it could be worse than the "problem" -- and the fact that it makes this one example behave as you want is no justification. John
On Monday 04 February 2002 02:25 am, John Hughes wrote:
Not so fast! Proposing a "solution" means this is regarded as a "problem"! But what is to say that the first behaviour is "right" in any general sense?
The important thing is that the language semantics is clear, and this is a semantic question. The static semantics of Haskell *is* clear: recursive calls are monomorphic unless a type signature is given; this is the basis for understanding the behaviour above.
I think part of the problem is that we've confused implicit parameterisation with polymorphism. Haskell has a two-level type system with monomorphic types at the bottom level, and polymorphic and qualified types at the second level. It turned out to be very straightforward to add implicit parameters to Haskell by treating them as a special kind of qualified type, and thus they also play according to the rules of polymorphic types - i.e. you `capture' implicit parameters exactly when you generalize a polymorphic definition. However, Koen's example suggests that maybe implicit parameters shouldn't necessarily play according to the rules of polymorphic types. Perhaps implciit parameters should be a special kind of monomorphic type instead. If this were the choice, then it's clear that they should be captured by recursive definitions.
When implicit parameters are used, it's very important to be aware whether a binding is monomorphic or not (can't resist plugging := again!). Will your "solution" make understanding when a binding is monomorphic simpler? If not, it could be worse than the "problem" -- and the fact that it makes this one example behave as you want is no justification.
I agree that we should tread carefully ;-) --Jeff
participants (2)
-
Jeffrey R. Lewis -
John Hughes