Ask Uncle Peter
Please put your questions here.

It is a poor replacement for being on IRC, but at least I would be able to interact faster. (now only to stop myself pressing enter at the end of lines...)

Peter Van Eynde


Q Could you elaborate on the physics problem mentioned in the memoization page, the one you solved with a trick that reduced runtime from billions of years to 15 minutes? -- Paolo Amoroso A It was a program to calculate the number of states in a QM system. You had to go over every particle, do some calculation that involved going over the same system, but with less particles. So for f(N) you would use f(M) with M < N. The way in which you had to go down with the number of particles is pretty complex, so there was no obvious way to reduce the complexity. The program could handle 50 particles in about 10 minutes of runtime, and the runtime would go up with a double or tripple exponential (T=A*exp(B*exp(N))) so calculating N=51 was already a problem. Using memoization on the function reduced runtime for N=51 to a fraction of a second, and what was even nicer was that the time became linear with the amount of particles, so N=51 would still take a fraction of a second. This enabled the program to calculate N=1000 in about 5 minutes. The FORTRAN program my friend had written still took 5 minutes or something for N=50, and could not be converted to use the memoization trick (no hashtables in FORTRAN). Extrapolating the data the program would have needed several million years to calculate N=1000. This is a nice example how a 'slower language' can beat a 'faster language' with better compilers (CMUCL is nice, but no match for a good FORTRAN compiler) purely by being easier to try out new approaches. I had no idea that memoization would help so much. I just did a tree line change to the function and presto it became very clear that this was a good idea. The fact that I had made the function functional (just depending on the arguments) and the availiblity of hash-tables made this a fast change. FORTRAN would have needed several hundred lines and a re-write of the algorithm.

Q Why use a hash table at all if the indexes are dense? And if they are sparse, wouldn't it have been easier to implement a one-of hash table (at most about a page of code) than to switch to a different language?

A The program was in the Mathematica language. It is pretty Lisp-like (it has Head[] Tail[] etc). I 'converted' it to Lisp by replacing [] with () almost. After cleaning it up and converting it to a more it already became a lot faster (it had a few problems like consing up a list of states and then adding them together at the end instead of just adding the current state to the number of states found). Adding memoization was a question of seconds of work.

A Unicode: This became Unicode and Lisp

Q Why does Common Lisp Controller have to recompile all lisp libraries for all lisp dialects? It makes my crappy computer slower! A With version 3 of Common Lisp Controller and adapted implementations this should no longer be a problem.

Q What is the difference between the cmucl-source package and the cmucl sources? A The sources can self-compile. The cmucl-source package should, but I've not tested this. The cmucl-source packages just exists so people can do source-level debugging on cmucl and send in patches :-)

That's not really what I meant Sir Slappy Pants ( sources rebuild fine too). There's a 221kB patch difference between the upstream ( sources and the debian binaries, but (AFAIKT) no summary of what these patches do. I can guess some of this by reading the patches, but it would be nice to have it documented somewhere (for example: what kernel versions does the -lazy option work on nicely?). -- Eric Marsden

A2 You can find the diffs split up here. Most of the high-security stuff nowadays is just compiling the system itself with (debug 3)...

Q What does it mean when Common-Lisp-Controller puts its compiled files in (/var/cache..) numbered directories instead of username directories? I've got two directories named 0 and 1000, with 1000 used as the current build. Also is there a website or place for the CLC project itself? I can't seem to find a relevant one. Thanks!

A Previously, CLC used the part after "/home/...", which is not good, because multiple Users might share one home directory. This is especially the case when you use sudo, where the Home dir of the underlying user is still present. The problem is the following: CLC checks whether the cache directory is owned and only writable by the user that is currently trying to load code, because otherwise some evil person could preload your cache with evil FASLs that do evil things. If now two users share one home directory, they would also need to share one cache directory. Only one of them would be able to use CLC, because everything else would be insecure. Since UIDs are the only way in Unix to have an unique distinction between users, CLC now places FASLs to /var/cache/common-lisp-controller/UID. Basically, your "0" directory contains the files that were compiled by "root", when installing CLC and CL implementations and "1000" contains files from your normal User. Please refer to the according changelog entry