Rebuilding Racket’s Graphics Layer

Racket version 5.1, which is scheduled for release in early February, will look a little different on the outside. Unix/X users will see the biggest difference: DrRacket and all Racket GUI programs will take on the desktop theme for menus, buttons, and other GUI widgets. Text handling is also better than before on Unix/X, especially when printing. Windows and Mac OS X users will see smaller changes, such as better printing, better handling of mouse-wheel events, and support for 64-bit Windows and Mac OS X.

On the inside, version 5.1 is the biggest single change in Racket (or PLT Scheme) history. We’ve reimplemented the GUI layer, which meant throwing out about 200,000 lines of C++ code that built on Xt, Win32, and Carbon. We’ve replaced that C++ code with about 30,000 lines of Racket code that builds on Gtk, Win32, Cocoa, Cairo, and Pango. This change modernizes Racket's graphics support while significantly reducing the cost of maintaining the GUI and drawing libraries.

In the space between the GUI implementation and the surface, there are many API improvements:

• You can run GUI programs with just racket, instead of having to use gracket. Depending on how much your platform distinguishes between GUI and console applications, there may still be an advantage to using gracket (i.e., to tell the OS that you mean to start a GUI application or that you want a single instance of the application), but the difference is minor.
• Most of the drawing library has moved to racket/draw, which you can use without the rest of the GUI library – and, in the case of Unix platforms, without an X-server connection. After detangling the graphics and GUIs libraries, the graphics library is now integrated in more places, such as adding pict support for Scribble documents.
• The drawing library includes some new capabilities, such as rotation, affine transformations, and bitmaps with alpha channels.

Replacing hundreds of thousands of lines of C++ code with tens of thousands of lines of Racket code sounds like a no-brainer. The old library was implemented in C++ because we started in 1995 by gluing together a Scheme interpreter with a portable GUI library. Then the GUI code stayed in C++, because the interpreter wasn’t fast enough and the foreign interface was too clumsy. Racket is now plenty fast and its foreign interface has improved a lot since then.

Still, the reimplementation took about 18 months. Smoothly integrating cross-platform GUI support with a programming language can be more difficult than it sounds, and mating new libraries with a legacy API creates additional challenges. Finally, many Racket tools depend Racket’s “eventspaces,” which are multiple process-like entities in the same virtual machine, each with its own GUI event loop. Implementing eventspaces on top of modern GUI toolkits turns out to be tricky, because the toolkits insist on a single event-loop per process and they cannot tolerate event-loop actions during certain callbacks. Fortunately, delimited continuations can help work around those limitations.

Cairo and Pango are the two big enablers of the Racket graphics rewrite. The old Racket graphics library depended on many toolkits (X11, Win32, QuickDraw, Quartz, PostScript, and more), and it had poor font handling. Again, the problem was that we chose the previous technology in 1995. Cairo and Pango have since solved the portable-graphics problem, and we were able to trade in 80,000 lines of C++ glue for about 8,000 lines of Racket glue. The code could be much less if we didn’t have to match most of the old drawing API, but we're still very happy with the result.

On the GUI side, the remaining 22,000 lines of Racket code replace similar C++ code that binds to three different toolkits. The set of underlying toolkits has changed, and a few eventspace tricks are new, but the approach is essentially the same as before. The code is nevertheless much more compact, because (no surprise) Racket is better than C++. Interestingly, the amount of toolkit-specific code is right around 6,500 lines for each toolkit, even though the way that a C programmer uses the different toolkits seems very different: Objective-C classes (Cocoa) versus signal callbacks with explicit wiring (Gtk) versus a single callback function for message handling (Win32). Maybe they're the same because we built a Racket mini-language for each toolkit that makes them all about equally convenient.

The rewrite is not perfectly compatible with old code, and no doubt we have many bugs to find before the release. The process is well on track, though, and the new library implementations give a us a solid foundation to keep making Racket better.

To try out the current development version, visit

http://pre.racket-lang.org/installers

Talk at Flourish

The image in this post shows a tree where the interior nodes represent directories and the leaf nodes represent files in the PLT source code. The leaves are colored based on the programming language used. (To avoid clutter, if there is more than one file in a given directory written in a particular language, that language only gets a single dot.)

Some highlights: the blues are Scheme-like languages, the reds are langauges we use to write documentation (see Scribble for more about them), the greens are teaching languages, orange is the language we use to bootstrap new languages, and yellow is a language for metadata about nearby files.

Curious about how we managed to write and use so many different languages? I'll be giving a talk at Flourish 2010 next week (3/19 @11am, UIC in Chicago) explaining how. Come to learn more!

DAGs vs Trees

As I wondering whether or not there is a better layout algorithm for the module browser window, I looked into tree maps. Of course, the modules in a program form a DAG, not a tree, so I wondered just how big the tree would get if all of the shared structure in the DAG were replicated. Hey, I figured, if a tree map can handle showing me my entire filesystem, maybe that could work.

... yeah, no. Turns out to be hopeless. In the spirit of a geeky take off on a jelly bean counting contest, lets see if you can guess just how big these things get. Consider the module graph from the program #lang scheme (ie, the graph that just contains an empty program). This program loads 170 modules with 917 connections between modules (counting the main file that just contains the #lang scheme).

So, the question: how many nodes are there in the unsharified tree? First one to come within 1 billion of the right answer gets all of the fame and glory that this blog brings to bear (har har). I'll post the answer in the comments in a few days (and no fair cheating, those of you that know enough to be able to get your hands on the DAG).

Benchmarks

First, the usual disclaimer:

That said, I've run the latest version of PLT Scheme on two sets of benchmarks:

• Benchmarks in the PLT sources – vs. Bigloo, Chicken, Gambit, Guile, Ikarus, Larceny, MIT Scheme, and Scheme48; safe operations and generic arithmetic only

• Benchmarks in the Gambit sources – vs. Bigloo and Gambit; generic vs. fixnum-/flonum-specific arithmetic, safe vs. unsafe operations

The second set is why I started running benchmarks. Fixnum-/flonum-specific arithmetic and unsafe operations are new in PLT Scheme 4.2.4. The benchmark results suggest that the new operations in PLT Scheme offer roughly the same performance benefits as in Bigloo and Gambit. There's room for improvement, but it's a good first cut. For the other results: PLT Scheme is rarely the fastest implementation on a given benchmark. For most purposes, though, it's in the same ballpark – except for programs that spend all their time capturing and invoking continuations. It's fun to run benchmarks occasionally. Now, back to working on language design, libraries, documentation, usability...

How many occurrences of car in the PLT source code?

Lets play a guessing game. See who can guess:

• How many occurrences of the identifier 'car' there are in the PLT tree (when using 'read' and just counting the symbols that come out)?
• Where does 'car' rank on the list of the most commonly used identifiers?
• What is the most common identifier, and how many occurrences of it are there?

UPDATE: The two files raw-hattori and raw-kajitani.ss are generated files containing solutions to Paint by Numbers problems and about 30,000 occurrences of x and o. Discounting them, this is the list of the top ten identifiers and the number of occurrences:

((define 25294)
 (quote 24101)
 (lambda 18883)
 (let 14796)
 (send 14349)
 (x 11877)
 (if 11118)
 (... 8474)
 (car 7610)
 (syntax 6537))

The identifier cdr ranks 21st with 5,259 occurrences, let* has 3,066 which, when combined with let comes out at 17,862, still not enough to pass lambda. Speaking of combining, λ has 2,271 occurrences, which is also not enough to move lambda. Finally map comes in 32nd with 3,853 occurrences and foldl beats out foldr (1168th place with 75 occurrences vs 1451st place with 58 occurrences).

PLT Modules and Separate Compilation

For my summer job this year, I'm programming in Common Lisp; this is the first time I've used the language for anything more than toy examples. The experience has given me new appreciation for the PLT module system and how it enables separate compilation.

Lisp has a package system, of course, but it's not the same thing. It's primarily a tool to make sure that the symbols in one part of the program don't collide with the symbols in another part (unless you ask them to). Packages aren't about abstraction: while you can specify which symbols are exported from the package and which aren't, that's just a suggestion that's not enforced by the language.

(You'll notice, by the way, that I used the word "symbol" and not "identifier," which is the more common term in the study of programming languages, in the previous paragraph. That's deliberate: the Lisp package system works on symbols, not identifiers, so it also affects quoted, literal symbols. In my experience, this is sometimes helpful, sometimes a real pain, and usually completely unexpected. But that's a topic for another post.)

Also, there's no real relationship between Lisp packages and files. One package can be spread across multiple files, and one file can contain code in several different packages.

All this means that separate compilation in Lisp is a real problem. There is a system, ASDF, that attempts to address this need. (For more details, consult the closest thing to a homepage that I could find for ASDF.) I'm no expert on ASDF, but essentially the programmer specifies the dependencies between source files, in a set of files that exist parallel to the Lisp source. (ASDF does support grouping source files into larger chunks and specifying dependencies between those chunks, but as far as I can tell that's largely a convenience thing.)

The key thing for separate compilation, of course, is the dependencies. With ASDF, the programmer specifies those manually, and then ASDF basically does a topological sort such that if file a depends on file b, then ASDF ensures that a is compiled and loaded before b is compiled, and again before B is loaded. (This should start sounding a little familiar to folks who've worked in the area where PLT's modules and macros intersect.)

So far, so good. Unfortunately, there are a couple of problems with this setup. First, the dependencies between files are specified outside the language. This means that, if you happen to forget one, the results are not well-defined. If ASDF happens to choose an order that's consistent with the dependency you left out, everything will just work, and you won't have any indication that there's a problem. If, however, it doesn't, then you'll get random "undefined function" and "undefined symbol" errors---if you're lucky (at least in SBCL, the implementation of Common Lisp that I use at my job). In PLT, by contrast, inter-module dependencies are part of the language, so the compiler will always give you an undefined-identifier error when it tries to compile a module in which you've forgotten a require form. Big win, in my opinion (although we could argue about whether this should be an error or a warning, and whether the compiler should report lots of errors or just one before giving up completely).

Second, because ASDF lives outside the compiler, it can't be very smart about how macros affect separate compilation. I don't fully understand this, perhaps because the folks who've been mentoring me at my job haven't thought it worth the time to explain it to me fully. But it appears that, if you change a macro that's used in other files, or change a function that's called by a macro at expansion time, you have to do the effect of a make clean in a distressingly large number of cases. This is a real problem when you've got a large source base (~200K LOC, I think) and you're trying to speed up builds, as we are, and it's especially problematic if you're trying to run unrelated parts of the build in parallel.

I've certainly griped about the complexity of the interaction between PLT's modules and macros in the past. But after this summer, I have to say it's awfully nice to have a module system that Just Works for separate compilation. Nicely done, Matthew.

(I've pointed the folks at work at Matthew's ICFP 02 paper, but as that technique requires a lot of support from the compiler, and we don't have the resources to add the necessary support to SBCL ourselves, I don't know that it'll be more than a "wouldn't it be nice if we could do that?")

(Answer to rhetorical question in preceding paragraph: Yes. Yes it would.)