Older blog entries for pfdietz (starting at number 15)

I sent the pdf of the ILC 2005 paper off last week, on the deadline day. Now I just need to register and reserve a rental car. Oh, and make the slides and practice the talk.

The gcl ansi-tests suite is close to done. I'm scanning back through the spec, filling in parts I missed. Compiler macros, various declarations. DEFINE-SETF-EXPANDER needs tests.

I've also started on a new Lisp testing project. It'll be located below the ansi-tests directory in the gcl tree, but it's not part of that test suite. I want to test that most undefined situations in the spec signal errors in safe code. The purpose is to make safe code truly safe (no buffer overflows or other potential security problems). The exceptional situations in the standard are just inadequate for this.

I've added a new feature to the RT module in gcl ansi-tests. It can now do 'extended random regression' testing. This involves repeatedly executing tests drawn randomly (with replacement) from the set of tests that normally pass. It stresses the system, looking for dependencies that the tests in their original order didn't exercise, for memory leaks, race conditions, and so on.

Bugs found by ERR can be very hard to track down, so it's not suitable for early debugging. On the other hand, it's been shown (see page 7) that ERR can expose defects that are very difficult to find otherwise.

The first thing I found when I ran these tests were many order dependencies in the test suite, particularly in package-related tests. I think they're all fixed now. SBCL has been running ERR for about ten hours on my machine with no failures or leaks. Clisp, on the other hand, showed an unexpected failure in one of the DEFCLASS tests. I'll try to track that down by doing ERR on limited subsets of the test suite.

I've been extended the random type prop tester for Common Lisp. The type arguments can be functions, which generate types that are dependent on the values of the preceeding arguments. This is useful for generating valid inputs to operators like AREF (the array indices have to be in range.) I've also added options to specify that the arguments should be replicated before use (necessary for testing destructive operators like RPLACA or NCONC).

I'm adding tested based on this infrastructure to the ansi-tests directory, but they're not going to be invoked directly in a normal run of the test suite, since they take a while to run, particularly on gcl.

Tests on PARSE-INTEGER brought up the question: what is (vector (member #\0 ... #\9))? Is it a subtype of STRING? The spec seems to say yes, but this is getting close to requiring that UPGRADED-ARRAY-ELEMENT-TYPE works on all types, not just those recognized by SUBTYPEP, and that's not possible in general unless U-A-E-T is an identity function (otherwise, it's undecidable.) I think the CL spec needs some work here.

Our late but not lamented HP Windows PC has died (drive failure caused by bad system thermal design), so I've decided to replace it with two machines, neither from HP. This evening I bought the first replacement -- a 1.4 GHz Mac Mini (the other will be a Dell). I've installed OpenMCL already, am downloading Xcode, and plan to begin testing it (and CMUCL, and SBCL) tomorrow.

I wrote a random type propagation tester for lisp compilers and have been extending it to more and more lisp types. Good type propagation is important for efficiently compiling Common Lisp, so testing it thoroughly is also important.

In a nutshell, this tester does differential testing between direct calls to an operator and calls that are embedded in a form with various inlined constants and with various type declarations. It found lots of problems with integer optimizations in gcl, problems with complexes and BIT-* functions in SBCL, a bizarre bug in Allegro CL's integer square root function, and many other bugs in various implementations.

Bill Clementson has posted on Concurrent Programming, and how a language that can effectively support concurrency may be able to displace current widely-used languages in which that support is flawed.

A language he focused on was Erlang, but I was reminded of another language, Cilk. Cilk is a variant of C with features for spawning parallel computations (Cilk programs become equivalent serial C programs when the new Cilk keywords are removed). Its implementation has an effective and highly cool 'work stealing' scheduler for allocating large numbers of fine grained tasks among a smaller set of worker threads.

I don't know if Cilk would be suitable for something like a web server, but for highly parallel computational tasks programs it has done well. A team using Cilk won the ICFP'98 Programming Contest, and Cilkchess, a chess program written in Cilk, came in 4th (out of 30 programs) in the 1999 World Computer Chess Championship.

The call for papers for the International Lisp Conference 2005 is up. Extended abstracts (1-2 pages) are due by March 15, 2005. I think I'll submit a paper on experience with the gcl test suite.

James Andrews has recently done an experiment with 'Coveraged-checked Random Unit Testing' (CRUT) (see also here. ) He took two sets of libraries with basic data structures (hash tables, trees, heaps, and so on) from Sourceforge, and wrote harnesses to make random function calls. The result logs were checked using an automated log checking system using an algebraic description of the expected results.

He found 6 major bugs (with no workarounds) in the two libraries and 12 additional bugs (either with workarounds or of lesser severity.) The random test generators achieved better than 90% statement coverage (as measured by gcov), which is even more impressive when one realizes that most of the uncovered lines were dead or untestable.

I'm not terribly surprised by these results -- it's easier to achieve high coverage with unit tests, and there are fewer low probability hoops for the random inputs to jump through -- but I'm troubled that free software packages labeled 'production/stable' had so many serious defects.

In a compiled dynamic language like Lisp, any information you have at compile time about the types of forms can be used to generate better code. Methods can be dispatched, type checks folded away, and, in some cases, objects of dynamic extent can be unboxed and stack or register allocated (this being particularly important for integer and float values.)

The importance of this is illustrated by a recent change to GNU Common Lisp. Camm Maguire has recently added a type propagator to the gcl compiler. It determines types for expressions in binding forms such as (LET ...) and, if a variable being bound isn't also assigned to, adds a declaration for that variable. The immediate motivation was to allow temporary variables in Lisp macro expansions to be well-typed, but the optimization applies to all local variables.

How much did it buy? Camm reports ansi-tests is running 27% faster in gcl, with a 41% improvement in garbage collection time. Not bad!

I've been bashing on this version with the random tester, but no problems have popped up yet.

Re 'Text Files Defended'

Another entry in Brian Marick's weblog:

(Not just to pick on Lisp and Smalltalk, two fine languages: how long did it take for a regex class to make it into Java? And a regex class is one significant affordance notch below regexps built into the language.)

Brian should take a look at CL-PPCRE, Edi Weitz's regex package for Common Lisp. The great thing about lisp, of course, is that the user can build the feature into the language, not just introduce a class -- and you get performance that's as good as or better than Perl's regular expression engine.

I came across the web log for testing guru Brian Marick, where he mentions lisp several times. Among other things, he ported CMUCL to a Gould processor in 1984.

I wonder what he'd think of the random tester?