sealed abstract class Bdd {}
sealed abstract class BddTerm extends Bdd {}
object BddTrue extends BddTerm {}
object BddFalse extends BddTerm {}
case class BddNode(label:Int, positive:Bdd, negative:Bdd) extends Bdd {
// equals and hashCode methods copied from here:
// https://users.scala-lang.org/t/what-does-equivalence-of-instances-mean/4368/11?u=jimka
override def equals(that: Any): Boolean = {
that match {
case b: Bdd => this eq b
case _ => false
}
}
override def hashCode(): Int =
System.identityHashCode(this)
}
Now if I have a variable hash of type hashMap[(Bdd,Bdd),Bdd], then what does hash((b1,b2)) do? Does it matter whether b1 and b2 are declared as Bdd or as BddNode?
The reason I ask is that when I use VisualVM on my program, it spends a huge about of time in BddNode.equals. Whereas, I though it would spend hardly any time there. Have I defined my ADT with weird semantics, having equal on some classes but not on others?
x.method(y) invokes method on object x, which means that method is looked up in the class of x. Type of y only matters if method is overloaded in class of x. Overloading is done statically (at compile time) so it doesn’t incur runtime cost.
In Scala world the type of reference doesn’t matter on method selection, i.e. it matters at compile time to decide whether code compiles, but runtime selection of method implementation is done using actual object class, not reference type. OTOH in Java world there are static methods that are resolved statically. Static methods also arent’ overridable or inheritable.
First, #equals() should be symmetric - a == b should always yield the same result as b == a, but you’ll run into different implementations depending whether a is a BddNode and b is a BddTerm or vice versa - in the first case, “your” #equals() will be called, in the second case the default implementation.
However, second, you’ll “accidentally” get symmetric behavior in your code, because your #equals()/#hashCode() doesn’t change the semantics of the default implementations at all - they operate on object identity. Which means that
The purpose of my equals is just to prevent the contents from being examined when equals is called.
As I understand my code, only objects which are actually the same object will be equal. Otherwise the objects are not equal despite their having the same or different content. My application has a factor function used for creating Bdd objects which promise to always return identical objects when the content is the same. So Bdd(1,BddTrue,BddFalse) == Bdd(1,BddTrue,BddFalse) because Bdd will return the same pointer each time.
Is there a better way? I thought about just defining equals and hashCode to call this.super, but I didn’t try it. This ordinarily (in non-scala OO systems) but scala write an equal method for you unless you provide one yourself. Right?
But am I sure that the HashMap internal code respects these semantics?
Here’s a very simplified example on how method invocation works:
class A {
override def equals(that: Any): Boolean = true
}
class B {
// program works the same even if below code line is commented out
override def equals(that: Any): Boolean = false
}
val a = new A
val b = new B
println(a.equals(b)) // prints: true
println(b.equals(a)) // prints: false
// upcasting to 'Object" doesn't change anything in the output
// because 'equals' method is non-static
// so the same method implementation will be invoked
val o1: Object = a
val o2: Object = b
println(o1.equals(o2)) // prints: true
println(o2.equals(o1)) // prints: false
equals is a method just like any other and follows the same rules. You don’t get automatic symmetry for any custom method implementation, so why equals should automatically get one?
== operator in Scala delegates to equals after checking for nulls. == operator in Java is equivalent to eq method in Scala. Default equals is equivalent to eq (except that equals can throw NullPointerException).
But then I won’t get pattern matching either. My applications uses pattern matching heavily on BddNode. Perhaps I want to avoid the case class, but instead write an unapply method?
So the method which is called is always computed according to the runtime class of the value to the left of the dot. However, this is not the case for the rest of the method arguments. In CLOS the same rules apply to all the arguments, even the first (the object to the left of the dot, as there is no left-of-the-dot in CLOS).
class X {
def m(x:X):Int = 1
}
class Y extends X {
override def m(x:X):Int = 2
def m(y:Y):Int = 3
}
val x:X = new X
val y:Y = new Y
val z:X = new Y
List(
List(x.m(x), // 1
x.m(y), // 1
x.m(z)), // 1
List(
y.m(x), // 2
y.m(y), // 3
y.m(z)), // 2, in CLOS this would be 3
List(
z.m(x), // 2
z.m(y), // 2 -- I fail to understand why this returns 2, while y.m(y) returns 3
z.m(z))) // 2
If I change this to a non-case class but with an unapply method, then can I be sure that equivalence checking within hash lookups NEVER traverses the tree of objects? Something like hash.get((bdd1,bdd2)) or hash((bdd1,bdd2)) = bdd3, I never want that to descend the BddNode object stores in the instance variables of bdd1 and bdd2. And if I create a set Set(bdd1,bdd2) then the equivalence check never looks at the instance variables of bdd1 and bdd2 ?
If I am the only one calling ==, then I can of course just call eq instead. But the point of providing a protocol for the class is that other function (that I didn’t write) may call ==.
I think this is perfectly fine if you want case-class advantaces (pattern-matching, avoid new() etc.) but want “reference-equalty”. I’d write equals() as follows tho:
override def equals(that: Any): Boolean = this eq that
Both the mutable and immutable HashMap in 2.12 and earlier perform equality checks once you hit the right hash bucket. The completely new implementations in 2.13 always compare the hashcodes first. This should lower the number of equality checks.