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.
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
Write a function called
area that calls the
#height methods on its argument and returns their product. What is the most general type of
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
square, and a
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.fold_left, etc. or with a recursive function you write yourself, compute the sum of the areas of the shapes in the list.
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
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
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
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
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#area, etc. If you name the other superclass
right, you can also use
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
class car w h r (x, y) = object (self) ... end
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
Create a mixin
movable that adds methods
#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
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
circle, etc. called
fuzzed_circle, etc. that mix in
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
# 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
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:
if true then e1 else e2to
if false then e1 else e2to
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
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
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;;