dmaze

For no terribly good reason, I'm writing a 6.035 Espresso compiler. (I told obra last night, "I want a compiler to hack on.") I'm doing this in Python, since that's a fairly sane (if weakly-typed) OO language, and the various arcane things I can think to do with it are easy. There aren't obvious parser/scanner generators for it, so I'm hand-writing a scanner and an LL(1) parser.

Having gone through this exercise, I'm almost done (can't deal with function-call as statement or interesting things on the left-hand side of an assignment) in about six hours of work. This makes me wonder what the motivation for tools like lex and yacc are. For lex, regexps for many things are almost overkill; my scanner is a state machine that builds up words, checks to see whether they're keywords, and emits an appropriate token. This is a little simpler for being a Python generator function (so I can return multiple values via yield), but it feels like a smallish constant factor away from equivalent C code and about as much code as the lex description. And in all that's 300 lines of code; is the code-space savings worth the loss of debuggability you get using a tool?

Pretty much the same thing can be said about yacc. Hand-writing the LL(1) parser was pretty easy. Maybe a table-based LR(k) parser has a smaller code size so it runs better on old machines? For your trouble you get zero debuggability, though possibly better performance than a recursive-descent parser. At MIT I used ANTLR, an LL(k) parser generator, but I don't think I get much beyond some automated munging of the grammar. My impression (not that I'm trying here) is that error recovery sucks in LR parsers and it's a little better in the LL world. yacc makes you munge your grammar less but you still need some work for things like operator precedence.

So if these tools don't generate fast or understandable code, and interpreting their output/error messages involves understanding their theoretical basis, and they make code harder to debug, why do they get so much use?

ET had a CCG-style game entitled Cthulhu: The Mercifully Uncollectible Card Game. It had the important feature that you had two key stats, Sanity and Knowledge; you started with 50 SAN and died if you dropped to zero, but whenever you lost a SAN you gained a KNOW, and you could use your KNOW to play cards out of your hand.

This corresponds scarily well with my job. Like, I've confronted the horror that is W3C XML Schema: it doesn't disgust me any more, which is probably bad, but mostly because I've converted the SAN loss from reading the spec into knowledge. Which then brings us into the fine world of Lovecraftian W3C specs...

XML Schema. KNOW 6 / 5 SAN. Specification. An oily black cloud that validates XML documents.

WSDL. KNOW 3 / 3 SAN. Specification. A screaming headless specification with a thousand young. Gain 2 KNOW if WSDL and XML Schema are both revealed.

Infoset. KNOW 2 / 4 SAN. Specification. A terrible tree-shaped mound of square brackets that devours all it comes across. +2 to attack any other specification.

The one terrible problem, of course, is the analog of Lightning Bolt, in which every player gains a single momentary glimpse of the horror of the entire web services specification series...I can't decide whether this should be Semantic Web or WS-Unspeakable.

Unlike much of the rest of the world, I seem to have had yesterday off. (Either that, or I'm about to go to work and get a rude surprise.) But I actually managed to get things done for once:

• Laundry.


• Zipcar'd to Furniture Store of DOOM! in Natick. It was impressive, and I'm glad I went, and I found a bed frame I liked (could, actually, be this, though their online catalog seems a little sparse), didn't actually buy anything. (Do these things normally cost $600-1000?) Didn't catch a movie.


• Since I had the car and was in the area, drove around Framingham kind of aimlessly for a bit, then rail-geeked around the commuter rail station. Maps show one line heading north and two south from Framingham, and somewhat surprisingly, they all seem to still be active.


• Installed "new" hard drive I bought in June. Started the long and arduous (well, long, anyways) process of formatting it; exhaustive badblocks check looks like it'll take a couple of days.


• Started poking at wireless router. Only useful if I can get a kernel onto it that supports IP-over-IP tunnelling (or perhaps IPSec, though I don't understand that terribly). If I can get a shell on it, I'll see if the Linksys kernel supports it (unlikely), or if one of the prebuilt kits out there supports it (only vaguely likely), before trying to build my own thing. Handily, I already have a Decaf compiler in Haskell for it if I need that.

watertown's syslogs think we lost power last night, with it being on at 1 AM, off at 1:20, and back on for sure at 1:28. The fan in the bedroom woke me up both when it went out and when it came back. Couldn't fall back asleep, finished reading fantasy trilogy I was working on, made it back to bed.

So this morning the network was down. donut was doing the thing recently it's been doing, which is being stuck on

GRUB Loading stage1.5...

GRUB Loading.....

(So, it found the boot sector, loaded GRUB's stage1, which loaded stage1.5, which got stuck loading stage2?) I kind of suspect this is the hard drive being picky, but then why would it find the boot block? At this point the system is old enough that I'd either want to consolidate it on to sol-draconi or go with the new-donut project ("build the house router into a Linux-based wireless AP").

watertown's subsequent reboot (to get ntp and zhm) wasn't entirely happy either. It booted fine, but the second monitor came up in 640x480 and off by a bit. So my background on the second screen was a nice picture of the lavender line, at a blue-over-purple signal. (The good news is, when I popped up an xterm, it was still the right physical size, so that bit of infrastructure definitely works.) Yay kicking the X server.

{1} dmaze% units
2084 units, 71 prefixes, 32 nonlinear units

There's this program called units. It does everything. Well, it won't read your email. But you can do things like find out how big that "120 GB" hard drive really is:

You have: 120 gigabytes
You want: gibibytes
* 111.75871
/ 0.0089478485

What about cooking? Iron Chef Units can figure out how much butter you need:

You have: 2 tbsp butter
You want: stickbutter
* 0.25
/ 4

I hear they say, "a pint's a pound the world 'round." Is it?

You have: 1 pint water
You want: pound force
* 1.0431756
/ 0.95861142

Hmm. We should check to see if it's versed in the classical sciences, like, say, alchemy:

You have: lead
You want: gold
* 1.0519553
/ 0.95061071

Unfortunately, it doesn't seem to know about ISO standard units:

You have: 364.4 smoots
Unknown unit 'smoots'

I finally have watertown up and running again, with connectivity to the outside world and everything. I was kind of cranky that Debian unstable didn't seem to have gotten any more usable in the past month. But Gnucash's issue, for example, was that if the "save window position" option was on it fervently believed it should move the main window off the bottom of the screen, which was the same problem as before. And LogJam seems to be working fine, don't know why it didn't start before.

Verizon DSL, if it wasn't obvious, is a bad idea. We seem to have a "business" account, for reasons unknown. It uses PPPoE. Ick. And if the modem loses connectivity at all for any reason, when it comes back up we get renumbered. So now we're on our third external IP address in under a week. This is irritating for me.

Need to figure out wiring. Should look into conduit-type things more; Home Depot had PVC conduit for about $2/foot, which seems like a lot. The new-donut plan may be to replace it with an off-the-shelf "broadband router" or some such that runs Linux, and move the data on to a machine a step or two forward on Moore's Law, but CompUSA in Braintree didn't have the particular model the Slashdot article mentioned. They did have something with a proprietary 802.11 extension to get 35% more speed if you use their branded cards, so you could have only 48 times as much internal bandwidth before you hit the cable modem pipe to get your Web pages. For only twice the price I was expecting. Woot. Should feed model numbers into Froogle, and search terms into normal Google.

I finally got the nnrss backend in Gnus working, so I have something I can use to read RSS feeds. I only have a couple in there now (the one for the donut.mit.edu blog and Slashdot's); are there any I might be interested in? It looks like there are a couple listings but they're not too useful just because of sheer volume and it being hard to tell if a particular feed is actually worthwhile. I'm open to suggestions for things people like, or think I might like, or even just dumps of your .meetings file or equivalent.

I finally got around to doing the first bit of work necessary to make my desktop machine, watertown, be functional again. I went ahead and opened up the machine, took out the power supply, broke the "never open this seal" seal, and took out the old (violates FAA noise regulations for aircraft in residential areas) fan. It turned out I had a fan of the right size lying around; after a quick Home Depot run and some application of wire cutters, wire nuts, and electrical tape, I have a functional, more normally noisy machine again.

Now I just need to remember what else it was that was wrong with this. The ergonomics aren't great but better than my laptop. The two screens are nice, but I should find a window manager that deals (again) or switch to XINERAMA (with one 1600x1200 and one 1280x1024 display, though?). There's the generic "it's slow"ness, which I think is mostly the CPU (a 700 MHz Athlon), and the generic "not enough disk"ness (a 20 GB hard drive partitioned a bit much, but with 8 GB for Windows 98, 10 GB for various chunks of Linux, and 2 GB wasted, where some of that last bit is because of a bad spot on the disk). More memory would be nice, but 256 MB is adequate. So for a couple hundred bucks I could turn this back into a modern machine. But for a couple hundred bucks I could also get a new machine. I'll figure this out the next time I want to spend money.

I was going to update the firewall on my gateway machine at home to use iptables and set the source address on outgoing SMTP packets to come from the tunnel address, rather than the "normal" external address, so those packets don't get dropped by RCN. I was also going to put some energy into Debian things, and totally failed to. (Though it looks like some angry mail started getting exchanged between people not me over my packages, and the right answer might just be "go back to a year ago before everything got messed up". I wonder if it's easy to do that with cvs-buildpackage, and if it's easy to do that with Subversion.)

In positive news, I at least got to getting train stuff, finally, so now I'm exercising my meager woodworking skills. Yay rolling critical failures.

I figured I'd upgrade the kernel on washington-street-elevated (my work desktop) to try to get around some NFS performance issues and maybe avoid the most recent local-root exploit. So from SIPB, remotely logged in, I used rpm to update the kernel RPM, and rebooted. Shockingly, it didn't work. I realized when I couldn't ping wse later that I had kind of forgotten the basics of Linux kernel updates ("rerun lilo, dumbass"); what I wound up with was the old kernel with no modules, which was pretty useless. It only took half an hour or so of fighting with that and the NVidia display driver module this morning to get everything back in working shape. But really, I should know better than to screw things up like this.

I'd like a function, in any language I'm using, to run a child process and collect its output, but to also kill that process and all of its children after some timeout. This is okay to do in C, provided of course that you've immersed yourself in Advanced Programming in the Unix Environment, and in fact we have a program that runs a child and kills it after some timeout. Needed to hack it to set up its own process group to really get all of the children, but it works.

So now I want to do the same thing, but in Python. Except that the environment I'm running under uses threads. Uh-oh. And I can't set a signal handler not-in-the-main-thread, so a direct port fails. Oh, and running our C binary fails, too, mysteriously. (Could be that the top-level process doesn't intelligently handle SIGTERM.) I can actually set a timer as a thread pretty easily in Python, but calling os.kill() from the timeout handler doesn't seem to have an effect, or more appropriately, it kills the top-level process but not any of the children. Grr.

We're trying to figure out how fast some code is running on a Pentium 3, and we're using a magic instruction that will give us the cycle counter. Dividing number of cycles by number of loop iterations gives 1962 cycles per iteration. But this number seemed unreasonable to us, so we went and looked at the assembly output of gcc.

The loop has 3772 instructions in it. According to the P3 manual, floating-point instructions pipeline but never run in parallel with each other (except for the FXCH instruction). There's 1007 FXCH instructions, and another 66 instructions that aren't floating-point. Assuming that the scheduling is perfect (doing the first couple of dozen instructions on paper, it isn't) that means that the loop could run in, at an absolute minimum, 2699 cycles per iteration. Which is much more than 1962. Something is wrong here...