Wednesday, January 6, 2010

Dynamic Method Interceptors in Scala

In my previous post I showed a rough simulation of Clojure's multimethods implemented in Scala. What if we wanted to extend that to allow dynamic interceptors on these methods?

Here's example usage showing how they stack on each other:

val numToString = DynDispatch.defMulti { i: Int =>
i match {
case 1 => "one"
case 2 => "two"
case 3 => "three"
case _ => "bignumber"
}
}

numToString(2) // "two"

// add logging?
numToString.onMethod { (i, s) =>
println("called numToString(" + i + ") and returned: " + s)
}

numToString(3) // called numToString(3) and returned: three

numToString.beforeMethod { _-1 } // evil... subtract one from input

numToString(3) // called numToString(3) and returned: two

numToString.afterMethod { _ toUpperCase }

numToString(2) // called numToString(2) and returned: ONE

numToString.afterMethod { _.substring(1) }

numToString(2) // called numToString(2) and returned: NE

numToString.aroundMethod { f =>
{ i: Int => f(i+1).reverse }
}

numToString(2) // called numToString(2) and returned: OW

numToString.aroundMethod { f =>
{ i: Int => "hello" }
}

numToString(2) // called numToString(2) and returned: hello


Our dispatcher definition looks like this:

object DynDispatch {
class DynMethod[A,R] {
import scala.collection.mutable.ListBuffer
private[this] val methods = ListBuffer[PartialFunction[A,R]]()
private[this] val around = ListBuffer[(A=>R) => (A=>R)]()
private[this] val on = ListBuffer[(A,R)=> Unit]()

def defMethod(m: PartialFunction[A,R]) = methods += m
def beforeMethod(b: A => A) = around += { f => { x => f(b(x)) } }
def afterMethod(a: R => R) = around += { f => { x => a(f(x)) } }
def aroundMethod(a: (A=>R) => (A=>R)) = around += a
def onMethod(o: (A,R) => Unit) = on += o

def apply(args: A): R = {
def applyChain[X,Y] = { ( x: X, f: X => Y) => f(x) }
def innerApply: A => R = { a: A =>
methods.reverse.find(_.isDefinedAt(a)) match {
case Some(f) => f(a)
case None => throw new Exception("Method not defined for: " + a)
}
}
val result = (around.foldLeft(innerApply)(applyChain))(args)
on foreach { _(args: A, result: R) }
result
}
}

def defMulti[A,R] = new DynMethod[A,R]
def defMulti[A,R](f: A => R) = {
val dm = new DynMethod[A,R]
dm.defMethod { case a => f(a) }
dm
}
}


And, here is an example class hierarchy showing some usage:

trait Comedian {
def perform(props: Props) = "Generic performance"
}

// comedic props
trait Props
case class NoProps extends Props
case class SledgeHammer extends Props
case class MultipleProps extends Props

trait DynamicComedian extends Comedian {
// make perform dynamic
val perform = DynDispatch.defMulti(super.perform _)
override def perform(props: Props) = perform.apply(props)
}

class Gallagher extends DynamicComedian {
perform.defMethod { case p: MultipleProps =>
"Lots of stuff"
}
perform.defMethod { case p: SledgeHammer =>
"Somebody is getting messy"
}
}

class ChrisRock extends DynamicComedian {
perform.defMethod { case p: Props =>
"Tell black jokes"
}
}

class GeorgeLopez extends ChrisRock {
perform.afterMethod { result =>
result.replaceAll("black", "latino")
}
}

class GeorgeCarlin extends DynamicComedian {
perform.defMethod { case p: Props =>
"I don't need any fuckin' props... shit!"
}
perform.defMethod { case p: NoProps =>
"Let me tell you about swear words"
}
}

trait LoggingComedian {
self: DynamicComedian =>
perform.onMethod { (props, result) =>
println("result: " + result)
}
}

trait UnpaidComedian {
self: DynamicComedian =>
perform.aroundMethod { perf =>
(props) => "Whatever, I'm not performing"
}
}

object App extends Application {

val gl = new GeorgeLopez with LoggingComedian
gl.perform(NoProps()) // result: Tell latino jokes

val gc = new GeorgeCarlin with LoggingComedian
gc.perform(NoProps()) // result: Let me tell you about swear words

val g = new Gallagher with LoggingComedian
g.perform(SledgeHammer()) // result: Somebody is getting messy

val gu = new Gallagher with LoggingComedian with UnpaidComedian
gu.perform(SledgeHammer()) // result: Whatever, I'm not performing

}


Now, if you haven't fallen asleep by now, you are probably wondering why we would go through this trouble? The Comedian class hierarchy with mixin traits could be more clearly and performantly defined statically using standard method overrides.

For example, the LoggingComedian trait could be defined like:

trait Comedian {
def perform(props: Props) = "Generic performance"
}

// comedic props
trait Props
case class NoProps extends Props
case class SledgeHammer extends Props
case class MultipleProps extends Props


class Gallagher extends Comedian {
def perform(p: MultipleProps) = {
"Lots of stuff"
}
def perform(p: SledgeHammer) = {
"Somebody is getting messy"
}
}

class ChrisRock extends Comedian {
override def perform(p: Props) = {
"Tell black jokes"
}
}

class GeorgeLopez extends ChrisRock {
override def perform(p: Props) = {
super.perform(p).replaceAll("black", "latino")
}
}

class GeorgeCarlin extends Comedian {
override def perform(props: Props) = {
props match {
case p: NoProps => "Let me tell you about swear words"
case _ => "I don't need any fuckin' props... shit!"
}
}
}

trait LoggingComedian extends Comedian {
override def perform(props: Props) = {
val result = super.perform(props)
println("result: " + result)
result
}
}

trait UnpaidComedian extends Comedian {
override def perform(props: Props) = {
"Whatever, I'm not performing"
}
}


So, unless you need the runtime argument specialization that defMulti provides, there is no need for the interceptors, right?

Let's run it:

object App2 extends Application {

val gl = new GeorgeLopez with LoggingComedian
gl.perform(NoProps()) // result: Tell latino jokes

val gc = new GeorgeCarlin with LoggingComedian
gc.perform(NoProps()) // result: Let me tell you about swear words

val g = new Gallagher with LoggingComedian
g.perform(SledgeHammer()) // no output!!

val gu = new Gallagher with LoggingComedian with UnpaidComedian
gu.perform(SledgeHammer()) // no output!!

}


What happened? Why is Gallagher not logging? Well, if you want to override a method in a trait, you need to override each combination of the arguments (here, SledgeHammer in addition to the generic Props).

Another useful property of the dynamic interceptors for this usage pattern is that you can use a class in the self type of the mixin, and not just a trait (what if Comedian was concrete?).

But, the most dramatic effect of these dynamic interceptors is that you can now get non-lexical, dynamic scoping. You can attach interceptors to individual instances of Comedian and send them down the call stack.


val georgeCarlin = comedianService.get("George Carlin")

georgeCarlin.perform.aroundMethod { f =>
(props) => {
myCallBack(props)
"Hear the one about the observer pattern?\n" + f(props)
}
}

myOtherService(georgeCarlin)


Any other uses?

Sunday, January 3, 2010

Dynamic Dispatch in Scala

Clojure has runtime polymorphism that goes beyond the single, receiver-based dispatch that you find in Java or Scala. You can dispatch based not only on the type of all objects involved (multiple dispatch), but also on the result of an arbitrary function (predicate dispatch).

Why should I care? Let's explore this in Scala using the Bunny/Lion example as shown on Clojure site.


trait Animal {
def encounter(a: Animal) = "Generic animal encounter"
}

class Bunny extends Animal {
override def encounter(a: Animal) = "Generic Bunny encounter"
def encounter(b: Bunny) = "Mate"
def encounter(l: Lion) = "Run away"
}

class Lion extends Animal {
override def encounter(a: Animal) = "Generic Lion encounter"
def encounter(b: Bunny) = "Eat"
def encounter(l: Lion) = "Fight"
}


This does what we want in a straight-forward example:

val bunny = new Bunny
val lion = new Lion
bunny encounter lion // Run away
bunny encounter bunny // Mate
lion encounter lion // Fight
lion encounter bunny // Eat


But, what happens if we are dealing with a List[Animal]? Or, we have some convenience function like this:

def printEncounter(a1: Animal, a2: Animal) = {
def s(a: Animal) = a.getClass.toString.split("\\.").last
println(s(a1) + " vs " + s(a2) + ": " + (a1 encounter a2))
}
val bunny = new Bunny
val lion = new Lion

printEncounter(bunny, lion)
printEncounter(bunny, bunny)
printEncounter(lion, lion)
printEncounter(lion, bunny)

/* Output:
* Bunny vs Lion: Generic Bunny encounter
* Bunny vs Bunny: Generic Bunny encounter
* Lion vs Lion: Generic Lion encounter
* Lion vs Bunny: Generic Lion encounter
*/


Oh, my! We seem to have dynamically determined which method definition to use based on the runtime type of the receiver object, but not on any of the objects in the argument list. This is the standard functionality you get with Java or Scala.

How would we fix this in Scala? A first pass might look like this:

trait Animal {
def encounter(a: Animal) = "Generic animal encounter"
}

class Bunny extends Animal {
override def encounter(a: Animal) = a match {
case b: Bunny => "Mate"
case l: Lion => "Run away"
case _ => "Generic Bunny encounter"
}
}

class Lion extends Animal {
override def encounter(a: Animal) = a match {
case b: Bunny => "Eat"
case l: Lion => "Fight"
case _ => "Generic Lion encounter"
}
}


Of course, like Clojure's multimethods, pattern matching in Scala is not limited to just type information, but can also look at dynamic runtime information. You could easily imagine a lazy rabbit that only ran from lions that had been identified as hungry at the time:

class Bunny extends Animal {
override def encounter(a: Animal) = a match {
case b: Bunny => "Mate"
case l: Lion if (l.isHungry) => "Run away"
case l: Lion => "Ignore"
case _ => "Generic Bunny encounter"
}
}


So, how is this different from the Clojure approach? Rich Hickey commented on this, which I'll quote here:
Multimethods differ from pattern matching in a number of ways. Two that matter (to me) are:

Pattern matching is usually ‘closed’, in the sense that all possibilities must be enumerated in a single scope.

Pattern matches are usually declaration order dependent.

Multimethods, OTOH, are an open set. You can define a new method any time, anywhere – they need not be lexically co-located. Multimethod operation is independent of definition order. They are very dynamic, and thus a good fit for Clojure.

There are other differences, of course, e.g. pattern matching usually has sugar for structural and type matches, and often exhaustiveness checking. I’m still waiting for someone to contribute a pattern-matching macro for Clojure, as I don’t think one makes the other redundant.


What could we do in Scala to address some of the deficiencies that Rich is pointing out? A dispatch mechanism could be defined like this:

object DynDispatch {
class DynMethod[A,R] {
val methods = scala.collection.mutable.ListBuffer[PartialFunction[A,R]]()
def defMethod(m: PartialFunction[A,R]) = {
methods += m
}
def apply(args: A): R = {
methods.reverse.find(_.isDefinedAt(args)) match {
case Some(f) => f(args)
case None => throw new Exception("huh?")
}
}
}
def defMulti[A,R] = new DynMethod[A,R]
}


Class and method definition would then look like this:

trait Animal {
val encounter = DynDispatch.defMulti[Animal, String]
encounter.defMethod { case a: Animal =>
"Generic Encounter"
}
}

class Bunny extends Animal {
encounter.defMethod { case a =>
"Generic Bunny Encounter"
}
encounter.defMethod { case b: Bunny =>
"Mate"
}
encounter.defMethod { case l: Lion =>
"Run away"
}
}

class Lion extends Animal {
encounter.defMethod { case a =>
"Generic Lion encounter"
}
encounter.defMethod { case b: Bunny =>
"Eat"
}
encounter.defMethod { case l: Lion =>
"Fight"
}
}


Calling syntax is the same as with the traditionally-defined methods, but the methods are dispatched dynamically. This seems to address the "closed" issue of needing to enumerate all the possibilities within a single scope. Heck, you can even add or redefine methods for individual instances of objects:

val lion = new Lion
val bunny = new Bunny
bunny.encounter.defMethod { case l: Lion if (!l.isHungry) =>
"Ignore"
}
bunny encounter lion // depends on if the lion is hungry


Note that the methods are still type-safe, as the type of the argument list is required to be declared in the DynDispatch.defMulti[A,R] method. For methods that have differing arities or disjoint types, you lose some type safety, but the syntax is still convenient:

class TigerWoods {
val tryst = DynDispatch.defMulti[AnyRef,Alimony]
tryst.defMethod { case m: Mistress =>
Alimony(1000000)
}
tryst.defMethod { case (m1: Mistress, m2: Mistress) =>
Alimony(5000000)
}
}

// ...

val t = new TigerWoods
t.tryst(Mistress("Diane"))
t.tryst(Mistress("Emily"), Mistress("Sara"))


One big disadvantage of this implementation is the runtime overhead of method definition and queuing with each object instantiation. I don't know to what extent this could be minimized with some magical combination of caching and laziness.

We are also still dependent on order of definition to resolve any ambiguities within the method definitions. This naive implementation takes the easiest path and matches from bottom to top within a scope, with scopes from instance -> subclass -> superclass. A more sophisticated approach would find the "most specific" combination of the receiver and argument list, with ambiguities resolved with runtime exceptions or some other approach (like order dependence).

I like the order dependence of pattern matching within Scala, where the different cases are all present within the same block. However, for this application, with methods defined in multiple places, I can see it as a source of confusion. But, I'm also not a big fan of discovering ambiguities at runtime.

What is your favorite way to dispatch?