Older blog entries for crhodes (starting at number 45)

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.

Ha ha ha. It's so simple!

Backstory: the CMUCL debugger has in its help for the debugger, among other things:

 (DEBUG:DEBUG-RETURN expression)
    returns expression's values from the current frame, exiting the debugger.

This is a marvellous feature to have -- it allows spectacularly dynamic interactive programming: "Oh, whoops, I made an error in that function; it lands me into the debugger. OK, from the debugger I redefine the function; then I return from the frame the answer I should have got, and the computation carries on." This means you can patch programs on the fly, even if they contain errors (this is so much nicer than just dumping core).

The catch is that the DEBUG:DEBUG-RETURN command was unimplemented, on the grounds that it would involve rearranging stack frames and so on, making it a "wizard-level" operation. Until now, when a self-confessed Lisp and CMUCL newbie popped up on the lists saying

I have implemented the ability to return a value from a frame chosen in the debugger. The solution is quite simple but it's probably possible to do it a lot more efficient. What I do is basically to encapsulate the code in all function defining forms (defun, flet, labels and function) with

(catch (incf c::*debug-catch-tag*) <original-code>)

It's so simple — the sound you're hearing is the sound of several CMUCL developers' foreheads being slapped.

Hackity hackity hack.

Though despite this seeming mass of work, not many of the grand plans are being brought to fruition... the most major change recently has been

-for early 0.7.x
+for late 0.7.x

Still, SBCL turns out to be quite reasonable as a working environment; it's quite standards-compliant (failing 5 out of 6109 tests in an (independent) ANSI test suite near you); it has support for advanced techniques in Object Oriented programming; it's generally whizzy and comes with spangly bits. My current efforts are going to zapping the last remaining confusion over when it's valid to define things behind the user's back (answer: usually not); maybe sometime I'll find time to implement my nifty plan to integrate PCL with the rest of the compiler more fully.

Maybe I should worry more about coming to the end of my doctoral studies and what happens next, too.

cactus: The answers to the exercises look perfectly reasonable, in the context of the tutorial that you're looking at. Apart from one or two minor style issues, mostly to do with indentation, the caveat that I would mention is that you should be aware that you are being exposed to atypical Lisp code. It's understandable that the tutorial starts with recursive definitions of list processing operators, but in doing so it is less teaching you about how to write Lisp code and more teaching the the concepts that underpin list manipulation.

To take as an example your final two answers. To compute the fibonnaci numbers, you give a perfectly good answer that reflects the natural recursive definition:

(defun fib (n)
  ;; altering the rules slightly by defining fib(0) as 0,
  ;; not 1.
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

but this happens to scale really badly. Try tracing the execution of, say, (fib 20) – or timing execution of (fib 30) – you'll see a large number of calls, all computing intermediate values. The neat bit about Lisp is how easy it is to fix this scaling problem:

(let ((table (make-hash-table)))
  (defun fib (n)
    (or (gethash n table)
        (setf (gethash n table)
              (if (< n 2)
                  n
                  (+ (fib (- n 1)) (fib (- n 2))))))))

where we cache previous answers in a hash table. Alternatively, we should perhaps solve the difference equation and simply write

(defun fib (n)
  (round #i"(((1 + sqrt(5)) / 2)^^n - ((1 - sqrt(5)) / 2)^^n)/sqrt(5)"))

or else, if the rounding errors start to bite in that version, rewrite as

(defun fact (n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))
(defun fib (n)
  (declare (fixnum n))
  (/ (loop for k fixnum from 1 to n by 2
           sum (/ (* (expt 5 (/ (1- k) 2)) (fact n)) (fact k) (fact (- n k))))
     (expt 2 (1- n))))

On a different note, for your my-merge problem, it would be rather more idiomatic to write it as:

(defun my-merge (x y)
  (reduce #'* (mapcar #'+ x y)))

(I personally wouldn't use cond in any case when there are only two branches, but that is a style matter that reflects how much editor macrology you're comfortable with).

I hope that helps.

ObRelease: SBCL 0.7.10 today; with a large slew of bugfixes, particularly to CLOS. Not a bad Common Lisp environment, even if I do say so myself.

Phew. Just as I was beginning to despair of the mountain of patches and exciting new stuff to look at (tbmoore's linkage table, which allows CMUCL to resolve references to foreign code at runtime; Gerd Moellmann's "PCL for the 1990s", which includes so many bugfixes along with new optimizations; bug fixes, McCLIM, and so on), along comes a mail that makes my heart sing, and restores my faith that it's all worthwhile. A chap of whom I've never heard takes the lisp environment that I work on, and makes it work on a previously unsupported OS. Nice work, Valtteri.

Meanwhile, quasi-audition for music school tomorrow; fun fun fun.

There's nothing quite like returning from holiday to a bulging inbox, this time including e-mails pointing out that the aforementioned bugfix introduced some hideous performance penalties.

Three iterations later[*], and the problem is more-or-less solved; the performance degradation (if any) from the fix I merged today is down in the noise.

Bugs bugs bugs... and speaking of bugs, the new bugs are probably about to arrive, fresh-faced and ready to go... teaching them the realities of undergraduate physics will be a pleasure as always.

[*] including one overnight revelation — corroboration of the notion that one gets some excellent ideas in one's sleep.

Remember those nasty problems regarding restarting lisp that we were having? No? Well, let me refresh your memory.

The symptoms were that a newly built lisp would die on startup, despite having been running safely for the previous 10 minutes or so compiling the Common Lisp Object System (which is marvellous, incidentally; maybe I'll chat about it another time). Anyway, this was only tickled by a bugfix patch of mine, so it got dropped.

Until this week, when I noticed a way to reproduce it trivially in our current builds. This elevated priority sufficiently for Dan to fix the symptoms. Phew.

But the really good news is that this fix has unblocked the bugfix patch that tickled the problem in the first place; which is nice, as it happens, because we had a user report the problem (again).

...and the backend cleanup effort is merged. 1900 lines of code have been deleted, with a common interface defined for six different architectures. While this may sound like quite a lot of code, it should perhaps be borne in mind that the project codebase is of approximately 180000 lines...

Still, it's a definite improvement; it's one less thing for the intrepid adventurers who feel a need for native-code compilation of Lisp on, say, ARM or IA64 to get wrong. And I've spotted several obscure bugs during the refactoring process, too.