Structural Versus Physical Comparsions in OCaml

Sideway view of a turtle on a log, looking up.

The comparison operators in OCaml are polymorphic.  That is, you can use them for various data types.  Because OCaml is a typed language, like any other operator, you have to apply them to the same type.  E.g., comparing a float to an int will give you a type error.

OCaml can perform two types of comparisons: structural and physical.  Structural comparison operators are (as in the Pervasives): equal (=), less than (<), less than or equal to (<=), greater than (>), greater than or equal to (>=), not equal (<>), and the functions compare, min, and max x y.  Physical comparison operators are physical equality (==) and negation of equality (!=).

Structural qualities concern the current contents of the arguments only.  Structural comparisons are therefore more straight forward: compare the contents of the arguments.  Comparing functions structurally is challenging though.  Applying structural comparison operators to functions will raise Invalid_argument.

Physical qualities concern the physical property.  Two things are physically equal if and only if changing one changes the other.  The distinction between structural and physical comparisons is especially important for mutable data types.  On non-mutable data types, the results are implementation dependent.  But physical equality implies structural equality.

Equality of Mutable Data Types

In the last post I explained lexical scoping in OCaml, which relates to non-mutable data types.  In imperative programming, mutable data types are more common.  Recall that values or functions (of non-mutable data types) are shadowed by their new definitions, but they are not overwritten.  Mutable data types behave differently.  When you assign a new value to them, their old value is overwritten by the new.  Only the new value is relevant.  Examples of mutable data types include ref cells and arrays.  A data type that is non-mutable by default can be declared mutable.  E.g., record or object fields.

When a variable is defined to be equal to another variable with a value of a mutable data type, mutating the variable changes the content of the original variable.  E.g.:

utop # let x = ref 2;;      (* The variable x is defined to be a ref cell of int with content of 2. *)
val x : int ref = {contents = 2}

utop # let y = x;;      (* The variable y is defined as physically equal to the variable x. *)
val y : int ref = {contents = 2}

utop # y := 4;;      (* The content of the ref cell of y now has the content of 4. *)
- : unit = ()

utop # x;;      (* The content of variable x now also has the content of 4, because x and y are physically equal. *)
- : int ref = {contents = 4}

utop # x = y;;      (* x is structurally equivalent to y because they have the same content. *)
- : bool = true

utop # x == y;;      (* x is physically equivalent to y because changing one changes the other. *)
- : bool = true

utop # let z = ref 4;;      (* z is defined to be a ref cell of int with content of 4. *)
val z : int ref = {contents = 4}

utop # x = z;;      (* z is structurally equivalent to z because they have the same content. *)
- : bool = true

utop # x == z;;      (* z is not physically equivalent. *)
- : bool = false

One should distinguish mutating the value of a ref cell from defining a variable.  E.g.:

utop # let x = ref 2;;      
val x : int ref = {contents = 2}

utop # let y = x;;      
val y : int ref = {contents = 2}

utop # let y = ref 4;;      (*  The variable y is defined to be a ref cell of int with content of 4.  The old definition of y is shadowed. *)
val y : int ref = {contents = 4}

utop # x;;      (* The variable x is not changed because y is no longer having the same content as x with the new definition. *)
- : int ref = {contents = 2}

utop # x == y;;      (* x is not physically equivalent to y because changing one does not change the other. *)
- : bool = false

utop # x = y;;      (* x is not structurally equivalent to y because they have different contents. *)  
- : bool = false

I hope I’ve made the distinction clear for you!  Feel free to comment or contact me if you have any questions!

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.