Oliver Steele

The OpenLaszlo application below demonstrates animation along a line, a quadratic Bezier, and a cubic Bezier (the top three paths). It also demonstrates (the bottom path) animation along a path composed of multiple segments.

Drag the slider back and forth to display the point on each path at t=slider.value/100, or click the “Animate” button to animate t from 0 to 1.

I wrote this in order to animate the state markers along the edges of the graph in reAnimator. The GraphViz dot tool, which I’m using for graph layout, generates cubic beziers, so I had to write code to render and evaluate them.

If you’re writing for FireFox a Browser that supports the canvas element, you can use the same code with the new HTML canvas element. Click on “Start Animation” to animate the points on the canvas below. And click here to open the HTML applet in its own window.

Files:
* bezier.js — measurement, interpolation, sampling, and subdivision for arbitrary-order Beziers
* path.js — measurement, interpolation, and sampling for paths composed of multiple lines and Beziers
* bezier-demo.js — the code to draw the paths in the demo. This is platform-agnostic, and works in OpenLaszlo (bezier-demo.lzx) and HTML (bezier-demo.html).
* bezier-demo.lzx — the OpenLaszlo demo
* bezier-demo.html — the HTML demo
* drawview-patches.js — patches to the OpenLaszlo LzDrawView. This includes an implementation of LzDrawView.bezierCurveTo.

A couple of caveats:
* This animates along the Bezier parameterization, not the path length. This was good enough for my application, but you could get animation that speeds up and slows down, depending on how you choose your control points.
* The demo code is written for brevity, not speed. In particular, it re-renders the background each time, which involves some expensive math to render the cubic. In reAnimator, I placed the animated elements on a separate view in front of the background. I didn’t do that here because I wanted to share code between the OpenLaszlo and HTML demos, and the techniques for doing overlays were too different.Using a separate overlay for the background didn’t actually speed this up. The hot spot is the parametric position calculation.

¹ I think the reason the code doesn’t work in Safari is that Bezier.draw uses the Function.apply method to apply methods on the graphics context, such as quadraticCurveTo, to argument lists. It looks like Safari doesn’t implement apply when the function is a native method. I didn’t try to work around this because in cases where I’ve actually tried to use canvas (such as the “Parse” and “Graph” tab in reWork), there were other problems with Safari anyway.

Update: The inline examples weren’t showing up. Thanks to Bret Victor for both finding and diagnosing the problem. (I was linking to my laptop, osteele.dev. The post looked fine from my laptop!)

reAnimator got me interested in writing something that would let you use regular expressions. That something is reWork. This web page has a couple of fields where you can type in a regular expression and a string to match it against, and see the results update as you type. It also displays the code to perform the match in some of the languages (JavaScript, PHP, Python, and Ruby) that I use with regular expressions.

reWork limited to the features of the JavaScript regex engine. In particular, it’s missing dotall (/.../s), because JavaScript is. I actually figured out a hack to implement dotall anyway, but this will have to wait for another day.

I suspect that it still has bugs involving scanning and splitting on regular expressions that match the empty string, and browsers that aren’t Safari and Firefox 1.5, but I’m publishing this now in the hope that it will be useful anyway.

JSON for OpenLaszlo is a JSON library for OpenLaszlo.

I wrote this in order to implement my regular expression visualizer.

There’s a live example below. Clicking on a button requests some JSON text from the server and parses it on the client. The source code to the example is here.

(When it runs off my web site, the debugger in the example displays a warning about not being able to connect to the LPS server. This means that the debugger can’t evaluate expressions, as it could if you were running it off the SDK. I’m just using the debugger here to print inspectable representations of the JSON parse results, and the warning doesn’t affect this.)

Rationale

OpenLaszlo implements most of JavaScript 1.5 (ECMAScript 3), but it’s missing regular expressions and throw/catch, so it can’t run JSON in JavaScript. And the OpenLaszlo compiler doesn’t (yet) implement the proposed JavaScript 2.0 (ECMAScript 4) extensions such as class and type declarations, so JSON in ActionScript doesn’t work either. Hence, this implementation, which doesn’t require either regular expressions or JavaScript 2.0 extensions.

It’s open source, of course. (MIT License.)

Here’s something I’ve wanted for a long time. So I finally built it. reAnimator is a tool for visualizing how regular expression engines use finite-state automata to match regular regular expression patterns against text.

This is intended to demonstrate the implementation of regular expressions. If you want to learn how to use them instead, I recommend these references instead:
* Regular-Expressions.info
* A.M. Kuchling’s Regular Expression HOWTO
* Steve Mansour A Tao of Regular Expressions
* Jeffrey Friedl’s Mastering Regular Expressions
* The Regular Expression Library’s list of resources
* New My own reWork online regular expression workbench.

The User Interface

The screen has these areas:

The Pattern

The “pattern” shows the regular expression. Click on it to set another regular expression to match against.

The Input

The “input” is the string that is matched. As you type into the input string, the color of this string indicates whether it’s a complete match (green), a partial match (blue), or a non-match (red).

The Graphs

There are two graphs, which each display a finite-state automaton (FSA) that corresponds to the regular expression in the “pattern” area. As you type into the “input” area, the graphs also update, to display the state of the match.

A deterministic FSA (a DFA) is like a board game, with a counter that is moved according to the successive letters of the input string. The counter starts at the initial state (the leftmost circle with the arrow from off the board). Each consecutive letter of the input string tells where to move the counter to next. If the counter ends up in a terminal state (a double circle), there was a match.

A nondeterministic FSA is the same except that when there’s more than one legal move, you take them both.

The nondeterministic FSA bears the most direct resemblance to the regular expression. In exchange for this simplicity in its construction, it’s more complex to evaluate: instead of keeping track of just one counter, you have to keep track of a set of them. (This is an instance of the compile-time versus execution-time trade-offs that computer science is rife with.)

If you want to learn more about finite-state automata, the wikipedia entry has some useful information, but this also seems like a good place to plug my father-in-law’s book.

Implementation details

The front end is written in OpenLaszlo, and compiled to Flash. It uses AJAX and JSON to request the FSAs and the graphs.

The back end is written in Python and C. The Python part is my PyFSA library, plus a bit of glue to turn various JavaScript objects and graph files into JSON strings. There’s also a cache so that my shared server doesn’t get quite so stressed even if the site becomes popular. (Having the front end logic on the client should help here too.)

The C portion is the wonderful GraphViz. PyFSA creates a .dot file for each FSA, and uses GraphViz to lay out the graph. The server parses the annotated .dot file into a JavaScript object, and uses JSON to download the resulting graph to the client.

An OpenLaszlo class on the client interprets the JavaScript graph description into a sequence of drawing instructions. It also saves the node positions, so that it can animate against them.

Update: Some of the support libraries are now available as open source. See JSON for OpenLaszlo, JavaScript Beziers, and Canvas with Text. OpenLaszlo and PyFSA were available previously.

Implementation choices

Client vs. server: There’s no reason that this couldn’t be a client-side-only application. I just happened to have PyFSA lying around, and didn’t feel like porting it to JavaScript. My goal for this was one day of implementation time, and I didn’t think porting PyFSA would fit into this. (It ended up taking three days anyway, because I forgot about implementing cubic beziers and JSON, and because I got carried away and added animation.)

CGI vs. FastCGI: I’ve been doing most of my server-side programming with either PHP or FastCGI and Ruby, so that pages don’t take so long to serve. This is the first Python service I’ve deployed since I started using FastCGI, and I was planning to use it. But Python doesn’t include FastCGI in its library, and the fact that there were four different third-party libraries with different APIs, none of them endorsed, and that the latest PEP to mention FastCGI was deferred five years ago, made me unwilling to take on the project of evaluating them.I’m glad to hear that I was completely off base about Python and FastCGI. See Phillip J. Eby’s comment below. I stuck with CGI, which is in the standard library.

OpenLaszlo vs. DHTML: It would be just as easy to draw the graph itself using the canvas class in DHTML. I balked at doing the animation and user interface in DHTML, though. (There’s little touches like laying the graphs out horizontally only if there’s enough room, which were only a few lines of declarative code in OpenLaszlo.) And then it wouldn’t have worked on as many browsers. I decided to wait until OpenLaszlo compiles to DHTML, for a DHTML version of this.

PyFSA vs. …: Higher-performance © implementations of FSA minimization and determinization exist. I went with my own because it’s the only one I know of that has the option of preserving source location information across transformations. I use source location information minimally in the interface, and might add more.

Credits

Thanks to Margaret Minsky and Gary Drescher for commenting on a draft of the application. I used Patrick Logan’s json-py for server-side JSON. The credits for GraphViz are here. Thanks to my former colleages at Laszlo Systems, Inc. for helping create the OpenLaszlo platform. I adapted Philip J. Scheider’s code for subdividing cubic beziers; this is a compact implementation of de Casteljau’s algorithm for Algol-like languages. Thanks to Guido and company for Python. Lastly, since people always ask, I drew the architecture diagram with Omigraffle (gee I wish I got a commission!) — which I like because I’m not much of a designer, and diagrams I draw with it are passable without much work.

Update: I changed the name to reAnimator. (It was reMatch.) Thanks to Apache RewriteRule for letting me do this without breaking the old URLs!

Last week I wrote a couple of tools to keep track of subversion checkins:

The Subversion Log Viewer is a master-detail list of recent subversion revisions. It’s based on the OpenLaszlo contactlist example. The nicest feature is really an afterthought: at the last moment, I added faces for authors; I think this makes projects a lot friendlier. Right now it only adds the faces to the OpenLaszlo log; let me know if you’re interested in using this for your own project, and I’ll make a public API for adding faces to a repository.

The Subversion iCalendar Gateway transcodes subversion logs into iCalendar files, that you can subscribe to with Apple iCal or Mozilla Sunbird. I find it useful for a projects that I want to check in on occasionally. Unlike an RSS feed, it gives you a sense of the activity level and the change frequency, at least if you’re a spatial person like me.

Both of these point at the OpenLaszlo log by default, but they’ve got a UI for putting in any subversion repository (http: or svn: protocol only), and generating a permalink for that repository.

One caveat: It takes a long time to request a complete subversion log, so the iCalendar gateway only requests the first 500 revisions the first time you (or anyone) view a given calendar, and then the next time anyone or refreshes the same calendar, it catches up to the present 500 revisions at time.

Jim Grandy wrote:

From: jgrandy

Subject: stupid Google game

Date: January 7, 2006 6:17:58 PM EST

Google for "unfortunately, yournamehere":

Lots of fun hits for "unfortunately, jim":

• unfortunately Jim’s orange dry suit made him look like a carrot
  
• Unfortunately Jim is no longer with us as he died of a brain tumor in 1993.
  
• Unfortunately, Jim did not respond. He disbelieved that it was an angel.
  
• Unfortunately, Jim is only one person with a limited amount of time available to
  help Jane find answers to her questions.
  

I’ve turned this into a web page here.

I prototyped it with a screen scraper for Google, but I didn’t want to deploy a screen scraper.

Fortunately, Google has a Search API.

Unfortunately, Google’s API uses SOAP.

Fortunately, Ruby has a SOAP library.

Unfortunately, the Ruby SOAP library doesn’t work on Dreamhost.

Fortunately, the Yahoo Web Search API uses REST.

Unfortunately, Yahoo’s summaries don’t include enough right-hand context, so it’s harder to extract decent sentences from them.

Maybe I’ll go back to screen-scraping after all.

Update: Jim tells me he got the idea from Jorg Brown at Google.

Expialidocio.us is a tool for visualizing your del.icio.us posting activity. It displays a graph of your posting activity over time. You can select a timespan from this graph, and it will show you a tag cloud weighted by just those dates.

Expialidocio.us was inspired by a posting by Jon Udell. Coming full circle, Udell has posted since posted about this application. Since then, I’ve published the sources.

openlaszlo.rb is a Ruby library for compiling OpenLaszlo programs. I use it to build this, this, and the toolbar here. This article describes how to use it with Rake.

Update: This is now available as a gem. The rdocs are here.

“Aargh!” But how do you spell it?

(Click here to skip straight to the visualization.)

In the late nineties, I tried using internet search as a spelling corrector. (I think I was using AltaVista at the time. It was the latest and greatest search engine, supplanting — was it Lycos?)

At the time, for the words I tried, there were about two orders of magnitude between a misspelling and the correct word. A spelling variant, such as “color” and “colour”, were typically less than one order of magnitude.

In 2002 I used Google to figure out the most common spelling for “closable”, for use in the OpenLaszlo API. It had been “closeable”; why use a spelling that most people would guess wrong the first time, I figured. [Update: This paragraph originally said the word was "resizeable", which is a straightforward misspelling.]

Here’s what this looks like today. First, a common misspelling:

And a couple of spelling variants:

(The percentage is the ratio of the page count to the page count of the most common variant, which is the form in bold above it.)

Some other misspellings:

And some other acceptable variants:

(What’s the difference between an acceptable variant, and a misspelling? An interesting topic for another posting. Maybe.)

What got me thinking about this again, was, of all things, thinking about how to spell “aargh!” One ‘a’, two, three…? And how many ‘r’s?

This is an interesting problem, first, because so many repetition counts are attested. There’s not just “mispelling” (1s) and “misspelling” (2s), but “argh”, “aargh”, “aaargh”, etc. And second, because the space is two-dimensional: not just “argh”, “aargh”, “aaargh”, …, but also “argh”, “arrgh”, “arrrgh”, … — and the product, with “aarrgh”, “aaarrrgh”, etc.

It’s clear that a wide range of spellings are acceptable. What’s the most common?

Without further ado, I created this page to help me find the answer.

PackageMapper shows you a map of your FedEx, UPS, USPS package routes. Enter a carrier and a tracking number to see your package’s progress plotted on the map. Sign in to enter a list of packages and see their current locations on a table or map.

This is an itch I’ve wanted to scratch for about a year now: being able to see where all my packages are on a map. On Thanksgiving morning I discovered SimpleTracking.com, which gives you an RSS feed for a UPS or USPS package. Over Thanksgiving weekend I added FedEx and mashed it up with Google Maps, and this is the result.

I can’t guarantee that this will stay up if it starts to get much traffic, but in the meantime I’m finding it useful myself, so, enjoy.