Tuesday, October 4, 2011

Starting Linear Programming in Lively using Cassowary

Software engineering is great because hacking a new feature in your program can be as simple as writing a few dozen lines. In fact, that is how many developers (including myself) think and act. While it is satisfying to write a lot of code that gets things done, I feel that we are reinventing the wheel (and a bunch of other things as well) way too often. We keep writing similar methods or functions over and over. We keep solving structurally similar problems over and over.

Last week at lunch - I do not remember the full context - Dan mentioned ThingLab [1]. ThingLab is a constraint oriented programming environment from the 1970s by Alan Borning. There is an impressive demo of the system available at UW [2]. The cool thing about ThingLab is that the simulations you see are expressed in a declarative way - you write down equations rather than imperative statements. Sure, you could do that in Prolog, too.
Then, the super cool thing about ThingLab is that it still looks reasonably fast, despite its many graphics operations, user interactions, etc. - it is lively!

Now, we want to do all of that in Lively, too. And since Alan Borning is still good at writing constraint solvers, there is a great option for us: Cassowary [3]. Cassowary is a linear constraint solver that is also available for JavaScript. Linear constraints will probably not be enough to do exactly what ThingLab is capable of, but there are certain obvious use cases like layout routines.

Last weekend I ported Cassowary/JavaScript from its mootools based class system to Lively [4]. I uploaded it into Webwerkstatt as well, just so we can see what we can make out of it. I hope that maybe some day it will save us many lines of unnecessary code.

In case you are wondering how to use it, here is an example. It looks very ceeplusplusy, but that's what Cassowary was written for. Get your workspace (the following works in Webwerkstatt) ready and load Cassowary:

module('apps.dwarfcassowary.js.DwarfCassowary').load();

All I want to show is how to solve "x * 2 = y". Now, that might look a bit trivial, but keep in mind that x can be a function of time - it will change every now and then. The solver is there to consistenly ensure that "x * 2 = y".

First, we need to create a solver and then do some data modeling:

var solver = new ClSimplexSolver();
var x = new ClVariable(5);
var y = new ClVariable(10);

Then we tell the solver that we want x * 2 to equal y.

solver.addConstraint(new ClLinearEquation((new ClLinearExpression(x)).times(2), y));

After that, there is a point when a GUI program enters its event loop and values (x, in our case) would change due to user interaction. We need to tell the solver that x is about to change:

solver.
addStay(y).
addEditVar(x).
beginEdit();

Next, we tell the solver that we want 34 to be the new value for x and ask it to resolve its equations:

solver.
suggestValue(x, 34).
resolve();

After that, y has already been asigned a new value (call y.value()), provided that Cassowary could satisfy all constraints.
At some point, we can tell the solver that we are done editing x (which does not make too much sense in this example) ...

solver.endEdit();

... and again, we can look at y's value:

y.value()

Let's do something productive with that :).

[1] http://en.wikipedia.org/wiki/ThingLab
[2] http://www.cs.washington.edu/research/constraints/videos/thinglab-1978.mov
[3] http://www.cs.washington.edu/research/constraints/cassowary/
[4] https://github.com/fbornhofen/dwarfcassowary

3 comments:

  1. That's cool. Now we could rebuild the engine with constraints. In fact it suggests a whole parts bin vocabulary with connectors and constraints.

    ReplyDelete
  2. Cool! But why can't I edit this article??? :-p

    ReplyDelete