Empty instance declaration
Dear all A student from a beginners course on Functional Programming came to me with a problem, he declared a type like: data WeekDay = Mon | Tue | Fri -- ... He had forgot to complete a Show instance definition. instance Show WeekDay where (empty) Then he complained about getting *** Exception: stack overflow when he tried to invoke some function on that type. After checking the Haskell98 grammar I found out that this is allowed syntactically and probably semantically too. Is there any reason to do that? Now I'm wondering: Shouldn't a class be an warranty of a well defined interface? Thus forcing the user to define the show function or showPrec? Am I missing any point? My best regards, Hugo
instance Show WeekDay where (empty)
You see, an empty instance like that may serve various purposes. In type-level programming, for example, they (roughly) correspond to facts in logic programming. However, in the case at hand, this is what happens: the doc for class Show reads thus: "Minimal complete definition: showsPrec or show." This (especially the word "or") means two things: (i) the class provides default definitions for its functions; (ii) the default definition for showsPrec (resp. show) is itself defined in terms of show (resp. showsPrec). The problem is, when you declare an empty instance, all functions (if any) assume their default definitions. Therefore, when you call show/showsPrec (even indirectly) you end up in an endless loop because of (ii). I agree with you that it'd be best if this sort of thing were detected at compile time, but it ultimately boils down to automatically detecting non-terminating programs... By the way, I haven't heard of a language that tackles the same problem differently. Cheers, Jorge.
Then he complained about getting *** Exception: stack overflow when he tried to invoke some function on that type.
After checking the Haskell98 grammar I found out that this is allowed syntactically and probably semantically too. Is there any reason to do that?
Now I'm wondering: Shouldn't a class be an warranty of a well defined interface? Thus forcing the user to define the show function or showPrec? Am I missing any point?
My best regards, Hugo _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Jorge M. Pelizzoni ICMC - Universidade de São Paulo
On Dec 27, 2007 2:20 PM, Jorge Marques Pelizzoni <jpeliz@icmc.usp.br> wrote:
The problem is, when you declare an empty instance, all functions (if any) assume their default definitions. Therefore, when you call show/showsPrec (even indirectly) you end up in an endless loop because of (ii).
I agree with you that it'd be best if this sort of thing were detected at compile time, but it ultimately boils down to automatically detecting non-terminating programs... By the way, I haven't heard of a language that tackles the same problem differently.
This is definitely not the same as detecting non-terminating programs, it's a case of wanting to add expressiveness so that the "minimal instance defines either show or showsPrec" could be placed in the code instead of in haddock, and ghc could at minimum generate a warning in this situation. Class designers would be delighted to be able to add this sort of information, and no longer have this tradeoff between making it easy to write correct instances and making it hard to write incorrect instances. The trouble, of course, is that classes could have rather complicated "minimum instance" requirements. Still, if someone came up with a decent syntax such as (but better than) class Foo f where foo :: f foo = bar bar :: f bar = foo requiring ( foo || bar ) it would be very nice. The trouble, of course, is deciding how expressive to make the requirements. David
David Roundy wrote:
The trouble, of course, is that classes could have rather complicated "minimum instance" requirements. Still, if someone came up with a decent syntax such as (but better than)
class Foo f where foo :: f foo = bar bar :: f bar = foo requiring ( foo || bar )
it would be very nice. The trouble, of course, is deciding how expressive to make the requirements.
probably a pragma, since it only affects warnings. And it seems like each class only has a finite number of functions, so a Boolean expression should be able to express the full range of possibilities with ( || , && , not , True , False ); and combinations that are complicated to express with those, aren't very common, due to the structure of the problem.
class Foo f where {-# MINIMAL_INSTANCE foo || bar #-} foo :: f foo = bar bar :: f bar = foo
I wonder whether it would be safe for the compiler to infer simply by the default methods mentioning each other in a cycle. It might miss some cases when (probably involving laziness) the default methods actually terminate and form an intended set of implemention, and warn when it shouldn't... which is bad, but does that ever happen? Isaac
Isaac wrote:
I wonder whether it would be safe for the compiler to infer simply by the default methods mentioning each other in a cycle. It might miss some cases when (probably involving laziness) the default methods actually terminate and form an intended set of implemention, and warn when it shouldn't... which is bad, but does that ever happen?
"mentioning each other in a cycle" is too imprecise unfortunately at least for two reasons: a) we could face a well-designed mutual recursion. b) we could face co-induction. The ultimate solution is to extend type signatures by termination requirements and to have a termination checker enforcing them. For instance, Andreas Abel has done groundbreaking work on termination checking. Cheers, Ralf
Ralf Laemmel wrote:
Isaac wrote:
I wonder whether it would be safe for the compiler to infer simply by the default methods mentioning each other in a cycle. It might miss some cases when (probably involving laziness) the default methods actually terminate and form an intended set of implemention, and warn when it shouldn't... which is bad, but does that ever happen?
"mentioning each other in a cycle" is too imprecise unfortunately at least for two reasons:
a) we could face a well-designed mutual recursion. b) we could face co-induction.
I know! I said so! My question is whether anyone has an example of doing either of those in mutually-recursive DEFAULT METHOD definitions? sorry for yelling You did not say anything that's imprecise about "mentioning each other in a cycle", just the well-known fact that it's not equivalent to total termination checking (in fact, it's neither fully an overestimate nor underestimate of termination -- it's just an estimate that's likely to be right when used in the context of default method definitions). Isaac
You did not say anything that's imprecise about "mentioning each other in a cycle", just the well-known fact that it's not equivalent to total termination checking (in fact, it's neither fully an overestimate nor underestimate of termination -- it's just an estimate that's likely to be right when used in the context of default method definitions).
It's imprecise also in so far that you would need to define what you mean by it. Does it mean that we focus on the "pattern" f ... = g ... g ... = f ... ... or does it include the case f ... = h g ... g ... = f ... ... and that's still very imprecise because the dots don't mean anything proper. Are you willing to look at the pattern *after* overloading resolution. Let's have a proper termination checker! Btw, obviously a class by itself would not be checked (in terms of the default methods), but only an instance (with the defaults pulled in). Cheers, Ralf
Ralf Laemmel wrote:
You did not say anything that's imprecise about "mentioning each other in a cycle", just the well-known fact that it's not equivalent to total termination checking (in fact, it's neither fully an overestimate nor underestimate of termination -- it's just an estimate that's likely to be right when used in the context of default method definitions).
It's imprecise also in so far that you would need to define what you mean by it. Does it mean that we focus on the "pattern"
f ... = g ... g ... = f ...
... or does it include the case
f ... = h g ... g ... = f ...
yes it does. It also probably includes f ... = ... where _ignored1 = g g ... = ... where _ignored2 = f Predictability is a good thing, I think although class where f ... = g ... g ... = h ... h ... = f ... gets more complicated, but 'h' does have to be defined in the same module or module-cycle, because it refers to the class and the class refers to it
... and that's still very imprecise because the dots don't mean anything proper.
Are you willing to look at the pattern *after* overloading resolution.
good point. I think GHC can know when it refers to the same instance.
Let's have a proper termination checker!
I think GHC already does, in its strictness analyzer? An incomplete checker of course, because termination checking of Haskell, like of most languages, is undecidable in general.
Btw, obviously a class by itself would not be checked (in terms of the default methods), but only an instance (with the defaults pulled in).
the class would at most be analyzed to see which were the minimal methods to implement -- it's warnings about instances that we've been talking about, anyway Isaac
On Dec 28, 2007, at 12:06 PM, Ralf Laemmel wrote:
You did not say anything that's imprecise about "mentioning each other in a cycle", just the well-known fact that it's not equivalent to total termination checking (in fact, it's neither fully an overestimate nor underestimate of termination -- it's just an estimate that's likely to be right when used in the context of default method definitions). [The hard general cases] ... and that's still very imprecise because the dots don't mean anything proper.
Are you willing to look at the pattern *after* overloading resolution.
Let's have a proper termination checker!
It occurs to me to ask: would "returns bottom given non-bottom arguments according to strictness analysis" be good enough? Because that information is useful for other things as well, and relatively easy to compute using strictness analysis. Then "extra pragmas" might be as simple as pragmas saying "yes, compiler, I expect the following function to return _|_"---again an annotation that has other potential uses. -Jan-Willem Maessen
G'day all. Quoting Isaac Dupree <isaacdupree@charter.net>:
I know! I said so! My question is whether anyone has an example of doing either of those in mutually-recursive DEFAULT METHOD definitions?
class (Eq a) => StupidEqList a where eqList :: [a] -> [a] -> Bool neqList :: [a] -> [a] -> Bool eqList [] [] = True eqList (x:xs) (y:ys) = x == y && not (neqList xs ys) eqList _ _ = False neqList [] [] = False neqList (x:xs) (y:ys) = x /= y || not (eqList xs ys) neqList _ _ = True Stupid, but not illegal. Cheers, Andrew Bromage
Hi
The trouble, of course, is that classes could have rather complicated "minimum instance" requirements. Still, if someone came up with a decent syntax such as (but better than)
You don't need a syntax, the information is already there. You also don't need to do complicated non-termination analysis. Taking the slightly simpler example of: class Eq a where a == b = not (a /= b) a /= b = not (a == b)
From this example its clear that (==) depends on (/=) and that (/=) depends on (==). i.e. its obvious they form a cycle. If the default methods form a cycle, and the user has not broken that cycle by inserting a real implementation, that's almost certainly a bug - I'd go as far as to say its an error rather than a warning.
Thanks Neil
Neil Mitchell wrote:
The trouble, of course, is that classes could have rather complicated "minimum instance" requirements. Still, if someone came up with a decent syntax such as (but better than)
You don't need a syntax, the information is already there. You also don't need to do complicated non-termination analysis. Taking the slightly simpler example of:
class Eq a where a == b = not (a /= b) a /= b = not (a == b)
From this example its clear that (==) depends on (/=) and that (/=) depends on (==). i.e. its obvious they form a cycle.
Ah, but it's not "clear" at all :) How about something wicked like class UselessEq a where (==), (/=) :: Bool -> a -> Bool True == b = b a == b = not (a /= b) False /= b = b a /= b = not (a == b) This may be useless but I wouldn't be surprised if interesting examples utilizing polymorphic recursion or multi parameter type classes exist. Regards, apfelmus
Neil Mitchell wrote:
If the default methods form a cycle, and the user has not broken that cycle by inserting a real implementation, that's almost certainly a bug - I'd go as far as to say its an error rather than a warning.
I'd agree except that "instance Num () where" with no specified definitions is already allowed in Haskell and can only generate warnings in GHC already. Isaac
You may be interested in a trick relating to type classes which can address this issue, though it's not the "Haskell way to do it." You can define Show as a data type, rather than a type class: type Show a = Either (a -> String) (Int -> a -> String -> String) show :: Show a -> a -> String show (Left s) x = s x show (Right sp) x = sp 0 x "" showsPrec :: Show a -> Int -> a -> String -> String showsPrec (Left s) n a str = s a ++ str showsPrec (Right sp) n a str = sp n a str A function using this "class" would take it as its first argument: print :: Show a -> a -> IO () The constructors for Show make explicit the two ways to define an instance. This technique also has the advantage of allowing multiple, non-conflicting instance declarations, selectable at runtime. Using Show as an example, you might have instances representing both formatted and unformatted display. An obvious disadvantage is that the instance needs a name and gets passed explicitly. Mike On Thu, Dec 27, 2007 at 04:34:06PM +0000, Hugo Macedo wrote:
Dear all
A student from a beginners course on Functional Programming came to me with a problem, he declared a type like:
data WeekDay = Mon | Tue | Fri -- ...
He had forgot to complete a Show instance definition.
instance Show WeekDay where (empty)
Then he complained about getting *** Exception: stack overflow when he tried to invoke some function on that type.
After checking the Haskell98 grammar I found out that this is allowed syntactically and probably semantically too. Is there any reason to do that?
Now I'm wondering: Shouldn't a class be an warranty of a well defined interface? Thus forcing the user to define the show function or showPrec? Am I missing any point?
My best regards, Hugo
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Dec 28, 2007 5:14 PM, Mike Haskel <mlh2131@columbia.edu> wrote:
You can define Show as a data type, rather than a type class:
type Show a = Either (a -> String) (Int -> a -> String -> String) ... The constructors for Show make explicit the two ways to define an instance. This technique also has the advantage of allowing multiple, non-conflicting instance declarations, selectable at runtime. Using Show as an example, you might have instances representing both formatted and unformatted display. An obvious disadvantage is that the instance needs a name and gets passed explicitly.
Seems to me that using Either is entirely orthogonal from type-vs-class :-) class Show a where show0 :: Either (a -> String) (Int -> a -> String -> String) show :: Show a => a -> String show = case show0 of Left s -> s Right sp -> \x -> sp 0 x "" etc. - Benja
G'day all. Quoting Hugo Macedo <hmacedo@di.uminho.pt>:
After checking the Haskell98 grammar I found out that this is allowed syntactically and probably semantically too. Is there any reason to do that?
One thing that hasn't come up yet is that empty instance declarations are the only decent option (that I know of) that we have in the absence of real class aliases. Here's an example from Dfa.lhs, which could probably be written slightly more simply now:
{-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-}
import Control.Monad.Identity import Control.Monad.Reader import Control.Monad.State
data (Ord t) => ReRead t = {- detail unimportant -}
data (Ord t) => ReState t = {- detail unimportant -}
type ReM m t a = StateT (ReState t) (ReaderT (ReRead t) m) a
class (Monad m, Ord t) => ReVars m t where { } instance (Monad m, Ord t) => ReVars m t where { }
remNullSet :: (ReVars m t) => ReM m t (SimplRe t) {- etc -}
class (ReVars m t, MonadIO m, Show t) => ReVarsIO m t where { } instance (ReVars m t, MonadIO m, Show t) => ReVarsIO m t where { }
remDump :: (ReVarsIO m t) => ReM m t () {- etc -}
Cheers, Andrew Bromage
ajb@spamcop.net wrote:
One thing that hasn't come up yet is that empty instance declarations are the only decent option (that I know of) that we have in the absence of real class aliases.
I agree. I use this in my code in a number of places. It helps to write readable signatures. Best regards, Johannes Waldmann.
ajb@spamcop.net wrote:
One thing that hasn't come up yet is that empty instance declarations are the only decent option (that I know of) that we have in the absence of real class aliases.
It does seem to me that compilers could reasonably distinguish between incomplete definition:
class (Monad m, Ord t) => ReVars m t where { } instance (Monad m, Ord t) => ReVars m t where { }
and intentionally incomplete definition: class (Monad m, Ord t) => ReVars m t instance (Monad m, Ord t) => ReVars m t Both syntaxes (with and without the 'where') are currently legal, but the latter is more obviously deliberate (at least to this human reader). Regards, Malcolm
participants (13)
-
ajb＠spamcop.net -
apfelmus -
Benja Fallenstein -
David Roundy -
Hugo Macedo -
Isaac Dupree -
Jan-Willem Maessen -
Johannes Waldmann -
Jorge Marques Pelizzoni -
Malcolm Wallace -
Mike Haskel -
Neil Mitchell -
Ralf Laemmel