Optimizing Lisp May 24th, 2009
Patrick Stein

Paul Reiners recently posted some code to the TC Lispers mailing list. The code began from Paul Graham’s ANSI Common Lisp book. Exercise 13b has you adding declarations to some code so that the compiler can better take advantage of the types involved. Oddly, the code ran more slowly with his typing than it did without it. I had the same experience when I tried this code under SBCL 1.0.23 on Mac OS X.

Here is Paul’s original code which he made available with Creative Commons License the Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.

I stripped out the declarations and started adding them in one by one, trying to deal with as many compiler notes as I could figure out in the process. First, in the base case, the following took 22.5 seconds on my computer.

(time (ray-test 8))

After much tweaking, I have gotten it down to just under 11 seconds. Most of that came with declaring the types of the slots in the (defstruct …)‘s and these three declarations:

(declaim (ftype (function (long-float) long-float) sq))
(declaim (ftype (function (long-float
                           long-float
                           long-float) long-float) mag))
(declaim (ftype (function (long-float
                           long-float
                           long-float)
                          (values long-float
                                  long-float
                                  long-float)) unit-vector))

This declaration, however, shot me back up to 22 seconds.

(declaim (ftype (function (long-float
                           long-float
                           long-float)
                          long-float)) minroot))

Of course, it really should have been returning (or long-float nil). But, that didn’t help either. From the compiler notes, it seems that (min …) in SBCL doesn’t deal well with unboxed floats. I will have to look harder at that section and ask on the SBCL lists. I believe that I tried decorating the expressions there, too.

(the long-float (min (the long-float
                       (/ (the long-float (+ (the long-float (- b))
                                             discrt)
                               (the long-float (* 2L0 a)))))
                     (the long-float
                       (/ (the long-float (- (the long-float (- b))
                                             discrt)
                               (the long-float (* 2L0 a)))))))

Lisp Patterns Question W.R.T. Clifford Algebras May 20th, 2009
Patrick Stein

Since I moved my website to WordPress, I have been watching what search-engine searches land people on my page.

Sadly, two of the things that get people to my page most often still have not been moved over to the new site from the old. One of those things is a C++ template library for Clifford algebras. I am going to move that stuff over this week, I promise. But, I thought I might also make a Lisp library for Clifford algebras, too.

An example Clifford algebra might be C_{3,0}. A generic element in this algebra is of the form:

a_0 + a_1 e_1 + a_2 e_2 + a_3 e_3 + a_{1,2} e_{1,2} + a_{1,3} e_{1,3} + a_{2,3} e_{2,3} + a_{1,2,3} e_{1,2,3}

where the a_* are coefficients. For ease in dealing with these items, I will probably store that in a vector that looks something like this:
#(a_0 #(a_1 a_2 a_3) #(a_{1,2} a_{1,3} a_{2,3}) a_{1,2,3})

If you want a simple element though (where most of the coefficients are zero), you shouldn’t have to stare down all of that stuff or remember that a_{1,3} comes before a_{2,3}. I want you to be able to make 3 + 4 e_1 + 5 e_{1,2,3} more simply. Something like one of the following:

(defvar *a* (ca-element '(3 (4 1) (5 1 2 3)) :p 3))
(defvar *a* (ca-element '(3 (4 . :e1) (5 . :e1-2-3)) :p 3))
(defvar *a* (ca-element :s 3 :e1 4 :e1-2-3 5 :p 3))

Similarly, I will define something akin to (aref …) so that one can check or change a_{1,2} like one of the following:

(caref *a* 1 2)
(caref *a* :e1-2)

By analogy with the complex numbers, I should instead have:

(e1-2 *a*)

But, that just doesn’t scale very well.

I am leaning toward using a list of numbers to tell which a_* is being referenced. This would allow greater flexibility in other functions. But, it’s also less mathy.

Does anyone have any suggestions? Should I really be supporting both? Through the same function names or through (caref …) and (caref* …) or something?

Code Clarity Revisited May 11th, 2009
Patrick Stein

In an earlier post, I showed a simple loop written in several programming languages. The loop had to sum the weights of each items in a list. Dmitry pointed out a much clearer loop in Lisp using the (loop …) construct.

(loop for item in item-list sum (weight item))

I then twiddled for the better part of an hour trying to find the clearest way to do weighted random choice with Lisp (loop …). This is the best that I have come up with:

(loop
   with total = (loop for item in item-list sum (weight item))
   with thresh = (random total)
   for item in item-list
   if (minusp (decf thresh (weight item)))
     return item)

The biggest pedagogical obstacle in the above is the (decf …) which decrements the variable in place by the given amount and returns the new value of the variable. What I really wanted to do was this:

(loop
   with total = (loop for item in item-list sum (weight item))
   for item in item-list
   tracking item
   as thresh downfrom (random total) by (weight item))

That fails on multiple fronts, however.

  • There is no tracking keyword in (loop …). I can sum or maximize or collect items, but I cannot keep track of the last one that I saw. I had hoped to use the finally keyword, but its value isn’t returned from the loop.
  • Lisp requires that the decrement amount in the by of a downfrom be greater than zero. As such, I have to filter out any items that have zero weight. Feh. I can do that. I would rather not. But, I can do that.
  • Lisp only evaluates the by expression once. It does not evaluate it each time through the loop.

I am still learning all of the ins and outs of (loop …). Today, I learned as many outs as ins. Feh.

Move over UML, I Have SQL May 8th, 2009
Patrick Stein

I have been trying to nail down a design for a sizable software project. I know how I want the system to behave. I just hadn’t nailed down a good API or internal structure for it yet.

I knew that I was going to have to track multiple versions of uniquely identifiable data with different versions stored in different locations.

I had all sorts of UML drawing on whiteboards and graph paper and in OmniGraffle. Everything just kept getting messy.

Earlier this week, I read a great article about Using SQLite on the iPhone. So, today, I tried to hammer out what I would do with this data if I were using SQL to track it. I wrote a bunch of CREATE TABLE statements and then a few SELECT statements.

It worked. Getting the JOINs in the SELECT statements to make sense forced me to make the relations in my data as simple as possible, but no simpler. I had been trying to jam many-to-many relationships into one-to-many or many-to-one relationships. The SQL exercise forced me to get it right.

Will I use SQL in the final project? Maybe, but it doesn’t seem like I will need it. Did I need to use SQL for the design? Absolutely.

What is Your Coding Style? May 7th, 2009
Patrick Stein

In cleaning out some directories, I stumbled upon a draft of a document that I wrote three and a half years ago. That document describes my programming style.

What the document says is mostly out of date. I hadn’t even used Perl or Lisp to any great extent at that time. But, here is the thing…. It doesn’t matter.

Writing the document was an important exercise. Looking at some of my Objective C code, I think it may be time to repeat the exercise. For months after writing that document, I named my variables better, I named my functions better, and I wrote more maintainable code.

So, what is your coding style?

RSS Feeds

l