programming musings

I just came back from the Scheme and Functional Programming Workshop at Montréal, hosted by Marc Feeley and an excellent organisation team. It’s been a fun couple of days putting faces to emails and IRC nicks and attending a handful of pretty interesting talks. Here’s a quick report.

My favourites were the two invited papers. The first day, Olin Shivers presented a pretty cool hack in a delicious talk consisting in actually writing the code he was explaining. Under the title Eager parsing and user interaction with call/cc, he showed us how call/cc is not just an academic toy, but can be put to good use in writing a self-correcting reader for s-expressions on top of the host scheme read (or any other parser, for that matter). He started from the very basics, explaining how input handling and buffering is usually delegated to the terminal driver, which offers a rather dumb, line-oriented service. Wouldn’t it be nice if, as soon as you typed an invalid character (say, a misplaced close paren) the reader complained, before waiting for the whole line to be submitted to read? Well, all we need to do is to implement the input driver in scheme, and he proceeded to show us how. As you know, reading s-expressions is a recursive task, meaning that when you detect invalid input in the middle of a partial s-expression, or want to delete a character, you might find yourself somewhere deep inside a stack of recursive calls and you’ll need to backtrack to a previous checkpoint. That’s an almost canonical use case for call/cc, provided you use it intelligently. Let me tell you that Olin is quite capable of using call/cc as it’s meant to be used, as he immediately demonstrated. I’m skipping the details in the hope that a paper will be available any time soon. As i mentioned, his talk was a beautiful example of live coding: he showed us the skeleton of the implementation and filled it up as he explained how it should work. Olin does know how to write good code, and it was a pleasure (and a lesson) seeing him doing just that. It was all so schemish: a terminal and emacs in the venerable twm: that’s all you need to create beauty.

The second invited talk was by Robby Findler, who gave us a tour of Racket’s contract system, how to use it and the subtleties of implementing it properly. The basic idea dates back to Meyer’s design by contract methodology of the early nineties, and was subsequently explored further by several authors, including Robby. Simple as they sound at first sight, good contracts are not trivial to implement. For instance, it’s vital to assign blame where’s blame is due, and Robby gave examples of how tricky that can get (and how Racket’s contracts do the right thing). Another subtlety arises when you try to write contracts assessing a property of an input data structure (say, you want to ensure that an argument is actually a binary search tree). The problem here is that checking the contract can alter the asymptotic complexity of the wrapped function (e.g., you can go from O(log n) to O(n) in a lookup, an exponential degradation). Racket provides an ingenious fix for that problem, by means of lazy contracts that are checked as the input is traversed by the “real” function.

There was also real-time scheme in Robby’s talk, although in a much more sophisticated way, thanks to Slideshow’s magic, which lets you embed code files and snippets in a presentation, evaluate them and show the results in the same or a new slide. Very elegant. He also used DrRacket a bit during the introductory part of his talk, and i’m starting to understand why some people are so happy with Racket’s IDE: it definitely felt, in his hands, professional and productive. And also kind of fun.

There were also lightning talks. I’m of course biased, but the one i enjoyed most was Andy Wingo’s Guile is OK!, where he showed us how Guile has overcome the problems, perceptual and real, of its first dozen years. For instance, he reminded us how Guile was traditionally a “defmacro scheme”, and he himself a “defmacro guy”… until he studied in earnest Dyvbig’s work and ported his syntax-case implementation to Guile, to become a “syntax-case man” as Guile gained full syntax-case support (i hope i’ll reach that nirvana some day; i still find syntax-case too complex and plagued by unintuitive corner cases (one of them was showed by Aaron Hsu in another lightning talk, where apparently none of us was able to correctly interpret 10 lines of scheme) that make me uneasy; but that’s surely just ignorance on my part). There are many other things that make Guile a respectable citizen of the Scheme Underground, which were also listed in Andy’s talk: i’ll ask him for a PDF, but in the meantime you can just try Guile and see :).

Although this time we didn’t have a talk by Will Clinger, to me it’s always a pleasure to listen to what he has to say, even if only as comments to other people’s talks. For instance, i enjoyed his introduction to Alex Shinn’s R7RS progress report. Will showed us three one dollar coins, of the same size and shape, but different, as he described, in almost everything else. And yet, all three were useful and recognised as (invalid) dollars by the Canadian vending machines at the entrance. He thinks that says something about standards, but he left to us to decide exactly what.

Finally, let me mention that this workshop has alleviated all my quibbles with what i’ve sometimes perceived as a fragmented, almost dysfunctional, community, made up of separate factions following their own path in relative isolation. My feeling during the workshop was nothing of the sort; rather, i’m back with the conviction that there’s much more uniting us that breaking us apart, and that there’s such a thing as a scheme underground ready to take over the world. Some day.

Here’s a list of (mostly) scheme video lectures, based on the links posted in this thread of the PLT mailing list, with some extra bits taken from my own collection:

• SICP lectures by Abelson and Sussman (see also here for more lightweight versions), still my all-time favourite lecture series on any field.
• Also based on SICP, Brian Harvey’s course on UCB is quite fun (and, while you’re at it, you may find interesting other UCB courses too). And the ADU course comes with lots of additional notes and materials, although i’ve only skimmed over it and i don’t really know how good it is. But let me tell you that, if it’s as good as Shai Simonson‘s course on Theory of computation, it’s probably worth your time.
• All videos from this year’s ICFP are available online. Among them, one can find Jay McCarthy’s talk on RESTful webapps in Scheme using serializable continuations; Matthew Flatt on PLT’s Scribble documentation system; Matthias Felleisen on how he and his collaborators are using purely functional programming for teaching kids and making them have fun; and Ralf Hinze’s La Tour D’Hanoï, which is not about scheme but is a pearl anyway (as is Ryan Newton’s report on how he used functional programming to implement an embedded bird detector via a parallel DSL with some metaprogramming for a good measure).
• During the latest GNU Hackers meeting, Andy Wingo talked about recent developments on Guile.
• Robby Findler on Why macros matter is a little nice introduction on how one can use macros not only in cases that lazy languages handle gracefully, but, more importantly, as a full-fledged language definition device.

• A clip featuring Shriram Khrisnamurthi, where he introduces WeScheme, a pretty interesting scheme-in-a-browser environment based on PLT’s Moby platform, which Shriram presented at the latest ILC; although there’s no video of that talk available, you can get the slides and a sound recording here (as is usually the case with Shriram, definitely worth your time).
• A talk by Matthias Felleisen on the evolution of Northeastern University’s CS curriculum, where scheme plays a central role.

• The DanFest videos, which i’ve mentioned before one or two times. Virtually all lectures in this series are worth watching, but, if Robby’s talk above picked your curiosity, don’t miss Ken Dyvbig’s Macro Writer’s Bill of Rights video and slides.

  
  And i cannot help mentioning neither Gerry Sussman’s The role of programming in the formulation of ideas

  
  (and its accompanying article) nor Oleg Kiselyov’s Normal-order syntax-rules and proving the fix-point of call/cc:

• As an aside, if you like Gerry as much as i do, you might be interested in hearing him sharing his enthusiasm for mechanical watches for a change. Or, if insist staying (more or less) on topic, take a look at his The Legacy of Computer Science, for Gerry’s take on how CS is making us smarter.
• Guy Steele’s Designing by Accident is a very interesting history on how Scheme came to life and its relationship with actors:

  
  for which you’ll need the accompanying slides. Although not specifically about Scheme, Steele’s Growing a language is also a must see.

• You will have to tell me how good Matthiew Flatt’s Processes without partitions is, because it seems to be available only in formats that i cannot play on debian.
• In The 90 minute Scheme to C compiler talk Mark Feeley shows how closure conversion and CPS can be used to put together a Scheme compiler (ninety minutes being the time needed to explain it, mind you).

• Those of you new to scheme and functional programming may enjoy this lecture by Jerry Cain, pertaining to Stanford’s course on Programming Paradigms, which discusses functional programming using Kawa scheme. Not stellar, but not bad as an introduction.

• Finally (for now), some fun livecoding with Fluxus:

  
  And don’t miss this gallery for some really beautiful ones.