Older blog entries for pfdietz (starting at number 17)

Hash Consing is an interesting non-standard idea that's been around for a long time, before Common Lisp. The idea is to make lisp's equal and eql be identical by storing cons cells in a hash table. When (cons x y) is computed, the two arguments are used as keys into the hash table. If a cons of these two values has already been computed, that cons cell is reused.

This idea is not consistent with the cons in Common Lisp, so it would either require a nonstandard lisp or an extension using something other than cons as the constructor (and, in which case, we may want to clone the other cons-related functions as well.) Hash cons cells must clearly be immutable, and only contain immutable data, so the idea is related to the immutable data types Baker mentioned in his ILC 2005 talk.

What's the benefit? Applications that manipulate mathematical formulas are a disproportionate share of Lisp's success stories (Macsyma/Maxima, Axiom, ACL2, various other theorem provers). It's nice if you can compare formulas for structural identity in O(1) time. I understand ACL2 does run on a hash-consed variant of gcl.

There's a variant of hash consing I'll call 'lazy hash consing'. In this scheme, eqlity of equal cons cells is established only when they are compared. Here's how it works. Let's suppose we're computing equal on two places, say x and y. If they are eql, stop. Otherwise, if they are cons cells, recursively compute equality (using hash codes stored in the cells to recognize inequality of subtrees with high probability). If x and y are equal, then we have two trees that are equal but not eq. What we do then is either (setf x y) or (setf y x). If we're using a generational collector, we choose so that the pointer that is changed is moved to point to the same generation as it pointed to before, or older (this might be as easy as comparing the two pointers, assuming newer generations are stored in progressively larger addresses on the heap). This means we don't need a write barrier.

The recursive equal calls on car/cdr of the cons cells in the trees would be done using this same algorithm, so after one sweep through two disjoint trees we've mostly collapsed the two trees into one (and many cells will likely be collectable.)

This scheme is nice in that it doesn't need a hash table, just hash values in each cons cells. Accidental collisions will be rare (assuming a good hash function), so inequality can be determined in O(1) time. It's also likely that older versions of trees will tend to have more shared references, so pointers should quickly be made to point to their final destinations.

A few thoughts on ILC 2005

Overall it was an enjoyable conference. There were some good papers, some duds, and some controversy. It was very good to see and talk to people who I knew only by name. Attendance appeared to be up from ILC 2003. ALU is in no danger of dying, with a nice surplus.

My talk went ok, but I (as always) underestimated how much time it would take, and how many questions I would get. Fortunately, I had designed the talk so the last part was optional, so I omitted it. I got positive comments, and William Clinger (who gave an interesting talk on Common Larceny, a Scheme-on-CLR implementation) liked it.

Moore's presentation on ACL2 was a big hit, and (unlike many of the other invited speakers) he actually submitted a full paper for the proceedings. I'm particularly gratified by ACL2 because its standard delivery platform is GCL (although it does run on other lisps, it gets its best performance on GCL.)

Now, about those last three presentations. A lot's already been said in other blogs, so I'll try not to repeat things I agree with.

Two presenters (Baker and McCarthy) complained about standardization. I wonder if the complaint isn't that standardization made it more difficult to get grants for new lisp implementations. Didn't the CMU CL effort have their funding dry up around the time the standard was being finalized?

Integration with CLR seems pointless if Common Lisp has to change too much. Move the language too much and one loses the community and software infrastructure behind it. One might as well start over and not call it Lisp.

The desire for a statically typed Common Lisp came up. But don't we already have this? Lisps can and do perform type inference. Many lisps propagate types inside functions, and GCL can generate function type declaims for all functions (and this is one trick used to speed up ACL2, I believe.) If the user wants to add manual type declarations, there's nothing in Lisp stopping him. Maybe it's just a matter of allowing the user to specify that the compiler should break on warnings?

I think many of the proposed extensions to CL are things that are either already done, could be done without changing the standard, or require only extensions to the standard.

Baker made a more interesting point when he complained that software didn't have the huge per-seat cost of chip design software packages. If chip designers found automated help useful enough to pay that much, then why didn't software developers? The reason, I think, is networking effects, which strongly encourages one to use the same development environment as everyone else. It's a point in Common Lisp's favor that it has survived (and, in its small niche, may even be thriving) even fighting against this tide.

Costly (but worthwhile) software development tools will impede the loss of software jobs to the low cost markets. From what I've seen of development there, their capital budgets are constrained; only in the last decade or so has the cost of equiping a developer there fallen low enough to make a good business case for offshoring.

What does that have to do with Lisp? Can we do something to Lisp, or Lisp implementations, so that expensive development platforms make more economic sense? I have some ideas here I'll expand on some other time.

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.