Older blog entries for pfdietz (starting at number 13)

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?

Dave Roberts (Finding Lisp) recently posted about the gcl ansi-tests' Common Lisp random tester and random testing in general.

I use random testing not only for testing CL compilers, but also for more focused testing of specific language features. For example, I randomly check SUBTYPEP (which caused crhodes some grief), various sequence functions, settings of control variables for printing/reading, and various numeric functions.

The idea of using randomized inputs to test compilers has been tried before, aside from McKeeman. Don Slutz at Microsoft wrote a random test generator for SQL database systems. B. A. Wichmann did random stress testing of compilers for various languages. Ariel Faigon talks about random testing of compiler backends targeting National Semiconductor 3200 series microprocessors.

Hmm. Where does the time go?

The ANSI CL test suite is now at over 18,000 tests. Right now I'm testing interactions between various kinds of unusual vectors and the builtin string/sequence functions. This is mostly to support crhodes in his effort to add unicode support to SBCL, but it's already found at least one five year old bug in CLISP (REVERSE didn't work on displaced vectors).

After that I'm going back to finishing the FORMAT tests. I'm still aiming for about 20K tests for the 'finished' test suite.