Defining instance methods (with defaults) of their super class doesn't work

[matil019]

Spawned from #387

For example, Eq.!= has a default implementation. If an instance Ord (subclass of Eq) has an implementation of !=, it fails. How it "fails" differs by which module an instance is defined in.

Be prepared because there are a lot of example code below.

(used a3c4f77, the current master).

Examples

If an instance is defined in the same module as the data type

If an instance is defined in the same module as the data type, the compiler crashes.

Foo.fr:

module Foo where

data Foo = Foo Int

instance Eq Foo where
  Foo a == Foo b = a == b
  hashCode (Foo a) = hashCode a

instance Ord Foo where
  _ != _ = error "(Ord Foo).!="
  Foo a <=> Foo b = a <=> b

Main.fr:

module Main where

import Foo (Foo)

main :: IO ()
main = println $ Foo 1 != Foo 2

Compiling:

$ java -jar ../fregec.jar -ascii -make Main.fr
calling: javac -cp ../fregec.jar:. -d . -sourcepath . -encoding UTF-8 ./Foo.java
F Main.fr:6:  substInst: trying Eq.!=, but Foo.Eq_Foo.!= does
    not exist!
frege.runtime.Undefined: fatal compiler error
        at frege.prelude.PreludeBase.error(PreludeBase.java:16255)
        at frege.compiler.common.Errors.lambda$fatal$50(Errors.java:867)
        at frege.run8.Thunk.call(Thunk.java:230)
        at frege.compiler.common.Errors.lambda$fatal$64(Errors.java:927)
        at frege.compiler.Typecheck.lambda$substInst$17(Typecheck.java:1878)
        at frege.run8.Thunk.call(Thunk.java:230)
        at frege.compiler.Utilities.lambda$mapEx$200(Utilities.java:3805)
        at frege.compiler.Utilities.lambda$mapEx$200(Utilities.java:3842)
        at frege.compiler.Utilities.lambda$mapEx$200(Utilities.java:3842)
        at frege.compiler.Utilities.lambda$mapEx$200(Utilities.java:3850)
        at frege.compiler.Typecheck.lambda$substInstMethod$67(Typecheck.java:2672)
        at frege.control.monad.State$IMonad_State.lambda$$gt$gt$12(State.java:1140)
        at frege.compiler.Typecheck.lambda$static$7(Typecheck.java:1740)
        at frege.run8.Thunk.call(Thunk.java:230)
        at frege.compiler.types.Global.lambda$forsome$43(Global.java:7343)
        at frege.compiler.Typecheck.lambda$static$790(Typecheck.java:18339)
        at frege.compiler.Main.lambda$runpass$34(Main.java:2143)
        at frege.compiler.types.Global.lambda$forsome$43(Global.java:7343)
        at frege.compiler.types.Global.lambda$liftIO$25(Global.java:6355)
        at frege.run8.Thunk.call(Thunk.java:230)
        at frege.compiler.Main.lambda$makeFile$320(Main.java:9221)
        at frege.compiler.Main.lambda$compileMe$358(Main.java:9850)
        at frege.compiler.Main$1Let$31146.lambda$async$16431$6(Main.java:10707)
        at frege.prelude.PreludeBase$TST.lambda$run$1(PreludeBase.java:10511)
        at frege.run8.Thunk.call(Thunk.java:230)
        at frege.prelude.PreludeBase$WrappedCheckedException.doCatch(PreludeBase.java:7495)
        at frege.prelude.PreludeIO.lambda$doCatch$9(PreludeIO.java:751)
        at frege.prelude.PreludeBase$TST.lambda$run$1(PreludeBase.java:10511)
        at frege.run8.Thunk.call(Thunk.java:230)
        at frege.java.Lang$1.run(Lang.java:2909)
        at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
        at java.util.concurrent.FutureTask.run(FutureTask.java:266)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
        at java.lang.Thread.run(Thread.java:748)
Main: aborted frege.runtime.Undefined: fatal compiler error
Build failed.

The interesting point is that the compiler crashes at Main.fr but not at Foo.fr.

If an instance is defined in the same module as the class

If an instance is defined in the same module as the class, the compiler silently ignores the method definition and the default implementation is used.

The following example makes up two classes MyEq and MyOrd which mimic Eq and Ord respectively.

Foo.fr:

module Foo where

data Foo = Foo Int

MyEq.fr:

module MyEq where

import Foo (Foo)

class MyEq a where
  equals :: a -> a -> Bool
  notEquals :: a -> a -> Bool
  notEquals a b = not $ equals a b

instance MyEq Foo where
  equals (Foo a) (Foo b) = a == b

MyOrd.fr:

module MyOrd where

import Foo (Foo)
import MyEq (MyEq)

class MyEq a => MyOrd a where
  greaterThan :: a -> a -> Bool

instance MyOrd Foo where
  notEquals _ _ = error "(MyOrd Foo).notEquals"
  greaterThan (Foo a) (Foo b) = a > b

Foo.fr:

module Main where

import Foo (Foo)
import MyEq (notEquals)
-- importing @instance MyOrd Foo@ doesn't change the result
import MyOrd ()

main :: IO ()
main = println $ notEquals (Foo 1) (Foo 2)

Compiling and running this program outputs true. However, it's likely that the programmer expected it to crash (at runtime) by evaluating error.

If an instance is defined as an orphan

By replacing instance MyEq and MyOrd by Eq and Ord resp. in the above example, we have orphan instances. The result is the same; compilation successful, running it outputs true.

Discussion

Implementing methods which have default implementations from the super class should be explicitly forbidden. The compiler should always emit a not-a-crash error on compiling a module which includes offending instances.

[Ingo60]

So, in my opinion, the second case is the worse one. In principle, the compiler did the "right thing" by not allowing the already established != to get overwritten. Of course there must be an error message in such a case.

First, I think it is immaterial, whether the method is a default class method or not, since when you make an instance of a class with default methods and don't give an implementation, then the code is simply copied from the class definition. Later, there is no way to know whether this implementation was supplied by the user or not.

In the following, I'll draw up an argument why overriding an already implemented function of the superclass should be forbidden.

Consider a type T and 3 modules E, O and M.
E defines instance Eq T. O imports E and defines instance Ord T overwriting != in such a way that it doesn't give the same results as the one in the Eq instance.
And finally M imports E and O and does some stuff.

Now consider a function E.foo that happens to use the (!=) from the Eq T instance. For some reason during a refactoring it turns out that it would be preferable to have it in O. And assuming that overriding already existing class functions did work, this would change the behaviour of the program.

Worse, in modules O and M, when we use (!=), we don't really know, nor have any influence, which (!=) would be used. The point is that the type checker collects the constraints raised, such that

 bar x y = if x != y then ... else ....

would get Eq a => but

bar2 x y = if x != y then if x < y then ... else .... else ....

would get Eq a, Ord a => and this would be reduced to Ord a becaue the class relationship dictates that Ord a implies Eq a, so there is no need to pass two instances to bar2

Conclusion: An instance for C T must not supply an implementation for any class method that originates from a super class of C when an implementation of that method already exists. It does exist whenever T is already an instance of the super class, no matter if the implementation of the method is supplied by the user, by a deriving definition or by a default class method.

For example:

instance Eq T where .....
deriving Enum T

must not override (==) and (!=).

And I guess here is the reason why there is no error message. Because a derive definition is simply desugared to an instance definition with all the needed methods (in the case of Enum, which implies Ord and Eq, this includes (==), (!=), (<) and so forth). I guess, because this happens often, I simply ignored this case, not giving a though about the possibility that the overriding method could have been supplied by the user.

Hence, the following is possible, and should be possible henceforth:

frege> data T = Foo | Bar
data type T :: *

frege> derive Eq T
instance Eq T

frege> Foo == Bar
false

frege> derive Enum T
instance Enum T

frege> succ Foo
T

frege> derive Show T
instance Show T

frege> succ Foo
Bar

And clearly, when we define a differing (!=) this should be respected:

frege> data T2 = A | B
data type T2 :: *

frege> deriving Show T2
instance Show T2

frege> deriving Enum T2
instance Enum T2

frege> succ A
B

frege> A != succ A
true

frege> instance Eq T2 where _ != _ = false; A == A = true; B == B = true; _ == _ = false; hashCode _ = 0
instance Eq T2

frege> A != succ A
false

And finally, an all-in-one instance definition (e.g. instance Ord T when no Eq instance is present, provided all needed methods are supplied) should still be possible. (It would then break when one imports a module that has an Eq T instance, which is a good thing, IMHO, as it points out conflicts).

By the way, the repl session above also shows nicely that the instance definitions are processed in dependency order, not in the order they appear in the source file.

Perhaps, to achieve what we want (ignore synthetic mehods if there is already an implementation, but complain about user defined ones) we would need a flag in the SymI (or whatever it is now) that tells whether this is a derived instance, and based on that, the error is emitted or not. It should be so as if the deriving only generates methods that are absolutely required, however, we can't do that actually, because at the time we desugar derive we're far from knowing what instances and types do exist.

It goes without saying that this would also make the compiler crashing program illegal, so that the compiler would fail well before it even reaches the type checking pass (which is where it crashes).

[matil019]

Adding as a memo:

If both Eq and Ord are orphans but put in the same module, the compiler crashes as if they are defined alongside the data type.

If at least Ord is an orphan and is defined in the different module as Eq, then the compilation succeeds while emitting a following hint:

H ./MyOrd.fr:7: There exists another implementation of
    `!=` for unrelated instance `MyEq.Eq_Foo`, this will
    make it impossible to access instance member value
    `Ord_Foo.!=` directly.