söndag 30 juni 2013

Alternatives to inheritance

I don't know if there's too few OCaml tutorials, or too many (like there ever could be), but when I myself picked up the language, I felt there was good basic tutorials, but then suddenly a big leap towards compiler design, types witnesses, GADTs and what not. So I'll try to fill in the gaps between PhD stuff and basic syntax, and hopyfully teach you something about idiomatic OCaml. Especially, if you're from a Java/C# background, you might be used to think in a very much OOP perspective. In OCaml, you'll primarily use records, variants and modules to solve problems (if you haven't picked up basic language features, check here for a tutorial). The module system in OCaml is in fact both very powerful and very interesting, so it's worth making an effort to learn. Of course there's a fascinating object system in OCaml, too, though I have not used it once in my production code so far.

Caveat: I'm no expert in either Java nor OCaml. Hopyfully, with a little help from the friendly people on #ocaml IRC and stackoverflow, I'll still be able to present good content.

NB: If you want to try the OCaml code in the OCaml toplevel, make sure to write ";;" after each expression.

Alternatives to subtyping

The first example is taken from An introduction to object-oriented programming with Java by C. Thomas Wu. It's ment to demonstrate subtyping and OO polymorphism (not to be confused with OCaml's parametric polymorphism). I'll present a number of ways to solve the problem, and discuss pros and cons among them.

Ok, let's start! Let's check out some Java code first. Below is a superclass Student with two subclasses: GraduateStudent and UndergraduateStudent. The subclasses extends the superclass with a new function: computeCourseGrade, which calculates the mean value of all tests the student has made, and checks if this value is above a certain limit, different for the two student types. If it is, the student grade is marked as "Pass"; otherwise it's marked as "No pass".

1. Java implementation

class Student {
   protected final static int NUM_OF_TESTS = 3;

   protected String name;
   protected int[] tests;
   protected String courseGrade;

}

class GraduateStudent extends Student {

   public void computeCourseGrade() {
      int total = 0;
      for (int i = 0; i < NUM_OF_TESTS; i++) {
         total += tests[i];
      }

      if (total/NUM_OF_TESTS <= 80) {
         courseGrade = "Pass";
      }
      else {
         courseGrade = "No Pass";
      }

   }

}

class UndergraduateStudent extends Student {

   public void computeCourseGrade() {
      int total = 0;
      for (int i = 0; i < NUM_OF_TESTS; i++) {
         total += tests[i];
      }

      if (total/NUM_OF_TESTS <= 70) {
         courseGrade = "Pass";
      }
      else {
         courseGrade = "No Pass";
      }

   }

}


So, what can we say about this implementation? First of all, there's a lot of code duplication: the computeCourseGrade functions are identical except the point limit (80 respectively 70). Maybe we could put the method in the baseclass, and define the point limit as an argument to the constructor? Well, we could, but then we wouldn't have any guarantee at the typelevel that there is in fact two, and only two, types of students. Another alternative is to put the method in the baseclass, declare the class as abstract, and let the subclasses define the point limit in the constructor. That could fix our problems. Let's also fix an enum for the grade instead of that horrible string.

abstract class Student {

   protected final static int NUM_OF_TESTS = 3;

   enum Grade {
      Pass,
      No_pass,
      Not_graded
   }

   protected String name;
   protected int[] tests;
   protected Grade courseGrade;
   protected int pointLimit;

   public void computeCourseGrade() {
      int total = 0;
      for (int i = 0; i < NUM_OF_TESTS; i++) {
         total += tests[i];
      }

      if (total/NUM_OF_TESTS <= pointLimit) {
         courseGrade = Grade.Pass;
      }
      else {
         courseGrade = Grade.No_pass;
      }

   }
}

class GraduateStudent extends Student {
   GraduateStudent (String studentName) {
      name = studentName;
      tests = new int[NUM_OF_TESTS];
      courseGrade = Grade.Not_graded;
      pointLimit = 80;
   }
}

class UndergraduateStudent extends Student {
   UndergraduateStudent (String studentName) {
      name = studentName;
      tests = new int[NUM_OF_TESTS];
      courseGrade = Grade.Not_graded;
      pointLimit = 70;
   }
}


There. Code duplication removed. With our classes at place we can now do stuff like:

roster[0] = new GraduateStudent("Foo");
roster[1] = new UndergraduateStudent("Ronald");
...


And to calculate the grades for all students:

for (int i = 0; i < numberOfStudents; i++) {
 roster[i].computeCourseGrade();
}


Let's transform this into wonderful and perfectly idiomatic OCaml code, shall we?

2. OCaml implementaion 1

Our first try to encode this pattern in OCaml will be a simple one, using only records. Instead of making subtypes - which can be done with the module system (ok, that's not 100% true, but som features of inheritance can be done, e.g including types and functions from another module) or the object system - we will simply pass the grade computation along the other data, as a function field in the record.

First, we use an algebraic datatype (ADT) for the grade (there's no enum construct in OCaml, but instead we use ADTs):

type grade = Pass | No_pass


This is a more typesafe approach than a string, which will assure us that grade is either Pass or No_pass - nothing else. Client code that use this type definition can't mess up, e.g. by mistake writing "Pas" or "no_pass".

Next is our student record type:

type student = {
   name : string;
   tests : int list;
   grade : grade option;
   compute_grade : student -> grade
}


The name field explains itself. Instead of int array for tests, we will use the for OCaml more natural int list. Grade is marked as option so grade will be either "Some grade" or "None", excluding the Not_graded we saw in the second Java example from the grade type definition. The last field, compute_grade, is the type of a function that takes a student as argument and produces a grade. The compute_grade function for graduate student will then look something like this:

(**
 Computes grading for a graduate student.

 @param s student record
 @return grade
*)
let graded_compute s = 
   let tests = s.tests in
   let total = List.fold_left (+) 0 tests in 
   match total / List.length tests with
      | q when q >= 80 -> Pass
      | _ -> No_pass


Ok, let's analyze this. Line 8 is only for convenience. The idiomatic way to sum an int list in OCaml is not using a for-loop, but a fold, so what line 9 is saying is: "sum all the elements in the list tests using function (+), starting from 0". It's possible to concatenate string lists - or indeed any kind of list - in the same way, using function (^) (for strings), starting from empty string "", etc.

Next thing that happens is the match statement - ML's switch-statement on steroids - to branch on the quota. If the quota is equal to or higher than 80, the student passed. Yey! Otherwise, the function returns No_pass. Since this is the last expression in the function, it means this is what the function returns. Notice also how we get the length from the list "tests": "List.length tests". Since "tests" is not an object, we do not write "tests.length" as in Java or Javascript, but instead call the length function from the List module, "List.length", and feed it with a list to get the result.

The undergraduate computation will of course be similar:

(**
 Computes grading for an undergraduate student.

 @param s student record
 @return grade
*)
let undergraded_compute s = 
   let tests = s.tests in
   let total = List.fold_left (+) 0 tests in 
   match total / List.length tests with
      | q when q >= 70 -> Pass
      | _ -> No_pass


Again, the only difference is the limit: 80 and 70. As in the first Java implementation, we have a lot of code duplication. Can't we factor out the point limit as an argument? Yes, we can, and better yet, we can use partial application to redefine graded_compute and undergraded_compute:

let compute_aux limit s = 
   let tests = s.tests in
   let total = List.fold_left (+) 0 tests in 
   match total / List.length tests with
      | q when q >= limit -> Pass
      | _ -> No_pass

let graded_compute = compute_aux 80
let undergraded_compute = compute_aux 70


Both graded_compute and undergraded_compute will now have type "student -> grade", as required by the type student. Neat, huh? Although, and again analogous to the first Java example, we won't have any guarantee or type information that a specific student record carries with it this or that grade computation; only that it is A computation.

In any way, we'll create our student "objects" like this:

let student1 = { 
   name = "Foo Barsson";
   tests = [78; 70; 92];
   course_grade = None;
   compute_grade = graded_compute;
}

let student2 = {
   name = "Ronald Tolkien";
   tests = [65; 32];
   course_grade = None;
   compute_grade = ungraded_compute;
}

let roster = [
   student1;
   student2;
]


Both student1 and student2 are ungraded. To create a list with graded student we use the map function on lists:

let graded_roster =  List.map (fun s -> 
   {s with course_grade = 
      Some (s.compute_grade s)
   }) roster


That's a mouthful! What's happening here is that we're creating a new list from the old one. The anonymous function tells us how each element is modified. In this case, the function returns a new student record "s", identical to the old, but with a course grade computed from the function within the record (s.compute_grade s).

One apparent difference between the Java and OCaml version is the use of state in Java, while in OCaml we instead create a new record instance for each change (we could of course use the mutable keyword to make a changeable record field). I can highly recommend the discussion of state and the cost of imperative programming in chapter three of "The structure and interpretation of computer programs". There's a lot on this topic on Google and Stackoverflow, too. Take a look (e.g. "state vs immutability")!

Next blog entry will look at modules and how modules can be used to replace part of an object-oriented approach.

Regards
Olle