Older blog entries for wnewman (starting at number 20)

In case anyone is interested in the somewhat obscure problem "how could I generalize the concept of interning and sharing unique DAGs so that I can allow the interned graphs to contain cycles?" or in any other formulation of the graph minimization problem described in Guido Tack's online notes, feel free to check out my latest attempt to solve the problem as a Common Lisp prototype program, with an unreviewed preprint describing the basic algorithm.

(The problem comes up in various fields. One example is detecting the equivalence of arbitrarily complex cyclic types in programming languages. Nonincremental minimization algorithms have been known for a long time, I'm trying to do it incrementally.)

I have some comments on the recent http://www.defmacro.org/ramblings/fp.html article on functional programming, and I decided I might as well post them here and send the author a pointer rather than just putting them in an email.

(You are approaching a skirmish in the language wars! Hit *BACK* now!)

I like functional programming, and I liked the http://www.defmacro.org/ramblings/fp.html article, but I think he probably should present more disadvantages up front.

One of the reasons that I prefer Common Lisp to Haskell (and why others prefer ML variants to Haskell) is that there are things which are clumsy or slow to express in purely functional form. Okasaki's _Purely Functional Data Structures_ is a marvellous book well worth reading for other good reasons, but one smaller benefit of reading it is that some such things come through there.

One annoying performance issue for me is hash tables; in an imperative language, it's straightforward to use the idiom of hash index into a modifiable collection to get O(1) lookup. Good luck doing this in FP! And, if you tell people that they should rewrite their BDD packages for reliability and clarity and shareability in Haskell instead of C++, and tolerate the extra O(log2 1E7) performance hit of doing all their cache lookups in nice purely functional search trees instead of ugly imperative hash tables, you will encounter some sales resistance --- though perhaps not as much, in the eventual runout, as if you conceal this performance issue from them and let them discover it for themselves.:-|

The issue of making small incremental modifications to large indexed or cross-linked data structures isn't just an algorithms performance issue, it can also make programs difficult to read and think about. I have done a lot of work on programs to play the game of Go, where on each move a player places a stone on one of the 361 points on a board. At various times I have written complete programs in C++, CL, and Haskell. In the imperative languages there is some programming hassle involved in making the changes undoable (so that you can try a variation, then backtrack to the starting point to try another), whereas you get undoability for free in Haskell; but in Haskell I found considerably more hassle in trying to express the small changes without doing a deep copy of potentially very large cross-linked data structures. It seems to me that this is a fundamental issue, not just a symptom of my naivete about functional programming. It might not be a big issue for an Erlang telephone switch, because I expect most of the state in such a switch is tied to an individual call, interacts weakly if at all with the state of other calls, and goes *poof* when the call ends. But if you tried to write, say, a MMORPG server in a purely functional language, I would expect that the ongoing small modifications to the complicated shared global state of the world would be a source of programming pain.

Also, purely functional languages seem to be unusable without laziness (to create cycles) and the purely functional languages people have not convinced me, as a casual user, that their handling of laziness is completely ready for prime time in large hairy systems. The difficulty of debugging lazy code is a minor issue; the difficulty of bounding the performance (especially heap usage) of complicated lazy code is worrisome, a potential showstopper. I would be very nervous about planning to develop a large Haskell system for something complicated and not similar to existing FP software (perhaps the MMORPG server example) without doing some serious investigation into that. I think it might be easy to end up with a server which failed from heap exhaustion when lazy-variable placeholders held pointers into futures which "common sense" shows could never happen, but which aren't manifestly unreachable and so therefore aren't garbage collected. Both my intuition and my superficial reading of the mailing lists suggests that such bugs are not hard to create, and can be hard to test for and hard to debug. The existence of various large FP systems successfully "used in anger" is reassuring, but only incompletely so: it's not hard for me to come up with a story why from the ability of version control systems and telephone switches and compilers to manage this problem it does not follow that it's manageable for all systems.

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

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