Structural Subtyping == Reduced Compile-Time Coupling

Although I've been wrapping my mind around structural subtyping in Java for quite some time now, there is one argument in favor of structural typing that didn't get the attention it deserves: it is much easier to develop code against an API that relies on structural types due to reduced compile-time dependencies.

As always I'll illustrate my point with an example. We'll start with the standard (non-structural) approach.

(Side note: In the very first lecture at the Programming-Languages class I took, my teacher, Prof. Ron Pinter, made the point that a programming language is an excellent device for formally expressing ideas: "Instead of battling a natural language hopelessly trying to get the precise meaning, just write the thing in a PL and your intention will be clear". I think this is a very good advice)

Suppose someone has finally written the huge algorithm that realizes the overwhelmingly complicated logic of the bridge-keeper from Monty Python and the Holly Grail. The algorithm is encapsulated within the Bridgekeeper class whose protocol relies on the Knight interface.

public interface Knight {
  public String answerMe(String question);
}

class Birdgekeeper {
  public boolean canCross(Knight k) { ... }
}

My friend Graham developed an AbstractKnight class which provides some services common to all knights:

public abstract class AbstractKnight 
    implements Knight {
  private final String name;

  protected AbstractKnight(String name_) {
    name = name_;
  } 

  protected abstract String nonNameQuestion(String q);

  public String answerMe(String question) {
    if("What is your name?".equals(question))
      return name;
    String answer = nonNameQuestion(question);    
    if(answer == null)
      answer = "I don't know that";
    return answer;
  }
}

If I want to develop a concrete subclass of AbstractKnight (Lancelot or Robin come to mind), Graham needs to send me two jars (or two source file packages):

1. Graham.jar - Providing the definition of the AbstractKnight class
2. Bridgekeeper.jar - Providing the definition of the Knight interface

Yes. Without Bridgekeeper.jar I will not be able to compile my Lancelot class, despite the fact that Lancelot is only indirectly coupled with Knight. When you compile a class the compiler requires all its ancestors to be present.

Graham is therefore forced to distribute Bridgekeeper.jar to allow other programmers to subclass his AbstractKnight class. This often leads to proliferation of download-able packages (with/without dependencies) which is a constant headache for open source developers. Of course, if you choose to download the full package (the one that does include the dependencies) you are then risking having several different version of the same library on your machine, which - again - leads to headaches.

With structural subtyping things are much simpler:

// library: Bridgekeeper.jar
public struct Knight {
  public String answerMe(String question);
}

...  // everything else remains the same


// library: Graham.jar
public abstract class AbstractKnight  { 
  // "implements Knight" removed
 
  ...  // everything else remains the same
  
}

With this approach, AbstractKnight has no compile-time dependency on Knight. Thus, you can compile your Lancelot class even if Bridgekeeper.jar is not present on your classpath:

public class Lancelot extends AbstractKnight  {

  public Lancelot() { 
    super("Sir Lancelot of Camelot"); 
  } 

  protected String nonNameQuestion(String q) {
    if("What is your quest?".equals(q))
      return "To seek the Holy Grail";
    if("What is your favorite color?".equals(q))
      return "Blue";
    return null;
  }
}

Update 1: OK. I couldn't resist the temptation. Here it is, in its full glory, scene 35:

Bulletprooof - II

Following my previous post, here is another example for bulletproofing your API (again, I am not saying that you should, just wanted to provide a few concrete examples).

Simple (non bulletproof) version:

public class Resource {
  public enum Mode { READ, WRITE }
  public Resource(String fileName) { ... }
  public void open(Mode m, boolean autoFlush) { ... }
  public char read() { ... }
  public void write(char c) { ... }
}

Legal usage:

Resource res = ... ;
res.open(Resource.Mode.READ, false);
char c = res.read();

Illegal usage:

Resource res = ... ;
res.open(Resource.Mode.READ, false);
res.write('a'); // Runtime error: 
                // Resource was opened for READ

The bulletproofing technique remains the same: introduce new classes to make it possible for the compiler to distinguish between the different variants.

public class Readable {
  public char read() { ... }
}

public class Writable {
  public void write(char c) { ... }
}

public class Resource {
  public Resource(String fileName) { ... }
  public Readable openRead(boolean autoFlush) { ... }
  public Writable openWrite(boolean autoFlush) { ... }
}

Bulletproof

This post waited a long-long time to be written. The motivation to finally do it came from a discussion I had with Andreas Brink at OOPSLA'08. We both felt that TDD made us more productive. In the pre-TDD era we were always trying to make our API bullet-proof, i.e.: that it will be really difficult to write code that will fail at run time. With TDD this is not such a big concern. You write simpler code (which is much faster than writing bulletproof code) and you rely on the tests suite to keep from you doing mistakes.

I don't want to get into the can-tests-really-prevent-bugs debate. My intention here is just to show what I mean by a bulletproof design. Here is a simple (non-bulletproof) Flight class:

public class Flight {
  private final int numSeats;
  private final Set<Traveler> travelers 
    = new HashSet<Traveler>();

  public Flight(int numSeats_) {
    numSeats = numSeats_;
  }

  public void book(Traveler t) {
    if(travelers.size() >= numSeats)
      throw new RuntimeException("Fully booked");
    travelers.add(t);
  }

  public void unbook(Traveler t) { 
    if(!travelers.contains(t))
      throw new IllegalArgumentException("t=" + t);
    travelers.remove(t);
  }
}

public class Traveler {
   ...
}

The predicament lies in the Flight.unbook() method. If we pass the wrong argument, this method will fail:

Filght f1 = ...;
Filght f2 = ...;
Traveler t = ...;
f1.book(t);
f2.unbook(t); // Illegal argument error!

And now, let's see the bulletproof approach. The trick is to use static type checking - sometimes in conjunction with encapsulation - to make it impossible to issue an incorrect unbook() request:

public class Flight {

  private final int numSeats;
  private final Set<Traveler> travelers 
    = new HashSet<Traveler>();

  public Flight(int numSeats_) {
    numSeats = numSeats_;
  }

  public Traveler book(Traveler t) {
    if(travelers.size() >= numSeats)
      throw new RuntimeException("Fully booked");
    travelers.add(t);
    return new Reservation(t);
  }

  public class Reservation {
    public final Traveler traveler;
    public Reservation(Traveler t) { 
      traveler = t;
    }

    public void unbook() {
      travelers.remove(traveler);
    }
  }
}

With this design unbook requests (now issued through a Reservation object) cannot fail:

Filght f1 = ...;
Filght f2 = ...;
Traveler t = ...;
Flight.Reservation r = f1.book(t);
r.unbook(); // Always safe!

Three Kinds of Bugs

I tend to classify bugs into one of these three groups:

• Laziness
• Lack of Creativity
• Betrayal

The running example that I'll use here is a method that finds the largest value in a list of integers.

Laziness

  public static Integer maxA(List<integer> list) {
     int result = Integer.MAX_VALUE;
     for(int i = 0; i < result)
        if(result < list.get(i))
           result = list.get(i);
     return result;
  }

Do you see the problem? result's initial value is completely wrong. Such bugs often happen when the programmer copies the code of a similar method but neglects to make all the neccssary adjustments.

Why is this group called "laziness"? That's because this method will not pass even the simplest test: assertEquals(new Integer(30), maxA(Arrays.asList(10, 20, 30))); In other words, if you weren't lazy you could have caught the bug with the very first test you threw at it. Actually, you don't even need a test case: just run it once on any piece of input and you'll find the bug. BTW, this "run it once" practice shows why read-eval-print shells are useful. Too bad they are common only in the arena of dynamically typed languages.

Lack of Creativity

  public static Integer maxB(List<integer> list) {
     int result = 0;
     for(int i = 0; i < result)
        if(result < list.get(i))
           result = list.get(i);
     return result;
  }

maxB() is clearly better than maxA(). It will not fail at the very first attempt. In fact, as long as your input contains only positive integers this method will seem fine. You need a certain degree of creativity to devise an input that will manifest the bug, such as: assertEquals(new Integer(-4), maxB(Arrays.asList(-4)));

Betrayal

  public static Integer maxC(List<integer> list) {
     int result = list.get(0);
     for(int i = 1; i < result)
        if(result < list.get(i))
           result = list.get(i);
     return result;
  }

This version works quite well. It will pass both of the aforementioned tests. The bug here is much more subtle. With Betrayal bugs the root of the problem is a disagreement between two methods.

Such a disagreement may occur if the method that builds the list (which is then fed into maxC()) will also generate empty lists. This situation contradicts maxC()'s assumption that the list is non empty. In a sense, maxC() is betrayed by its own program.

It is very tempting to say something like: "Well, maxC() has a clear precondition. This precondition is not met, so the bug is in the caller". However tempting, this view is overly simplistic. Suppose the program method that the code that calls maxC(), looks like this:

public class Driver {
  public int n;

  public List<Integer> listBuilder() { 
    List<Integer> newList = new ArrayList<Integer>
    for(int i = 0; i < n; ++i)
      newList.add(i);
    return newList;
  }

  public Integer m() {
    return maxC(listBuilder());
  }
}

The contract of listBuilder() says that it should return a list with the integers 0..n-1 (inclusive). In particular, if n is zero the returned list should be empty. The contract of m() says that it should apply maxC() on the list created by listBuilder(). The contract of maxC() says that it should return the highest number from a non empty list.

So, every method is doing exactly what it is supposed to be doing, and yet the net effect is a runtime error. Despite the fact that maxC() is the one being betrayed we may decide that the correct way to fix the program is to change maxC() rather than listBuilder(). This is typically the case when we realize that our program needs to handle a wider range of inputs.


This type of bug cannot be detected by a testing maxC() in isolation. We need a higher level test, to expose the bug.

One final comment: Earlier I defined m()'s contract to be: "inbvoke maxC() on whetever listBuilder() returns" . I guess that some people may claim that this is not a valid contract for a method since it specifies implementation details rather than taking a black-box approach for specifying m()'s behavior. I am sorry to disappoint you guys, but such an approach will only work with simple programs. If your program is doing complicated computations you will not be able to express the contract (purely) in terms of input- vs. output- data. The input data will undergo such complicated transformations that you will have to use some form of abstraction, which is exactly what I did. Given that abstraction is the process of ignoring some details, there is an inherent lose of precision when one tries to formulate the contracts of elaborate computations.

Reuse: A goal or a by-product?

I found this gem in the comp.object mailing list:

"Re-use is a happy side-effect of good designs. The primary goal is managing dependencies between modules, by making them more pluggable"

I like this statement because it captures an important insight that is too often overlooked due to us following common conceptions without questioning them. Reuse is not a goal. Reuse is a trait of source code that usually goes hand in hand with good programs. This does not mean that a high degree of reuse is a must for achieving high quality code.

If your program's complexity is well controlled then you're in a good position regardless of the amount of duplicated code therein. Conversely, having no duplications does not mean that you successfully tamed complexity. One reason for that is that highly-reused modules are also highly-coupled: even a tiny a modification in a (highly reused) module is likely to break a good fraction of its many clients. This is sheer mathematics: the more clients you have, the greater the chances that you break something.

Degradation of locality is also a risk: when you reuse (for instance by means of inheritance), the various pieces making up your class are actually defined outside the scope the class. This will make it difficult to understand what the class is doing because it's actual definition is scattered across several locations.

These ideas are not new. They were already expressed by Riachard Gabriel in his book "Patterns of Software".

Gabriel coined the term "compression" to describe reuse within a program. In the very first chapter, "Reuse vs. Compression", he says:

"Compression is a little dangerous because it requires the programmer to understand a fair amount about the context from which compressed code will take its meaning.

...The primary feature for easy maintenance is locality: Locality is that characteristic of source code that enables a programmer to understand that source by looking at only a small portion of it. Compressed code doesn’t have this property, unless you are using a very fancy programming environment."

Java Scripting

Last week I devoted the time for going through Steve Yegge's talk on Rhino (Rhino = "...an open-source implementation of JavaScript written entirely in Java"). In particular, I liked the idea that thanks to the scripting support of Java6, Javascript is "...finally becoming the scripting language for Java".

Naturally, I wanted to see how easy it is to make Java scriptable. So I sat down and played with the Java scripting engine and my answer is this: very easy!

package rhinodemo;

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;

public class Factorial {
 private final int n;
 private int result = 1;
 
 public Factorial(int n) {
   this.n = n;
 }

 public int getResult() {
   return result;
 }

 public Factorial compute() {
   if(n >= 1) {
     Factorial that = new Factorial(n-1);
     that.compute();
     result = n * that.getResult();
   }
 
   return this;
 }

 public static void main(String[] args)
   throws Exception {
   ScriptEngineManager mgr
     = new ScriptEngineManager();
   ScriptEngine engine
     = mgr.getEngineByName("JavaScript");

   engine.eval(
   "importClass(Packages.rhinodemo.Factorial);" +
   "importClass(Packages.junit.framework.Assert);" +
   "" +
   "Assert.assertEquals(24, " +
   "  new Factorial(4).compute().getResult());" +
   "println('-ok-')");
 }
}

What we have here is a Java class, Factorial, that computes n!. The protocol of this class is deliberately cumbersome: I wanted to have a real class with a real constructor and two meaningful methods, and not just one static method. The main() method executes Javascript code that tests the Factorial class using JUnit's Assert class (you need to have junit.jar on your classpath).

Even this short program demonstrates a few key points:

• Accessing Java libraries from Javascript
  
• Passing Javascript objects to Java code
• Creating instances of Java classes from within Javascript
  

An Arithemetic Expressions Solver in 64 Lines

A few months ago Martin Fowler published a post titled Parser Fear. As always (well, almost always) I found myself agreeing with his main point: people are often intimidated by parsers.

Fowler's post advocates the use parser generators (in particular, ANTLR). I'd like to go a little further and make the following points:

• Writing a recursive decent parser is much easier than you think.
• You don't need a parser generator to overcome your parser fear.
• Get over the trauma induced by the compiler class you took.

Actually I only need to show a good argument for point #1. The other two points naturally follow.
I will make my case by using the well established technique of proof by example: A 64 lines Java class that evaluates arithmetic expressions supporting +, -, *, /, negation, and parenthesis.

public class CompactSolver {
 private String input;

 public CompactSolver(String input_) {
   input = input_.trim();
 }

 private char peek(int offset) {
   return offset >= input.length() ? '\0' :
     input.charAt(offset);
 }

 private boolean consumeIf(char c) {
   if (peek(0) != c)
     return false;
   consume(1);
   return true;
 }

 private String consume(int numChars) {
   if (numChars == 0)
     throw new RuntimeException("syntax error");
   String result = input.substring(0, numChars);
   input = input.substring(numChars).trim();
   return result;
 }

 public double eval() {
   double lhs = mul();
   if (consumeIf('+'))
     return lhs + eval();
   else if (consumeIf('-'))
     return lhs - eval();
   return lhs;
 }

 private double mul() {
   double lhs = unary();
   if (consumeIf('*'))
     return lhs * mul();
   else if (consumeIf('/'))
     return lhs / mul();
   return lhs;
 }

 private double unary() {
   if (consumeIf('-'))
     return -unary();

   if (consumeIf('(')) {
     double result = eval();
     if (!consumeIf(')'))
       throw new RuntimeException("Missing ')'");
     return result;
   }
  
   return literal();
 }

 private double literal() {
   for (int i = 0; true; ++i)
     if (!Character.isDigit(peek(i)))
       return Integer.parseInt(consume(i));
 }
}

Update 1: Changed the precedence of the (unary) negation operator (Many thanks to Orlando).

Examining Command-Query-Separation

I have already written at least once on the command-query-separation (CQS) principle. Today, I would like to show a class which benefits from NOT following this principle.

So, here is a snippet from a class that parses and evaluates arithmetic expressions.

public class Solver1 {
   private String input;

   public Solver1(String input_) {
      input = input_.trim();
   }

   private boolean consumeIf(String s) {
      if (!input.startsWith(s))
         return false;
      input = input.substring(1).trim();
      return true;
   }

   public double eval() {
      double lhs = multiplication();
      if (consumeIf("+"))
         return lhs + eval();
      else if (consumeIf("-"))
         return lhs - eval();
      return lhs;
   }

   private double multiplication() {
      double lhs = unary();
      if (consumeIf("*"))
         return lhs * multiplication();
      else if (consumeIf("/"))
         return lhs / multiplication();
      return lhs;
   }
   ...
}

Looking at consumeIf() we note that it violates the CQS principle. This method is a query (it computes and returns a result - either true of false) which is also a command (it changes the value of a field). Let's see the looks of the code after decomposing consumeIf() into two methods: a query and a command:

public class Solver2 {
   private String input;

   public Solver2(String input_) {
      input = input_.trim();
   }

   private boolean nextIs(String s) {
      return input.startsWith(s);
   }
   
   private void move(int numChars) {
      input = input.substring(numChars).trim();
   }
   
   public double eval() {
      double lhs = multiplication();
      if (nextIs("+")) {
         move(1);
         return lhs + eval();
      }
      else if (nextIs("-")) {
         move(1);
         return lhs - eval();
      }
      return lhs;
   }

   private double multiplication() {
      double lhs = unary();
      if (nextIs("*")) {
         move(1);
         return lhs * multiplication();
      }
      else if (nextIs("/")) {
         move(1);
         return lhs / multiplication();
      }
      return lhs;
   }
   ...
}

There is a 25% increase in code size, 42 vs. 33 lines of code, but I will put this aside because I think that #LOC is not a very good estimate of code quality. (Actually, I don't believe in any code quality metric)

Nonetheless there is a another issue which is much more significant: in the second program we have this recurring idiom of calling nextIs() and then calling move(), as in: if (nextIs("/")) { move(1); ... }. These two calls are mutually dependent: the parameter passed to move() must be the length of the string passed to nextIs(). This idiom is error-prone as the programmer may accidentally change one of the parameters while leaving the other intact.

This shows that arbitrarily applying the CQS principle may yield bad results. A good programmer should be aware of that and should make judgment calls rather than blindly following principles. In fact, this happens a lot with many other programming principles. They are usually much closer to guidelines (and therefore require judgment) than to absolute rules. I think that Lars summarized it pretty well: "I generally dislike '-isms' because they set up rules that people try to apply without understanding the preconditions that need to be met."

Evaluating a Language

I decided to try Ruby. Don't get me wrong. I had already written a few things in Ruby. But today I was a bit more serious about it.

My motivation was to get some more insight regarding the never-ending static vs. dynamic typing debate. So, this morning I wrote a Java program (the standard arithmetic expressions parser/evaluator) and then I tried to write it in Ruby. Unlike previous occasions I actually took the time and searched the web for a real Ruby IDE. After a few disappointments (#1, #2 and #3 - it was on my Windows machine, maybe they work better w/ Linux) I settled on NetBeans.

My Ruby skills felt somewhat rusty so I decided to warm-up by TDDing an easy kata. After the third or fourth test case I noticed a very funny thing: Ruby was much easier than I remembered. Suddenly I didn't feel so rusty. Thinking about it I realized that this was not due to the language but rather due to the IDE. In all past attempts I was too lazy to install an IDE so my Ruby experience was always through a text editor and a command prompt. Once I had an IDE at my disposal (and I mean a serious IDE: completion, go to declaration, templates, the works) the learning curve has flattened.

For example, I wasn't falling back to Java's curly braces as much as I used to in the past, because pairs of def/end keywords were being injected by the IDE as I was typing; Fixing the (highly non-friendly) syntax error: "unexpected $end, expecting kEND" was much less painful since I had this nice red thingy on the editor's side bar; Determining whether an expression such as assert_equal(0, x.get_result) can also be written as assert_equal 0, x.get_result was a breeze.

The morale here is two fold. First, there is the trivial issue of WYSIWYG tools making it possible even for a complete beginner to get things done. Second, you can't really evaluate a language without an IDE. When you evaluate a language you are unconsciously comparing it against your programming experience with your current, favorite, language. For sure, you have all the tooling support you need for your current language, so unless you get some tooling support for the new language, the comparison is unfair. Once you set up an IDE for the new language your programming experience will (dramatically) improve.

I guess there is a deep psychological issue here. We are humans. We always try to do as little work as possible. When we try a new language we tend to download the least amount of tools. We rationalize it by saying something like: "well I am a seasoned programmer. I don't need an IDE/Debugger/whatever to get the feeling of the language". This is a risky -- and usually a plain wrong -- assumption.

Whiteoak 2.1

This week, Whiteoak 2.1 has been officially made public. This release includes a command line compiler, an Eclipse plugin, a new mailing list and a top-notch, AJAX-powered web-site.

Whiteoak in a nutshell

The Whiteoak programming language is an extension to Java that introduces a new degree of flexibility into the language.

Motivating the development of Whiteoak is the understanding that
due to extensive use of libraries, components and external data sources, the developer has limited control on how the objects in her program are created. The developer then spends a great deal of her time just gluing together systems of objects using all sorts of fancy patterns.

Whiteoak addresses this predicament by the introduction of structural types, thereby allowing abstraction over objects. This mechanism nicely complements the well known inheritance mechanism which allows abstraction over classes. Specifically, Whiteoak's key features are:

• Structural subtyping (AKA: duck typing, structural conformance)
• Introduction of default, override-able, method implementations to existing objects
• Virtual fields and constructors
• Anonymous types
• Type expressions, with mixin-like or traits-like semantics