Khoo Yit Phang

Collecting my ideas and musings about programming

Archive for the ‘Arrowlets’ Category

New release of Arrowlets: now with pair (***), split (&&&), bind and join

with 2 comments

I’ve just released a new version of Arrowlets which finally implements all the basic arrow combinators. Where then (a nicer alias of next1) expresses sequential composition—i.e., connect the output of f into the input of g—the combinators pair (***) and split (&&&) express parallel composition—i.e., running f and g on the same input and outputting the combined result:

  • f.pair(g) takes a Pair(x, y) as input, runs f on x and g on y respectively, and combines the outputs into a Pair(fx, gy);
  • f.split(g) takes any input x, runs both f and g on x, and combines the outputs into a Pair(fx, gx).

In previous releases of Arrowlets, arrowlets can be run in parallel, but they are not easy to synchronize as they run independently of each other. Using pair and split makes it much easier to perform synchronization, since they will wait for their constituent arrowlets to complete before outputting the combined result.

Collecting outputs

Oftentimes I need to keep the results from an earlier arrowlet in addition to that from the most recent arrowlet in a sequence. Two new combinators—bind and join—are useful for this purpose: they are similar to then, but will combine the input and the output in a Pair:

  • f.bind(g) takes the input x, runs f on x, runs g on the Pair(x, fx) and outputs its result;
  • f.join(g) takes the input x, runs f on x, runs g on the output fx and combines the outputs into a Pair(fxgfx).

JavaScript Function, Tuple and Arr

If you haven’t yet noticed, all the new combinators above uses Pair objects, which is simply a tuple with two values (a tuple can be thought of as a collection of values). While arrows in Haskell can be naturally defined with pair tuples, it is a problem in JavaScript which has no notion of tuples! So, this release of Arrowlets introduces Tuple objects as well as Pair objects (which are instances of Tuple with additional methods fst and snd), with support for pattern-matching.

However, introducing tuples leads to compatibility issues with existing JavaScript functions which do not understand Tuple objects. Since one of my design goal for Arrowlets is to be as compatible as possible with existing JavaScript code, I spent a great while trying to bridge the mismatch between two different usage of functions:

  • tuple-aware functions that take a single tuple argument (e.g., for defining arrow combinators);
  • standard JavaScript functions which take any number of arguments (and can be called with more or less arguments than declared).

JavaScript doesn’t have Haskell’s sophisticated type system, so it is not possible to detect these two usage automatically. So, the solution I’ve come up with is to explicitly distinguish between these two usage of functions, and call them differently when the input is a tuple:

  • tuple-aware functions are explicitly created as Arr(function(tuple) { ... }), and are called with the tuple as the only argument (somewhat resembles arr in Haskell);
  • standard JavaScript functions are declared normally as function(x, y, ...) { ... }, but are called with a flattened representation of the tuple as the argument list. E.g., (function() { return Tuple(1,2,Tuple(Tuple(3,100),4,5)); }).then(Math.max) will output 100.

So far, this seems to me like the most intuitive way to use standard JavaScript functions with Arrowlets. I might revisit this issue in the future: I wonder if there is a way to define combinators in terms of records (JavaScript objects) instead of tuples?

Next up…

At this point, I need a testing framework for Arrowlets, but from my cursory survey, it seems that most JavaScript-based unit-testing framework aren’t adequately equipped to handle the asynchronous nature of Arrowlets. It occurs to me that with support for exceptions, Arrowlets itself makes a nice basis for a unit-testing framework, so that’s my plan for the next release.

I hope you enjoy this latest release of Arrowlets, and please use the comments to let me know of any issues!

P.S. I can’t quite figure out why Firefox/Tracemonkey takes 6x as long as WebKit/Squirrelfish Extreme to complete my matrix multiplication example. Any ideas why?


1 Thanks to Andrew Davey for this suggestion.

Written by Khoo Yit Phang

November 3, 2008 at 10:54 pm

Posted in Arrowlets

Introducing Path Projection and Arrowlets (and me)

with 2 comments

I recently found a couple of blog posts writing my Arrowlets library. Also, I presented a poster at ICFP 2008, and it was quite exciting to meet with various researchers and bloggers who knew about my work. These events have inspired me to start blogging about Path Projection and Arrowlets, two of my research projects, and exchange ideas with fellow bloggers.

Path Projection

Path Projection Close-up ScreenshotPath Projection, my main research project, is a user interface for exploring program paths, such as call stacks or execution traces. It is designed to work with defect detection tools that typically produce paths as part of their error report; taking as input an XML file describing the path and the program source code, and automatically generating a visualization that makes it easier for programmers to understand the cause of the error. We have some promising results from a user study that showed users performing a bug triaging task 18% faster compared to a conventional source code viewer.

I developed Path Projection because I believe that, while there are many useful defect detection tools today, they are often very difficult to use. A good tool should consider the user interface to be just as important as the algorithm, because ultimately, a programmer has to understand the reported error to be able to fix it.

Arrowlets

You might be surprised to know that Path Projection is a web-browser based tool. It is written mainly in JavaScript with some offline preprocessing, but no server component. In developing Path Projection however, I found the standard way of writing responsive event-driven programs in JavaScript to be quite unmanageable, invariably leading to a complicated spaghetti mess of event handlers and callback plumbing.

And that’s the motivation for my Arrowlets library: it is a JavaScript library based on arrows that makes it easy to write event-driven programs. Arrowlets allows you to compose asynchronous event listeners, synchronous event handlers or any function using a uniform arrow combinator interface. My favorite example is drag-and-drop, which in Arrowlets, the entire control-flow can be composed as in the following snippet:

var dragOrDropA =
    (   (EventA("mousemove").next(dragA).next(Repeat))
     .or(EventA("mouseup").next(dropA).next(Done))
    ).repeat();

var dragDropOrCancelA =
       (EventA("mousemove").next(dragA).next(dragOrDropA))
    .or(EventA("mouseup").next(cancelA));

var dragAndDropA = /* drag-and-drop */
    EventA("mousedown").next(setupA).next(dragDropOrCancelA);
ElementA("dragtarget").next(dragAndDropA).run();

Arrowlets cleanly separates the actual event handling code from the callback plumbing, and also makes it much easier to write event-driven programs in a modular fashion (and quite elegantly too, if I may add).

(I should thank Chris Eidhof and Adam Turoff for blogging about Arrowlets.)

About Me

And lastly, let me introduce myself: I’m a graduate student at the University of Maryland and a member the PL group with Mike Hicks, Jeff Foster, and Vibha Sazawal as my advisors. My research interest lies in developing tools or libraries that make programming tasks easy, and make sophisticated program techniques accessible to programmers of various skill levels.

P.S. I write my name in Chinese order which tends to confuse people, so Khoo is my last name and Yit Phang my first name, and you can call me Yit.

Written by Khoo Yit Phang

October 16, 2008 at 7:57 pm

Follow

Get every new post delivered to your Inbox.