Wednesday, February 12, 2014

Different approaches to binary methods: double-dispatch, pattern matching and multimethods

I've chosen a simple problem that can be solved using binary operations to show some different approaches to them: the Rock, Paper and Scissors game

Binary methods in OOP.
This is a Ruby code that is using the double-dispatch pattern to solve this problem following a "full" OOP approach (not using any conditionals on types):

When you call hand with two variants of Gesture (Rock, Paper and Scissors are all variants/types of Gesture but since Ruby has duck typing we don't need to have this superclass), it sends the message play_against to the first variant. That's the first dispatch.

Rock, Paper and Scissors have its own version of play_against and the first dispatch sends, according to the type of the message receiver, the execution to one of them. It uses polymorphism on the receiver to get to the right method.

Once in there, instead of falling in the temptation of using a conditional depending on types, we use polymorphism again but this time on the object passed as a parameter.

For instance, if we call hand(Rock.new, Paper.new) the first dispatch will send us to the play_against method of Rock. If you've got there, you know that the first player's gesture is a Rock, so we keep that information in the name of a new method, play_against_rock and use polymorphism again sending that message to the second object. This is the second dispatch that, in this case, will send us to the play_against_rock method of Paper where we can return that a Rock is beaten by a Paper: Lose.new(aRock, self).

For three variants there are nine possible combinations (3 x 3), which originates 9 functions: a version of play_against_rock, play_against_paper and play_against_scissors for each variant.
You might imagine how complicated would be implementing n-ary methods.

You can check the whole example with its tests in Rock, Paper, Scissors game using double dispatch in Ruby.

Binary methods with functional decomposition
In functional decomposition all the cases are considered in the same function: hand.


In hand we first use pattern matching on the first variant and then pattern matching again on the second. In this code, I nested the second pattern matching but I could have used helper functions called play_against_rock, play_against_paper and play_against_scissors to make it more similar to the OOP version.

As you see there are again 9 cases, but this code is less "spread out" than the OOP one.
However it seems that implementing n-ary methods would also be very complicated using this approach.

You can check the whole example with its tests in Rock, Paper, Scissors game using pattern matching in OCaml.

Multimethods
Quoting Dan Grossman:
"Not all OOP languages require the cumbersome double-dispatch pattern to implement binary operations in a full OOP style. There are languages that support multimethods, also known as multiple dispatch that provide more intuitive solutions. Multiple dispatch is "even more dynamic dispatch" by considering the class of multiple objects and using all that information to choose what method to call."
Ruby, Java and C++ don't support multimethods. Java and C++ have static overloading by which you can have multiple methods with the same name but different types for the arguments. The difference is that the method to call is determined in this case at compilation time and not in run time. This can be convenient but does not avoid having to use double-dispatch in this example.

Clojure has multimethods:


The treatment of the binary method is much simpler in this example than in the other two. Moreover, you can use the multimethods for n-ary methods too.

You can check the whole example with its tests in Rock, Paper, Scissors using Clojure multimethods

I had been thinking about doing this posts since I finished the great Programming Language course in Coursera.
Well, better late than never.

-----------------------------------------------

PS: According to Dan, it seems that in C# one can achieve the effect of multimethods by using the type "dynamic" in the right places.

No comments:

Post a Comment