Tuesday, May 24, 2011

Cassowary Constraint Solver in JavaScript

As a longtime-recovering academic, I still occasionally feel the urge to make the work I did for my Ph.D. back in the '90s matter more in the real world.  Recently, I had the chance to use two different and unrelated pieces of my research together.... as any fellow technologist knows, that makes doing the work way more than twice as fun!

One of the projects I found a new use for is JavaML – work I did in 1999. For my grad school career, JavaML was perhaps most notable because it was done right before I finished my Ph.D. but was not included in my thesis at all... quite literally, I went to my advisor one week before the submission deadline and said "I'm gonna disappear for a week while I work on this cool idea, ok?" Luckily, that paper was accepted to WWW in 2000 which was hosted in Amsterdam. Yes, the choice of conference was somewhat influenced by its being hosted in the Netherlands, but also because the project idea was grounded in something I knew the WWW community would be excited about: the use of web standards applied to developer, language, and compiler tooling. Specifically, my idea was appealingly simple: convert Java source code into XML so that one could use XML tools such as XSLT, SAX parsers, DOM trees, and more, to write code transformations  and analysis and querying tools. The primary challenge was the exact design of the XML schema for the Java AST.  That piece was critical in making downstream tools powerful and easy to build.  As with all of my work, I backed the theory with an implementation that I built using IBM's then state-of-the-art Java compiler. All told, that JavaML paper turned out well, I made a cool poster for UW's industrial affiliates one year and I had a working implementation that had plenty of reasonably compelling examples. And I had a fun visit to Amsterdam... But never did I myself use the tools I built for anything practical. Until a couple weeks ago....

The other prior research I dusted off in my latest personal project is the Cassowary Constraint Solving Toolkit. That work and its applications made up the bulk of my PhD thesis. In a nutshell, Cassowary is a library and framework for expressing linear arithmetic equality and inequality relationships among variables and solving systems of those relationships incrementally and in real time. Most of my work involved applying the incremental solver to graphical applications such as the Scheme Constraints Window Manager or the Cascading Style Sheet engine in web browsers and Scalable Vector Graphics renderers, but other researchers used it for satisfiability engines and resource planning, and more. For many years, I used Cassowary daily in the Scheme Constraints Window Manager, but it never achieved widespread use on the web. In part this is because it needed to be built into the browser... although I made the Cassowary toolkit available in C++, Java, Smalltalk, Python, and Scheme, none of those languages were easy to demonstrate over the web.

A few weeks ago, I realized something both obvious and important. We all know that JavaScript implementations have improved leaps and bounds over the last decade. IE6 was a disaster to work with in large part because the JavaScript implementation was good enough only for the tiny little scripts that defined JavaScript in the 90s. Today, Chrome and its V8 engine along with similar advances in Safari  (Nitro) and Firefox (TraceMonkey) make JavaScript performance scream. That meant that I could run Cassowary natively in the browser with good performance if only I had a JavaScript implementation. (Or, more properly, ECMAScript.)

Thus, my plan was hatched: given that I wrote a Java implementation of Cassowary, I would use JavaML to serialize that code into its XML representation. Back in 2000, I wrote an XSLT-based converter to go back from JavaML's XML representation to plaintext Java source code (in fact, round-tripping between those representations was my unit test as I was building JavaML). For this project, I'd change that converter to, instead of outputting Java source code, transliterate language constructs and generate a close-to-correct JavaScript plaintext representation of the program. Then, after some editing and debugging, I'd end up with a complete JavaScript implementation of the solver enabling me and others to explore the use of constraints for layout or other functionality within rich, modern AJAX web applications. In case you're impatient, here's the bounded quadrilateral demo in JavaScript. The full JavaScript implementation of Cassowary is available via CVS at Sourceforge with the rest of the Cassowary distribution.

Let me go through that last paragraph in slow motion. First, I took my Java implementation of Cassowary which has code like this:

public String toString()
    { 
      StringBuffer bstr = new StringBuffer("[");
      for (int i = 0; i < _values.length-1; i++) {
        bstr.append(_values[i]);
        bstr.append(",");
      }
      // ...
      return bstr.toString();
    }

after running it through my Jikes-JavaML tool, I get JavaML XML code like this:

<method name="toString" visibility="public" id="meth-3340">
  <type name="String"/>
  <formal-arguments/>
  <statements>
    <!-- StringBuffer bstr = new StringBuffer("[") -->
    <local-variable name="bstr" id="locvar-11045"> 
      <type name="StringBuffer"/>
      <new><type name="StringBuffer"/><arguments>
           <literal-string length="1">[</literal-string></arguments></new>
    </local-variable>
    <loop kind="for">
      <init> <!-- int i = 0 -->
        <local-variable name="i" id="locvar-11050">
            <type name="int" primitive="true"/>
            <literal-number kind="integer" value="0"/></local-variable>
      </init>
      <test>
        <binary-expr op="lt">  <!-- i < _values.length - 1 -->
          <var-ref name="i" idref="locvar-11050"/>
          <binary-expr op="-">
            <field-access field="length"><var-ref name="_values"/></field-access>
            <literal-number kind="integer" value="1"/>
          </binary-expr>
        </binary-expr>
      </test>
      <update> <!-- i++ -->
        <unary-expr op="++" post="true">
            <var-ref name="i" idref="locvar-11050"/>
        </unary-expr>
      </update>
      <statements>
        <send message="append"> <!-- bstr.append(_values[i]) -->
          <target><var-ref name="bstr"/></target>
          <arguments><array-ref><base>
                <var-ref name="_values"/></base><offset>
                <var-ref name="i"/></offset></array-ref>
          </arguments>
        </send>
        <send message="append"> <!-- bstr.append(",") -->
          <target><var-ref name="bstr"/></target>
          <arguments><literal-string length="1">,</literal-string></arguments>
        </send>
      </statements>
    </loop>
    <!-- ... ... -->
    <return> <!-- return bstr.toString() -->
      <send message="toString">
        <target><var-ref name="bstr" idref="locvar-11045"/></target>
        <arguments/>
      </send>
    </return>
  </statements>
</method>

Note that I specifically designed features of the JavaML representation to support edges (via id/idref pairs) between uses of variables and their declarations (which include their static types). That means that I can convert the above XML into JavaScript, essentially transliterating from Java to JavaScript, in a type-aware way using XSLT and template precedence rules to specialize rewrites based on details of the AST. For example, these rules make sure that StringBuffer.append and .toString method invocations result in the appropriate JavaScript constructs of "+=" and a no-op, respectively:

<xsl:template
    match="send[@message='append'][id(./target/var-ref/@idref)/type/@name='StringBuffer']">
  <xsl:apply-templates select="target"/>
  <xsl:text> += </xsl:text>
  <xsl:apply-templates select="arguments/*"/>
</xsl:template>


(The above template matches send elements with message attributes of 'append' that also have the target/var-ref/@idref pointing to a declaration that has a type element with name attribute of 'StringBuffer'.  I.e., apply this rule to all sends of the "append" message to variables with static type "StringBuffer".)


<xsl:template 
    match="send[@message='toString'][id(./target/var-ref/@idref)/type/@name='StringBuffer'][not(arguments/*)]">
  <xsl:apply-templates select="target"/>
</xsl:template>

Those rules applied to the JavaML representation of the Java source code then result in this JavaScript:

  toString: function() {
    var bstr = "[";
    for (var i = 0; i < this._values.length-1; i++) {
      bstr += this._values[i];
      bstr += ",";
    }
    // ...
    return bstr;
  },

In this case, the converted code is perfect and ready to execute.  The actual process was a bit more laborious, involving iterating on specializing the XSLT transformation for each subsequently more complex Java source program in the full library and hand-editing the output to fix the places where it was not worth my while to make the XSLT smarter (and finding a few bugs in Jikes-JavaML and my XSLT transformations along the way).  I also had to make several choices of libraries and JavaScript langauge extensions as dependencies to the converted JavaScript.  For a simple object-oriented framework, I used the server-side MooTools, and for a true hashtable and hashset (i.e., one that can have arbitrary objects as keys, not just strings), I used jshashtable and jshashset (with some minor modifications to support an escapingEach mechanism to allow break and non-local returns since the algorithm uses those patterns throughout).

After about three weekend days of working on this, I ironed out the last of the (known) bugs (which turned out to be an error in my Java implementation that I'd fixed in the C++ implementation years ago).  Then I implemented the previously-mentioned bounded quadrilateral demo in JavaScript, learned about Touch events on iOS devices and made the demo work on my iPad and iPad2.

I hope developers out there are able to find creative uses of the constraint solver on their web pages and applications.  And maybe someone will improve the JavaScript implementation with something that truly looks and feels like JavaScript (rather than Java hiding behind a JavaScript surface syntax)!  Until then, I may port to JavaScript the string expression parser to make it easier to specify constraints just by writing something like "x + width < screen_width".  The dynamic expressiveness of JavaScript should be a huge help in experimenting with tighter integration with the rest of the environment, similar to my Scheme implementation and the way it interacted with the Scwm Window Manager.

6 comments:

Wei Zhu said...

Greg, have you tried using GWT (http://code.google.com/webtoolkit/overview.html) to compile your Java code into JavaScript?

Wei

Greg Badros said...

@Wei, yea, I've used GWT for some UI prototypes before, and I spent a little while try to make the commandline tools work for this purpose. I ultimately didn't spend much time on it better that the GWT JavaScript supplemental libraries might be more onerous than I wanted and also that the generated code would look more like the C output from compilers rather than looking like it was written by hand. I'm not sure if either of those worries have foundation.

Unknown said...

Howdy,

I've been working recently to remove some of the dependencies of this (exciting!) port which should help provide both some performance improvements (currently 2x faster) and some licensing clarity. Dropping external libraries also has load-time virtues, but the price is dropping support for ancient browsers (although I'm pretty sure this code wouldn't have run on IE 7 as it was).

You can check out (and collaborate with me on) the work in progress here:

https://github.com/slightlyoff/cassowary-js-refactor

Regards

Interesting facts said...
This comment has been removed by a blog administrator.
Ken M said...

Noticed that the other constraint library from my distant past -- Garnet and its gemstone friends at CMU -- has transmogrified into ConstraintJS, a relatively lightweight constraint library for Javascript. Compatible with jquery. http://cjs.from.so/

Unknown said...

Having written massive amounts of Java and vast quantities of JavaScript, my view is very simple. Use JavaScript when you must — as in cross-browser UI. Use Java mostly because it’s a true programming language with strong variable typing.
I’m just now getting into GWT. My team has just transitioned from an HTML/CSS/JS + Java applets and servlets system to a 100% Java application to avoid browser dependencies. In order to provide mobile solutions (and Chromebook), we are working on changing our system (50,000+ lines of Java) into GWT. This is not something we do lightly.
The Java application plus servlet combination is fast, efficient, and bug-free (no known bugs) and in use by tens of thousands of students from grades 5 through college. It’s easy to maintain, build, and deploy — via JWS.
This system could never have been written in JS and maintained and updated. Besides, its performance would have stunk.
For the Java purists and the JS purists, I say, “Get a life!” I think java is not “powerful.” That’s a better description of Java, the most popular programming language in the world. Javascript is not to be avoided at all costs (e.g. root canal) because it solves problems that are not solvable in the real world in any other way. Get over it. HTML5 requires JS.
So, we’ll be delivering two solutions. I hate having more than one, but it’s lots better than three or four. And, importantly, much of the code remains unchanged. We’ll only have to rewrite a few thousand lines. Sigh! :O