Older blog entries for crhodes (starting at number 52)

Inevitably, as one gets nearer to the end of one's funding for any given project (in my case: doctoral studies) one finds less time for peripheral activities. In my case, the first out of the window was keeping this diary up to date: I can offer no apology to the masses of addicted readers other than "sorry". Somewhat more painfully, I've let my music lapse (apart from paying gigs or favours); I haven't even found time to bash through piano duets with another physicist.

I haven't yet managed to kick the Lisp compiler addiction, though. Highlights of the last two months: MacOS X port merged; implementing an ANSIly-correct (stupid) array type structure without any impact on user code; improvement in compiler diagnostic handlability; and a data structure improvement leading to a 25% performance increase in the compiler.

Microoptimizations are the most fun, though; right now, I'm working on implementing automatic detection of when modular arithmetic (as is the default in e.g. C, where overflow wraps round) is wanted, and also optimizing constant multiplies (which, on the x86 processor, is a tricky problem). Obviously, what I should be doing is writing up my thesis...

Rencontres Mondiales du Logiciel Libre

Otherwise known as the Libre Software Meeting. This year, after Bordeaux declined to host it on grounds of organizational difficulties, it was held in Metz; since they started organizing it late, it's not surprising that there were one or two hiccups in the smooth functioning, but there was fortunately nothing which interfered with sitting en terrasse and sampling beers.

Most of the action that I was expressly there for was the dubiously-titled "Very High Level Languages for Writing Applications" track, which in practice was a bit of an excuse for several Lisp bigots to get together and plot the next stages of world domination. Mostly this involved talking about real-time garbage collection, but the demonstrations of McCLIM and especially Marc Battyani's FractalConcept Web Application Framework were very impressive.

Also useful was meeting several researchers who, while not following our track, were nevertheless using Lisp to do neat stuff; Axiom and Maxima developers were on hand to inform us that we needed to implement reliable callbacks from C to Lisp in the next six months.

Apart from that, I managed to avoid most of the politics (not all!) by taking a day to go to visit Strasbourg; highly recommended (though avoid cafés on the Place Kleber; they're overpriced and the beer isn't as good). Then 8 hours of train back to good old England.

So while I'm waiting for the fuss^Wdiscussion about (VECTOR NIL)to die down on comp.lang.lisp, here's a new version of CLX.

"What is CLX?", I hear you cry. CLX is, roughly speaking, Xlib for Lisp. It is an implementation of the client-side of the X protocol. So, why "roughly speaking", then? Well, mostly because by all accounts programming for raw Xlib is extremely painful, whereas the macrology of Common Lisp allows syntactical abstractions to be built, allowing for ease of development.

For instance, the WITH-BUFFER-REQUEST macro allows for rapid implementation of extensions to the X protocol. In fairly short order, we have acquired implementations of the SHAPE, RENDER and XVidModeExtension (sic) extensions, so we can make Lisp applications just as pretty as their counterparts.

And, oh look, something nasty did happen to the guys wearing red.

* Krystof sighs at the irony in CLHS 15.1.2.2
<pfdietz> And its interaction with the rules for upgraded array element types?
* pfdietz realizes that those bizarre NIL arrays are strings!

Most Common Lisp implementations purporting to conform to the standard have only one internal representation for strings: it simplifies the logic; it allows for fast string access (no need to do a type test to see how big each string element); it makes type derivation easy. Several implementations can talk different representations, but internally, they're canonicalized to ASCII, UCS-16, UCS-32 or whatever.

Sadly, since we've previously deduced that arrays specialized to hold no objects must exist, and since strings are defined to be vectors specialized to hold a subtype of character, vectors specialized to hold objects of the NIL type are indeed strings.

Aargh. I have a working prototype, but there are going to be plenty of issues involved in sorting this out. At least they're mostly the same issues as would be involved in dealing with the Unicodization of SBCL, so it's not wasted work. It might even encourage me to do some more refactoring to share more code among the six backends.

Quiet. Too quiet. This is usually the time for something nasty to happen to the guys wearing red.

In our case, that means pfdietz comes along, with his mutant superpower of "being able to read the ANSI specification", and blasts holes in implementations. Since the last time I complained about this nasty habit of his, he's made some other unwelcome discoveries: some more stuff about array element type upgrading; some nastiness about keyword argument checking in various protocol methods; SLOT-EXISTS-P being required to work on condition objects (even though nothing else from the CLOS machinery is required to do so); and much else besides.

On the other hand, much has changed for the better in the SBCL world. In addition to the native threads implementation and the ability to build from CLISP, we have an integrated implementation of CLOS (no more bogus CL:CLASS/SB-PCL:CLASS distinction) and consequently a mostly-compliant MetaObject Protocol; an accurate type system, which is in use to do sophisticated type inference at compile-time; and we're up to 10 contrib modules, including an efficient implementation of MD5, a friendlier read-eval-print loop, and an improved extensible stream framework.

Was that worth waiting a month for? I think so.

Busy busy busy (yes, with real work, too).

On the other hand, I have had the time to do enough mindless debugging to enable SBCL to build using CLISP as a cross-compilation host.

Remember way back, when we were looking at ensuring that SBCL didn't actually have any leakage from the cross-compilation host to the target code, so that in fact the sources, and not whatever compiler you happened to be compiling the sources on, determined the nature of the resulting executable? Well, OpenMCL was a decent enough first choice, because it was based on mature technology and had a suitably non-painful debugger.

So there wasn't going to be anything terribly fundamental about making it work under CLISP; "mindless debugging", I said. The process did pick up one or two real portability bugs (depending on the initial element of an uninitialized array, for instance); some annoying portability bugs (CLISP gives a full WARNING on function redefinition, which plays havoc with detecting failures), and one real leakage:

CLISP has a value of MOST-POSITIVE-FIXNUM of 16777215, unlike CMUCL, SBCL and OpenMCL which all have a value of 536870911. This lower value was leaking through into some type declarations, which were then erroneously signalling errors. Fixing this made it all worthwhile: now SBCL can build, in a slightly roundabout way, on a system with only gcc installed. Oh, yeah, and several bugs in CLISP were exposed and fixed as a result of this exercise, too.

In other news, SBCL has native threads on x86/Linux. Cool.

There are times when you stare at disassembly, wondering just how your 'optimization' has managed to cause a tenfold degradation in performance. "This version can't possibly be slower: look, the old version has several full function calls per loop, has to rotate words to get the right bit out, and more besides..."

It turns out that I was completely right with this assertion. The moral of the story is not to test your optimization against something that the compiler is smart enough to constant-fold, for fear of discouragement.

Before I start on this entry proper, I should perhaps say that I find the ANSI specification for Common Lisp (unauthoritatively available as the HyperSpec) a fine document; as an implementor, it gives sufficient freedom to experiment with ideas, while nonetheless pinning down the behaviour in sufficient circumstances for it to be of great use to the user of the language; furthermore, the language itself oozes quality -- all of the operators are designed to interact well with each other; and when there are of the order of 750 standardized macros or functions, this is no mean feat.

However, there are some corner cases that are coming to light; one of them has resulted in a fair bit of work for me recently. From the standards document:

Type upgrading implies a movement upwards in the type hierarchy lattice. A type is always a subtype of its upgraded array element type. Also, if a type Tx is a subtype of another type Ty, then the upgraded array element type of Tx must be a subtype of the upgraded array element type of Ty.

and (from the description of the function UPGRADED-ARRAY-ELEMENT-TYPE)

If typespec is bit, the result is type equivalent to bit. If typespec is base-char, the result is type equivalent to base-char. If typespec is character, the result is type equivalent to character.

Now, consider the universal subtype, NIL. This is a subtype both of BASE-CHAR and of BIT, so the upgraded-array-element-type of NIL must be a subtype both of BASE-CHAR and BIT. But BASE-CHAR and BIT are disjoint, so the only type which is a subtype of both is NIL itself. This therefore implies that conforming implementations of Common Lisp must include an array type that is specialized to be able to hold no objects at all.

So these objects aren't completely useless: they have dimensions, can be displaced to other arrays, and so on; however, the fact that no-one in 16 years has noticed that no implementation actually includes them would indicate that, were it not for a recently-developed test suite, no-one would implement them now, either...

* (aref (make-array 10 :element-type nil) 5)
debugger invoked on condition of type SB-KERNEL:NIL-ARRAY-ACCESSED-ERROR:
  An attempt to access an array of element-type NIL was made.  Congratulations!

So this month's SBCL will be quite exciting, in that it provides a framework for experimentation. Yes, we have a contrib/ directory, wherein things that aren't portable enough to go into a cross-vendor repository and yet aren't stable, documented or mature enough to be included as a supported extension, can live or die as determined by the user community (all two of you).

This can be viewed as a way of involving the users in the direction of the project, or as a way of punting on the difficult decisions. Be that as it may, as of Wednesday, SBCL users will be able to do

* (require 'asdf)
NIL
* (require 'sb-bsd-sockets)
[...]
NIL
* (make-instance 'sb-bsd-sockets:inet-socket :type :stream :protocol :tcp)
#<SB-BSD-SOCKETS:INET-SOCKET descriptor 5 {30FBA761}>

As well as an interface to the BSD socket API, and asdf itself, there is an implementation of rotate-byte, a hack to make pseudo-standalone executables, and a package that hooks in to the read-eval-print-loop to give a different interface.

Cool beans.

So what's been happening since the 21st of December?

In case anyone hasn't noticed, there was Christmas and New Year, the latter of which brought the last release of SBCL in 2002. The usual slew of bugfixes and compiler enhancements; nothing earthshaking, but nice nonetheless. Since it's been such a long time, the first SBCL release in 2003 has likewise occurred; more of the same, but better! (and landing the DEBUG-RETURN enhancement was nice, too).

And in between? Well, writing the first (zeroth, really) draft of my PhD thesis was equal parts scary and terrifying. Still, that's 30,000 words or so out of the way; all I need to do is the remainder of the work. Cosmic Microwave Background perturbations, here we come.