Older blog entries for wnewman (starting at number 18)

These days I am at least as much an amazed spectator as active participant in free software development. Alert readers may have noticed that I haven't posted to advogato in, um, two years. But, I did just finish an algorithms paper (with some early guidance from pfdietz and with helpful feedback from crhodes).

Now that I have finally gotten around to getting a website (to have someplace to point Citeseer to, donchaknow) I might find myself tempted to write something there. Perhaps something totally off-topic for advogato; except I did that already, huh? So perhaps something about lizards again but this time with pictures? I can brood about it over Thanksgiving, anyway. Then, if it happens, there'll probably be some pointer to it here.

16 Sep 2002 (updated 16 Sep 2002 at 15:41 UTC) »

When I come home quietly at night, I usually see some unobtrusive neighbors -- several lizards who hang out over my door. I theorize that they've learned that insects have their navigational systems jammed by the lights and crash land on the walls, and jack-lighted bugs taste just as good as bugs hunted down in more sporting ways.

The lizards are weird things which look like they were bred to live in dim caves, with pale uncamouflaged bodies and outsized dark staring eyes. They're never, ever, out in the daytime, and I wonder whether their seeking out the artificial light is learned behavior which overcomes their nocturnal instincts, or what.

So many questions, actually. What are the feng shui implications of night artificial light door lizards?

Most everything seems to have become complicated. Compiler patches. Debugging problems. Even birthday shopping. (Pondering for 20 minutes or so, I finally decided I knew just the thing, drove to just the store, and found out that it's backordered indefinitely.)

Hopefully this complexity is just a statistical aberration instead of the foothills of a long-term rising trend. Or failing that, I hope I can find a trick to get smarter or sleep less or something. Or, as long as I'm wishing, both would be nice.:-)

not a bad programming day, overall, but a slightly iffy SBCL programming day

What does PARSE-LAMBDA-LIST do? Does it parse lambda lists? Well, that is one of the things it does.

As they say, "To foil the maintenance programmer, you have to understand how he thinks."

a new apartment! hopefully this time without neighbors spraypainting graffiti on the structures they aren't burning down...

In the medium term, I should now have fewer excuses for not getting s/w things done. Just now, however, I haven't quite got the two steps forward bit yet and in the meantime have taken a step back, as the ongoing confusion of moving has promoted my usual dignified absentmindedness to fullblown ditzy scatterbrainedness.

Meanwhile people keep sending patches for SBCL. As long as I don't manage to mess up not only my own mail spool but also the SourceForge list archives, I should have a good chance of merging them presently. Meanwhile, thanks, guys.

In unrelated news, not only have several #lisp IRC denizens decided to try Go, I've found a strong (master) Chess player IRL who is actively interested in learning, which is an interesting experience for me. (Gosh, he learns tactics fast!)

It looks like my next computer will be a $350 Athlon with 512 Mbytes of memory. I rather wish that instead for $1000 or so I could get either a 64-bit single CPU or -- what would be rather niftier IMHO -- a 64-way hypercube with 4 Mbytes or so of memory at each node. Not that I'd have the s/w for either, of course. Maybe if I wait 'til Christmas?

I'm still not doing much programming to improve SBCL, but at least I'm doing quite a lot of programming using it, benefitting(intransitive) more than I used to even if not benefitting(transitive) as much as I once did.

Hardware bit rot proceeds apace. My once-reasonably-spiffy 700 MHz PIII laptop is looking distinctly anemic these days.

On the other hand, I'm still using keyboard, von Neumann architecture, and IPV4. What's up with that?

Egads. I expected there would be undetected CMU CL dependencies lurking in the SBCL build process, but the :JUST-DUMP-IT-NORMALLY thing is somewhat more horrible than I was really expecting. Live and learn, I guess. (And hope we can bootstrap from some unrelated compiler someday...)

I hope my OpenBSD CDs will arrive someday. Oh, happy anticipation. Of course, I still have my not-entirely-pain-free memories of the 3.0 upgrade, so there is a certain admixture of free-floating anxiety in the happy anticipation. But any version which makes getrusage() nondecreasing so that I can actually profile my Lisp code without trying to set up a patch branch of the kernel (like the one I forgot to maintain in the 3.0 upgrade, yep) is off to a good start in my book. Godspeed, mail monopoly. May you live up to whatever shining glamour it is which inspires people to support detailed micromanaged franchise monopolies in telecomms and transport and health care and whatnot, instead of being weighed down by any pointy-headed theoretical or rock-ribbed libertarian skepticism about incentives and public choice theory or historical performance or, for that matter, the gritty reality of the thunderstorms outside. Go mail go.

It's hard to believe I've been stuck in the same stupid module in Go programming for so long. How hard can this be? On the plus side, it's still cool (though less intensely cool than, say, a month ago, somewhat earlier in the process of being stuck in this module) that I noticed that the failure cases of this part of the algorithm match, in considerable detail, the the failure cases of whatever my subconscious is doing when it looks at similar problems. Now if only I could get this and a few other things up through a few layers of abstraction to where they'd actually solve complete problems, or else step into a parallel universe where I were an academic with nice incentives to publish cool partial results...

Come the nanotech revolution, the technology may become available to visit poetic justice upon people who, in an earlier less-advanced era, configured their car alarms so that they automatically announced their entry to, and exit from, their cars at all hours (e.g. 10:45 pm, currently) to any other apartment dwellers who might otherwise have slumbered foolishly unaware. One can only hope that this power will not be abused.

I have done hardly any SBCL programming for some time. However, I did just finish (modulo some bad naming choices that Dan Barlow pointed out, which I still need to fix) fixing the minor problem that accidental stack overflow crashes the entire Lisp process, even in code compiled with the "safety" optimization option maximized.

Naysayers may gripe that the new checking code is pretty inefficient. I'm more than usually pleased with this change nonetheless, seeing as how the old response (for, IIRC, at least five years, going back before the CMU CL fork) would've been a Unix-level error message (e.g. "illegal instruction") and a shell prompt. Progress...

(Life? What life? Maybe next week.)

"Do not want to go through Mines of Moria, as suspect Balrog still angry about bad date we went on back in Second Age." -- The Very Secret Diary of Gandalf the Grey

My hacking on SBCL has slowed to a crawl, in large part because although it's far from perfect, it works well enough it's attractive to work with it instead of working on it. But it would nice if it didn't crash when you overflow the stack, wouldn't it? Maybe I can get that to work presently. (It would also be nice if the system's foundations were solid enough that trying to get stack checking to work didn't expose other problems...)

I've moved to a new apartment. "Quiet" and "convenient location" were what I wanted. I got "convenient location" anyway. I tested "quiet" by standing in the apartment and listening carefully, and wandering around for a while. Alas, the universe blindsided me: I had no idea that the Autosound business in the strip mall directly in front of me installs superpowered speaker systems in automobiles, much less that they test them at maximum volume with the garage doors open. It blows my mind that city nuisance laws permit this. For that matter, it seems pretty strange that their landlord tolerates it, since even if he doesn't give a damn about his neighbors, I'd expect it to cause enough friction with his other tenants that it would impact his pocketbook. Oh well.

"The universe is not only stranger than we imagine, it is stranger than we can imagine." -- J. B. S. Haldane

programming programming programming

Today I had occasion to write three dozen lines of code which deserved a hundred or so lines of comments containing explanation, several examples, and a DANGER UNEXPLODED MINDS header. Generally I believe that too many comments strongly suggest that something is wrong with the code. In this case I did it anyway. The new code is tricky because it's generalized in at least three ways (over maximization and minimization, over upper and lower bounds, and over BOOLEAN, REAL, and an application-specific domain which is only partially ordered). Thus, the alternative is twelve (two extremization operations times two bounds times three domains) more straightforeard functions, four of which already existed at the time that I discovered the need for the third generalization and started writing the all-in-one generalized version. Exploding my mind once and only once has got to be better than feeling my brain atrophying at superluminal speed as I try to proof-read twelve different fundamentally equivalent variant functions. And it's not *that* complicated, anyway, it's just that most humans, including me, tend to have trouble thinking accurately about double negatives and triple negatives, even whan as in alpha-beta search it's really fundamentally simple. (Rationalize, rationalize, rationalize?)

Also I think I may have figured out why some related code is so astonishingly slow. It's a menagerie of objects sending a storm of "I've changed, update yourself" messages. I've spent quite a lot of time off and on trying to understand the problem. Now I think I see a way for a cascade of update events to require a number of operations which grows exponentially in the length of the cascade, even though there are efficient, reasonably obvious update sequences which are nearly linear in cost. I suspect that this kind of pathological update mis-ordering is actually happening in my ridiculously long problem cases. I hope so, since it should be easy to fix by replacing my old trivial obvious eager update scheme with a few dozen lines of code (a FIFO queue, some flags, and perhaps some heuristics).

I wish I knew a better way of debugging things like this mis-ordering. It seems as though it should be easy to spot exponential growth! But it's obscured by a thicket of other polynomially large stuff. By the time that the test case is big enough that the exponentially large misbehavior would dominate, the number of operations the system is doing is so large that it's really hard to see any pattern at all. Hmm.

I also wish I had known what I was doing before I started. I suspect I might be rediscovering and reimplementing what practitioners in another specialty (truth maintenance systems?) consider to be the basics. I doubt, though, that these basics are universally known, or at least that they were universally known in the late '80s. SBCL's compiler is very slow, and when I use a debugger to follow what it's doing, I see it transforming code and inferring types and updating this because that thing upstream has changed over and over again. It's rather reminiscent of what I seem to have stumbled over in this unrelated code. As I've gone over the SBCL code (mostly looking for bugs, not performance issues) I've seen plenty of signs of serious effort (in, I think the late '80s and early '90s) to make it run faster, but no sign of any attempt to analyze and rationalize this kind of update scheduling. Hmm again.

In another kind of update problem, my dark engines of computation are grinding out and testing sbcl-0.7.1, and I hope it will not have an undetected severe bug as sbcl-0.7.0 did...

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