the gnu extension language
I'm sitting on a train waiting to leave Paris for Barcelona, returning from the 2011 GNU Hackers Meeting. It was fantastic, clearly the best we have had yet. Thanks a lot to Ludovic Courtès for organizing it, and to IRILL and Sylvestre Ledru for hosting. I hope to write more about it in the future, but this essay will be long enough :)
I gave a talk entitled "The User in the Loop", which made the perhaps obvious argument that "extensibility is good & stuff". I hope that it did so in an entertaining and illuminating fashion. It also argued that Guile is a great fit for the extensibility needs of the GNU project. The video will be out shortly. Slides are available here, though you probably just want the notes instead.
going meta: goals and strategies
Guile is the GNU extension language. This is the case because Richard Stallman said so, 17 years ago. Beyond being a smart guy, Richard is powerfully eloquent: his "let there be Guile" proclamation was sufficient to activate the existing efforts to give GNU a good extension language. These disparate efforts became a piece of software, a community of hackers and users, and an idea in peoples' heads, on their lips, and at their fingertips.
So, Guile is a great language. But is it still the right extension language for GNU? At this GHM, Jim Blandy brought up the good point that we should revisit our past decisions periodically, to see if they still fit with our goals and with the world. "X is the GNU Y" is still a powerful, generative proclamation, so we should be careful with that power, to make sure that we are generating the right world. In that spirit, I would like to re-make the argument for Guile as the GNU extension language.
Why care about extension languages? My presentation deals with this issue at length, but a nice summary can be found in the Guile manual:
Guile was conceived by the GNU Project following the fantastic success of Emacs Lisp as an extension language within Emacs. Just as Emacs Lisp allowed complete and unanticipated applications to be written within the Emacs environment, the idea was that Guile should do the same for other GNU Project applications. This remains true today.
The idea of extensibility is closely related to the GNU project's primary goal, that of promoting software freedom. Software freedom means that people receiving a software package can modify or enhance it to their own desires, including in ways that may not have occurred at all to the software's original developers. For programs written in a compiled language like C, this freedom covers modifying and rebuilding the C code; but if the program also provides an extension language, that is usually a much friendlier and lower-barrier-of-entry way for the user to start making their own changes.
Although GNU maintainers are free to do as they wish with their packages, we are working on making an integrated system, and a system that mostly uses one extension language is better than one with many implementations. It is reasonable to promote one language as the default choice, while not forbidding others, of course.
I think that Guile is a great strategy to achieve this goal. Guile is good for the programs it extends, it is good for users, and it is good for GNU as a whole. The rest of this article argues these points in more detail.
languages do matter
An extension language is first and foremost a language: a vehicle for expression and for computation. Guile is an implementation of Scheme, one of the most expressive languages out there.
In his 2002 essay, Revenge of the Nerds, Paul Graham argues (somewhat polemically) that some languages are better than others, and that you should use the better languages. Of course he identifies "better" with "closer to Common Lisp", which is somewhat naïve, but the general point still stands.
At the time when Guile was started, it was quite clear that Scheme was indeed more expressive than Bourne shell, or than Tcl. Since then, many languages have come and gone, and most of those that have stuck around do have many of the features of Scheme: garbage collection, closures, lexical scope, etc.
But still, there are many areas in which Guile Scheme remains more powerful than other languages.
macros: language extensibility
First and foremost, Scheme's macros have no comparison in any other language. Macros let users extend their language. Macros allow a language be adapt to time, to the different needs of the future (unevenly distributed as it is).
I realize that this broad argument will not speak to people that do not use macros, so here is a concrete example.
Some languages have pattern-matching facilities, like Erlang. Pattern-matching goes like this: you have a datum, and a set of expected patterns. You go over the patterns in order, seeing if the datum matches the pattern. If it matches, some matching part of the datum is extracted and bound to local variables, and a consequent expression is evaluated.
With most languages, either you have pattern matching, because Joe Armstrong put it there, or you don't, in which case you are either blissfully ignorant or terminally frustrated. But in languages with macros, like Scheme, you can extend your programming language to give it pattern-matching features.
I'll show an implementation here, to keep things concrete. Here's a definition of a match macro. If you are unfamiliar with Scheme macros, do take a look at the relevant section in Guile's manual.
(define-syntax match (syntax-rules (else) ;; Use `pat' helper macro to see if a clause matches. ((match v (p e0 e ...) cs ...) (let ((fk (lambda () (match v cs ...)))) (pat v p (begin e0 e ...) (fk)))) ;; If we get to an `else' clause, evaluate its body. ((match v (else e0 e ...)) (begin e0 e ...))))
There are two rules in this macro. The first rule hands off the real work to a helper macro, pat. The second just matches an else clause at the end.
(define-syntax pat (syntax-rules (_ unquote) ;; () succeeds if the datum is null, and fails ;; otherwise. ((pat v () kt kf) (if (null? v) kt kf)) ;; _ matches anything and succeeds. ((pat v _ kt kf) kt) ;; ,VAR binds VAR to the datum and succeeds. ((pat v (unquote var) kt kf) (let ((var v)) kt)) ;; If the pattern is a pair, succeed if the datum ;; is a pair and its car and cdr match. ((pat v (x . y) kt kf) (if (pair? v) (let ((vx (car v)) (vy (cdr v))) (pat vx x (pat vy y kt kf) kf)) kf)) ;; Literals in a pattern match themselves. ((pat v lit kt kf) (if (eq? v (quote lit)) kt kf))))
The pat helper macro is written in so-called continuation-passing style. This means that pat receives the consequent expressions to evaluate as arguments: one if the pattern matches (kt), and the other if it doesn't (kf). I have commented the clauses to help readers that are unfamiliar with syntax-rules.
I hope that you find this implementation to be elegant, but that's not really the important thing. The important thing is that if we put this code in a module and export match, then you have provided pattern matching to a language that didn't have it. You, as a user, have extended your programming language.
This facility is quite useful. Let us consider the case of some HTML, which you have parsed to an SXML representation:
(define html '(a (@ (href "http://gnu.org/")) "GNU"))
We can use the match form to get the URL for this link:
(define (link-target x) (match x ((a (@ (href ,target)) . _) target) (else #f))) (link-target html) => "http://gnu.org" (link-target '(p "not a link")) => #f
Sometimes people say that macros make code hard to read, because (they say) everyone makes up their own language. I hope that this example demonstrates that this is not the case: link-target above is eminently more readable, robust, and efficient than rolling your own matcher by hand. Good programmers use macros to bring the language up to the level of the problem they are solving.
Note that you didn't need to build consensus in the ECMAScript committees to add match to your language. Nor do you have to be satisfied with Joe Armstrong's particular implementation of matching, as you do in Erlang. Guile's default matcher has a number of bells and whistles, but you are free to write custom matchers for other formats, extending matchers to protocols and binary records of various types.
Finally, this same argument applies to embedded parsers, domain-specific languages, dynamic binding, and a whole host of other things. You don't have to wait for a language like Python to finally add a with statement; you can add it yourself. To paraphrase Alan Perlis, Guile is an extensible extension language.
Delimited continuations let a user extend their code with novel, expressive control structures that compose well with existing code.
I'm going to give another extended example. I realize that there is a risk of losing you in the details, dear reader, but the things to keep in mind are: (1) most other programming languages don't let you do what I'm about to show you; and (2) this has seriously interesting practical applications.
So, let's take coroutines as the concrete example. Guile doesn't define a standard coroutine abstraction yet, though it probably should. Here is one implementation. We begin by defining call-with-yield:
(define (call-with-yield proc) (let ((tag (make-prompt-tag))) (define (handler k . args) (define (resume . args) (call-with-prompt tag (lambda () (apply k args)) handler)) (apply values resume args)) (call-with-prompt tag (lambda () (let ((yield (lambda args (apply abort-to-prompt tag args)))) (proc yield))) handler)))
The guts of this function is the call-with-prompt call, which makes a yield procedure, and passes it to proc. If the yield is called, it will jump back up the stack, passing control to handler.
The handler builds a resume function, and returns it along with the values that were yielded. The user can then call the resume function to continue computation, possibly passing it some values.
If we would like to add some syntactic sugar to make this form easier to read, we can do so:
(define-syntax with-yield (syntax-rules () ((_ yield exp exp* ...) (call-with-yield (lambda (yield) exp exp* ...)))))
As an example, here is a function that turns a traversal operator into a generator:
(define (generate traverse collection) (with-yield yield (traverse yield collection)))
Let's see a use of it.
> (generate for-each '(three blind mice)) $1 = #<procedure resume args> $2 = three > ($1) $3 = #<procedure resume args> $4 = blind > ($3) $5 = #<procedure resume args> $6 = mice > ($1) $7 = #<procedure resume args> $8 = blind > ($5) >
This is fascinating stuff. Normally when you call for-each, you lose control of your execution. for-each is going to call your function as many times as it wants, and that's that. But here we have inverted control-flow so that we're back in charge again.
Note that we did this without any cooperation from for-each! In Python, if you want to compose a number of its generators into a coroutine, every procedure in the call stack must cooperate. In fact until recently this wasn't even possible to implement efficiently. But in Guile, delimited continuations allow us to remove the unnecessary restrictions that make yield from seem like a good idea. Our with-yield composes with the other parts of our language.
Also note that these generators are functional: instead of mutating an object, causing the next call to it to proceed, we return the resume procedure as a value. It's not always what you want, and indeed you could make different choices, but this does have the advantage that you can rewind your traversal to different points, as I did above by calling $1 after calling $3. You can use this strategy to implement other advanced control-flow operators, like amb.
For more on delimited continuations, see the readable 1993 paper by Dorai Sitaram, Handling Control.
the next 700 language features
Guile has a number of other language features that other extension languages do not. Here's a short list.
GOOPS is Guile's Object-Oriented Programming System. It implements OOP like Common Lisp's CLOS does.
What this means to most programmers is that GOOPS is a little different. In Smalltalk-style OOP, the focus is on classes. In Self-style OOP, the focus is on prototypes. But in CLOS-style OOP, the focus is on generic functions. A good introduction to this topic can be found in Gregor Kiczales' beautiful book, The Art of the Metaobject Protocol. At OOPSLA 1997, Alan Kay called it "the best book written in computing in ten years".
Anyway, what I mean to say here is Guile does support object-oriented programming, and although it is not the same as (for example) Python's model, it is quite capable and expressive. Some of its features, like class redefinition, are not found in any of the more common OO systems.
- parallel computation
Guile supports POSIX threads, with no global interpreter lock. Coordination between threads is managed via the normal primitives like mutexes and conditional variables, though there are higher-level forms like with-mutex.
I'm going to go out on a limb here and say that managing concurrency is the major problem of programming today. Guile's existing facilities are OK, but are not as convincing as those of Clojure or D. Is STM the right answer? Or is it shared-nothing by default, like Erlang? I don't know, but I'm pretty sure that we can build the right answer in Guile, whatever the right answer is.
- the numeric tower
Guile implements the full numeric tower: integers (of any precision), real numbers, rationals, complex numbers, and the strange IEEE-754 values like negative zero, not-a-number, and the infinities. Arithmetic works with them all. In addition, there are some plans afoot to add support for optional multi-precision floating-point and complex numbers.
I shouldn't have to say this, but in Guile, (/ 12 10) is not 1. Nor is it a double-precision approximation, for that matter; it is the rational number, 6/5.
- data types
Guile comes with a wealth of built-in data types: bytevectors, uniform arrays (for example, a vector of packed unsigned 16-bit integers), multidimensional arrays (possibly of packed values), bitvectors, strings consisting of characters (as opposed to bytes), records, etc. There are also the standard Lisp data types like symbols, pairs, vectors, characters, and so on.
You can define your own data types, using GOOPS, using the record facility, or the lower-level structs. Of course you can build ad-hoc data structures using the other predefined data types; after all, as Alan Perlis says, "it is better to have 100 functions operate on one data structure than 10 functions on 10 data structures."
- functional programming
Scheme is a multi-paradigm language, supporting many kinds of programming techniques. It has excellent support for the functional style, with its lexical scope, closures, and proper tail calls. Also, unlike their call/cc cousins, Guile's delimited continuations are practical to use in a functional style, as shown above in the generator example.
Finally, I should mention that all of these features are designed to work well together. Macros compose with modules to preserve lexical scoping. Delimited continuations can transfer control through functional combinators while preserving referential transparency. Dynamic bindings behave sanely when continuations are unwound and reinstated. Scheme is a language that "hangs together": its features are carefully chosen to produce sound semantics when used in combination.
So much for the Scheme language, as implemented by Guile. On a related but not identical tack, I would like to argue that Guile's implementation is a good practical fit for GNU.
- development experience
Guile has a fantastic developer experience. Two factors contribute to this. One is that it ships with a full-featured, pleasant REPL, with tab-completion, readline, and a debugger. The second factor is Guile's reflective capabilities, coupled with the excellent Geiser Emacs mode.
As Geiser hacker Jao says, when it comes to debugging, you can be a mortician or you can be a physician. Core dumps are corpses. The REPL is the land of the living. If you run Guile with the --listen argument, it will spawn off a REPL thread, listening on a port. Geiser can telnet into that port to work with your program as it is running.
See Using Guile in Emacs, for more on how to hook this up.
- multiple languages
It's pretty clear to me that we're going to nail the Elisp / Scheme integration. BT Templeton has been doing some great work on that this summer, and we are closer than ever. Admittedly some folks have doubts about how we will pull this off, but I am convinced. I will have to defer detailed arguments to some other forum, though.
Guile is some 16 years old now, and time has winnowed its interface to something that's mostly clean and orthogonal. There are still some crufty pieces, but we have a good deprecation story, both for Scheme code and for C code linking to libguile.
Despite its maturity, Guile is a very healthy project. Check the Ohloh page for details, but note that the activity statistics are based on the master branch, whereas most commits have been landing on stable-2.0 since 2.0.0 was released in February. We'll move back into a development phase at some point in the next few months.
And on the level of users, things seem to be going well -- it's not the most-used language out there, but it is gaining traction and in respectability. The number of contributors is going up, and the various forums are active.
choosing a strategy to achieve our goals
I have argued, I hope convincingly, that Guile is a good choice for an extension language. Now I would like to put the decision itself in a context. As Noam Chomsky keeps reminding us, we need to judge decisions by their expected consequences, not their proclaimed intentions. Does Guile generate the right future for GNU?
For me, the answer is no. First of all, what does it mean to have a GNU system based on a non-GNU technology? What would be left of GNU? It might be lack of imagination on my part, but such a future makes me think of country folk come to the city and losing sight of who they are. GNU is a social organization that makes software, with particular social characteristics. Mixing GNU with a foreign language community sounds dangerous to GNU, to me. See Kent Pitman's Lambda, the Ultimate Political Party for similar musings.
Paul Graham concludes Revenge of the Nerds with the following advice:
"If you start a startup, don't design your product to please VCs or potential acquirers. Design your product to please the users. If you win the users, everything else will follow. And if you don't, no one will care how comfortingly orthodox your technology choices were."
In the case of a GNU extension language, our users are developers, so we do need to work hard to please them. But free software has a different life cycle than a VC-backed startup; instead of racing to the flip, we have to please our users now and in ten years. Viewed from the long now, the future is not simply a first-order extrapolation of the present: it is something that we generate. Guile is still the right choice for the GNU extension language because it generates the right future: a healthy, sustainable, powerful GNU project that adapts to the changing needs of time.