Thursday, June 20, 2013

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 :)

7 comments:

opensas opensas said...

I like the three examples you gave (functional, OOP, dynamic) but I don't quite get your reasoning behind it.

What's the meaning of the "don't recompile" constraint?

If your are working with a language like scala, you have no other choice but compiling it. If you really need to add new classes or methods (functions) at runtime, then it's undeniable that js really has the advantage there.

In any other case, what you did could have been done in OOP or functional style with almost the same effort (unless I'm missing something)

More over, you could specify in your Expr trait that the tostring method has to be implemented, and the compiler could enforce it.

I think there's something about yor article that I don't quite get...

Paulo said...

I made a solution to this problem, but using duck typing, as presented in my ES5 class solution for node, as you can see here

https://github.com/pocesar/ES5-Class#duck-typing-nothing-stops-you-to-not-using-inheritance-and-decoupling-classes

Kinda verbose at first, but highly maintainable :)

Anders Janmyr said...

@opensas, You are right that the recompile constraint doesn't really apply to
Javascript since it is interpreted. What I chose to interpret it as in this
case is load time.

The point of the post is that I can easily add methods to existing classes in
Javascript and therefore the problem completely disappears.

Anders Janmyr said...

@aaronj1335, Yes you do lose type safety, but then we never had it in Javascript anyway :)

It can actually be solved in c# with extension methods if we make sure the members are public.

public static class Extensions {
public static string ToStr(this Expr expr) {
throw new Exception("Subclass responsibility");
}
public static string ToStr(this Add expr) {
return expr.e1.value() + " + " + expr.e2.value();
}
public static string ToStr(this Sub expr) {
return expr.e1.value() + " - " + expr.e2.value();
}
public static string ToStr(this Num expr) {
return "" + expr.n;
}
}

Anonymous said...

The expression problem is about how *statically typed* languages can accomodate extensions (both data and operations) without modifying existing code. Functional languages make it easy to add operations but not data, while OOP languages make it easy to add data (subclasses) but not operations. This problem is trivial to solve in languages like JS, Ruby and Python

Hilda said...

Awesome!

jorda0mega said...

@opensas in the original problem recompile doesn't actually mean compiling the language, rather it means to not have to go back to the original code and modify it. In the functional case if you were to add a new object you would have to modify the value function to include a new match for say Multiplication. In the OOP case if you were to add a new toSTring() method you would have to go back to each type of Expression and add the new method.