Saturday, April 26, 2008

Scala's Pattern Matching = Visitor Pattern on Steroids

Since I had my first adventure in Scala a month and a half ago, I've been delving more deeply into Scala and functional programming in general. One of the things I ran across is Pattern Matching. Apparently, it's a key-feature in functional programming languages because it facilitates definition of recursive functions in a way that maps closely to functions in lambda calculus.

Let's take Fibonacci for an example:

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

This is how you'd define it with Scala's Pattern Matching:

def f(n: Int) : Int = n match {
  case 0 => 0
  case 1 => 1
  case n => f(n-1) + f(n-2)
}

Here is another example of Pattern Matching that is a bit more advanced:

abstract class Expr
case class Num(n: Int) extends Expr
case class Sum(l: Expr, r: Expr) extends Expr
case class Prod(l: Expr, r: Expr) extends Expr

def evalExpr(e: Expr): Int = e match {
  case Num(n) => n
  case Sum(l, r) => evalExpr(l) + evalExpr(r)
  case Prod(l, r) => evalExpr(l) * evalExpr(r)
}

def printExpr(e: Expr) = e match {
  case Num(n) => print(" " + n + " ")
  case Sum(l, r) => printExpr(l); print("+"); printExpr(r)
  case Prod(l, r) => printExpr(l); print("x"); printExpr(r)
}

What we have above is an abstract class to represent math expressions, and three implementations to represent numbers, sum operation, and product operation.

For example, the math expression "1 + (2 x 3)" can be composed using the expression classes as follows:

var expr1 = new Sum(new Num(1), new Prod(new Num(2), new Num(3)))

The syntax may seem verbose, but Scala's operator overloading can simplify it. I won't go over that right now. Let's focus instead on pattern matching.

So, we have two functions to evaluate expressions and print expressions.

Here are examples of using them on expr1:
evalExpr(expr1) => 7
printExpr(expr1) outputs 1 + 2 x 3

Now, what does the above example remind you of in the Object-Oriented world?

You guessed it! The Visitor Design Pattern by the Gang of Four. At first glance, I thought pattern matching was heresy by the OO standards as it looks like the dreaded switch statement that often breaks the open/closed principle and causes maintenance hell. After pondering it for a while though, I changed my mind and decided to see pattern matching as its own separate thing, which happens to provide another way of accomplishing the goals of the Visitor Pattern.

Now in Java, how would this have been implemented with the Visitor Pattern?

abstract class Expr {
  public <T> T accept(ExprVisitor<T> visitor) {visitor.visit(this);}
}

class Num extends Expr {
  private int value;

  public Num(int value) {this.value = value;}

  public int getValue() {return value;}
}

abstract class BiCompositeExpr extends Expr {
  private Expr left;
  private Expr right;

  protected BiCompositeExpr(Expr left, Expr right) {
    this.left = left;
    this.right = right;
  }

  public Expr getLeft() {return left;}
  public Expr getRight() {return right;}
}

class Sum extends BiCompositeExpr {
  protected Sum(Expr left, Expr right) {super(left, right);}
}

class Prod extends BiCompositeExpr {
  protected Prod(Expr left, Expr right) {super(left, right);}
}

interface ExprVisitor<T> {
  T visit(Num num);
  T visit(Sum sum);
  T visit(Prod prod);
}

class EvalExpr implements ExprVisitor<Integer> {
  public Integer visit(Num num) {
    return num.getValue();
  }

  public Integer visit(Sum sum) {
    return sum.getLeft().accept(this) + sum.getRight().accept(this);
  }

  public Integer visit(Prod prod) {
    return prod.getLeft().accept(this) * prod.getRight().accept(this);
  }
}

class PrintExpr implements ExprVisitor<Void> {
  public Void visit(Num num) {
    print(" " + num.getValue() + " ");
    return null;
  }

  public Void visit(Sum sum) {
    sum.getLeft().accept(this); print("+"); sum.getRight().accept(this);
    return null;
  }

  public Void visit(Prod prod) {
    prod.getLeft().accept(this); print("*"); prod.getRight().accept(this);
    return null;
  }
}

As you can see, each case statement in the Scala example maps to a visit method in the Java example. So, another way of looking at the Visitor Pattern is that it's simply a special case of pattern matching, which matches only on the type of method parameters.

Of course, if we add a new expression type in Java, such as Div, we have to add a new visit method for that type in every visitor. Likewise, to handle Div in Scala, we would also have to add a new case statement in every Scala function that works with expressions. This is a famous trade-off for using the Visitor Pattern as it enables you to define new operations easily, but makes it difficult to add new types to visit.

Now, I am sure everyone noticed how the amount of code written with Scala's Pattern Matching was a tiny fraction of that written with Visitor Pattern in Java!!!

Why?
  • Scala's case classes provide a shortcut for creating classes with a constructor and getters, saving you from all the manual labor provided you just define the signature of the constructor
  • Scala's use of recursive functions instead of visitors accomplishes the same goals while saving you from creating all the boiler-plate code for the Visitor Pattern (e.g. Visitor superclass and double-dispatch accept method on expressions)
  • Scala's use of pattern matching with case classes and recursion allows you to evaluate values from expression objects without having to call getters or visitor accept methods, thus yielding a much more concise syntax
So as you can see; in a way, Scala's Pattern Matching is Visitor Pattern on steroids!!!

Friday, April 25, 2008

XOR vs Equality Operators (^ vs !=)

A while ago, I committed code to my client's code-base that reads like this:

public boolean isSomethingValid() {
  return !a ^ b;
}

At the end of the day, Nick Malnick came to me and mentioned that a discussion broke out in his room because "someone used an XOR!" I went to the room to see what the matter was, and apparently another programmer who encountered that statement rushed to others for help because he didn't know what to make of the ^ operator and didn't know it was even a part of the Java syntax.

As Nick and I were leaving home, we had a talk about it, and I realized that I could have achieved exactly the same effect by writing the following instead:

public boolean isSomethingValid() {
  return a == b;
}

In fact, we discovered the following equivalence relationships:

 a ^ b <=> a != b
!a ^ b <=> a == b

Given these relationships, we had further discussion about whether it's a good idea at all to use the XOR operator in our client's code-base given that the developers rarely ever use it and aren't accustomed to it.

So, again in the spirit of the past blog post If-Else vs Direct Return and Manuel's blog post If Then (If Then Else) Else (If Then Else), I'd like to know the public's opinion on the matter.

Would you use XOR or equality operators? Does the decision possibly depend on the context? In other words, do the equality operators make more sense in some situations and XOR make more sense in others? If so, what are the different situations that warrant the use of each?

Saturday, April 12, 2008

Template Method Design Pattern in Ruby

One of the Gang of Four Design Patterns that benefit quite a bit from static typing in Java is Template Method.

You have an abstract class like this:

public abstract class Template {
  public void templateMethod() {
    performStep1();
    performStep2();
    //do some extra work
  }
  protected abstract void performStep1();
  protected abstract void performStep2();
}

And then a concrete implementation:

public class Implementation extends Template {
  protected void performStep1() {
    //implementation goes here
  }
  public void performStep2() {
    //implementation goes here
  }
}

The nice thing with the Eclipse IDE is that the moment you make the Implementation class extend the abstract Template class, the Java Editor immediately notifies you of the missing implementations of the hook methods (performStep1() and performStep2()) so that you go ahead and implement them. In other words, having the step methods abstract provides us with a guiding API that helps developers figure out what to implement.

During development of Glimmer, I wanted to use the Template Method pattern for something. As I started to implement it, I remembered that there are no abstract methods in Ruby because you cannot have a compiler check that you implemented all abstract methods due to Ruby being an interpreted language.

When writing Ruby programs test-first however, not having a compiler is not a problem since compilation is really just a tiny part of proving that a program is correct. In reality, unit and integration tests are what truly give the confidence that a program works anyways. Also, while a compiler is useful in providing quick feedback about errors if a developer was testing the program functionally through the user-interface, tests provide feedback that is almost as fast, so with a language that requires much less keystrokes like Ruby, you end up with higher productivity gains in the end even without the benefit of compilation.

Here is how template method was implemented in Ruby:

class Template
  def template_method
    perform_step1;
    perform_step2;
    #do some extra work
  end
  def perform_step1
    raise "must be implemented by a class"
  end
  def perform_step2
    raise "must be implemented by a class"
  end
end

class Implementation < Template
  def perform_step1
    #implementation goes here
  end
  def perform_step2
    #implementation goes here
  end
end

So when writing a class that extends Template, if either of perform_step1 or perform_step2 was not implemented, you get an exception right away when running template_method. Of course, with test-driven development you have assertions, which will be better indicators of whether you implemented things correctly.

Still, in Ruby, you can have an alternative Template Method implementation by relying on blocks:

class TemplateImplementation
  def template_method(step1, step2)
    step1.call;
    step2.call;
    #do some extra work
  end
end

It is used as follows:

implementation = TemplateImplementation.new
implementation.template_method(
  lambda {print "Hello"},
  lambda {print "World"}
)

This way, you can pass the hook methods performStep1 and performStep2 as anonymous function blocks, which can be created in Ruby using the lambda keyword (a shortcut for Proc.new.) Lambda produces Proc objects, which can be easily executed by calling the call method on them.

In conclusion, while Template Method in Ruby misses the benefit of static typing, it can yield shorter more concise code, especially by relying on blocks, and it can still be implemented correctly by following test-driven development.

Sunday, April 06, 2008

If-Else vs Direct Return

The other day I was pair-programming with a colleague at my client's site, and after we had a newly written unit-test fail, the implementation that my colleague wrote was something like this:

public boolean isConsumable() {
  if (STATUS_NEW.equals(getStatus())) {
    return true;
  } else {
    return false;
  }
}

After the test passed, I went ahead and did a refactoring by turning the method into:

public boolean isConsumable() {
  return STATUS_NEW.equals(getStatus());
}

The test passed again. However, my colleague wasn't happy with that implementation. I was taken aback because I thought since it was shorter, that meant we had less code to maintain. But, my colleague expressed that he found it more understandable as an English-statement to say something like:

if a.equals(b) return true else return false

instead of

return a.equals(b)

The first time I personally learned the ternary expression "condition ? true-result : false-result", I found it a mind-bender and preferred to use traditional If-Else statements instead. After a while, I got used to the ternary expression and it became a basic construct in my thinking. In the same token, right now whenever I read a line like "return a.equals(b)" under a boolean method, I quickly translate it in my mind to something like: method value is determined by equality of a to b. Therefore, I believe it is just a matter of habbit and getting used to the shorter syntax.

Still, I am curious to know other people's perspectives on this. Which syntax do you prefer and why (If-Else statement or shorter direct return statement)?

Thursday, April 03, 2008

Glimmer Eclipse Project Creation Review

You've heard about Glimmer:
http://www.infoq.com/news/2008/02/glimmer-jruby-swt
http://andymaleh.blogspot.com/2007/11/glimmering-philosophy.html
http://andymaleh.blogspot.com/2007/12/listeners-in-glimmer.html
http://andymaleh.blogspot.com/2007/12/glimmers-built-in-data-binding-syntax.html
http://andymaleh.blogspot.com/2008/02/table-data-binding-and-mvp-in-glimmer.html

shell {
  text "JRuby on SWT"
  composite {
    label {
      text "Hello World!"
    }
  }
}

You've seen Glimmer in action at EclipseCon 2008:
http://andymaleh.blogspot.com/2008/03/glimmer-at-eclipsecon-2008.html
http://andymaleh.blogspot.com/2008/04/first-glimmer-game.html



And finally, Glimmer is proposed as an Eclipse Technology Project with the Creation Review scheduled on Wed, 16 Apr 2008 at 1600 UTC:
http://www.eclipse.org/proposals/glimmer/

If you appreciate the ideas behind Glimmer, and would like to see it grow, or would like to become a part of the project by contributing your own ideas or code, feel free to express your interest by joining the Creation Review call-in meeting on April 16th at 11AM CT (GMT -06:00).

I will be presenting some slides to review the purpose of Glimmer, where it is now, and where it is going in the future.

Wednesday, April 02, 2008

Eclipse Regional Communities, Chicago Edition

Yes, if you're not living close to Austin, you can come to Chicago instead. ;)

Please click >>here<< to sign up for the Chicago Eclipse Community mailing list.

We are open to any event ideas. For now, it seems like the first two events will be an Eclipse DemoCamp where participants get 5-10 minutes each to demo local Eclipse projects, and an Eclipse Ganymede overview.

We'll keep you posted. Otherwise, hang on in Chicago's windy weather!

Tuesday, April 01, 2008

First Glimmer Game

Nick Malnick and I programmed the first game to utilize the Glimmer engine. We did so by writing tests first and following the model-view-presenter pattern with data-binding.

It is a simple 2-player Tic Tac Toe game that I demonstrated during my talk at EclipseCon 2008:



I finally committed the completed version to SVN. For those interested in looking at the code, feel free to do so by clicking on these links:Notice how easy it is to create a 3x3 grid in Ruby by relying on (1..3).each iterator statements and blocks. Also, notice how simple it is to data-bind and add listeners using the Glimmer bind keyword and on_[action] syntax.

Of course, a big part of the reason why I like Glimmer for building desktop applications is to have the ability to write very concise domain model code in Ruby. Check out the TicTacToeBoard and TicTacToeBox classes for examples of very readable and easy-to-maintain domain model code, especially in comparison to the often bloated setter/getter infested Java domain models.