INF 441 / TD 5 : Objects and Classes

Kaustuv Chaudhuri

Introduction

In this TD you will gain some experience programming with objects and classes in OCaml. Remember that OCaml’s view of objects and classes is very different from other object-oriented programming languages that you may be familiar with such as Java or C++. If you have such a background, you may have to fight any misconceptions you have about how objects and classes should behave.

Warmup: Objects and Row-Polymorphism

In OCaml, records have a fixed field structure known at compile time, and hence it is not possible to write a function such as the following:

let get_field_x thing = thing.x

The OCaml type-checker tries to infer the type for thing, but all it can determine is that it has a field named x (of unknown type). Unless it already knows of a record with such a field name, it will raise an error.

Characters 30-31:
  let get_field_x thing = thing.x;;
                                ^
Error: Unbound record field x

To get this kind of flexibility in OCaml, we have to resort to objects.

# let call_method_x thing = thing#x;;
val call_method_x : < x : 'a; .. > -> 'a = <fun>

The way to interpret this is that call_method_x can be invoked on any object-value that has a method called x, which is then called. The .. in the type of the argument means that there can be other methods besides x.

Write a function called area that calls the #width and #height methods on its argument and returns their product. What is the most general type of area?
Construct a value of type < width : int; height : int > and call area on it.

Write the following functions:

val rectangle : int -> int -> < width : int; height : int >
val square : int -> < width : int; height : int >
val triangle : int -> int -> < width : int; height : int >

Write the following function:

val growable : int -> int ->
  < width : int; height : int;
    grow_width : int -> unit;
    grow_height : int -> unit >

The arguments are the initial width and height.

Suppose we change the definition of area as follows:
```
let area (thing : < width : int; height : int >) = ...
```
Can you use this definition to compute the area of a growable? If not, why not?
From what you learned in the previous item, can you create a list containing a rectangle, a square, and a growable?

Of course the simple-minded area function that just multiplies the width and height overapproximates the actual area of the shape. Let us now flip things around and make the area an essential part of the shape.

type shape = < area : float >

Complete the definition of the following functions.

let triangle base height : < area : float > = ...

let square side : < area : float; side : float > = ...

let circle radius : < area : float; radius : float > = ...

Make a list of three shapes: a triangle, a square, and a circle. Using List.map, List.fold_left, etc. or with a recursive function you write yourself, compute the sum of the areas of the shapes in the list.

Class Types, Classes, and Inheritance

The syntax of object types in OCaml tends to get very cumbersome very quickly, and so the object notation is also allowed to be reused at the type level by means of class types

class type shape = object
  method area : float
end

Now we can just say shape instead of < area : float >. Moreover, we can use this to make subtypes as well; in particular, #shape stands for the row-polymorphic type < area : float; .. >.

Define the function larger that takes two #shapes and returns the one that has the bigger area. Concretely, complete the following definition.
```
let larger : #shape -> #shape -> #shape =
  fun sh1 sh2 -> ...
```
What type does OCaml assign to larger? Can you explain why it comes up with that type?

Accompanying class types is the notion of classes which allow us to use inheritance, which is one of the defining characteristics of object-oriented code. Consider the following class definition of rectangle.

class rectangle (width, height : float * float) (x, y : float * float) = object (self)
  val mutable x = x
  val mutable y = y

  (* a reference point, e.g., the bottom left corner *)
  method key = (x, y)

  method area = width *. height

  (* return true if (px, py) is part of the rectangle *)
  method contains (px, py) =
    x <= px && px <= x +. width &&
    y <= py && py <= y +. height
end

Create a new rectangle instance of width \(10\) and height \(4\) with its reference point at the origin. You will need to use the new keyword.
Create the class square by inheritance from rectangle. That is, complete the following implementation
```
class square (side : float) (x, y : float * float) = object
   inherit rectangle ...
end
```
You should not have to write any other code besides the inherit line.
Create a circle class that takes a radius and a reference point as argument. Make the reference point its center.
Define the following shape by suitable multiple inheritance from rectangle.
```
class box2 (w1, h1) (w2, h2) (x, y) = object (self)
  ...
end
```
Hint: each inherited superclass can be named using a declaration such as:
```
  inherit rectangle (w1, h1) (x, y) as left
```
Subsequently, you can use left#contains, left#area, etc. If you name the other superclass right, you can also use right#contains, right#area, etc. Then the methods of this combined shape are boolean or arithmetic combinations of the same methods on the superclasses.
(Optional) Define the following shape by suitable multiple inheritance from rectangle and circle.
```
class car w h r (x, y) = object (self)
  ...
end
```

Mixins and Self-Reference

Multiple inheritance can lead to a lot of confusion, but there is one use-case for multiple inheritance that is both practical and useful: mixins. A mixin is an abstract class, containing virtual values and methods that are seen as parameters, and it implements a given feature in terms of these parameters. Inheriting from the mixin class allows the features to be imported into any class that contains implementations of the virtual elements.

For example, the following is a mixin class that implements a ‘string’ representation of a shape.

class virtual describable name = object (self)
  val virtual mutable x : float
  val virtual mutable y : float
  method virtual area : float

  method describe =
    Printf.sprintf "Shape %S at (%f, %f), area %f"
      name x y self#area
end

Mix in the class describable to the shapes you have defined earlier by adding a suitable inherit declaration in their class definitions. Pick a suitable name for each shape. Create a few shapes and run their #describe method.
Create a mixin movable that adds methods #move_x and #move_y to the class for moving the entire shape along the \(x\)-axis or \(y\)-axis respectively. Mix it into all the shapes you have defined earlier.
Create a mixin randomized that adds a random fuzz in \([-1, 1]\) to the x and y coordinates on initialization. (To get a random float between 0 and x you can use Random.float x.) This means that you need to put the fuzzing code in the initializer for the mixin class. Recall that initializers are written using the initializer declaration in the classes. Create subclasses of rectangle, circle, etc. called fuzzed_rectangle, fuzzed_circle, etc. that mix in randomized.

Open Recursion

At this point you probably do not think that objects contribute much to OCaml. Indeed, most of the benefits of data encapsulation, code reuse, and information hiding are already achievable using the module system.

However, one area where objects shine is open recursion. You are already familiar with ordinary recursion using let rec such as:

let rec fib = function
  | 0 -> 0
  | 1 -> 1
  | n -> fib (n - 1) + fib (n - 2)

Imagine, however, if instead of calling fib recursively, the function were to take an extra argument (lets call it self) and make the recursive calls use self#fib instead.

# let open_fib self = function
    | 0 -> 0
    | 1 -> 1
    | n -> self#fib (n - 1) + self#fib (n - 2);;
val open_fib : < fib : int -> int; .. > -> int -> int = <fun>

This definition appears on the surface to be rather silly, but the indirection through self works wonders, because you can plug in whatever you want in its place. For instance, here is a version that adds a debug statement before every call to fib.

# let debug_fib =
    let dbg = object (self)
      method fib n =
        Printf.printf "Calling fib(%d)\n" n ;
        open_fib self n
    end in
    dbg#fib;;
val debug_fib : int -> int = <fun>

# debug_fib 4;;
Calling fib(4)
Calling fib(2)
Calling fib(0)
Calling fib(1)
Calling fib(3)
Calling fib(1)
Calling fib(2)
Calling fib(0)
Calling fib(1)
- : int = 3

Write a variant of debug_fib called pretty_debug_fib that not only prints the call but also indents it based on its call depth and also prints the returned value. That is, you should see output such as this:

# pretty_debug_fib 4;;
Calling fib(4)
  Calling fib(2)
    Calling fib(0)
     Returning 0
    Calling fib(1)
     Returning 1
   Returning 1
  Calling fib(3)
    Calling fib(1)
     Returning 1
    Calling fib(2)
      Calling fib(0)
       Returning 0
      Calling fib(1)
       Returning 1
     Returning 1
   Returning 2
 Returning 3
- : int = 3

This simple example of open recursion could have been achieved without the complexity of classes and object-oriented programming. To really see it shine, we have to move to a slightly more complex setting where we are performing operations on a complex tree-like family of algebraic datatypes.

For instance, here is a very tiny subset of the grammar of OCaml itself.

type ocaml_type =
  | Int
  | Bool
  | Arrow of ocaml_type * ocaml_type
  | Product of ocaml_type list

type ocaml_expr =
  | Const_int of int
  | Const_bool of bool
  | Variable of string
  | If of ocaml_expr * ocaml_expr * ocaml_expr
  | Fun of string * ocaml_type * ocaml_expr
  | Tuple of ocaml_expr list
  | Apply of ocaml_expr * ocaml_expr
  | Let_in of ocaml_decl * ocaml_expr

and ocaml_decl =
  | Var_decl of string * ocaml_type * ocaml_expr
  | Rec_decl of (string * ocaml_type * ocaml_expr) list

Suppose you want to go through a given expression and perform a few simplifications such as the following:

rewrite if true then e1 else e2 to e1
rewrite if false then e1 else e2 to e2

while leaving everything else that doesn’t fit this pattern untouched. This is pretty easy to write as a recursive function simplify_ifs : ocaml_expr -> ocaml_expr.

Now suppose you want to do another modification: changing occurrences of fun (x : t1 * t2) -> e to fun (x1 : t1) (x2 : t2) -> let x = (x1, x2) in e (also known as Currying). Once again this leaves most of the tree untouched except for this small change, and the function is easy enough to write by recursion.

However, you will notice that there is a considerable amount of duplicated code between the two operations above. Most of the time the functions do nothing of importance. Writing tedious boilerplate code is one of the most preventable sources of bugs.

Fortunately, open recursion gives us a way to avoid repeating the common parts of all such operations and instead focus on just the important parts.

Complete the implementation of the following class.
```
class ocaml_map = object (self)
  method for_type (ty : ocaml_type) : ocaml_type = ...
  method for_expr (ex : ocaml_expr) : ocaml_expr = ...
  method for_decl (dl : ocaml_decl) : ocaml_decl = ...
end
```
The methods in this class basically traverse their arguments fully recursively, but perform no significant computation; instead, they just recreate the argument in each case from its components. In other words, these methods are very elaborate “copy” methods.

Remember to use open recursion via self instead of making direct recursive calls.
Now create an object inheriting ocaml_map that performs the if true/if false simplification above.
```
let if_simplify = object (self)
  inherit ocaml_map as super
  ...
end
```
In this class, override the for_expr method of the superclass by writing a few cases to detect the two if patterns and rewrite them if so; if they are not detected, just continue with calling super#for_expr instead.
Similarly, make another object called curry that performs the second optimization mentioned above.

A more interesting case is that of a fold that threads an accumulator through the entire recursive computation. It can be used for all kinds of information retrieval.

Complete the implementation of the following class. The parameter is the type of the accumulator. In the default implementation in the class below, the accumulator is just passed along completely untouched.

class ['acc] ocaml_fold = object (self)
  method for_type (acc : 'acc) (ty : ocaml_type) : 'acc = ...
  method for_expr (acc : 'acc) (ex : ocaml_expr) : 'acc = ...
  method for_decl (acc : 'acc) (dl : ocaml_decl) : 'acc = ...
end

Using inheritance from the above class, write the following function that extracts all the free variables in an expression. Note that the free variables of an expression are all the variables that are not within the scope of a fun or let that declares that variable.
```
let ocaml_free_vars = object (self)
  inherit [string list] ocaml_fold as super
  ...
end;;
let free_vars_expr e = ocaml_free_vars#for_expr [] e;;
```