Older blog entries for wnewman (starting at number 13)

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...

I spent much of the day doing applications stuff with the current CVS version of SBCL. There were no unpleasant surprises. So far it looks as though I can actually release sbcl-0.7.0.

"Applications stuff" ended up being mostly ripping out my old nasty-and-becoming-nastier a-functor-is-a-macro implementation of ML-style functors and replacing them with a package-based implementation, where a functor is essentially a file full of code which, with help from some nicknaming and other hacks, maps domain packages onto a created package. So far it looks reasonably good: various rough edges, but none of them dangerously close to the tricky parts of the stuff I'm trying to express. And rough edges and all, the functor-based code seems substantially cleaner and closer to what I'm trying to express than either the ancestral "functor? whazzat?" OO-and-stuff code or the intermediate a-functor-is-a-macro code did.

Of course, ML does this better. Or mostly. Last year, when I was playing with this in ML, I did end up very frustrated with some natural-seeming stuff involving mutually recursive types. But certainly ML does the easy cases much better. And that's not necessarily a put down: it can be a real danger sign when my small programs already seem a little kludgy when I know I still need to scale them up. So I'm still somewhat nervous about the upcoming push to generalize the current code.

Before we get too much closer to the end of the line with Von Neumann architecture stuff, it would sure be nice if someone could put together a language which (1) did Lisp stuff, (2) shaded smoothly over into statically typed stuff like ML, and (3) didn't bog down on too many reasonable type relationships the way that ML did in my experiments late last year. Or, if its type inference logic did bog down, then having some way of being lifted out by suitable manual declarations.

Meanwhile, I haven't actually hit any real gotchas with my Lisp and duct tape approach, or even spotted them on the horizon. Maybe I'll be OK.

Not a bad day.

Hopefully, my next diary entry will not be whining. It's just that while there are many nice things in my life, they aren't all that newsworthy.

As a marginally geeknewsworthy nonwhining item, I'll point out that it's nice that it's relatively easy to find unused electrical outlets in the Atlanta airport, and beyond that there are even laptop mini-office-with-T1 facilities for rent (at $36/hour).

Now, back to the regularly scheduled whining.

The ordinary level of US airline service mediocrity extends to getting you into the system's hub so late that your connecting flight has already departed, then telling you to wait on standby for the last flight of the night so that you can listen to the attendants turning away volunteers willing to stay overnight. That way, when the attendants finally deign to tell you that yes, you are involuntarily stranded overnight, you can more fully appreciate your position in the great scheme of things.

Delta Airlines, however, goes above and beyond. They methodically check their planeloads of stranded passengers into a motel far enough from the airport that the shuttle to the airport has a 25 minute cycle time, and they are serenely untroubled by the way that their chosen motel uses a single 8-passenger van to operate its shuttle service. (After I was one of more than 10 passengers left behind by the first van visit, I took a cab. The driver tried to charge me $22 dollars for the $10 trip. Welcome to Atlanta.:-)

I can offer a heartfelt recommendation for Delta Airlines if you enjoy the kind of warm fuzzy feeling you get from this kind of thing. (And after my Atlanta double whammy, it may be a while before I can drink Coca Cola without an ominous feeling of impending disaster.)

I'm still working on sbcl-0.7.0 after three months, aka "on the order of a month".

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

If you define two similar and closely coupled but different classes named DEBUG-FUNCTION in two different packages, you're off to a solid if unimaginative start. Don't neglect the basics just because they seem pedestrian.

Now, set up two independent ways to associate the debug names of functions with the function objects themselves. CL:DESCRIBE and CL:FUNCTION-LAMBDA-EXPRESSION look up names in the slot of the function object itself, but BACKTRACE and other logic in the debugger looks up names by finding the function's DEBUG-FUNCTION object and looking up the name in a slot in that DEBUG-FUNCTION object. (Actually the debugger looks up the function's DI::DEBUG-FUNCTION object, then looks at a slot in that object to find the C::DEBUG-FUNCTION object, then looks up the name there, as per the name confusion described in the previous paragraph.)

So far, the two systems look redundant (as in "violation of once and only once", not as in "reliable because one can carry on when the other fails"). That's good, you've caused quite a bit of friction and confusion already, especially when you hard-code a lot of the lookups by cut and paste programming instead of running through common functions defined for the purpose. But you shouldn't let up while you've got the maintenance programmer off by balance, by letting the two redundant systems be independent. This is your chance to deliver a mighty blow for chaos by coupling them in a bizarre, fragile, critical, poorly- or un-documented way. Why not store the C::DEBUG-FUNCTION objects in a per-COMPONENT list (where there are in general multiple functions per COMPONENT, and they're lumped together in the COMPONENT for purposes of block compilation and GC and stuff like that) then decide which DEBUG-FUNCTION of the list corresponds to which function object by testing for equality of the per-function-object name value with the per-DEBUG-FUNCTION name value? Wouldn't that be cool?

The Dallas Bach Society tends to do very good concerts, and last night was probably no exception -- not one of their masterpieces, but very good nonetheless. But oh my! seeing Handel's _Samson_ after the last month of crazy acts and crazy rhetoric is freaky enough that it's hard to come away with as strong an impression of the music as of the content. A suicide attack against a prestigious building filled with people of a rival civilization, check..

Mahoah (i.e. Dad): Come, come! No time for lamentation now, no cause for grief; Samson like Samson fell, both life and death heroic. To his foes ruin is left; to him eternal fame.

Brr.

It's enough to make you think, you'd think. Although if I understood correctly the remarks of the VIP (artistic director? I dunno) between acts -- something about last month's events being an attack on the values of our civilization, and after some attendance problems at other public events he was grateful to us for upholding our civilization's values like early music -- I'm reminded that it doesn't necessarily makes you think deeply, at least not in the first month. (Not that I have had a shortage of reminders..)

Oh well, to knee jerk is human. (And as of this writing David Friedman quotes a noteworthy remark on the subject here.)

How do we measure the changing of the seasons? It gets harder to find good fresh fruit. It gets easier to find good classical music concerts.

I thought I was going to see a good pop music concert, too, since my brother saw the Twang Bangers (sp?), loved them, and convinced me to go see them when they hit Dallas last Friday. But Everything Is Harder Than You Think. (Did I mention that once I finally got SBCL to work again, sometime after my last diary entry, my ISP's connection went down for the day so I couldn't check it in?) Unfortunately the venue the TBs were booked (Sons of Hermann hall) in was so laid back that we showed up, couldn't get anyone to sell us tickets or tell us when the show would start, waited half an hour until second hand cigarette smoke got to my SO, and bailed out.

My last article was grumping about complex software which arguably was fundamentally broken inside when I started working on it, and which had become unarguably broken outside by the time I started grumping. Now it's no longer so unarguably broken outside, and is arguably less broken inside too, so life is better. Now if only it were last month or so, life would be even better, but I haven't figured out how to get everything.

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