Solving the Expression Problem in Javascript

I just watched a great presentation by Daniel Spiewak called Living in a Post-Functional World. I watched it mainly because I heard it was a great presentation on how to deal with modules, which it was. A concept which is just as important in Javascript as it is in Scala.

But at the end of the presentation Daniel talks about the Expression Problem as defined by Philip Wadler.

Here it is as summarized by Daniel Spiewak:

The Expression Problem

• Define a datatype by cases
• Add new cases to the datatype
• Add new functions over the datatype
• Don't recompile
• Good Luck!

Functional Style

If we try to solve the problem in a functional style, we get something like this (also from Daniel's presentation).

sealed trait Expr
case class Add(e1: Expr, e2: Expr) extends Expr
case class Sub(e1: Expr, e2: Expr) extends Expr
case class Num(n: Int) extends Expr

def value(e: Expr): Int = e match {
  case Add(e1, e2) =>
    value(e1) + value(e2)

  case Sub(e1, e2) =>
    value(e1) - value(e2)

  case Num(n) => n
}

The functional style uses pattern matching. We see that it is easy to add new functions, such as a toString that returns a string representation of the expression without changing any code. If we add a new class, such as Mul, we have to change all the existing functions.

Here are the main points of this solution:

• Dumb cases
• Every function enumerates full algebra
• Very easy to add new functions
• Very difficult to add new cases

We get an open set of functions and a closed set of cases!

Object-Oriented Style

If we try to solve the problem in an object-oriented style, we get something like this (again from Daniel's presentation).

sealed trait Expr {
  def value: Int
}

case class Add(e1: Expr, e2: Expr) extends Expr
  def value = e1.value + e2.value
case class Sub(e1: Expr, e2: Expr) extends Expr
  def value = e1.value - e2.value
case class Num(n: Int) extends Expr
  def value = n

The object-oriented solution uses subtype polymorphism. We see that it is easy to add new classes, such as a Mul, but if we try to add new function, we have to change all the existing classes.

Here are the main points:

• Smart cases, i.e. Objects
• Every case enumerates all functions
• Very easy to add new cases
• Very difficult to add new functions

We get a closed set of functions and an open set of cases!

Dynamic Style

Now lets solve it with Javascript in a dynamic style. The solution we have looks a lot like the subtype polymorphic solution above.

function Add(e1, e2) {
    this.e1 = e1;
    this.e2 = e2;
}
Add.prototype.value = function() { return this.e1 + this.e2; };

function Sub(e1, e2) {
    this.e1 = e1;
    this.e2 = e2;
}
Sub.prototype.value = function() { return this.e1 - this.e2; };

function Num(n) {
    this.n = n;
}
Num.prototype.value = function() { return this.n; };

Just as in the polymorphic solution, it is easy to add a new class.

// Adding a new class
function Mul(e1, e2) {
    this.e1 = e1;
    this.e2 = e2;
}
Mul.prototype.value = function() { return this.e1 * this.e2; };

But, what about adding a new functions? It turns out that this is just as easy because of the dynamic nature of Javascript. We just add them to the prototype.

// Adding new functions to existing prototypes
Add.prototype.toString = function() {
  return '(' + this.e1.toString() + ' + ' + this.e2.toString() + ')';
}
Sub.prototype.toString = function() {
  return '(' + this.e1.toString() + ' - ' + this.e2.toString() + ')';
}
Num.prototype.toString = function() {
  return this.n;
}
Mul.prototype.toString = function() {
  return '(' + this.e1.toString() + ' * ' + this.e2.toString() + ')';
}

Now getting a string representation of an expression is a simple as:

var x = new Num(1);
var y = new Num(2);
var z = new Add(x, y);
var w = new Sub(x, y);
var e = new Mul(z, w);

e.toString(); // returns ((1 + 2) * (1 - 2))

Well, isn't that nice!

Sometimes I feel like I don't have a problem
...
I don't ever feel like I did before
But take me to a place I love, a dynamic place!
I don't ever feel like I did before
But take me to a place I love, a dynamic place, yeah, yeah, yeah!
Misquoting Red Hot Chili Peppers :)