Jeremy Hylton : weblog : 2003-11-13

2003 Scheme Workshop

Thursday, November 13, 2003, 1:51 a.m.

My overall impression of the workshop is that the presentations were interesting and well-done, but didn't have a lot of sizzle. Scheme has been around for a long time (closing in on 30 years) and is very well understood in theory and in practice. The talks seemed to be exploring several small corners of the Scheme world.

The workshop ended with a group discussion of Scheme standardization. The plan presented and largely agreed upon there was to appoint editors for a new Scheme standard within two weeks.

I was in Boston for the LL3 workshop on Saturday. We planned to have the two events on back-to-back days to allow people to attend both, and it was convenient for me at least. I wouldn't have gone to a Scheme workshop otherwise.

Richard Kelsey gave an excellent talk on the interaction between call/cc and dynamic-wind; basically, if you want to use continuations for threads, you can't use call/cc because it invokes dynamic-wind thunks. One conclusion from the paper: "It is better to build first-class continuations and dynamic-wind on top of a native thread system rather than building the thread system on top of continuations." This didn't come through as directly in the talk; too bad there wasn't any debate of it.

Greg Cooper's demo of FrTime (pronounced "father time") was the highlight of the day. He has implemented a functional reactive programming system for PLT Scheme. It allows values in the language to vary with time (as opposed to having an elaborate structure for polling for new values from some external source). When he showed an interactive interpreter prompt where the value of current-seconds updated itself every second in the history, he got a spontaneous round of applause from the audience.

There were a dozen talks, but I don't have time to write up my notes on all of them. Here are a few of the highlights.

From Python to PLT Scheme

Daniel Silva presented his work on embedding Python in Scheme. The Python source is translated into Scheme source. It's just a proof of concept at the moment, running many times slower than the Python interpreter. Most of Python is too dynamic to translate directly into similar features in Scheme. MzScheme has modules and classes, but Python's module and classes are implemented using namespaces and hash tables.

One concern for the project is integration with the runtime system provided by the Python interpreter. A goal here was to make Python C extensions available in the Scheme environment, but Python's use of direct access to the ob_type field defined by PyObject_HEAD is a major stumbling block.

Matthias Felleisen, who advises the students, told me he was disappointed that their static debugger, MrFlow, did not work well with Python. The value flow analysis that MrFlow performs does not work well with Python's very dynamic style. Since an class or instance's dict can be manipulated directly, the flow analysis can't infer much beyond access to the underlying hash table. Typical Python coding style favors an imperative rather than functional style, where objects are modified in place and methods don't return anything. Felleisen didn't like that either.

Python can be very dynamic, but in practice changes to classes and objects at runtime via __dict__ is fairly rare. It's too bad you can't partition the analysis into two parts -- one ignoring runtime introspection and another part that attempts to identify the risks of that introspection. For example, ZODB does a lot of dynamic modification of objects, but only to migrate object state in and out of the database.

I was a little surprised that the focus was on close integration with the existing Python interpreter. I would have guessed that you could translate Python to pure Scheme and then compile the code to get good performance.

PICBIT: A Scheme System for the PIC Microcontroller

Danny Dubé gave the PICBIT talk -- a Scheme implementation for the pic microcontroller. The chief challenge was to get programs running with less than 2KB of RAM.

It was a good nuts-and-bolts talk. How did they do it? A compact object representation, pre-allocate a bunch of ints in ROM. They use the Deutsch-Schorr-Waite mark-and-sweep collector. Stop the word isn't too costly when the world is only 2K.

They showed some space results for a bunch of small programs, including a 600-line Earley parser and an 800-line Scheme interpreter. ROM size ranged from 20 to 35KB. RAM size was a little over 2KB for Earley, but other things fit.

Enabling Complex UI in Web Applications with send/suspend/dispatch

Peter Walton Hopkins presented an extension to the basic Web UIs as continuations work for the PLT Scheme web server. The framework provides a singlue continuation for each page. This becomes hard to use when a page has many links; you need to dispatch to the code that handles the particular action performed via the continuation URL.

send/suspend/dispatch gives you a continuation plus a closure, which makes it easier to manage the dispatch code. I'm not terribly familiar with the original send/suspend framework, but the talk was interesting enough that I'd like to investigate.

Programming the Web with High-Level Programming Languages ( PDF), from the 2001 European Symposium on Programming, was cited, as was Queinnec's work on continuations and web servers. He also had a recent article in SIGPLAN Notices.

Well-Shaped Macros

This talk was interesting, but it was given while I was dragging after lunch. Definitely worth reading the paper. During the discussion, Shriram Krishnamurthi asked two good questions. First, aren't you just recreating BNF; the same question had occurred to me, but I didn't catch any of Matthias's answer beyond "No." The other question was about the complexity of checking, given experience with XML transformers. Here Matthias explained that XML was big, but macros were small.

Scheme standardization

The new plan is to have a steering committee (of gray beards) and a small group of editors to draft a new standard. The session was run by Alan Bawden; he and Will Clinger did most of the talking.

The existing standard series, ending with R5RS, was compsed by a group knows as the "authors group." It seems this was basically whoever happened to come to an early meeting of people interested in Scheme. It includes people who aren't actively working on Scheme anymore and excludes many people who are.

The biggest problem with the authors group was that decisions were unanimous, which meant that a small minority. As a result, R5RS does not address a lot of important issues. I've never written large scheme programs (outside coursework), but it seems that the lack of a module system is a key issue. perhaps in the absence of the module system, there don't seem to be a lot of modules.

I checked later and was surprised to see just how many Scheme implementations have enough life to get mentioned in the FAQ. There are perhaps a dozen implementations I've heard of; the full list is in the FAQ. (And this doesn't count all the people who did a little one as a hack, like Cotton Seed's implementation in Display Postscript for the NeXT.)

Why do they think they'll make progress? In the past, they've been stuck by disagreements over basic design issues. Either people are going to have agree to go along with individual decisions they don't like, or the people who had prevented progress are no longer are part of the process. Regardless, the standard will only work if people implement it and write code against it. Best of luck.