Chapter 12: Objects

Objects

What is OOP? #

Paradigm that groups computation and data within logical objects. It’s interesting how the OCaml folks set the vocabulary around this:

• object contains data within fields

• method functions can be invoked against the data within the object \(\implies\) “sending a message” to the object

  this “sending a message” part is interesting because it aligns with the opinion that OOP is intrinsically imperative, where the object is like an FSM. Sending messages to an object causes it to change state, possibly sending messages to other objects. Naturally, this is assuming the object’s state is allowed to be mutable.

• class: code definition behind an object

• constructor: builds the object

5 fundamental properties that makes OOP unique:

1. Abstraction

   Implementation details hidden within the object, external interface is the set of publicly accessible methods

2. Dynamic Lookup

   When sending a message to object, method to be executed is dynamically determined by the implementation of the object, not by some static property of the program. Therefore, different objects may react to the same message in different ways.

3. Subtyping

   If an object a has all the functionality of an object b, then we may use a in any context where b is expected.

4. Inheritance

   Definition of one object (class) can be used to produce a new kind of object (class). The new definition may override behaviour, share behaviour with parent.

5. Open recursion

   Methods within an object can invoke other methods within the same object using a special variable (self or this). Objects created from classes use dynamic lookup, allowing a method defined in one class to invoke methods defined in another class that inherits from the first.

OCaml Objects #

OCaml Object system is very surprising to OOP-folks:

Class System: Separation of Object and their types #

Typically, we’d expect the class name to be the type of objects created when we instantiate it, and the relationships between object types correlate to inheritance.

1. In OCaml, Classes are used to construct objects and support inheritance. However, Classes are not types. Objects have object types.

   If we want to use objects, we don’t need to use classes at all.

      (* ==== defining an object *)
      open Base;;
      let s = object
        val mutable v = [0; 2]
   
        method pop =
          match v with
          | hd :: tl ->
            v <- tl;
            Some hd
          | [] -> None
   
        method push hd =
          v <- hd :: v
      end;;
      (* val s : < pop : int option; push : int -> unit > = <obj> *)
   
      (* ==== Usage: *)
      s#pop;;
      (* - : int option = Some 0 *)
      s#push 4;;
      (* - : unit = () *)
      s#pop;;
      (* - : int option = Some 4 *)
   

   Some notes:

   1. object type is what is within the <...> which only contains the types of the methods
   2. fields are typically private, only modifiable from the functions that cause side-effects on their state.
   3. methods can have 0 params.
      • we don’t need to use the unit argument (unlike the equivalent functional version)
      • this is because method call is routed to a concrete object instance. so zero argument methods can be invoked directly by writing obj#method without parens. It’s really because of the dynamic dispatching pattern.

2. objects may be constructed by functions (without being placed within a class(?)).

      let stack init = object
        val mutable v = init
   
        method pop =
          match v with
          | hd :: tl ->
            v <- tl;
            Some hd
          | [] -> None
   
        method push hd =
          v <- hd :: v
      end;;
      (* val stack : 'a list -> < pop : 'a option; push : 'a -> unit > = <fun> *)
      let s = stack [3; 2; 1];;
      (* val s : < pop : int option; push : int -> unit > = <obj> *)
      s#pop;;
      (* - : int option = Some 3 *)
   

   NOTE:

   1. the function stack’s returned object now uses the polymorphic type 'a instead of the previous example where it was bound to int.

Object Polymorphism #

Similar to polymorphic variants, we can use methods without a typedef.

This means that the compiler will infer the object types automatically from the methods that are invoked on them. The type system complains if it sees incompatible uses of the same methods.

(* === 1: automatic inference *)
let area sq = sq#width * sq#width;;
(* val area : < width : int; .. > -> int = <fun> *)
let minimize sq : unit = sq#resize 1;;
(* val minimize : < resize : int -> unit; .. > -> unit = <fun> *)
let limit sq = if (area sq) > 100 then minimize sq;;
(* val limit : < resize : int -> unit; width : int; .. > -> unit = <fun> *)

(*== incompatibility is caught!!:==== *)
(*
  let toggle sq b : unit =
  if b then sq#resize `Fullscreen else minimize sq;;

(*
Line 2, characters 51-53:
Error: This expression has type < resize : [> `Fullscreen ] -> unit; .. >
       but an expression was expected of type < resize : int -> unit; .. >
       Types for method resize are incompatible
*)
*)

(* ==== 2: closing the object type *)
let area_closed (sq: < width : int >) = sq#width * sq#width;;
(* val area_closed : < width : int > -> int = <fun> *)

(* so if we define sq object type again, it's going to error out because it was closed earlier *)
let sq = object
  method width = 30
  method name = "sq"
end;;
(*
val sq : < name : string; width : int > = <obj>
area_closed sq;;
Line 1, characters 13-15:
Error: This expression has type < name : string; width : int >
       but an expression was expected of type < width : int >
       The second object type has no method name
       *)

Notes:

1. object types may be open or close:

   • open: more methods can be inferred still

     the .. (ellipsis) in the inferred object types indicate that there could be other unspecified methods that the object may have

     this is actually called an ellision \(\implies\) stands of “possibly more methods”

   • closed: no more inferring of other methods and such

     we can see how the object’s definition is extensible from the examples, we also see that we can close the object so that the object type is fixed.

Elisions are Polymorphic (row-polymorphism) #

An elided object type is polymorphic. SO if we try to write a type definition using it, then we get an “unbound type variable error” type square = < width : int; ..>;;

This kind of polymorphism is called row polymorphism and it uses row-variables (.. is a row-variable). OCaml’s polymorphic variant types also use row-polymorphism; close relationship between objects and polymorphic variants: “objects are to records what polymorphic variants are to ordinary variants”

So, an object with object type < pop: int option; ..> can be any object with a method pop : int option regardless of how it’s implemented. The dynamic dispatch handles the method invocation when we invoke that method.

let print_pop st = Option.iter ~f:(Stdio.printf "Popped: %d\n") st#pop;;
(* val print_pop : < pop : int option; .. > -> unit = <fun> *)

(* == works on the stack type defined above: *)
print_pop (stack [5;4;3;2;1]);;
(* Popped: 5 *)
(* - : unit = () *)

(* === consider a whole separate implementation for stack: *)
let array_stack l = object
  val stack = Stack.of_list l
  method pop = Stack.pop stack
end;;
(* val array_stack : 'a list -> < pop : 'a option > = <fun> *)

(* the print_pop function works the same: *)
print_pop (stack [5;4;3;2;1]);;
(* Popped: 5 *)
(* - : unit = () *)

Immutable Objects #

The view that OOP is intrinsically makes sense. Objects are like FSMs and message-passing is what allows us to changs FSM state.

However, this assumes that the objects are mutable.

We can make them immutable too:

let imm_stack init = object
  val v = init

  method pop =
    match v with
    | hd :: tl -> Some (hd, {< v = tl >})
    | [] -> None

  method push hd =
    {< v = hd :: v >} (* <== this is special syntax for shallow-copying an object and overriding a field within*)
end;;
(*
val imm_stack :
  'a list -> (< pop : ('a * 'b) option; push : 'a -> 'b > as 'b) = <fun>
  *)

NOTEs:

• Special syntax:

  uses a special syntax {<...>} to produce a copy of the current object (and the assignment is an override of the copied object). In so doing, we don’t cause any modifications to the existing object.

  Syntax rules:

  1. can only be used within a method body
  2. only values of fields may be updated
  3. method implmentations are fixed @ the time of object-creation, so they can’t be chagned dynamically.

When to use Objects #

RULE OF THUMB: The main value of objects is really the ability to use open recursion and inheritance which is more of part of the class system.

What are the alternative toolings at our disposal?

1. classes and objects

   Pros:

   1. no need type definitions
   2. good support for row-polymorphism
   3. benefits comes from the class system

      • inheritance

      • open recursion

        Open recursion allows interdependent parts of an object to be defined separately. This works because calls between the methods of an object are determined when the object is instantiated, a form of late binding. This makes it possible (and necessary) for one method to refer to other methods in the object without knowing statically how they will be implemented \(\implies\) open recursion

        This also means that some part of the code may have its implementation deferred and it will still work.

   Cons:

   1. syntax-heavy
   2. runtime costs, might as well use records

2. first-class modules + functors + data types

   pros:

   1. more expressive (can include types)

   2. very explicit

   cons:

   1. is early binded – can only parameterise module code so t hat part of it can be implemented later via a function / functor. This explicitness can be quite verbose.

Subtyping #

Central concept in OOP that governs when an object with type A can be used in an expression expecting object of type B.

Concretely, subtyping restricts when e :> t (coercion operator) can be applied. Coercion only works if type of e is a subtype of t

Width Subtyping for coercing objects #

Width subtyping means that an object type A is a subtype of B if A has all of the methods of B (and possibly more). A square is a subtype of shape because it implements all the methods of shape, which in the example below, is just area.

type shape = < area : float >;;
(* type shape = < area : float > *)

type square = < area : float; width : int >;;
(* type square = < area : float; width : int > *)
let square w = object
  method area = Float.of_int (w * w)
  method width = w
end;;
(* val square : int -> < area : float; width : int > = <fun> *)

(* === example of just assignment but NOT coercion (will error out) *)
(square 10 : shape);;
(*Line 1, characters 2-11:
Error: This expression has type < area : float; width : int >
       but an expression was expected of type shape
       The second object type has no method width
       *)

(square 10 :> shape);;
(* - : shape = <obj> *)

Depth Subtyping for coercing objects #

Depth subtyping allows us to coerce and object if its individual methods could be safely coerced. So object type < m: t1 > is a subtype of object type < m: t2 > if t1 is a subtype of t2.

Given the shape type as type shape = < area : float >;;,

In the example here, both coin and map have a method called shape which is a subtype of the shape type and so, both of them can be coerced into the object type <shape: shape> (NOTE: the method shape that returns the type shape):

• within coin: shape : < area : float; radius : int > and the type of this method is a subtype of the shape type.
• within map: shape : < area : float; width : int > and the type of this method is a subtype of the shape type.

type circle = < area : float; radius : int >;;
(* type circle = < area : float; radius : int > *)
let circle r = object
  method area = 3.14 *. (Float.of_int r) **. 2.0
  method radius = r
end;;
(* val circle : int -> < area : float; radius : int > = <fun> *)

(* ==== both of the types below have a shape method whose type is a subtype of the shape type. So they can both be coerced.*)
let coin = object
  method shape = circle 5
  method color = "silver"
end;;
(* val coin : < color : string; shape : < area : float; radius : int > > = <obj> *)

let map = object
  method shape = square 10
end;;
(* val map : < shape : < area : float; width : int > > = <obj> *)

(* === example of depth-subtyping coercion.  *)
type item = < shape : shape >;;
(* type item = < shape : shape > *)
let items = [ (coin :> item) ; (map :> item) ];;
(* val items : item list = [<obj>; <obj>] *)

Polymorphic Variant Subtyping #

We can coerce a polymorphic variant into a larger polymorphic variant type. A polymorphic variant type A is a subtype of B if the tags of A are subset of the tags of B. This is aligned to the use of structural subtyping that is used for polymorphic variants.

type num = [ `Int of int | `Float of float ];;
(* type num = [ `Float of float | `Int of int ] *)
type const = [ num | `String of string ];;
(* type const = [ `Float of float | `Int of int | `String of string ] *)
let n : num = `Int 3;;
(* val n : num = `Int 3 *)
let c : const = (n :> const);; (*<=== so the subtype here is type num and the supertype is type const. We can type-coerce num into const *)
(* val c : const = `Int 3 *)

• The compiler allows coercion because:

  • Every value of num can safely fit into const, since every tag of num (Int, Float) also exists in const.
  • const might allow more tags (String), but anywhere a const is required, a value of type num is guaranteed to match at least some of its cases– so it’s a valid, safe substitution.

• Key intuition:

  1. Subtype: The more specific type (with a smaller set of allowed tags) is the subtype.
     • Here: num allows only Int and Float.
  2. Supertype: The broader type (with a superset of supported tags) is the supertype.
     • Here: const allows Int, Float, and String.

Variance #

The classic variance forms in OOP but in the context of object types in OCaml.

Notes based on the code below:

1. immutability allows us to do the first type coercion from square list to shape list.

   so 'a list is covariant (in 'a)

   If it was mutable (e.g. square array) then we would have been able to store non-square shapes into what should be an array of squares. So, square array is NOT a subtype of shape array.

   so 'a array is invariant (only accepts its own type)

2. Finally for the contravariant example, consider a function with the type square -> string. We can’t use it with types wider than itself like shape -> string because if we get a circle we wouldn’t know what to do. However, we can use it with types narrower than itself.

   Similar argument applies to why a function with type shape -> string can be safely used with type square -> string

(* ==== 1: COVARIANCE: a square is a shape, so a square list can be type coerced into a shape list *)
let squares: square list = [ square 10; square 20 ];;
(* val squares : square list = [<obj>; <obj>] *)
let shapes: shape list = (squares :> shape list);; (* == relies on lists being immutable*)
(* val shapes : shape list = [<obj>; <obj>] *)

(* === 2: INVARIANT: 'a array is invariant  == this will error out.*)
let square_array: square array = [| square 10; square 20 |];;
(* val square_array : square array = [|<obj>; <obj>|] *)
let shape_array: shape array = (square_array :> shape array);;
(*
Line 1, characters 32-61:
Error: Type square array is not a subtype of shape array
       The second object type has no method width
*)

(* === 3: CONTRAVARIANT: *)
let shape_to_string: shape -> string =
  fun s -> Printf.sprintf "Shape(%F)" s#area;;
(* val shape_to_string : shape -> string = <fun> *)
let square_to_string: square -> string =
  (shape_to_string :> square -> string);;
(* val square_to_string : square -> string = <fun> *)

Variance Annotations #

The compiler can infer the variance of types. In some cases, we wish to explicitly annotate the type.

One such case is if there’s a signature that hides the type parameters of an immutable type.

In those cases we can manually annotate the variance to the type’s parameters in the signature:

• +: for covariance
• -: for contravariance

(* === the implementation of the Either type -- so the type may be inferred as covariant *)
module Either = struct
  type ('a, 'b) t =
    | Left of 'a
    | Right of 'b
  let left x = Left x
  let right x = Right x
end;;
(*
module Either :
  sig
    type ('a, 'b) t = Left of 'a | Right of 'b
    val left : 'a -> ('a, 'b) t
    val right : 'a -> ('b, 'a) t
  end
  *)

(* these usage will allow the type to be inferred as covariant *)
let left_square = Either.left (square 40);;
(*
val left_square : (< area : float; width : int >, 'a) Either.t =
  Either.Left <obj>
  *)
(left_square :> (shape,_) Either.t);; (* <=== we can type coerce to a supertype.*)
(* - : (shape, 'a) Either.t = Either.Left <obj> *)

(* === interface that hides the definition for others -- the type can't be known by consumers of this interface and so the variance will be inferred as invariant. *)
module Abs_either : sig
  type ('a, 'b) t
  val left: 'a -> ('a, 'b) t
  val right: 'b -> ('a, 'b) t
end = Either;;
(*
module Abs_either :
  sig
    type ('a, 'b) t
    val left : 'a -> ('a, 'b) t
    val right : 'b -> ('a, 'b) t
  end
  *)
(* -- so this will be inferred as invariant *)
(Abs_either.left (square 40) :> (shape, _) Abs_either.t);;
(*
Line 1, characters 2-29:
Error: This expression cannot be coerced to type (shape, 'b) Abs_either.t;
       it has type (< area : float; width : int >, 'a) Abs_either.t
       but is here used with type (shape, 'b) Abs_either.t
       Type < area : float; width : int > is not compatible with type
         shape = < area : float >
       The second object type has no method width
       *)


(* ========== USING VARIANCE ANNOTATIONS to the Type's params in the signature: *)
module Var_either : sig
  type (+'a, +'b) t
  val left: 'a -> ('a, 'b) t
  val right: 'b -> ('a, 'b) t
end = Either;;
(*
module Var_either :
  sig
    type (+'a, +'b) t
    val left : 'a -> ('a, 'b) t
    val right : 'b -> ('a, 'b) t
  end
  *)

(* -- type coercion works again. *)
(Var_either.left (square 40) :> (shape, _) Var_either.t);;
(* - : (shape, 'a) Var_either.t = <abstr> *)

We consider a more concrete variance example.

1. the problem we see is that the push method makes it such that the square stack and circle stack are not subtypes of shape stack.

   • in shape stack the push method takes an arbitrary shape.

     If we could actually coerce square stack to a shape stack then it means it’s possible to push an arbitrary shape onto the square stack and this would have been regarded as an error.

     In other words, < push: 'a -> unit; .. > is contravariant in 'a so < push: square -> unit; pop: square option> can’t be a subtype of < push: shape -> unit; pop: shape option>

   • the push method makes the stack object type contravariant in 'a

2. to make it work, we use a more precise type that indicates that we will not be using the push method. That’s how we get the type readonly_stack .

   • shape_stacks is ascribed a composite polymorphic type:

     what the total_area’s parameter type annotation means (let total_area (shape_stacks: shape stack list)):

     • a list of objects of type < pop: shape option >, where readonly_stack is parametrized by shape.

(* === 1. we applied the stack function to some squares and some circles:  *)
type 'a stack = < pop: 'a option; push: 'a -> unit >;;
(* type 'a stack = < pop : 'a option; push : 'a -> unit > *)
let square_stack: square stack = stack [square 30; square 10];;
(* val square_stack : square stack = <obj> *)
let circle_stack: circle stack = stack [circle 20; circle 40];;
(* val circle_stack : circle stack = <obj> *)

(* === 2: attempting to use a area accumulating function*)
let total_area (shape_stacks: shape stack list) =
  let stack_area acc st =
    let rec loop acc =
      match st#pop with
      | Some s -> loop (acc +. s#area)
      | None -> acc
    in
    loop acc
  in
List.fold ~init:0.0 ~f:stack_area shape_stacks;;
(* val total_area : shape stack list -> float = <fun> *)
(* === problem:
total_area [(square_stack :> shape stack); (circle_stack :> shape stack)];;
Line 1, characters 13-42:

Error: Type square stack = < pop : square option; push : square -> unit >
       is not a subtype of
         shape stack = < pop : shape option; push : shape -> unit >
       Type shape = < area : float > is not a subtype of
         square = < area : float; width : int >
       The first object type has no method width

(* === problem: the push function makes it such that the shape stack object type is contravariant in 'a
*)
*)

(* ==== 3: precise type to avoid the contravariance *)
type 'a readonly_stack = < pop : 'a option >;; (* === this is a polymorphic object type *)
(* type 'a readonly_stack = < pop : 'a option > *)
let total_area (shape_stacks: shape readonly_stack list) =
  let stack_area acc st =
    let rec loop acc =
      match st#pop with
      | Some s -> loop (acc +. s#area)
      | None -> acc
    in
    loop acc
  in
List.fold ~init:0.0 ~f:stack_area shape_stacks;;
(* val total_area : shape readonly_stack list -> float = <fun> *)
total_area [(square_stack :> shape readonly_stack); (circle_stack :>
shape readonly_stack)];;
(* - : float = 7280. *)

It should be pointed out that this typing works, and in the end, the type annotations are fairly minor. In most typed object-oriented languages, these coercions would simply not be possible. For example, in C++, a STL type list<T> is invariant in T, so it is simply not possible to use list<square> where list<shape> is expected (at least safely). The situation is similar in Java, although Java has an escape hatch that allows the program to fall back to dynamic typing. The situation in OCaml is much better: it works, it is statically checked, and the annotations are pretty simple.

Narrowing #

Narrowing is NOT allowed in OCaml.

So we can’t downcast a supertype to its subtype because:

1. technical reason: hard to implement it

2. design argument: narrowing violates abstraction

   For structurally type-systems like in OCaml, if we allowed narrowing, then we could effectively enumerate the methods in an object (e.g. To check whether an object obj has some method foo : int, one would attempt a coercion (obj :> < foo : int >).).

TODO: there’s an example here that I just skipped. It talks about how to handle some cases where one might wish for type narrowing to be possible and suggests using pattern matching amongst other patterns (and discusses its drawbacks).

Subtyping vs Row Polymorphism #

Subtyping and Row-polymorphism are 2 distinct mechanisms and they overlap a lot in the sense that both are mechanisms we can use to write functions that can be applied to objects of different types.

Some notes:

1. Row polymorphism may be preferred over subtyping because there’s no explicit coercions \(\implies\) perserves more type information

      (* ==== row-polymorphism example: *)
      let remove_large l =
      List.filter ~f:(fun s -> Float.(s#area <= 100.)) l;;
      (* val remove_large : (< area : float; .. > as 'a) list -> 'a list = <fun> *)
      (* --- so this method is still preserved *)
      let remove_large l =
      List.filter ~f:(fun s -> Float.(s#area <= 100.)) l;;
      (* val remove_large : (< area : float; .. > as 'a) list -> 'a list = <fun> *)
   
      (* ==== subtyping coercion example: *)
      (*
        Writing a similar function with a closed type and applying it using subtyping does not preserve the methods of the argument: the returned object is only known to have an area method:
        *)
      let remove_large (l: < area : float > list) =
      List.filter ~f:(fun s -> Float.(s#area <= 100.)) l;;
      (* val remove_large : < area : float > list -> < area : float > list = <fun> *)
      remove_large (squares :> < area : float > list );;
      (* - : < area : float > list = [<obj>; <obj>] *)
   

2. There are some cases where row polymorphism can’t be used.

   1. Can’t be used to place different types of objects in the same container (heterogeneous elements can’t be created using row-polymorphism).

            let hlist: < area: float; ..> list = [square 10; circle 30];;
            (*
            Line 1, characters 50-59:
            Error: This expression has type < area : float; radius : int >
                   but an expression was expected of type < area : float; width : int >
                   The second object type has no method radius
            *)
      

   2. Can’t be used to place different types of objects in the same reference:

            let shape_ref: < area: float; ..> ref = ref (square 40);;
            (*
            val shape_ref : < area : float; width : int > ref =
              {Base.Ref.contents = <obj>}
              *)
            shape_ref := circle 20;;
            (*
            Line 1, characters 14-23:
            Error: This expression has type < area : float; radius : int >
                   but an expression was expected of type < area : float; width : int >
                   The second object type has no method radius
                   *)
      

   In both cases, subtyping works:

      let hlist: shape list = [(square 10 :> shape); (circle 30 :> shape)];;
      (* val hlist : shape list = [<obj>; <obj>] *)
      let shape_ref: shape ref = ref (square 40 :> shape);;
      (* val shape_ref : shape ref = {Base.Ref.contents = <obj>} *)
      shape_ref := (circle 20 :> shape);;
      (* - : unit = () *)