Older blog entries for crhodes (starting at number 42)

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.

SBCL on MIPS still mostly works. It seems, with a little encouragement, to be able to build itself, at least to the point when my hardware dies:

 I/O error: dev 08:02, sector 136384
 I/O error: dev 08:02, sector 136456
 I/O error: dev 08:02, sector 136376
etc. So I am now engaged on backend refactoring, having actually RTFCVSM to find out how to branch... which is lucky, because these changes are tricky to synchronize across six architectures, so I'm glad I don't have to.

WARNING: If you like haiku, look away now, but I don't want these to be lost for posterity...

So this started with Raymond Toy:

<rtoy> Krystof:  Do you remember your haiku for CMUCL? If so, can I use it in my personal CMUCL startup banner?

I'd (on the spur of the moment, a few days ago) come up with a haiku that summarised CMUCL's performance:

<Krystof> cmucl / compiles beauty to fast code / life springs eternal
<Krystof> Ah yes, traditional "wise guy" cheat on the season-word 'requirement'
On the other hand...
<wnewman> steel bank common lisp / compiles beauty carefully / finished by winter
and
<wnewman> openmcl / spring for proprietary hardware / get lisp for free

Dan gets to be a bigger wise guy than me, though, because of these gems:

<dan_b> on axp / sbcl has type issues / is that uint? uh ...
<dan_b> cltl  was / summa theologica / but now outdated
<dan_b> frankly, I'm struggling

Ideas on a postcard for other lisp implementations... we now return you to our regular schedule.

29 Aug 2002 (updated 29 Aug 2002 at 10:14 UTC) »

So, well, a mostly-functioning HPPA port of SBCL has been merged, SBCL 0.7.7 has been released, tbmoore's linkage tables stuff has landed in CMUCL, Gerd Moellmann has been busily cleaning up PCL, Alexey Dejenka's nailed a few more obscure compiler bugs, and I've started reviving the MIPS backend. It mostly works, but sadly not entirely.

On the plus side, this backend is the last of the legacy ones from CMUCL that I care about (I am planning to abandon the support for the IBM RT; so sue me), so after this it should be much more fun... if refactoring compiler code can be described as fun, that is. Maybe I'll be able to help merge the wave of patches to the compiler codebase that have been rolling in recently, too, and even work on some of my blue-sky projects (loop invariants, mmm).

[ Edited to get names more correct ]

33 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!