34

In OCaml, we have two kinds of equity comparisons:

x = y and x == y,

So what's exact the difference between them?

Is that x = y in ocaml just like x.equals(y) in Java?

and x == y just like x == y (comparing the address) in Java?

4 Answers 4

35

I don't know exactly how x.equals(y) works in Java. If it does a "deep" comparison, then the analogy is pretty close. One thing to be careful of is that physical equality is a slippery concept in OCaml (and functional languages in general). The compiler and runtime system are going to move values around, and may merge and unmerge pure (non-mutable) values at will. So you should only use == if you really know what you're doing. At some level, it requires familiarity with the implementation (which is something to avoid unless necessary).

The specific guarantees that OCaml makes for == are weak. Mutable values compare as physically equal in the way you would expect (i.e., if mutating one of the two will actually mutate the other also). But for non-mutable values, the only guarantee is that values that compare physically equal (==) will also compare as equal (=). Note that the converse is not true, as sepp2k points out for floating values.

In essence, what the language spec is telling you for non-mutable values is that you can use == as a quick check to decide if two non-mutable values are equal (=). If they compare physically equal, they are equal value-wise. If they don't compare physically equal, you don't know if they're equal value-wise. You still have to use = to decide.

5
  • 1
    Java is object-oriented, so I expect that the difference between the equals method there and OCaml's (=) is that the equals method works for structured types such as maps, sets, hashtables. The polymorphic type of OCaml's (=) makes promises that its implementation cannot fulfil. Nov 28, 2012 at 15:52
  • Agreed, the OCaml (=) operator is trickier than it seems, prone to raising an exception or looping. In my own code I've had good luck with it, and have rarely needed to write my own equality comparison. Nov 28, 2012 at 15:59
  • 4
    I would add a strong caveat about the recommendation to use == for a fast path, since the runtime already does that in most cases where it is semantically correct. I think the only case where it really makes sense to do it manually is on non-flat data structures for which you happen to know that no float, no function, and no abstract tag can ever occur inside, but the compiler does not. Jan 6, 2015 at 14:43
  • 1
    You wrote: "for non-mutable values, the only guarantee is that values that compare physically equal (==) will also compare as equal (=)."; that's not fully correct, as if you define let f x = x, than f == f evals to true :bool but f = f raises Invalid_argument exception. The correct statement is: "for non-mutable values v1 and v2, the only guarantee is that v1 == v2 implies compare v1 v2 = 0."
    – pifu
    Jun 10, 2020 at 21:58
  • 1
    This says something interesting about compare, mostly, I think. In essence, it has a special case when comparing a function to itself. (Note that compare f g throws that same invalid argument exception.) At any rate you have a good point. Some values can't be compared using = that can be compared with ==. Jun 10, 2020 at 22:10
23

Edit: this answer delves into details of the inner working of OCaml, based on the Obj module. That knowledge isn't meant to be used without extra care (let me emphasis on that very important point once more: don't use it for your program, but only if you wish to experiment with the OCaml runtime). That information is also available, albeit perhaps in a more understandable form in the O'Reilly book on OCaml, available online (pretty good book, though a bit dated now).

The = operator is checking structural equality, whereas == only checks physical equality.

Equality checking is based on the way values are allocated and stored within memory. A runtime value in OCaml may roughly fit into 2 different categories : either boxed or unboxed. The former means that the value is reachable in memory through an indirection, and the later means that the value is directly accessible.

Since int (int31 on 32 bit systems, or int63 on 64 bit systems) are unboxed values, both operators are behaving the same with them. A few other types or values, whose runtime implementations are actually int, will also see both operators behaving the same with them, like unit (), the empty list [], constants in algebraic datatypes and polymorphic variants, etc.

Once you start playing with more complex values involving structures, like lists, arrays, tuples, records (the C struct equivalent), the difference between these two operators emerges: values within structures will be boxed, unless they can be runtime represented as native ints (1). This necessity arises from how the runtime system must handle values, and manage memory efficiently. Structured values are allocated when constructed from other values, which may be themselves structured values, in which case references are used (since they are boxed).

Because of allocations, it is very unlikely that two values instantiated at different points of a program could be physically equal, although they'd be structurally equal. Each of the fields, or inner elements within the values could be identical, even up to physical identity, but if these two values are built dynamically, then they would end up using different spaces in memory, and thus be physically different, but structurally equal.

The runtime tries to avoid unecessary allocations though: for instance, if you have a function returning always the same value (in other words, if the function is constant), either simple or structured, that function will always return the same physical value (ie, the same data in memory), so that testing for physical equality the result of two invocations of that function will be successful.

One way to observe when the physical operator will actually return true is to use the Obj.is_block function on its runtime representation (That is to say, the result of Obj.repr on it). This function simply tells whether its parameter runtime representation is boxed.

A more contrived way is to use the following function:

let phy x : int = Obj.magic (Obj.repr x);;

This function will return an int which is the actual value of the pointer to the value bound to x in memory, if this value is boxed. If you try it on a int literal, you will get the exact same value! That's because int are unboxed (ie. the value is stored directly in memory, not through a reference).

Now that we know that boxed values are actually "referenced" values, we can deduce that these values can be modified, even though the language says that they are immutable.

consider for instance the reference type:

# type 'a ref = {mutable contents : 'a };;

We could define an immutable ref like this:

# type 'a imm = {i : 'a };;
type 'a imm = {i : 'a; }

And then use the Obj.magic function to coerce one type into the other, because structurally, these types will be reduced to the same runtime representation.

For instance:

# let x = { i = 1 };;
- : val x : int imm = { i = 1 }
# let y : int ref = Obj.magic x;;
- : val y : int ref = { contents = 1 }
# y := 2;;
- : unit = ()
# x
- : int imm = { i = 2 }

There are a few exceptions to this:

  • if values are objects, then even seemingly structurally identical values will return false on structural comparison

    # let o1 = object end;;
    val o1 : < > = <obj>
    # let o2 = object end;;
    val o2 : < > = <obj>
    # o1 = o2;;
    - :  bool = false
    # o1 = o1;;
    - :  bool = true
    

    here we see that = reverts to physical equivalence.

  • If values are functions, you cannot compare them structurally, but physical comparison works as intended.

  • lazy values may or may not be structurally comparable, depending on whether they have been forced or not (respectively).

    # let l1 = lazy (40 + 2);;
    val l1 : lazy_t = <lazy>
    # let l2 = lazy (40 + 2);;
    val l2 : lazy_t = <lazy>
    # l1 = l2;;
    Exception: Invalid_argument "equal: functional value".
    # Lazy.force l1;;
    - :  int = 42
    # Lazy.force l2;;
    - :  int = 42
    # l1 = l2;;
    - :  bool = true 
    
  • module or record values are also comparable if they don't contain any functional value.

In general, I guess that it is safe to say that values which are related to functions, or may hold functions inside are not comparable with =, but may be compared with ==.

You should obviously be very cautious with all this: relying on the implementation details of the runtime is incorrect (Note: I jokingly used the word evil in my initial version of that answer, but changed it by fear of it being taken too seriously). As you aptly pointed out in comments, the behaviour of the javascript implementation is different for floats (structurally equivalent in javascript, but not in the reference implementation, and what about the java one?).


(1) If I recall correctly, floats are also unboxed when stored in arrays to avoid a double indirection, but they become boxed once extracted, so you shouldn't see a difference in behaviour with boxed values.

5
  • 5
    let phy x : int = Obj.magic (Obj.repr x);; will return an int”: This is a common misconception, but it doesn't. It returns a value with type int and whose run-time representation is unchanged, and therefore does not have its lowest bit set. If you apply a function that reads this bit (such as hash or, in some circumstances, (=)), then the function will behave as it does for allocated values. If you apply an arithmetic int function that works without reading the lowest bit, you will get an int correlated to the address of the initial allocated value… Nov 28, 2012 at 15:59
  • 4
    If you apply an arithmetic int function that assumes the lowest bit of its argument is set, you may get an invalid pointer, and the GC will crash shortly afterwards. An example of the first kind of arithmetic function would be (lor) 0, and of the second kind typically succ. Nov 28, 2012 at 16:01
  • 3
    And the above two comments are only examples of why it is an utterly bad idea to mention the module Obj in an answer to an OCaml question asked by a beginner. Nov 28, 2012 at 16:05
  • @PascalCuoq of course, it's an abuse of language to say that it returns an int, since both Obj.magic and Obj.repr are actually the identity function. In the runtime world, these functions return the value itself casted as an int, which may or may not be a pointer. As you nicely point it out, I should have certainly clarified the aim of my answer, a mistake easily fixed. Thanks for your input!
    – didierc
    Nov 29, 2012 at 0:32
  • 1
    It looks more reasonable with the warning at the top. And, good link. Nov 29, 2012 at 0:54
11

Is that x = y in ocaml just like x.equals(y) in Java?

and x == y just like x == y (comparing the address) in Java?

Yes, that's it. Except that in OCaml you can use = on every kind of value, whereas in Java you can't use equals on primitive types. Another difference is that floating point numbers in OCaml are reference types, so you shouldn't compare them using == (not that it's generally a good idea to compare floating point numbers directly for equality anyway).

So in summary, you basically should always be using = to compare any kind of values.

3
  • So in summary, you basically should always be using = to compare any kind of values., so why == existing in ocaml then? When to use == exactly? Nov 27, 2012 at 18:14
  • 1
    My take on this question is in my answer: you can safely use it as a quick check for equality of non-mutable values, as long as you use the full (=) check when the answer is false. It also makes sense for mutable values. Nov 27, 2012 at 20:03
  • 1
    Just a small issue: not every kind of values are structurally comparable, functional values may not.
    – didierc
    Jan 6, 2015 at 14:10
2

according to http://rigaux.org/language-study/syntax-across-languages-per-language/OCaml.html, == checks for shallow equality, and = checks for deep equality

3
  • 5
    This is not a good summary of the difference, in my opinion. For example comparing two floating constants with == will always return false. Seems neither shallow nor deep to me. Nov 27, 2012 at 18:12
  • 1
    @JeffreyScofield it is interesting that if you try 1.0 == 1.0 in try.ocamlpro.com, it gives true all the time Nov 27, 2012 at 18:39
  • 3
    That is interesting! It gives false in 4.00.0 OCaml toplevel (just tested). It really is impelementation dependent I guess you could say. Nov 27, 2012 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.