Mike Schaeffer's Blog

Another one along the lines of My last post. I tried to compile this source file today, using the compiler in my little Lisp:

(define (values . args) (%panic "roh roh"))

(define (test x) (+ x 1))

I got the following result:

d:\test>vcsh -c test.scm
;;;; VCSH, Debug Build (SCAN 0.99 - Dec 17 2007 16:47:30)

; Info: Loading Internal File: fasl-compiler
; Info: Package 'fasl-compiler' created
; Info: Loading Internal File: fasl-write
; Info: Package 'fasl-write' created
; Info: Loading Internal File: fasl-compiler-run
; Info: Package 'fasl-compiler-run' created
; Info: stack limit disabled!
Fatal Error: roh roh @ (error.cpp:168)

Needless to say, fatal errors still aren't any good. However, this one is a bit more interesting than a simple type checking problem. The function %panic is the internal function used to signal fatal errors from Lisp code. The first definition above redefines values, the function to return multiple return values, so that it always panics with a fatal error. This is the kind of thing that, if done in a running environment, would break things almost immediately.

But, the compiler is slightly different.... it isolates the program being compiled from the compiler itself. This is done to keep redefinitions that might break the currently running compiler from doing just that. Redefinitions by the compiled program are only supposed to be visible to the compiled program. Since the above program never itself invokes values, it should never hit the call to %panic... except that it does.

What's happening here lies in the processing of the second definition. The definition itself is transformed a couple times by macroexpansion, first to this:

(%define test (named-lambda test (x) (+ x 1)))

And then, basically, to this:

(%define test (%lambda ((name . test) (lambda-list x)) (x) (+ x 1)))

The second macroexpansion step is the step that looks for optional arguments, and the internal function that parses lambda lists for optional arguments returns three values using values. This invocation of values happens in the environment of the program being compiled, so it hits the new %panic-invoking definition and the whole show grinds to a halt. The 'easy' fix, ensuring that macro expansion is isolated from potentially harmful redefinitions, won't work. Macro expansion has to happen in the user environment, so that macros can see function definitions that they might rely upon.

I don't have a unit test for the user/compiler seperation logic, so I thought when I started this blog post I was going to say something like: 'look, something else fundamentally broken, and without a test case'. That's interesting, but if you need convincing to write unit tests, you're probably already lost. What I actually learned while researching this post is a bit more subtle: it's a fundamental problem, but it's more about the design than the code itself. While the design I have for user/compiler seperation seems to work most of the time, it's not adequate to solve this kind of problem. I'm not yet exactly sure what the solution is, but it won't necessarily involve a missing unit test.

The other day, I had the following (abbreviated) dialog with my little Scheme interpreter:

scheme> (intern! 'xyzzy2 (find-package "keyword"))
; Fatal Error: Assertation Failed: STRINGP(pname) @ (oblist.cpp:451)
c:\vcalc>vcsh.exe

scheme> (intern! 12)
; Fatal Error: Assertation Failed: STRINGP(sym_name) @ (oblist.cpp:269)
c:\vcalc>

Needless to say, 'Fatal errors' aren't good things, and fatal errors in intern!, a core function, are even worse. Without going into too many details, the first call should be returning successfully, and the second should be throwing a runtime type check error. However, the implementation of intern! wasn't checking argument types and passing invalid arguments into lower layers of the interpreter's oblist (symbol table) code, which died with an assertation failure.

To put this in perspective, my implentation of intern! is about five years old, and something that I thought to be a fairly reliable piece of code. At the very least, I didn't think it was susceptable to something as simple as a type checking error that would crash the entire interpreter. Of course, when I looked at my test suite, there wasn't a set of tests for intern!. That might have something to do with it, don't you think?

Here are the morals I'm taking from this little story:

• Do not assume something works, unless you have a complete test suite for it. (Even then be wary, because your test suite is probably not complete.)
• Shoot for more than 60% code coverage on your test cases.
• Don't write your own interpreter, because there are probably hundreds of other bugs just like this one. :-)

I don't usually write posts for the sole purpose of linking to other posts, but this is an exception. This is brilliant. What it is is the USDA's Food Pyramid but adapted to how programmers should spend their time. My one complaint is that it's way too focused on coding. My experience has been that it really pays to spend time on design work and learning to how to better interact with others, be they clients or team-mates. If you can design your way out of a rewrite, or work with your client to recast requirements to save complexity, it can be far more cost effective than even the best raw code.

Last June, I wrote a bit on my experiences with the Cingular 2125 Windows Smartphone. After more than a year, the phone has been a good choice, but there have been several suprises, for both the good and the bad.

• This is the first phone I've used with a web browser that's usable for general web surfing. Most sites render reasonably correctly, and the display is large enough to contain a useful amount of content. It's still not perfect, the browser crashes too often and it is difficult to log into reddit, but this is a vast improvement over conventional phones.
• I installed a 1GB SD Card that is borderline useless. This might be different if I'd been more aggressively installing software or music, but as it is, the primary benefit of having a card like this is that I can now take 40,000 pictures before I run out of space.
• Outlook integration is still incredibly useful, but it's been harder to keep the calendar in sync than I thought. This is probably due to the fact I get lots of meeting invites that change, but it's made it difficult to rely on the phone as the 'authoritative' source for my scheduling information I hoped it would be.
• J2ME is a non-starter on this phone. There is a JVM, but it's buried under a submenu and the applications running on it look more like 'steerage class' than 'first class' citizens of the phone. They aren't integrated with the main application launcher, and their interfaces look like something out of 1988. I really get the impression that the phone has J2ME solely for the purpose of selling into corporate clients with a requirement to run custom J2ME code.
• Given the power of the underlying hardware and the quality of the display, I was hoping to find more games for the phone. My previous two phones both had small collections of J2ME games purchased through my service provider's web site. AT&T has finally started adding games for this phone to their site, but the selection is limited, expensive, and not that great. I did at least find a few games elsewhere that are pretty fun, Atomic Cannon and Nethack. These were both pretty easy to install. Atomic Cannon, in particular, demonstrates the graphics of the phone quite well.
• I don't use the 'Phone as Modem' capability at all. I don't have as many places where I need to use it as I thought. That said, it does work, and would be a nice way to check mail in a pinch.