Older blog entries for crhodes (starting at number 73)

Differential calculus, check. Integral calculus, check. Tensor calculus: well, at least the University of Cambridge believes I can do this adequately, so check. Lambda calculus is not a problem; though I haven't got the complete exposure to β-reduction and whatnot, I can fake it plausibly enough; check.

I'd vaguely heard of the pi calculus before; I had ignored it as being something Computer Sciency that was more-or-less completely irrelevant to practical programming. I can't honestly say that yesterday's joint uk-lispers/scheme-uk meeting (or the ensuing discussion at the pub) opened my eyes or changed my mind about it, but it might be worth a second read anyway.

The context? Dan gave a talk about SBCL's threading implementation, based on Operating System threads (and not userland implementations); we talked, among other things, about clone(); futexes and furwocks; locking and safety in data structures; signal handling (with particular reference to Linux on the SPARC — you don't want to know); and the default value of dynamic (“special”) variables in new threads.

The pi calculus bit relates, if I understood things correctly, to what primitives the implementation threading model should expose. There are probably cool theoretical results, but the impression I got yesterday was that no-one yet had a real-world implementation of anything interesting... the idea is that pi calculus gives you a set of ultraprimitives on top of which, given operating system support, one can build all the locking and synchronization operations one would like; the current situation is that we provide a set of primitives that are good for building some things and bad at others. Clearly I need to go away and read about things.

Ugly tiepography sighted.

In my defence, it's probably quite tricky to get pretty ties. To start with, the curves should have a variable thickness through the tie, so we're automatically dealing with filled polygons at the very least. In addition, there's a bunch of functionality hidden behind the ties (for instance, export to MIDI) which is rather better implemented. And this was the result of a relatively short hacking period.

On the other hand, it was probably harder than it should be; there is a relatively odd use of data structures (notes in gsharp are currently read-only, so any modification to one involves creating a near-copy) that threw me for a while. In addition, the system layout isn't ideal for incremental changes. Still, I'm relatively pleased with it, because we can probably take my patch forward.

On a different note, I verified today that sbcl builds under the latest release of clisp. The clisp developers broke the build with their previous release by sabotaging all attempts to use their pretty-printer; pleas to use sbcl compilation as a regression test before releasing have so far been ignored.

News from the trenches: more speed!

No-one doubts the utility of regression test suites to verify that a given change doesn't cause more problems than it fixes (well, most people don't, but the cmucl team still seems to be in the stone age on this issue). Regression tests, and conformance tests in addition (thank you pfdietz), allow developers to manage the complexity explosion involved in interactions between areas of functionality.

While one of the guiding principles of sbcl is maintainability (considered at least by me as more important than speed), it is nonetheless important to know the performance impact of changes, even when such changes are motivated by correctness issues. In a similar way to regression tests, the complexity of a large system is such that an apparently innocuous change can have a large effect on the performance characteristics of a priori unrelated areas.

It isn't quite so important to know before making checkins the performance delta of a change, but it is important to be able to find and fix regressions before too long. The problem until now is that there has been no systematic collection of data — so it was quite hard to deal with performance issues objectively.

Now, with (other) developers having reasonably fast computers, it is possible to keep track of these things, given a decent benchmark suite. I'm not sure that Eric Marsden's cl-bench suite is “decent”, but it's the best we've got. So thank you to Andreas Fuchs, who is not only tracking CVS HEAD on Eric's benchmarks, but has also collected very interesting historical data (SBCL releases on that latter series of graphs are approximately monthly).

What's doubly interesting about all that historical data is that not only can we identify regressions, as I've indicated above, but we can also use statistical methods to estimate similarities in codepaths covered by the individual benchmarks. Hierarchical clustering (on which more later, I hope) even on fairly naïve distance measures, reveals some interesting similarities. Graph layout in that plot courtesy of McCLIM's graph formatting protocol and a couple of home-rolled methods (which I have since improved to give a clearer dendrogram). Cool beans.

I'd forgotten how much work making binary releases was.

chandler suggested that we release binaries for as many platforms as possible for this month's sbcl release — particularly since last month's release didn't happen. So, log in remotely to five different hosts, start screen (after compiling it, in one case), run a compile (which in practice can take overnight on old and cranky hardware), swear at sourceforge's compile farm which has decided not to allow logins this morning, make binary distribution tarballs, take md5sums, scp all over the place, bzip2 (oh, yes, not all hosts have md5sum or bzip2 installed), sign md5 document, ftp to sourceforge, fight with the sourceforge web interface of death (you are in a maze of twisty web pages, all alike).

Still. Mostly done now. If your platform doesn't have a binary here, and you expected there to be one, shout. Or preferably build one yourself.

In the interests of more screenshots, here's an example of what one can do in a real Lisp application. Full disclosure: all of the layers of software above glibc (sbcl, McCLIM and gsharp itself) have version numbers below 1.0 — so don't be too surprised that it doesn't display the second beam of the semiquavers...

Consider the engraving of a piece of music such as Dvořák's Humoresque. You know the one: ‘dum-de dum-de dum-de dum-de dum-de dum-de dum-de dum-de dum-de dum-de dum-de dum-de daaaaah’. Well, typing this in in a linear fashion is an absolute pain; the engraver must change the input state between each note, or must modify each note after placing it.

What are computers for? Well, one would hope that at least one could use them to automate repetitive tasks. Emacs, for one, has keyboard macros for just this. So, first enter the notes, then C-x ( ] . C-f [ [ C-f C-x ) defines a keyboard macro for turning crotchets into real rhythm, and C-x e executes it. Apply a liberal dash of barlines, and voilà! Kudos to Robert Strandh for a neat patch (and, let's face it, for writing most of gsharp and a fair bit of McCLIM in the first place). One could also imagine writing a specialized function to alter the input state in the desired fashion automatically; that wouldn't be hard either, I think; but this is already a good feature to have.

Some bugs are more fun than others.

<Kryztof>   could be a ppc backend bug                                21:16:47
<antifuchs> what's the difference that makes the ppc act up on that?  21:16:56

So apart from demonstrating my latent psychic abilities, this bug was responsible for quite some head-scratching:

(iter (for i in '(1 2 3)) (+ i 50))
  => NIL ; on x86 and sparc
  => ERROR "2 is not a LIST" ; on ppc

Eventually, though, I tracked it down (:TRACE-FILE as an option to COMPILE-FILE is a wonderful thing), and it was amusing. The distilled test case I came up with was as follows

(defun foo () (values 1 2 3 4 5 6 7))
(defun bar (fn)
  (let (aa bb cc dd ee ff gg hh)
    (multiple-value-bind (a b c d e f g h)
        (funcall fn)
      (setq aa a)
      (setq bb b)
      (setq cc c)
      (setq dd d)
      (setq ee e)
      (setq ff f)
      (setq gg g)
      (setq hh h))
    (values aa bb cc dd ee ff gg hh)))
(assert (null (nth 7 (bar #'foo))))

So what's going on here? Well, the relevant piece of information here is that since calling FOO only returns seven values, the 8th (or, counting from zero, the 7th) should default to NIL. So that's what the ASSERT is doing; what's going wrong? To answer that, it helps to know that Gary Byers based his PPC backend of CMUCL (from which SBCL liberally borrowed) on the already-existing SPARC backend. However, the SPARC instruction set architecture has branch delay slots, such that the instruction following a branch is executed whether the branch is taken or not; the PPC has no such thing. So the cleverly-optimized loop for defaulting unknown values in the SPARC backend, when transcribed into PPC, doesn't work nearly so well...

Latest new toy: gsharp. The first surprise is that it's a Lisp application that looks, well, nice. OK, nice-ish. It's version 0.2, it has time to improve.

The second surprise was that the current CVS is noticeably more responsive than the version I'd been reading and playing with. I like it when things like that happen.

So, in any case, there are plenty of things missing, but I think it has potential. Let's get hacking!

(This cringe-inducingly upbeat tone will not last, I promise. Normal behaviour will resume shortly)

As an introduction to this entry, I should perhaps point out that writing papers is not a completely foreign craft to me; as part of my PhD, I have written a number of articles for peer-reviewed journals (and had my name added to a couple more...), so it's not a new thing. Also, I hope that this will continue — my academic career will be fairly short if I find myself unable to get anything anything else past referees.

However, it's unlikely that an article on the use of read-time conditionals in Common Lisp will interest the journals with which I'm most familiar; and if I am honest I don't think that the article in question is really journal material: it's simply a collection of anecdotes, arranged to tell a story with a moral. Also, at least certain publishers show a decided lack of enthusiasm about the subject matter, though fortunately other publishers would appear to be less reticent. So, anyway, it's probably better all round if I simply make it available to interested parties and leave it at that.

So, you heard it here first, probably: Maintaining Portable Lisp Programs, a study of how *features* can become bugs.

Others have written about what Common Lisp's logical pathnames (sic) are good for, and what not: the short version is that they are not intended for accessing or even describing files not under the control of the Lisp program.

However, we still have to implement the damn things. So here's an entertaining question: what does

  (directory "FOO:DEFSYSTEM.*")
mean, given that (logical-pathname-translations "FOO") returns
(("**;*.LISP" "/usr/share/common-lisp/source/**/*.lisp")
 ("**;*.FASL" "/usr/lib/common-lisp/**/*.lisp"))
? Naïve implementations of directory will throw an error, because they will attempt to translate (in the translate-logical-pathname sense) a logical pathname for which no translation exists. I would advocate a different interpretation: that all possible pathnames matching the queried one should be translated, and the resulting physical queries carried out.

In practice, this requires computing the intersection of two wild pathnames (in the example above, "FOO:DEFSYSTEM.*" and "FOO:**;*.LISP", for instance, which clearly have an intersection of "FOO:DEFSYSTEM.LISP"). This turns out, somewhat surprisingly, to be an immensely difficult operation to express — it took me over 100 lines of Lisp, and I'm still not confident that it's doing the right thing even for a relatively limited, though common, subset of pathnames.

But what sweet joy it is to be able to do (directory "SYS:*;") and have SBCL return (#P"/home/csr21/sourceforge-cvs/sbcl/contrib/" #P"/home/csr21/sourceforge-cvs/sbcl/src/").

We did quite well for last year.

Yesterday, after meeting Oxford physics people during the day to discuss moving forward on our projects, I met Dan for dinner, and the 2003 SBCL (UK branch) AGM. Two is quorate, yes.

So, let's see:

  • Native threads: check.
  • Better, faster, more integrated CLOS: check.
  • GenGC on non-x86: partly done.
  • Contributed modules infrastructure: check.
  • More ports: check.
  • Linkage Tables: partly done.
  • State of the Implementation: oops.
  • XREF: sort of.
which isn't a bad strike rate considering the various other things that happen in people's lives. As for this year, well, 64-bit will probably happen; some form of Unicode support will probably happen; I will write up some of the stuff that's important; and I hope that we'll release that dream of software writers: version 1.0.

64 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!