A demo of Objects in Caml

This is a quick demo of the object-oriented features of Objective Caml. Demonstrated a language with type inference is often frustrating, since the better the inference works the fewer types need to be shown. In the following we always print types of programs but the types themselves type inference will only be explained, or rather sketched in section X typechecking.

Traditional programming style

Traditionally, data is distinguished from functions operating on it. Data are integers, characters,

let integer = 1;; 
val integer : int = 1

let character = 'a';; 
val character : char = 'a'
but also, concrete data-types, etc.

type stone =  Opal | Pearl | Diamond;;
type stone = | Opal | Pearl | Diamond

type 'a list_ = Cons of 'a * 'a list_ | Nil;;
type 'a list_ = | Cons of 'a * 'a list_ | Nil
Functions are either primitive, as

succ, pred;;  
- : (int -> int) * (int -> int) = <fun>, <fun>
or defined.

let print_integer n =  print_int n; print_char ' ';;
val print_integer : int -> unit = <fun>
A function grind that breaks stones into their constituents may also be defined using pattern matching.

let grind =  function
    Opal -> ['O'; 'p'; 'a'; 'l'; ' ']
  | Pearl -> ['P'; 'e'; 'a'; 'r'; 'l'; ' ' ]
  | Diamond -> [ 'D'; 'i'; 'a'; 'm'; 'o'; 'n'; 'd'; ' '];;
val grind : stone -> char list = <fun>
In this traditional view, computation is described by the application of some function to some data.

let print_stone x =
  List.iter print_char (grind x);;
val print_stone : stone -> unit = <fun>

print_stone Opal;;
Opal - : unit = ()

The object-oriented programming style

In the object oriented style, a piece of data is grouped with all the functions that may operate on that data in a structure called an object. Objects are built from classes. That is, classes abstract objects over the actual data they carry. For instance, here are two classes of integers and stones.

class integer n = object
  val value = n
  method zero = (value = 0)
  method successor = {< value = value + 1 >}
  method predecessor = {< value = min 0 (value-1) >}
  method print = print_integer value
end;;
class integer :
  int ->
  object ('a)
    val value : int
    method predecessor : 'a
    method print : unit
    method successor : 'a
    method zero : bool
  end

class stone c = object
  val matter = c
  method grind = grind matter
  method print = print_stone matter 
end;;
class stone :
  stone ->
  object val matter : stone method grind : char list method print : unit end
An object is created as an instance of a classes.

let thirteen = new integer 13;;
val thirteen : integer = <obj>

let stone = new stone Diamond;;
val stone : stone = <obj>
The computation is now described by message invocation.

thirteen # print; stone # print;; 
13 Diamond - : unit = ()
As shown above, several messages with the same name print may have different behaviors. This is made possible since the behavior to be performed is carried by the object that receives the message. It provides a new form of polymorphism, called polymorphic message invocation. The following function echo emphasizes the use of polymorphic message invocation.

let echo x = x # print; x # print;;
val echo : < print : 'a; .. > -> 'a = <fun>
This function can be applied to any object that has a print method, as integers or stones.

echo thirteen; echo stone;;
13 13 Diamond Diamond - : unit = ()
Polymorphic message invocation is an essential feature. A language that possesses this ability can already claim to have some object-oriented ``flavor''.

Inheritance

Another essential feature of object-oriented languages is some inheritance mechanism that allows to defined new classes from older ones. This is illustrated below by defining a new class of jewels from the previous class of stones, adding a value field and a method price.

class jewel c v = object
  inherit stone c as plain
  val value = v
  method price = 2 * value
  method print =
    plain # print;
    print_int value;
    print_string " carats"
end;;
class jewel :
  stone ->
  int ->
  object
    val matter : stone
    val value : int
    method grind : char list
    method price : int
    method print : unit
  end
Note that jewels are printed by first printing them as plain stones with no value (here as binds the jewel to the variable plain as if it were from the superclass stone), then its price is printed followed by the unit carats.

let solitaire = new jewel Diamond 13;;
val solitaire : jewel = <obj>

solitaire # print;;
Diamond 13 carats- : unit = ()

Recursion in objects

Since recursive functions play an important role in the traditional programming style, methods soon also need to be recursive. This uses the so call self-binding mechanism. That is, the ability to bind the object receiving the message (to the variable game in the example below) and recursively invoke several messages of the object. We illustrate this on the famous roulette war game. A roulette game has a state position that remembers the slot carrying the unique bullet in the barrel. It has a method roulette that randomly turns the barrel, a method shoot, and two methods i_play and you_play for each of the players. A player shoots at himself, dies if the shoot fires; otherwise he forces the other play to play in turn. Thus, each of the player recursively calls the other one to play until one dies.

class roulette () = object (game) 
  val mutable position = 0
  method roulette = position <- Random.int 8; game
  method shoot = position <- (position + 1) mod 8; position = 0
  method i_play = if game # shoot then "I die" else game # you_play
  method you_play = if game # shoot then "You die" else game # i_play
end;;
class roulette :
  unit ->
  object ('a)
    val mutable position : int
    method i_play : string
    method roulette : 'a
    method shoot : bool
    method you_play : string
  end
Let's play!

(new roulette ()) # i_play;;
- : string = "You die"
You died! Fortunately, this was a virtual game, so that you can have another chance...

(new roulette ()) # i_play;;
- : string = "You die"
Next time, do not forget to do the roulette before I start...

(new roulette ()) # roulette # i_play;;
- : string = "You die"

Late binding

The ability to send messages to self also provides late binding. That is, the recursive calls are not resolved when the class is defined (as they would by a ``let rec'' construction), but when objects of that class are actually created. This is illustrated in a specialization of the roulette game, when one player takes double risk. The implementation of the class roulette_2_for_1 inherits from the class roulette and redefines the method i_play to shoot twice (if not dead at the first shoot) before calling you_play.

class roulette_2_for_1 () = object (game)
  inherit roulette ()
  method me =
    if game#shoot or game#shoot then "I die" else game # you_play
end;;
class roulette_2_for_1 :
  unit ->
  object ('a)
    val mutable position : int
    method i_play : string
    method me : string
    method roulette : 'a
    method shoot : bool
    method you_play : string
  end

    
(new roulette_2_for_1 ()) # roulette # you_play;;
- : string = "You die"
It is important that the unchanged method you_play now calls the new method i_play so that I really take twice as much risk.

A new form of modularity

The traditional programming style allows to define more functions without code duplication, but any change in the data representation requires redefinition of all functions operating on the same data-type.

The object-oriented style allows both the addition of operations (vertical extension) and the modification of the data-representation (horizontal extension) to be performed in a modular way. We shall illustrate this flexibility on the well-known lisp structure of cells. As opposed to the implementation of stones, we choose a fine-grain object-orientation flavor for cells. A cell is defined as a module will two classes. The main class cons defines real cells. The other defines the ``empty'' cell nil. It is important here that both classes have the same interface. Thus we defined the methods head and tail for object of class nil as raising exceptions. This should not be thought as a way around type safety, since in traditional ML one would also raise an exception when trying to access the head of an empty list. The module structure is used for sake of readability and to avoid name clashes, since we will consider several version of cells below.

module Cell = struct
  class ['a, 'b] cons (h:'a) (t:'b) = object 
    val head = h
    val tail = t
    method null = false
    method car = head
    method cdr = tail
  end
  
  exception Null
  class ['a, 'b] nil () = object
    method null = true
    method car = (raise Null : 'a)
    method cdr = (raise Null : 'b)
  end
end;;
module Cell :
  sig
    class ['a, 'b] cons :
      'a ->
      'b ->
      object
        val head : 'a
        val tail : 'b
        method car : 'a
        method cdr : 'b
        method null : bool
      end
    exception Null
    class ['a, 'b] nil :
      unit -> object method car : 'a method cdr : 'b method null : bool end
  end
These cells are unconstrained. In particular, we can store completely unrelated data in the car and the cdr as in ML pairs or lisp cons cells.

new Cell.cons thirteen solitaire;;
- : (integer, jewel) Cell.cons = <obj>

Let us make a detour though this amusing example of alternating lists that have been proposed by the Java community (it seems to have been a very challenging one). To increase readability, we define the type abbreviation ('a, 'b) alt_list for a recursive list structure whose elements are alternatively of type 'a and 'b. Then we simply define a recursive alternating list.

type ('a,'b) alt_list = ('a, ('b, ('a, 'b) alt_list) Cell.cons) Cell.cons;;
type ('a, 'b) alt_list = ('a, ('b, ('a, 'b) alt_list) Cell.cons) Cell.cons

let x = ref (new Cell.nil() : ('a, 'b) alt_list) in
  x := new Cell.cons thirteen (new Cell.cons solitaire (!x)); !x;;
- : (integer, jewel) alt_list = <obj>
Of course, although we do not show it here, this pattern is fully compatible with inheritance. For instance, alternating lists could still be define after having added iteration to cells as shown below.

We recover traditional lists by enforcing cells to be of a recursive type. The following definition weakens the types but does not actually change the behavior.

module L = struct
  class ['a] cons h t = object (self : 'mytype)
    inherit ['a, 'mytype] Cell.cons h t
  end
  class ['a] nil () = object (self : 'mytype)
    inherit ['a, 'mytype] Cell.nil ()
  end
end;;
module L :
  sig
    class ['a] cons :
      'a ->
      'b ->
      object ('b)
        val head : 'a
        val tail : 'b
        method car : 'a
        method cdr : 'b
        method null : bool
      end
    class ['a] nil :
      unit ->
      object ('b) method car : 'a method cdr : 'b method null : bool end
  end

Adding functionality

In the object oriented style, we use inheritance to add new methods to classes. This can be done without redefining any old method. Moreover, using multiple inheritance, we first define several refinements independently and later provide different options by selecting different groups of refinements.

For instance, let us add the iteration to lists. The Iter module defines the iteration refinement for both cells and empty cells. It assumes two virtual methods car and cdr for the class cons, thus the class is declared virtual, since no instance can be taken until the class is combined with some other appropriate class providing the required methods.

module Iter = struct 
  class virtual ['a,'b] cons () = object (self)
    method virtual car : 'a
    method virtual cdr : 'b
    method iter f =
      (f self#car : unit); self#cdr#iter f; ()
  end
  class ['a] nil () = object 
    method iter (f : 'a -> unit) = ()
  end
end;; 
module Iter :
  sig
    class virtual ['a, 'b] cons :
      unit ->
      object
        constraint 'b = < iter : ('a -> unit) -> 'c; .. >
        method virtual car : 'a
        method virtual cdr : 'b
        method iter : ('a -> unit) -> unit
      end
    class ['a] nil : unit -> object method iter : ('a -> unit) -> unit end
  end
Lists with iteration are obtained by multiple inheritance.

class ['a] cons h t = object (self : 'mytype)
  inherit ['a] L.cons h t 
  inherit ['a, 'mytype] Iter.cons ()
end

class ['a] nil () = object
  inherit ['a] L.nil ()
  inherit ['a] Iter.nil()
end;;
class ['a] cons :
  'a ->
  'b ->
  object ('b)
    val head : 'a
    val tail : 'b
    method car : 'a
    method cdr : 'b
    method iter : ('a -> unit) -> unit
    method null : bool
  end
class ['a] nil :
  unit ->
  object ('b)
    method car : 'a
    method cdr : 'b
    method iter : ('a -> unit) -> unit
    method null : bool
  end
As a test, we build and print a list of prime numbers.

let primes =
  List.fold_right
    (new cons) [2;3;5;7;11;13] (new nil());;
val primes : int cons = <obj>

primes#iter print_integer;;
2 3 5 7 11 13 - : unit = ()

Adding a new constructor

This other direction consists in adding a new constructor to an already existing data-types. Assume for instance that lists are often concatenated, and less often read. To avoid the computation of concatenation in the traditional style, one could add a new constructor Append to lists, creating a new incompatible type of lists. Therefore, this would necessitate to redefine all list operations.

In the object-oriented style, it is sufficient to define a new class append that implements the behavior of the new constructor. The older constructors are compatible and therefore remains unchanged.

class ['a] append l r = object (self : 'mytype)
  val left = (l : 'mytype)
  val right = (r : 'mytype)
  method null = left # null && right # null
  method car =
    if left # null then right # car
    else (left # car : 'a)
  method cdr =
    if left # null then right # cdr
    else if left # cdr # null then right
    else {< left = left # cdr >}
  method iter (f : 'a -> unit) =
    (left#iter f; right#iter f : unit)
end;;
class ['a] append :
  'b ->
  'b ->
  object ('b)
    val left : 'b
    val right : 'b
    method car : 'a
    method cdr : 'b
    method iter : ('a -> unit) -> unit
    method null : bool
  end
We introduce an infix notation for append, and just write an arbitrary test

let (@@) = new append;;
val @@ : 'a append -> 'a append -> 'a append = <fun>

let double_primes =
  primes @@ (new nil() @@ new nil ()) @@ primes;;
val double_primes :
  < car : int; cdr : 'a; iter : (int -> unit) -> unit; null : bool > as 'a =
  <obj>

double_primes#iter print_integer;;
2 3 5 7 11 13 2 3 5 7 11 13 - : unit = ()

Typecheking

Typing is always a good thing. When programming with objects, this statement is reinforced by the complexity of recursive calls via late binding.

In Objective Caml, typechecking heavily relies on row variables. Row variables provide polymorphic messages. When typing messages, constraints on the existence of methods and their types are gathered in the type of the object.

let g x = if x # null then x # car else x # cdr;;
val g : < car : 'a; cdr : 'a; null : bool; .. > -> 'a = <fun>
Thus, the echo function defined above can be applied to stone but not to the list primes.

echo;;
- : < print : 'a; .. > -> 'a = <fun>

echo stone;;
Diamond Diamond - : unit = ()

echo primes;;
Characters 5-11:
This expression has type
  int cons =
    < car : int; cdr : int cons; iter : (int -> unit) -> unit; null : bool >
but is here used with type < print : 'a; .. >
Only the second object type has a method print

Subtyping

Explicitly typed languages often use subtyping polymorphism instead of parametric polymorphism to type messages. To illustrate subtyping, we must first turn off polymorphism artificially using a type constraint. The monomorphic echo function can be applied to stones but not to jewels anymore.

let monomorphic_echo (x : stone) = echo x;;
val monomorphic_echo : stone -> unit = <fun>

monomorphic_echo stone;;
Diamond Diamond - : unit = ()

monomorphic_echo solitaire;;
Characters 17-26:
This expression has type
  jewel = < grind : char list; price : int; print : unit >
but is here used with type stone = < grind : char list; print : unit >
Only the first object type has a method price
Ocaml also allows subtyping, but it must always be stated explicit.

let as_a_stone x =  (x :> stone);;
val as_a_stone : < grind : char list; print : unit; .. > -> stone = <fun>
Then, the monomorphic echo function can be applied to jewels by explicitly coercing them to stones, using a coercion function or a type annotation:

monomorphic_echo (as_a_stone solitaire);;
Diamond 13 caratsDiamond 13 carats- : unit = ()

monomorphic_echo (solitaire :> stone);;
Diamond 13 caratsDiamond 13 carats- : unit = ()

The type of self

Typing recursion is often hard to get right. Actually, since Ocaml uses parametric polymorphism instead of subtyping, all difficulties are avoided. We summarize all kinds of operations involving self and recursion in a demoniac class.

class demon () = object (it_self)
  val mutable genes = Random.int 9999999
  method identity = genes
  method self = it_self
  method clone = {< >}
  method reproduction = {< genes = genes + 1 >}
  method mutation = genes <- genes + Random.int 9999999
end;;
class demon :
  unit ->
  object ('a)
    val mutable genes : int
    method clone : 'a
    method identity : int
    method mutation : unit
    method reproduction : 'a
    method self : 'a
  end
A demoniac object has genes that memorize its identity. It has a method self that returns the object itself, a method clone that duplicates the object, and two method reproduction and mutation, that respectively returns a modified copied of the object and modifies the object itself. We type and check all this properties below:

let dolly = new demon();;
val dolly : demon = <obj>

dolly =  dolly # self;;
- : bool = true

dolly <> dolly # clone;;
- : bool = true

let id = dolly # identity in
  dolly # reproduction; id =  dolly # identity;;
- : bool = true

let id = dolly # identity in
  dolly # mutation; id <> dolly # identity;;
- : bool = true
The demon is not a useless abstraction. Indeed, every concrete class may hide a little demon in itself. For illustration, here are demoniac lists.

module D = struct 
  class ['a] cons h t = object
    inherit demon()
    inherit ['a] L.cons h t
  end
  
  class ['a] nil () = object
    inherit demon()
    inherit ['a] L.nil ()
  end
end;;
module D :
  sig
    class ['a] cons :
      'a ->
      'b ->
      object ('b)
        val mutable genes : int
        val head : 'a
        val tail : 'b
        method car : 'a
        method cdr : 'b
        method clone : 'b
        method identity : int
        method mutation : unit
        method null : bool
        method reproduction : 'b
        method self : 'b
      end
    class ['a] nil :
      unit ->
      object ('b)
        val mutable genes : int
        method car : 'a
        method cdr : 'b
        method clone : 'b
        method identity : int
        method mutation : unit
        method null : bool
        method reproduction : 'b
        method self : 'b
      end
  end
and some experimentation...

let experiment = new D.cons dolly (new D.nil());;
val experiment : demon D.cons = <obj>

experiment # self # reproduction # clone # self # car # identity;;
- : int = 8346501
Similarly, binary methods cause no difficulty in Ocaml. The prototype of binary methods

class compare () = object (self)
  method compare x = compare x self
end;;
class compare : unit -> object ('a) method compare : 'a -> int end
can indeed be added to almost any object

class jeweler c v = object 
  inherit jewel c v
  inherit compare ()
end;;
class jeweler :
  stone ->
  int ->
  object ('a)
    val matter : stone
    val value : int
    method compare : 'a -> int
    method grind : char list
    method price : int
    method print : unit
  end

Remaining problems

For completeness, we end this demo with a few examples that Ocaml cannot type yet in its current implementation.

Polymorphic methods

We have shown how to equipped lists with iterators. Of course, one would also want to equipped them with folding methods. This, however requires polymorphic methods, which Ocaml does not yet allow. Indeed, a methods are part of objects which are first class values, and thus are not allowed to be polymorphic. Fortunately, some recent result would allow to extend Ocaml with some form of first class polymorphism and define the following class

module P = struct
  class ['a] cons h t = object (self)
    inherit ['a,'h] L.cons h t
    method (fold : All 'b. ('a -> 'b -> 'b) -> 'b -> 'b) f x = 
      self#cdr#fold (f self#car)
  end

  class ['a] nil () = object
    inherit ('a) L.nil ()
    method (fold : All 'b. ('a -> 'b -> 'b) -> 'b -> 'b) f x = x
  end
end;;
Characters 98-99:
Syntax error

Hiding components

Fields of objects can be hidden at any time. Methods, however, can only be hidden if they have been declared private when first introduced. This guarantees that they have never been assumed visible in self. This is a limitation to modularity that we would like to remove.

Methods v.s. Modules

Because Ocaml has both a powerful module system and powerful object operations, one often has a choice of programming style. Traditionally, one would write a stack as a module.

module Stack = struct
  exception Empty
  let create () = ref []
  let push s x = s := x::!s
  let pop s = match !s with [] -> raise Empty | a::l' -> s := l'; a
  let clear s = s := []
  let length s = List.length !s
end;;            
module Stack :
  sig
    exception Empty
    val create : unit -> 'a list ref
    val push : 'a list ref -> 'a -> unit
    val pop : 'a list ref -> 'a
    val clear : 'a list ref -> unit
    val length : 'a list ref -> int
  end
Indeed, stacks can also be defined as a class.

module Stack' = struct 
  exception Empty
  class ['a] stack () = object
    val mutable l = ([] : 'a list)
    method push x = l <- x::l
    method pop = match l with [] -> raise Empty | a::l' -> l <- l'; a
    method clear = l <- []
    method length = List.length l
  end
end;;
module Stack' :
  sig
    exception Empty
    class ['a] stack :
      unit ->
      object
        val mutable l : 'a list
        method clear : unit
        method length : int
        method pop : 'a
        method push : 'a -> unit
      end
  end
The choice of one or the other is not always obvious, and is often a commitment to the whole style of the application. We would like to close the gap between the two programming styles.

In summary:

  1. Polymorphic methods could be added,

  2. Hiding methods should soon be possible,

  3. Modules and Objects can be seen as structures, but we do know yet how to unify the two different programming styles.