Liam Healy

07:33 pm - SBCL in Debian testing (lenny)

Recently I noticed that SBCL in Debian testing is quite old; it is currently at 0.9.16 and evidently blocked there:

=== sbcl:
= Missing build(s) on alpha,sparc
 This might need manual action from your side.
 See http://buildd.debian.org/pkg.cgi?pkg=sbcl
= No migration to testing for 585 days.
 See <http://release.debian.org/migration/testing.pl?package=sbcl>

08:50 am - Cairo for Lisp

I have been looking into using Cairo for various 2D drawing needs. A key advantage is the availability of a variety of output formats, including both screen and hardcopy. One potential application is traditional x-y scientific/engineering plots. Although there are many options for doing that, even using Lisp, I have a Lisp package I adapted many years ago for this purpose that now lacks a good back end for output. My thought is that Cairo would be good for that, as it is a standardized library, widely available, with many modern output formats. I also have other 2D output that I do from Lisp, which I now do with a thin postscript definition layer that I wrote. Switching to Cairo would give me some more flexibility.

I did some research and found that there were three sets of bindings for Cairo:

• cl-cairo


• cl-cairo2


• cffi-cairo

It looks like I'll be using cffi-cairo.

02:16 pm - Never a NaN or Inf

In very few cases is it acceptable to me that a floating-point calculation would produce NaN or Inf; it almost always means that there is an error somewhere in my program. Following the principle that it is best to detect an error as soon as possible, I would like to know immediately whenever either of these is created, by trapping the exception and signaling an error. Depending on the language and implementation, this doesn't always happen by default. Here are some different languages and compilers, and how to set to make this happen:

• Lisp: SBCL: (sb-int:set-floating-point-modes :traps '(:invalid :divide-by-zero :overflow)) and
CMUCL: (ext:set-floating-point-modes :traps '(:invalid :divide-by-zero :overflow)).
  Also GSLL provides #'set-floating-point-modes.
  
• Fortran: for gfortran, use the compiler flag -ffpe-trap=invalid,zero,overflow.

• C/C++: use
  

  #include <fenv.h>
  trapfpe () {
    feenableexcept(FE_INVALID|FE_DIVBYZERO|FE_OVERFLOW);
  }
  

  
  In C, this will need to be included: void trapfpe();
  In C++, this will need to be included (also works for C):
  

  #ifndef _TRAPFPE_H_
  #define _TRAPFPE_H_
  
  #include <sys/cdefs.h>
  
  __BEGIN_DECLS
  void trapfpe(void);
  __END_DECLS
  
  #endif /* _TRAPFPE_H_ */
  

  
  and then in either, include trapfpe(); at the beginning. This should be portable to C99 compilers/libc but I've used only gcc and glibc. Also, GSL has gsl_ieee_env_setup.
  

08:54 am - SBCL, libc6, and GCC

For those that don't follow the mailing list, SBCL on Debian is unusable in unstable. SBCL did not change, but Debian upgraded libc6 to 2.7-9. This causes SBCL to spin at 100% usage, or simply to hang, while starting up. The only relevant change to libc6 is that it is now compiled with GCC 4.3 instead of 4.2; the libc6 maintainer has confirmed that backing out this change and recompiling libc6 with GCC 4.2 allows SBCL to work. It is still unclear where the problem(s) is/are; but the experts have narrowed it down further. Follow the developments on the Debian bug report; even if you don't use Debian, presumably this combination of software is a problem. In the meantime, if you are a sid user, don't upgrade! Though apparently some people have experienced the problem as a random failure, my experience is that it's 100% reproduceible.

Software is complicated.

06:27 pm - GNU Scientific Library for Lisp

The GNU Scientific Library is a library of applied mathemetics commonly used in science and engineering. I have written GNU Scientific Library for Lisp (GSLL), a fairly complete interface to this library from Common Lisp. My intent is that the interface be as Lisp-natural as possible. Though this will be useful for those of us that do scientific programming in Lisp, even those who aren't Lisp programmers might use this library as a desk-calculator interface to GSL.

01:29 pm - Comparison of floating point numbers in Common Lisp

Floating point numbers are a computer representation of the real numbers. Unlike the real numbers, there are a finite number of them. So there is a smallest and largest floating point number, and all others have a predecessor and successor.

Because different compilers and platforms can reorder a calculation and optimize in a way that is approximated differently and so do not necessarily produce the same floating point number, it is difficult to compare two floating point numbers and conclude that they represent the same result. For the purposes of regression (or unit) testing, we would like to do exactly this. Bruce Dawson addressed this problem in "Comparing Floating Point Numbers." He makes the point that the best way to do this correctly is to interpret each floating point number as an integer. By taking advantage of the IEEE 754 standard for representation of floating point numbers, we can construct a function that maps the floating point numbers to the integers. The genius of the standard's inventor W. Kahan is that a mapping derived from the standard, call it i(x), satisfies three properties:

• If two floats a<b, then i(a)<i(b),
• if two floats are adjacent and a<b, then i(b)=i(a)+1,
• and finally i(0.0)=0.

Dawson provides some clever C constructs to read a floating point number as an integer, and instruction on how to prevent the compiler from complaining about your trickery in doing so. Common Lisp instead provides us with functions with which we can properly construct our own integers. As a side benefit, we don't care what the actual representation of the floating point number is; we will build our own IEEE-like representation. We don't exactly want the full IEEE754 word though; we leave off the most significant bit, which is a sign bit, and instead make the sign of the integer agree with the sign of the float.

What we end up with is an enumeration of the floats. That is, for every single precision float, there is one integer in the range [-2139095039, 2139095039], and vice versa, with the exception that both positive and negative zero (allowed by the standard) map to zero. Likewise, there is a one-to-one mapping of the double precision floats to [-9218868437227405311,9218868437227405311]. Floats with special values (positive and negative infinity, and NaN) that are required by the standard do not have integer values.

I have written the following functions in Common Lisp:

• float-as-integer which is the function i(x);
• integer-as-float which is the inverse function (this isn't necessary but can be useful) and also returns the rational form of the float;
• decode-IEEE754 (used by other functions) that returns five values: significand, exponent, sign, bits in significand, bits in exponent, all as integers;
• format-IEEE754-bits which prints out the binary form of the IEEE word, separated into the three parts (this isn't necessary but is nice for comparing with bit expansions shown in references like the Wikipedia page).

Here are some interesting floats:

(float-as-integer most-negative-single-float)
-2139095039
(float-as-integer least-negative-single-float)
-1
(float-as-integer -0.0f0)
0
(float-as-integer 0.0f0)
0
(float-as-integer least-positive-single-float)
1
(float-as-integer (- 1.0f0 single-float-negative-epsilon))
1065353215
(float-as-integer 1.0f0)
1065353216
(float-as-integer (+ 1.0f0 single-float-epsilon))
1065353217
(float-as-integer most-positive-single-float)
2139095039

A regression test would record not the floating point number, but the integer produced by float-as-integer. Since integers can be unambiguously formatted to and read from a text file in a unique way, a subsequent recomputation would provide a clear indication of how close the floats are. Of course, we must decide how much error we're going to allow, because a correct calculation may produce slightly different integers. As an added bonus, these functions can be used to identify (in languages other than Lisp) when a positive single float has been interpreted as a double float.

06:00 pm - Multiprocessing lisp evaluations

I sometimes need to evaluate the same form with different parameters repeatedly. Such as

(job 1)
(job 2)
(job 3)
...

(defparameter *job-lock* (sb-thread:make-mutex :name "job lock"))
(defparameter *results* (list nil))
(defvar *end-of-jobs* (make-symbol "EOJ"))
(defvar *jobs* nil)

(defun worker (job)
  (let ((my-job nil)
	(more-jobs t))
    (loop while more-jobs
       do
       (sb-thread:with-mutex (*job-lock*)
	 (setf more-jobs (or *jobs*))
	 (setf my-job (when more-jobs (pop *jobs*))))
       (when my-job			; there is a job to be done
	 (if (eq my-job *end-of-jobs*)
	     (setf more-jobs nil)
	     (let ((my-results (apply job my-job))) ; call the job outside the mutex
	       (sb-thread:with-mutex (*job-lock*)   ; save results
		 (push my-results *results*))))))))

(defun run-tasks (job dataset number-of-workers)
  "The job is a function that takes one non-null argument.
   The dataset is a list of arglist sets for the job.
   The number-of-workers is the number of workers desired, 
   presumably the number of processors available."
  (setf *jobs* (make-list number-of-workers :initial-element *end-of-jobs*)
	*results* (list nil))
  (dolist (ds dataset) (push ds *jobs*))
  (let ((threads (list nil)))
    (loop repeat number-of-workers
       do (push (sb-thread:make-thread (lambda () (worker job))) threads))
    (dolist (thread (butlast threads)) (sb-thread:join-thread thread))
    (butlast *results*)))

(defun job (x) (list x (+ (loop for i from 1 to 2000000 sum (let ((p (* i x))) (1- (expt p (/ p))))))))
(run-tasks #'job '((1) (2) (3) (4) (5) (6) (7) (8) (9) (10)) 2)
((1 105.73587) (2 58.11023) (3 41.245914) (4 31.676012) (5 26.053244)
 (6 22.305136) (7 19.607342) (8 17.642727) (9 15.433696) (10 14.060191))

12:45 pm

I have my new OLPC XO-1 now, from the "Give one get one program". My intended use is mainly for updates from the road while on bike tours.

One thing I'd like is instant messaging. The "Chat Activity" works to other XOs but evidently not to anyone else. Pidgin and Finch have been ported, so I tried Finch, being text-based and therefore presumably simpler. It works, but unfortunately it is based on ncurses. Evidently, few if any of the curses controls work on th XO, so I can't even expand the "window" to full screen. It would be nice if there were a plain text (no pseudo-windowing, no curses, etc.) IM client, perhaps one based on libpurple?

Update: I found NAIM which is full screen and does not try to emulate windowing, but has an odd choice of colors - the typein area is white letters on a white background, which makes it hard to see.

06:54 pm - Profiling in SLIME

This is about the easiest profiling I've seen in any language. In
fact, I think it's the only time I been able to make significant
improvements based on the report.

M-x slime-toggle-profile-fdefinition

M-x slime-profile-reset

M-x slime-profile-report

12:44 pm - DoD authentication in Iceweasel/Icedove

Common DoD authentication with certificates and the Common Access Card (CAC) is possible in Debian for Iceweasel (Firefox) and Icedove (Thunderbird). It can be reduced to the following:

1. Install the DoD Configuration add-on in Iceweasel by clicking on "Install Now" button.
   
2. Save that xpi file from Iceweasel by clicking right on the button. Install the file in Icedove: Tools -> Add-ons -> Install.
   
3. Test from web by visiting http://www.navy.mil; the URL should be green. You do not need your CAC.
   
4. Load packages in Debian:
   

   sudo aptitude install libpcsclite1 pcsc-tools libccid coolkey
   

   
   This will enable the CAC reader in Debian unstable; I don't know if the versions of previous Debian releases will work. Note that not all CAC readers are supported; see the list. In particular, the ActivCard 2.0 USB, which is very common, is not supported.
   
5. With your CAC inserted, visit http://infosec.navy.mil. You will be prompted for your PIN, and you should be able to select your certificate. To see the certificate information that the server has, visit the PKI Cert test page.
   
6. You can sign/encrypt email by using the S/MIME button, and set up defaults for every email with Edit -> Account Settings -> Security. Note that OpenPGP security is completely separate from CAC security, and the icons that display in messages and the composition area shouldn't be confused.
   

03:45 pm - Extension functions in sqlite3, again

I mentioned before that I cleaned up and posted mathematical and string extension functions for SQLite3. Some things have changed in the interim, which necessitated going through a few revisions. So now the new version is available which makes compilation and use easier. For one thing, the SQLite source is no longer required to compile it. Second, it uses the standard sqlite3_load_extension interface, which should make it easier to use. The interface through CL using CLSQL is now

(in-package :sqlite3)

;;; Add mathematical and string functions to SQL queries using
;;; libsqlitefunctions from
;;; http://www.sqlite.org/contrib/download/extension-functions.c?get=22

(def-sqlite3-function
    "sqlite3_enable_load_extension"
    ((db sqlite3-db) (onoff :int))
 :returning :int)

(def-sqlite3-function
    "sqlite3_load_extension"
    ((db sqlite3-db)
     (filename :cstring)
     (entrypoint :int)
     (errmsg :int))
  :returning :int)

(eval-when  (:compile-toplevel :load-toplevel :execute)
  (export 'enable-sqlite3-extension-functions))

(defun enable-sqlite3-extension-functions (database)
  "Set up the SQLite3 mathematical extension functions.  This
   must be called every time the database is connected
   before any extension function is used."
  (let ((db-ptr (clsql-sqlite3::sqlite3-db database)))
    (sqlite3-enable-load-extension db-ptr 1)
    (unless (zerop
	     (sqlite3-load-extension db-ptr "libsqlitefunctions.so" 0 0))
      (error "Can't load libsqlitefunctions.so."))))

11:57 am - cl-mcclim out of date in Debian unstable

People are talking about the hot new mcclim (0.9.5). But unstable has 0.9.2; experimental only has 0.9.4 and it has not migrated to unstable in the six months it's been there because, supposedly, the etch freeze http://packages.qa.debian.org/c/cl-mcclim.html. But etch has long since been released; why the continued logjam?

12:57 pm - GMAT on Debian amd64

NASA has recently made available its General Mission Analysis Tool (GMAT), a space trajectory and mission analysis system, under an open source license. The precompiled version relies on WxWidgets 2.8, which aren't yet available in Debian (though there are debs available) and is for i386. So I have tried to compile under etch/amd64 using WxWidgets 2.6. The src/README file explains very well how to set options, but not how to compile, so here's what I've figured out.

sudo aptitude install libwxgtk2.6-dev libwxbase2.6-dev wx2.6-headers
sudo aptitude install libdevil-dev libdevil1c2
In src/topLevelBuildFiles/linux/BuildEnv.mk, remove local/ from the path:
WXCPPFLAGS = `/usr/bin/wx-config --cppflags`
WXLINKFLAGS = `/usr/bin/wx-config --libs --gl-libs --static=no`
Make source code changes in src/base/forcemodel/ForceModel.cpp, line 1129 add "long"
std::sprintf(sataddr, "%x", (unsigned long)sat);
Change to the src directory, and make links
ln -sf topLevelBuildFiles/linux/MakeGmat.eclipse topLevelBuildFiles/linux/BuildEnv.mk .
Then make
make -f MakeGmat.eclipse

Unfortunately, the compilation ends in error.

01:39 pm - DRAKMA

Yesterday's blog mentioned trouble I'm having with cl-curl, my own package. A comment pointed me to DRAKMA, yet another Edi Weitz bequest to the lisp world. It is a native common lisp http client that handles the particular web site I am scraping data from, complete with password and cookies. It was very simple to rewrite my access functions to use DRAKMA, and it is able to retrieve all the data I wanted, no memory fault like cl-curl. So I will update the cl-curl project page to recommend DRAKMA.

It was a little unclear how to install DRAKMA; here is my condensed summary, on Debian:

1. sudo aptitude install cl-chunga cl-puri cl-flexi-streams
   
2. wget http://common-lisp.net/project/usocket/releases/usocket-0.3.2.tar.gz
   
3. wget http://common-lisp.net/project/cl-plus-ssl/download/cl+ssl-2007-03-10.tar.gz
   
4. wget http://weitz.de/files/drakma.tar.gz
   
5. tar zxvf usocket-0.3.2.tar.gz
   
6. tar zxvf cl+ssl-2007-03-10.tar.gz
   
7. tar zxvf drakma.tar.gz
   
8. clc-register-user-package usocket-0.3.2/usocket.asd
   
9. clc-register-user-package cl+ssl-2007-03-10/cl+ssl.asd
   
10. clc-register-user-package drakma-0.7.0/drakma.asd
    
11. ,l drakma (in slime)
    

10:24 am - Parsing HTML and memory fault from cl-curl

I've had need to parse HTML in lisp from time to time. The latest reason is some very specific and uncomplicated HTML that I scrape for some satellite data off a published database. A search online turns up XMLS as a likely candidate for this task. I have used it successfully in the past, but recently I find it won't parse its own example and its own supplied HTML documentation, to say nothing of the real HTML I want it to parse. It either returns NIL (meaning an error in parsing the correct HTML), or only the first line of HTML. There is a thread on comp.lang.lisp about how to parse HTML, and many people recommend cl-html-parse. I was dissuaded at first because of the wiki comments implying that it had been superseded by pxmlutils whose web page in turn implies that it had been superseded by... XMLS! But cl-html-parse works just fine on the web pages I need to scrape.

So, success. But then, I am grabbing the web page with cl-curl which works most of the time, but for a particular query gives "memory fault," I think because there is a lot of data. And the author/maintainer of cl-curl is... me! D'Oh. It would be nice to have cl-curl using CFFI instead of UFFI, maybe based on the pedagogical development given in the CFFI tutorial. My hope is at least it would solve this problem. Any interest/volunteers/motivators?

07:02 pm - Math and string extension functions for SQLite

I have posted my port of Mikey C's extension functions for sqlite,
http://sqlite.org/contrib/download/extension-functions.tgz?get=17
but a more thorough list of functions would be as follows:

Math:
acos, asin, atan, atn2, atan2, cosh, asinh, atanh, degrees,
radians, cos, sin, tan, cot, cosh, sinh, tanh, coth, exp,
log, log10, power, sign, sqrt, square, ceil, floor, pi

String:
difference, replicate, charindex (2 or 3 arguments),
leftstr, rightstr, ltrim, rtrim, trim, replace,
reverse, proper, padl, padr, padc, strfilter

Aggregate:
stdev, variance, mode, median, lower_quartile, upper_quartile

03:16 pm - Rebuilding the sqlite3 library with extensions in Debian

The new version of the library libsqlite3.so in Debian needs to be rebuilt in order that extension functions can be used, because apparently it's hard to get autoconf to learn where dlopen is located. This will fix the problem:

 sudo aptitude install fakeroot dpkg-dev build-essential
 cd /tmp
 apt-get source libsqlite3-0
 sudo apt-get build-dep libsqlite3-0

 #TCC += -DSQLITE_OMIT_LOAD_EXTENSION=1

 cd /tmp/sqlite3-3.3.14
 dpkg-buildpackage -rfakeroot -uc -us
 dpkg -i /tmp/libsqlite3-0_3.3.14-1_amd64.deb

09:59 am - SQLite math and string functions simplified

Thanks to Mikey C, there are now a number of math and string functions available in SQLite SQL queries. I blogged this before, but now I have simplified and cleaned up his code, and made it available.

The functions are: Math: acos, asin, atan, atn2, atan2, acosh, asinh, atanh, difference, degrees, radians, cos, sin, tan, cot, cosh, sinh, tanh, coth, exp, log, log10, power, sign, sqrt, square, ceil, floor, pi. String: replicate, charindex, leftstr, rightstr, ltrim, rtrim, trim, replace, reverse, proper, padl, padr, padc, strfilter.

For CLSQL users, the Lisp portion of the instructions in my previous post remain the same.

10:03 pm - Math extension functions in SQLite3 using CLSQL

Inconveniently, nature has made the semimajor axis of an orbit proportional to the -2/3 power of the mean motion, so when retrieving element sets from an SQL database, it is very useful to have a POWER function, as Oracle does. Since I have now moved to SQLite3, this function is no longer available. The topic of adding mathematical functions like power comes up repeatedly every few weeks on the SQLite mailing list. Unhelpfully, someone always replies "it's easy" with no further information. It is not easy. Fortunately, Mikey C offered his C extension functions
which include most common math functions --- not just power, but trigonometric functions, logarithm, etc.

1. Download Mickey C's source zip
   
2. Unzip it, and optionally move the needed files btree.h, config.h, func_ext.c, hash.h, map.c, map.h, opcodes.h, os.h, pager.h, parse.h, sqliteInt.h, vdbe.h, vdbeInt.h into a separate directory
   
3. Compile
   

   gcc -DHAVE_ISBLANK -DHAVE_LOG10 -DHAVE_COSH -DHAVE_SINH -DHAVE_TANH \
    -DHAVE_ACOSH -DHAVE_ASINH -DHAVE_ATANH \
    -fPIC func_ext.c map.c -shared -o libsqlitefunctions.so
   

   
   

Now these functions can be used through CLSQL.

(in-package :sqlite3)

(def-sqlite3-function
    "sqlite3_enable_load_extension"
    ((db sqlite3-db) (onoff :int))
 :returning :int)

(uffi:load-foreign-library 
 (uffi:find-foreign-library "libsqlitefunctions" #p"/path/to/library/")
 :module "sqlitefunctions"
 :supporting-libraries '()
 :force-load t)

(def-sqlite3-function
    "sqlite3RegisterExtraFunctions"
    ((db sqlite3-db))
 :returning :void)

(eval-when  (:compile-toplevel :load-toplevel :execute)
  (export 'enable-sqlite3-extension-functions))

(defun enable-sqlite3-extension-functions (database)
  "Set up the SQLite3 mathematical extension functions.  This
   must be called every time the database is connected
   before any extension function is used."
  (let ((db-ptr (clsql-sqlite3::sqlite3-db database)))
    (sqlite3-enable-load-extension db-ptr 1)
    (sqlite3registerextrafunctions db-ptr)))

(clsql:query 
    "SELECT (POWER((398600.4415 /
    POWER((7.27220521664304e-5*MEAN_MOTION), 2.0)), 0.3333333333333333)
    * (1.0 - ECCENTRICITY)) - 6378.1363 from nscels where catdate = '2007-03-16 06:16:48'
     AND satnum = 24937"
   :database *nscels-database*)

10:48 am - Conditionalizing minor system dependencies

If a system could make use of another but the usage is incidental and you don't want to break the loading of the first if the second is unavailable, it would be nicer to skip over it or provide an alternative. I have used an idiom like this:

(remove string *sf-name-mapping*
	  :key #'rest
	  :test-not
	  (if (find-package :ppcre)
	      (symbol-function (intern "ALL-MATCHES" :ppcre))
	      #'string-equal))