Tamas K Papp's blog

cl-cairo2: new maintainer, new license

2012-01-26T01:12:00.000-08:00

cl-cairo2 was one of the first Common Lisp libraries I wrote, but I haven't been using it much for the last year or so (currently I am experimenting with cl-pdf as a backend for my new plotting library, which will be released soon). I have been pretty busy with research, so I didn't have time to merge (and test) patches, also, I didn't even contemplate updating the library to make use of the latest version of cairo. So when Ryan Pavlik contacted me about adding compatibility with cl-freetype2, I asked him whether he wants to take over as a maintaner. He kindly agreed, so I have transferred the repository to him, and he already merged a lot of patches.

One last thing that I wanted to fix before handing the repository over is the license. Originally, the library was licensed under the GPL — in retrospect, I think that

I was very naive about software licenses, and didn't really understand what GPL means in the context if Common Lisp (I still don't claim that I do :-P), and
I didn't realize that there are a lot of commercial applications in the Common Lisp world, whose authors are wary of depending on GPL'ed libraries.

Consequently, I received many complaints about the license of the library, and decided to change it. I picked the Boost Software License, and contacted all who contributed to the library for permission. All contributors approved the change, so now the library has a simple, permissive non-copyleft free software license. However, it is always possible that I missed someone, so if you contributed to cl-cairo2 in the past but didn't hear from me regarding the license change, please get in touch (eg via the Github issue tracker).

I would like to thank (in alphabetical order) Ala'a Mohammad Alawi, Jay Bromley, Pau Fernández, Johann Korndoerfer, Peter Mikula, and especially Kei Suzuki (who did the last major reorganization) for their contributions to the library (again, I apologize if I missed anyone). I would also like to thank Ryan for taking over — I am convinced that the library is in good hands.

Color schemes to prevent eye fatigue

2011-11-01T01:23:00.000-07:00

I have been sitting in front of the computer quite a bit in the past few weeks, and I noticed that my eyes get very tired by the end of the day (I used to get back pain too, but stretching helped a lot). After a bit of reading I learned that the maximum-contrast white-on-black-based color scheme I was using is in fact extremely stressful for the eyes, and I started looking for something designed for the specific purpose of reducing eye fatigue. After checking out Zenburn for a few days, I started using Solarized by Ethan Schoonover. I find it really nice and relaxing, here is a screenshot of Emacs editing Common Lisp code:

New and updated libraries

2011-11-01T00:59:00.000-07:00

Lately I have been trying to be more organized about updates to my libraries: I always try to keep the master branch on Github in a consistent state for all of them, and merge the development branches for all libraries at the same time. I have been doing that yesterday, here is a brief summary of the changes.

cl-num-utils mostly received minor fixes: I cleaned up the accumulator code a bit, and added a few minor convenience functions. The package now exports median, which causes a symbol conflict with alexandria:median so you need to shadow if you are using both. Maybe I should ask the developers of Alexandria to make mean, variance and median generic.

LLA underwent a medium-scale rewrite: I sanitized the type system (internal types are no longer exposed), cleaned up object creation functions (CLO replaced with HERMITIAN, LOWER, etc), and wrote specialized routines for array sharing which are about 30 times faster than they used to be — this of course doesn't mean that LLA is now 30x faster, just that they overhead for sharing arrays got a lot smaller. Since many operations are $O(n^\alpha), \alpha \geq 2$, this is mostly noticeable for small arrays. Note that this is still generic CFFI-based code, preliminary tests indicate that implementation-specific tricks could yield array copying code that is 2-5x faster, but currently I have neither the time nor the inclination to write this, because I would rather wait for other parts of LLA to settle down before I micro-optimize. However, if you find that array copying overhead is critical for you, please let me know and I will see what I can do — this rewrite was prompted by the benchmarks sent by Robert Brown.

Realizing that implementing special functions in Common Lisp is perhaps not the best use of my time, I decided to use a foreign library for this purpose in cl-random. I chose R's standalone math library, with an SWIG-generated wrapper (it took about 30 minutes to have this library running, SWIG is amazing). I made the result available as a small standalone library called cl-rmath in case anyone else wants to use it. I really appreciate that the R developers made this available as a standalone library, it makes my life much easier. Besides these changes, I only made small changes to cl-random, for example, the univariate normal now has the syntax (r-normal mean variance) instead of the standard deviation, to be more consistent with the multivariate case.

Finally, it looks like cl-2d refuses to die, so I fixed some of the minor bugs that were the result of other libraries moving on. I am working on a replacement library, but I will probably keep cl-2d updated until the new library is ready. It amazes me how many people are using cl-2d: I get questions and bug reports all the time. It is not a bad library, but I wrote it when I was a CL newbie and I hope that I can write a much better one — we shall see. In any case, if you are not using cl-2d, I would recommend that you don't start now.

Is anyone using cl-2d?

2011-09-06T23:36:00.000-07:00

I wrote a Common Lisp plotting library called cl-2d in 2009, and I have been using it for my own graphs ever since. I am currently working on a library that implements the same functionality but with a much more friently interface and a different engine, using LaTeX and pgf to generate the plots instead of cairo. This gives me a lot of useful features out of the box, including very nicely formatted formulas if I want to use them in annotations, and it is reasonably fast for my purposes.

I plan to remove the existing cl-2d repository from Github, put up a new one (it is a complete rewrite from scratch, there isn't much sense in carrying around the old source), and recycle the name (for both the package and the library).

I don't think that there is anyone out there using the current version of this library, but in case you are, please let me know soon.

Persistent misconceptions about Lisp

2011-09-02T04:54:00.001-07:00

I am in the process of implementing (yet another) graphing library Common Lisp, one that would conform to my requirements better (I will blog about it later on). In order to understand some issues better, I decided to read The Grammar of Graphics by Leland Wilkinson. The book is very well written and clearly organized, and I think it will turn out to be very useful for what I am doing. However, I encountered a couple of misconceptions about Lisp in the Introduction. On page 4, the author claims that

Some languages, like Simula, Smalltalk, and Java, make it easy to implement objects and difficult to implement procedures. Others, like C++, enable development of both objects and procedures. And others, like C, Pascal, Ada, BASIC, Algol, Lisp, APL, and FORTRAN, make it difficult (but not impossible) to develop objects.

O RLY? Most users of CLOS find both objects and "procedures" very easy to use, and at least on par with other OO languages. Moreover, I don't understand how Lisp ended up in the company of C, which doesn't have any OO whatsoever.

On page 5, we are told that

Lisp is ideal for manipulating lists of words and symbols because it is a list processing language.

Strictly speaking, this is true, but Lisp is much more than a list processing language: it is also used to tackle numerical problems and usually does a very good job. Compiled code can be very fast, especially with implementations like SBCL, and Lisp has a very nice foreign function interface library.

That said, from what I have read so far, the book appears to be excellent, and the author is clearly an expert on the topic. Statements about programming languages are tangential to the book in any case, so I don't understand why the author found it necessary to talk about a language that he is not so familiar with.

Library configuration in Common Lisp: an example

2011-07-21T05:30:00.001-07:00

I have been dodging the issue of configuration for LLA for a while, but eventually I had to come up with a solution for the revised version that I pushed to Github yesterday.

LLA users may need to configure two things: the location and name of libraries that they want to use, and whether LLA should use 64-bit integers to interface with BLAS/LAPACK (this is rarely needed, even on 64-bit platforms, as many implementations still use 32-bit integers). In the previous versions of LLA, I tried to do this with read-time conditionals (based on trivial-features) but this was not satisfactory as it is impossible to figure out the list of libraries from nothing but the platform information — for example, a Linux user could use ATLAS or MKL.

I read Maintaining Portable Lisp Programs by Christophe Rhodes and also asked on cl-pro, where I got a lot of good suggestions and decided to follow the advice of Pascal Costanza. This is how configuration works at the moment for LLA:

The user may define a variable *lla-configuration* in the CL-USER package. The variable should contain a plist of configuration options, eg :libraries. The variable does not need to be bound, and it can be NIL or incomplete: the user only needs to deal with configuration when he wants to override the defaults of the library. LLA makes an effort to come up with sensible platform-specific defaults.
When loaded/compiled, LLA checks whether cl-user::*lla-configuration* is bound, and if it is, it uses the corresponding values. If the variable is not bound or doesn't contain the desired property, a default value is used instead.

Internally, some features are implemented by pushing symbols like lla::int64 to *features*. I have do admit that I didn't even consider the possibility of package qualifiers in read-time conditionals before I read the appropriate sections of the Hyperspec, but in retrospect it makes perfect sense as it helps to avoid name clashes. LLA also removes its own symbols from *features* if they don't belong there: this means that you can reload the library with a different configuration without restating your CL image.

LLA reorganization almost finished, new version on Github

2011-07-20T04:43:00.000-07:00

I have almost completed the reorganization of LLA and merged it to the main branch on Github (sorry, no installation via Quicklisp until the library is fully stable, for the moment you have to check it out from Github). Make sure that you get the latest dependencies, most importantly cl-num-utils and let-plus.

This version of LLA boasts a reorganized interface: most importantly, now it works with plain vanilla Common Lisp arrays:

LLA> (defparameter *a* #2A((1 2) (3 4)))
*A*
LLA> (mm t *a*) ; same as A^T A, but LLA recognizes that the result is Hermitian
#<HERMITIAN-MATRIX 
  10.00000        *
  14.00000 20.00000>
LLA> (elements *)  ; Lisp arrays inside all special matrices
#2A((10.0d0 0.0d0) (14.0d0 20.0d0))
LLA> (svd *a* :thin)
#S(SVD
   :U #2A((-0.40455358483375703d0 0.9145142956773045d0)
          (-0.9145142956773045d0 -0.40455358483375703d0))
   :D #<DIAGONAL 
  5.46499       .
        . 0.36597>
   :VT #2A((-0.5760484367663207d0 -0.817415560470363d0)
           (-0.817415560470363d0 0.5760484367663208d0)))
LLA> (elements (svd-d *)) ; Lisp arrays again
#(5.464985704219043d0 0.3659661906262576d0)

LLA uses clever tricks to avoid transposing when it can. Row-major and column-major representations are transposes of each other, and instead of calculating an SVD as $$A=UDV^T$$ LLA justs calculates $$A^T={V^T}^T D^T U^T$$ and returns $U$ as $V^T$ and vice versa. Of course transposing cannot be avoided all the time, but it is not needed often and should not impose a large performance penalty. So LLA can work with row-major Common Lisp arrays natively — in fact, that's the only array representation it supports.

This version of LLA has a reorganized DSL for BLAS/LAPACK calls which makes it really easy to wrap Fortran functions in general, not just LAPACK/BLAS functions for which it has extensions. For example, this is how Cholesky factorization is implemented:

(defmethod cholesky ((a hermitian-matrix))
  (let+ ((a (elements a))
         ((a0 a1) (array-dimensions a)))
    (assert (= a0 a1))
    (lapack-call ("potrf" (common-float-type a)
                          (make-instance 'cholesky :left-square-root 
                                         (make-lower-triangular-matrix l)))
                 #\U (&integer a0) (&array a :output l) (&integer a0) &info)))

The first two lines are just bookkeeping: the array A containing the elements of the hermitian (symmetric) matrix (in the lower triangle) is extracted, and its dimensions are examined. LAPACK-CALL figures out whether to use SPOTRF, DPOTRF, CPOTRF, ZPOTRF from the element type of the matrix, allocates memory for atoms (recall that Fortran takes pointers) using the macros, and automatically examines the INFO parameter at &info to catch exceptions. The #\U in the code suggests that storage is upper-triangular, even though in CL we store elements of the hermitian matrix in the lower triangle: this is because we avoid transposing. I find that it is really easy to write wrappers to Fortran code using this macro family (there is also a BLAS-CALL and a LAPACK-CALL-W/QUERY that queries workspace sizes), and it should be easy to write a FORTRAN-CALL for general Fortran code, or even a wrapper for C functions that handle arrays. Let me know if you are interested in any of these, I would be happy to add them or even factor out this part of LLA into another library.

By the way, contrary to what my previous post on LLA said, you no longer need the C wrappers in MKL or CLAPACK, so ATLAS or something similar is just fine. The README has instructions on how to set up these libraries (unless you want to compile your own, a single apt-get install or similar is enough to satisfy LLA's dependencies) and configure custom library locations.

Even though LLA is now perfectly usable and all the unit tests work just fine, there are still some things left to do:

Write the array implementation-specific sharing macros.: LLA uses a few macros to make arrays available for foreign functions, and all the wrappers are built around these. The idea is to avoid copying if the implementation supports it, and otherwise fall back to copying. I decided to focus my efforts on getting LLA to work again first, and this means that currently all operations fall back to copying, which should entail a slight performance penalty. I will of course remedy this at some point, first for SBCL and ECL and then for the other distributions, but I am waiting for the rest of LLA to stabilize before I start fiddling with low-level optimizations.
Eigenvalues/eigenvectors are not yet implemented.: LAPACK's handling of eigenvalues and especially eigenvectors is a mess, and I need to dust off the code that picks out paired eigenvectors. It should be fairly easy, but I prefer not to add functionality without thorough testing, so currently I am postponing this until someone needs it (just drop me a line).

Also, even though I wrote a lot of unit tests, it is of course possible (and probable) that LLA has bugs. Please report them on Github.

I would like to thank all users of LLA for helpful suggestions and for the gentle nudging I received during LLA's reorganization. I believe that LLA fills an important niche, and I will continue to work on it.

Why I only buy e-books from indie publishers

2011-07-14T08:16:00.000-07:00

Nikodemus Siivola blogged about the $2 surcharge Amazon extracts from Kindle customers outside the US. I use my Kindle every day, and I buy e-books to read on a regular basis, spending around $10-30 a month (depending on how much time I have for reading). I have owned a Kindle for almost a year now, but I didn't know about this surcharge: I guess the reason for this is that none of the money I spent on e-books went to Amazon.

There are two reasons for this: their non-competitive pricing and DRM. First, I am reluctant to pay more for an e-book than I would for a paperback, yet I frequently saw e-books on Amazon that cost more than their paperback versions. I understand that Amazon is trying to extract economic rents using its strong position in this market, but I would feel like an idiot if I participated in this scheme.

Regarding DRM: I like my Kindle very much, but I think that in the long run e-book readers will become even more of a commodity (like laptops or cell phones), and I don't wish my e-book collection to be tied to Amazon. Call me old-fashioned, but I do want to own the content I pay for, especially if I paid almost as much as I would pay for a hardcopy. So I only buy DRM-free books.

I mostly read literature on my Kindle. I buy quite a bit of sci-fi from Baen books — they also have a lot of books available for free, knowing full well that good sci-fi is addictive for some people anyway, but they don't exploit this: most of their books sell for $5-6. I haven't head a chance to check out Calibre's DRM-free book store, but it looks very promising.

I think that unless Amazon changes its pricing policy and considers offering DRM-free content, there is very little chance that I will buy anything from them. If you know some indie authors or publishers who sell reasonably priced DRM-free e-books, I would be interested in hearing about them.

LinkedIn: an obnoxious spam engine

2011-07-12T03:59:00.000-07:00

I have to admit that I don't see the point of so-called social networking sites, but I recognize the possibility that some people may find them useful, and I am just not one of them. Nevertheless, I still fail to see why random people I have never met want to add me as a contact. I get invitations from these people on LinkedIn almost daily, and to make it worse, LinkedIn then sends me reminders about them. Note that I am not even registered on their damn site. I don't have a profile, and I have no intention of creating one.

Which presents another problem: I couldn't find a way of opting out from these invitations without creating a profile. Clever, isn't it? They send you spam, and then they are trying to sucker people into registering to stop spam. I could just start marking these messages spam, but I think that my spam filter would take a while to learn this, and in any case, I don't want to add noise to the Bayesian model just to create false positives for relevant e-mail. The cleanest solution I found is putting the whole linkedin.com domain on my blacklist.

I want to emphasize that this is a rare distinction: with spam filters getting so clever (thank you, Gmail!), I haven't had to manually blacklist a sender in years. Congratulations are in order: dear LinkedIn, you are a really obnoxious engine for spam! I sincerely hope that you vanish to oblivion soon.

Goodbye Ubuntu, hello Debian

2011-07-11T08:21:00.000-07:00

My road to Ubuntu

I have started using Linux around 1998. I remember that I wanted to try out several distributions before settling on the one the "best" one, but I had a dial-up connection (28kbps, if I remember correctly) and downloading all of them seemed infeasible, so I mail-ordered a set of CDs that contained Red Hat, Slackware and Debian. I think I decided on Debian because I liked the clean and transparent package management system, especially APT which seemed way ahead of other distributions at that time. Linux became my primary OS within a few months: even though it didn't have a fraction of the tools that are available today, it had everything I needed.

A lot happened in the Linux world since then. I don't know when (if?) Linux "conquered" the desktop, but in 2003 it became mature enough that I installed Linux (Debian, of course) on my parent's desktop. Neither of my parents are very computer-savvy, but they also found Linux much nicer than Windows. I think what mattered the most to them is its stability: I would update the software once in a while, test that everything was working (and fix it when it didn't), but in the meantime, the system was rock-solid. This was important as I no longer lived in the same city, so I couldn't just drop by to fix computer problems on a short notice, which I had to do with Windows.

When they got another computer (I think it was around 2005), I replaced Debian with Ubuntu, figuring that it would provide a more polished user experience, and I was pleased with the result. I installed Ubuntu on all computers that family members asked me to help with, and in 2009, I installed Ubuntu on a new laptop I got. It was a bit more polished than Debian, especially when it came to setup things like printers and network drives. I knew how to do those things via the relevant config files, but I appreciated the GUI.

Why I moved back to Debian

I think that I like Linux because it allows me to concentrate on my work: I came to accept that sometimes setting things up required a bit of tweaking, but once I configured something, it would work exactly the way I liked it. I welcome changes if they make sense (eg a feature extension), but I don't see the point of gratuitous ones. In retrospect, I should have considered the moving of window buttons a warning sign, especially when Mark Shuttleworth refused to move them back despite popular demand. The fix was easy, but the whole move was totally unnecessary and resulted in a lot of confusion: until I fixed it (I really did give it a try for a few days), my desktop just felt like a car with the gas and brake pedals interchanged.

The controversy surrounding Unity was the real eye-opener for me. I dist-upgraded Ubuntu on my parents current computer (a perfectly good desktop for office work, around 2 years old) and was informed that the system doesn't have the resources to run the damn thing. I tried it out on my laptop briefly, and realized that all that glitz and glitter is unnecessary and a waste of resources (most importantly battery power), and Ubuntu was trying to force yet another gratuitous UI change on its users. I backed up my data, wiped my HD, and within an hour, I was back to good old Debian. Which still rocks.

Why Debian is perfect for me

In order to answer that question, here is a sample of the desktop software that I use (of course I use a lot of other programs, eg Git or SBCL, but there is no purpose in enumerating all of them):

desktop environment: XFCE (with some Gnome applets in the panel)
e-mail: mutt, offlineimap, msmtp
shell: zsh, running under screen in yakuake (with the Tango color scheme — I got used to that from Gnome)
editing: emacs, TeX Live, AUCTeX, org-mode, …
browser: chrome
password manager: Revelation
newsfeeds: Liferea

This is a pretty eclectic mix with no overall GUI concept — for example, it has programs from Gnome and KDE — but I have come to like each of these programs and they work very well for me. Debian testing has pretty recent releases for all of them, and more importantly, the idea of Debian developers forcing any particular choice on how I set up my desktop never even comes up at any point. They provide excellent software, take care of packaging new releases and fixing bugs, but I doubt that any of them would even entertain the idea of pushing some wacky desktop du jour concept on their users. I think that they have better things to do with their time, including maintaining the best Linux distro out there, and that's the way I like it.

The icing on the cake

Compared to my previous desktop (which was plain vanilla Gnome, Ubuntu/Maverick), the above setup appears to be much less resource intensive. I have plenty of RAM and CPU power, but I noticed that my laptop gives me about 20% more battery time than it used to. I cannot help but love Debian. It is good to be back!

LLA reorganization almost done

2011-06-27T06:30:00.000-07:00

As many of you have noticed, the Lisp Linear Algebra library is currently undergoing a major reorganization. The new branch is incomplete, but what is there is perfectly is usable and passes all unit tests. The purpose of this post is to give a preview of changes and invite LLA users to experiment with the new version before it is "released".

Why the new version?

Also relying on LAPACK, the previous version of LLA used a column-major representation. This meant that even though matrices were represented using Common Lisp arrays (in particular, vectors) under the hood, they had to be wrapped to indicate that they were column-major. However, less then a year ago the LAPACK Team finally standardized the C interface for the library, which now provides row-major matrices. This means that you can use Common Lisp arrays in LLA:

(let ((a #2A((1 2)
             (3 4)))
      (b #(5 7)))
  (solve a b))

which computes $A^{-1}b$, evaluating to

#(-3.0d0 4.0d0)

Note that the result contains double floats instead of integers: in fact, in implementations that support it, the element type of the array will be double-float.

This is because most LLA operations work like this:

Determine the narrowest common element type of each argument. Unless the element type of the array is something specific that LLA can recognize (eg single and double floats and their complex versions), LLA needs to traverse the array, which costs a bit in terms of speed. Use arrays with specialized element types to avoid this cost. Integers and rationals are converted to floats (you can control which, double is the default).
Determine the narrowest common element type of the pertinent arguments. For example, in the code above, LLA decided to use double floats, which also determines the element type.

The use of Common Lisp arrays made LLA much more transparent without any noticable overhead, especially if you use arrays that have the appropriate element types (instead of T). Even if you don't, LLA functions will return arrays that have specialized element types, so if you chain LLA operations, your code should be efficient without any particular effort.

Hermitian and triangular matrices are now wrappers around simple two-dimensional arrays. You should use as-array to convert to a dense matrix.

Required libraries

You need an implementation of LAPACK that provides the C interface. Currently, the two available choices are LAPACKE and Intel's MKL. I have been using the latter to develop the new version of LLA, so I don't have instructions on how to compile and set up LAPACKE with other libraries. If you figure it out, please write it up and I will post it in the README file of LLA.

If you install MKL on Linux, all you have to do is tell the linker where the libraries are: for example, all I had to do was create the file /etc/ld.so.conf.d/mkl.conf with contents

/opt/intel/mkl/lib/intel64
/opt/intel/composerxe/lib/intel64

and run ldconfig.

Portability

LLA uses CFFI, and should be perfectly portable. However, implementations that don't support arrays with element types single-float, double-float, (complex single-float) and (complex double-float) will suffer a performance penalty because LLA has to check the array elements to determine the narrowest type.

State of the new version

Everything works except eigenvalues and singular value decompositions. Drop me a line if you are using the new version and need either one of those, I am happy to implement them — it should be relatively easy, but I have kept features to the minimum while the library is in flux.

In principle, LLA should be clever enough to avoid copying of arrays when possible (ie no type conversion is necessary and the implementation supports foreign arrays — most of them should), but currently I am using the CFFI backend for testing.

As always, feedback, bug reports and suggestions are very welcome.

Validate XHTML 1.0

Introducing LET+, a destructuring extension of LET*

2011-05-23T22:48:00.000-07:00

Why another destructuring library?

This Common Lisp library extends the syntax of let*. In that respect it is pretty similar to other destructuring libraries, most importantly Gary King's excellent metabang-bind. I have been using the latter for years now, but at some point I decided to write a library of my own, aiming for a cleaner syntax, more concise implementation and a more consistent interface (whether I have succeeded is of course a matter of judgement — try metabang-bind to see if you like it better).

This library differs from metabang-bind in the following ways:

Placeholder macros like &slots, mainly for providing editor hints (completion, eg syntax reminders in the Emacs status bar with SLIME, displaying of arguments, etc).
More consistent naming of destructuring forms. In particular, when both read-write and read-only forms are available the latter always have the -r/o suffix
&flet and &labels resemble the Common Lisp syntax more closely.
The code is extremely simple (< 300 loc, not counting unit tests), and the library should be easier to extend.

Examples

Lists are destructured unless recognized as something else (values mapping to NIL are ignored):

(let+ (((a (b &optional (c 3)) nil &key (d 1 d?)) '(1 (2) 7 :d 4)))
  (list a b c d d?))  ; => (1 2 3 4 T)

Slots and accessors have a syntax similar to with-slots:

(defclass foo-class ()
  ((a :accessor a :initarg :a)
   (b :accessor b-accessor :initarg :b)))

(let+ (((&slots a (my-b b)) (make-instance 'foo-class :a 1 :b 2)))
  (list a my-b))  ; => (1 2)

(let+ (((&accessors a (b b-accessor)) (make-instance 'foo-class :a 1 :b 2)))
  (list a b))  ; => (1 2)

Slots in structures can be accessed by giving the conc-name:

(defstruct foo-struct c d)
(let+ (((&structure foo-struct- c (my-d d)) (make-foo-struct :c 3 :d 4)))
  (list c my-d))  ; => (3 4)

but if you use defstruct+ to define your structure, you automatically get a corresponding deconstructing form:

(defstruct+ interval left right)

(let+ ((interval (make-interval :left 1 :right 2))
       ((&interval left right) interval))
  (incf right 10)
  interval)  ; => #S(INTERVAL :LEFT 1 :RIGHT 12)

Multiple values are also supported:

(let+ (((&values a nil b) (values 1 2 3)))
  (list a b))  ; => (1 3)

You can access array elements in many different ways:

(let+ ((#(a nil b) (vector 1 2 3)))
  (list a b))  ; => (1 3)

(let+ (((&array-elements (a 0 1)
                         (b 2 0))
        #2A((0 1)
            (2 3)
            (4 5))))
  (list a b))  ; => (1 4)

You can use &flet (and &labels, if the function needs to refer to itself) to write functions:

(let+ (((&flet add2 (x)
          (+ x 2))))
  (add2 5))  ; => 7

&plist and &hash-tables allow access to elements property lists and hash tables.

Read-only forms

All of the &... forms have a read-only version, eg &slots-r/o. With these, the values are read at the beginning, and you can modify them without modifying the original structure. Read-only forms may also give you a slight increase in speed, and promote better style by indicating that you are not modifying the original structure.

How to get it

The library is a available on Github, under the Boost Software License (Version 1.0). The README file there serves as the documentation, see the source code and unit tests for mode details. As always, bug reports and suggestions are welcome.

The status of cl-sparsematrix

2010-10-06T09:23:00.000-07:00

In 2008, I had to solve some linear equations of the form Ax=b, where A was a sparse matrix (usually a design matrix for B-splines). I wrote up a library called cl-sparsematrix in one afternoon, and put it on the web.

This was not a sophisticated library. It did three very basic things: it helped construct a sparse matrix using a hash-table, had a function to pack that up in CSC format, and finally, a function to call UMFpack via CFFI to solve the equation mentioned above. This was it. It worked fine for what I wanted to use it, but it was not a sophisticated sparse matrix library.

I didn't have a need for sparse matrices ever since, and the library succumbed to bit rot: some other libraries it depended on moved on, quite substantially in some cases, and now it doesn't even load cleanly. But I still get a few e-mails every month asking about this library. So apparently there is a need in the CL community for a sparse matrix library. I have no time to clean it up at the moment, and you are probably better off writing your own. The library is no longer available online, because it doesn't work and I don't want to mislead people who are looking for a sparse matrix library.

When LLA is finalized, I will include sparse matrix functionality at some point. But LLA is undergoing (yet another) major reorganization now — I think I finally figured out how to interface native Lisp arrays to LAPACK in the implementations that support pinned arrays. So sparse matrices are not on the immediate horizon. Unless, of course, I need to solve sparse systems again, and hack up yet another quick-and-dirty solution.

Sub-array indexing

2010-05-30T11:08:00.000-07:00

One of the things I have been missing in CL was convenient indexing for sub-arrays. Languages like R and Octave all have convenient sub-array indexing. I have experimented with various designs before (some of them I made public, eg AFFI and xarray), but none of them were entirely satisfactory and I kept searching for new solutions.

This is primarily an issue of syntactic convenience: I want to be able to select elements from arrays without writing (nested) loops. I also want to be able to copy elements from arrays to other arrays, similarly selected. Speed is welcome, but at this stage it is secondary: so far, profiling indicates that these operations comprise a tiny fraction of execution time in my programs, but having the ability to capture operations using (sub)arrays is an enormous timesaver and an invaluable semantic abstraction.

Introduction to `sub`

My latest attempt at tackling this problem is the generic function sub in my cl-num-utils library (BTW, this library is the successor of my earlier cl-numlib, which is now deprecated, all useful functionality will end up in other libraries, eventually). The syntax is as follows: (sub object &rest ranges). Each range is either a fixnum (selecting a single index), (cons start end) (selecting indexes in that range, excluding end as is usually done for CL library functions), t for all indexes, and finally, a vector of fixnums for anything else.

Let's see some examples:

CLNU> (defparameter *a* #2A((1 2 3 4) (5 6 7 8) (9 10 11 12)))
*A*
CLNU> *a*
#2A((1 2 3 4) (5 6 7 8) (9 10 11 12))
CLNU> (sub *a* 1 t) ; second row
#(5 6 7 8)
CLNU> (sub *a* '(1 . 2) t) ; second row as matrix
#2A((5 6 7 8))

Notice how a single fixnum will drop that dimension (making a vector from a matrix), while selecting the same row with a cons doesn't.

For all other cases, you can use vectors:

CLNU> (sub *a* t #(0 3)) ; first and last columns
#2A((1 4) (5 8) (9 12))
CLNU> (sub *a* t #(3 0)) ; last and first columns
#2A((4 1) (8 5) (12 9))

You can also use negative numbers for indexes: if (minusp index), it will select the column (- dimensions index):

CLNU> (sub *a* -1 t) ; last row
#(9 10 11 12)
CLNU> (sub *a* #(-2 -1) #(-2 -1)) ; bottom right 2x2 matrix
#2A((7 8) (11 12))

Finally, 0 in a cons corresponds to the largest possible index in that dimension:

CLNU> (sub *a* '(-2 . 0) t) ; last two rows
#2A((5 6 7 8) (9 10 11 12))

Setting subarrays

sub can also be used with setf:

CLNU> *a*
#2A((1 2 3 4) (5 6 7 8) (9 10 11 12))
CLNU> (setf (sub *a* 1 t) #(-1 -2 -3 -4)) ; replace second row
#(-1 -2 -3 -4)
CLNU> *a*
#2A((1 2 3 4) (-1 -2 -3 -4) (9 10 11 12))
CLNU> (setf (sub *a* 2 t) (map 'vector #'+ (sub *a* 0 t) (sub *a* 1 t)))
#(0 0 0 0)
CLNU> *a*
#2A((1 2 3 4) (-1 -2 -3 -4) (0 0 0 0))

Note that the ranks have to be equal, make sure that you keep/drop dimensions as needed.

Macros for implementing `sub`

In cl-num-utils, you also find the macro with-range-indexing, which preprocesses the range arguments and implements an internal counter for row-major indexing. For example, sub for arrays is implemented as

(defmethod sub ((array array) &rest ranges)
           (declare (optimize debug (speed 0)))
  (with-range-indexing (ranges (array-dimensions array) next-index
                               :end? end?
                               :range-dimensions dimensions)
    (let ((result (make-array (coerce dimensions 'list)
                              :element-type
                              (array-element-type array))))
      (iter
        (until end?)
        (for result-index :from 0)
        (setf (row-major-aref result result-index)
              (row-major-aref array (next-index))))
      result)))

The macro takes the range specification as the ranges argument, and also needs the original dimensions of the array. next-index should be the name of the function that will be used to query the next index: it increments the internal counter and delivers the next index. The internal counter is an array of fixnums, and the index is calculated with an affine mapping, but the algorithm allows to update the sum only for the indexes which actually changed. All this is hidden by the macro. end? is a boolean, which can be used to query when all the elements have been traversed. dimensions will be bound to the dimensions of the result, after allowing for dimension droppings.

This macro is pretty versatile: I used it in LLA to implement (sub dense-matrix-like ...), ((setf sub) array dense-matrix-like ...) and ((setf sub) dense-matrix-like array ...) methods, even though LLA is column-major. The trick is to swap dimensions.

Upgraded array element types and pinned arrays (updated)

2010-05-17T08:56:00.001-07:00

I am planning to do a major rewrite of my LLA library in the near future. LLA, which stands for Lisp Linear Algebra, uses BLAS and LAPACK to perform operations on matrices (and vectors), ranging from matrix multiplication to singular value decompositions. LLA is experimental, and its aim is to provide semantics which recognize special matrix types both as inputs and outputs. Maybe I will blog about it sometime, but that's not the focus of this post.

Currently, LLA uses Lisp arrays, but wrapped in a class which has a slot signifying the element type of the arrays. This is because it is meant to be portable, and not all implementations have upgraded array element types for every type LAPACK recognizes (see below). Also, LLA matrix representation is currently column major, and Lisp arrays are row-major.

However, I realized that I can use Lisp arrays in more places - LAPACK handles row-major arrays just fine (as transposed column-major arrays). Besides, having a native Lisp array is nice, eg one can just use functions like REDUCE or REPLACE, without dealing with a special type. However, there is a price to pay: when LAPACK routines are called, the array element type has to be detectable. For implementations which upgrade element types use by LLA to themselves or something specific, this is a cheap operation. For implementations that don't, it requires an extra pass.

Another issue is whether your implementation has what SBCL calls "pinned" arrays. Pinned arrays can make their contents available to foreign routines directly with negligible overhead for a limited duration (or maybe indefinitely, but I prefer the first).

I asked for implementation-specific details on c.l.l, and got the following information:

Implementation	Machine	S	D	CS	CD	I32	I64	pinned?
SBCL (1.0.38)	64-bit	*	*	*	*	*	*	yes
Lispworks (6.0.1)	32-bit	*	*	T	T	*	*	?
Lispworks Personal Edition (5.1.1)	32-bit	*	*	T	T	*	T	?
Clozure CL (1.4, 1.6)	32-bit	*	*	T	T	*	T	yes
Clozure CL (1.6)	64-bit	*	*	T	T	*	*	yes
ECL (10.3.1)	32-bit	*	*	T	T	T	T	yes
ABCL (0.13.0)	64-bit	T	T	T	T	T	T	?
Allegco CL Enterprise Edition (8.1 & 8.2, Linux and Windows)	32-bit	*	*	*	*	*	T	?
Allegco CL Enterprise Edition (8.1 & 8.2, Linux and Windows)	64-bit	*	*	*	*	*	*	?
CLISP (2.48)	both	T	T	T	T	T	T	?
CMUCL (19e)	32-bit	*	*	*	*	*	T	yes
Corman Common Lisp (3.01, Windows)	?	*	*	T	T	T	T	?

The interpretation is this: S, D, CS and CD correspond to (complex) single and double float. I32 and I64 are signed-byte types of 32 and 64 bits. * means that the element type is upgraded to itself, otherwise the table shows the upgraded type.

The following table gives some details on the pinning mechanism when the implementation has it:

Implementation	Pinning construct	Notes
SBCL	sb-sys:with-pinned-objects with sb-sys:vector-sap	pins object only where GC granularity allows
Clozure CL	ccl:with-pointer-to-ivector	disables GC
ECL	?	conservative GC, data can be used as long as the object is alive

So LLA is likely to have the following optimization model: it will be blazingly fast (basically the speed of LAPACK, with a tiny bit of overhead) on implementations which support all upgraded types and pinning, and a bit slower on other ones. If your implementation supports upgrading some of the above element types to themselves, those arrays will require no element type detection so they will be faster. I64 is only needed on 64-bit machines.

The motivation behind this decision is that if you are doing serious numerical work, your implementation should support all relevant array element types and also pinning. SBCL does, and since I am using that, the new version of LLA will take advantage of all its nice facilities — it already does, but currently it only runs on SBCL so that was natural. LLA will be fully functional on other implementations, but may be slower.

Please keep sending in information for the implementations you don't see in the table above. I am especially interested in which implementations support pinning. You can use this code snipped to generate output on array element type upgrading:

(flet ((check-upgraded (type)
         (let ((upgraded (upgraded-array-element-type type)))
           (format t "~A is upgraded to ~A~%"
                   type
                   (if (equal type upgraded)
                       "itself"
                       upgraded)))))
  (format t "~2&~A (~A) on ~A (~A)~2%"
          (lisp-implementation-type) (lisp-implementation-version)
          (machine-type) (machine-version))
  (map nil #'check-upgraded '(single-float double-float
                              (complex single-float) (complex double-float)
                              (signed-byte 32) (signed-byte 64))))

Revenge of the reader

2010-03-01T08:07:00.001-08:00

Yesterday, I was compiling a function in SLIME, and I consistently got error: illegal function call messages from SBCL. The function was a pretty complicated one, and I couldn't figure out the error. I even resorted to commenting out sections, until I had an empty shell, with only the docstring. Then realization dawned — here is a simplified example of how the function looked like:

(defun foo (bar)
  "Docstring, followed by accidental dot".
  (let ((baz (1+ bar)))
    baz))

Did you notice the dot? I didn't, for a while (guess I should take breaks every hour or so and rest my eyes, especially in the evening). But the reader did.

God wrote in LISP

2010-01-06T01:08:00.000-08:00

I was googling for this XKCD comic when I accidentally found The Eternal Flame (God Wrote in LISP) by Julia Ecklar. The song itself is a parody of a filk. The parody lyrics were written by Bob Kanefsky.

Book review: Pro Git by Scott Chacon

2009-12-31T01:46:00.000-08:00

Like many others, I use git as a version control system for my Lisp code. Version control is one of those things that offer a lot of benefits with relatively little investment: I picked up a few basic git commands from tutorials on the internet (Github has a nice collection), but didn't bother to learn about git in depth.

However, as others started to contribute to my libraries, I was forced to learn more about certain features, most importantly branching and merging. After spending a few hours doing things the wrong way, I realized that I need to do some reading, and I was lucky to find Pro Git by Scott Chacon, one of the prominent git developers. Thanks to the author and the publisher (Apress), the book is available online. I really appreciate that Apress makes its books available online so I can start reading them immediately, and I have already ordered a dead tree copy.

The book is a pleasure to read, and is really useful. Instead of simply rehashing the manual, it focuses on explaining the concepts of git, and illustrates them with typical workflows. I found this invaluable: understanding the concepts behind git made me realize that I have been doing things the wrong way. I used subversion before, and it was still influencing the way I use git. For example, branching in git is really, really cheap, and I learned that I should do it more often.

My favorite chapters from this book are Git Branching, which explains the concept of branches, gives examples of basic branching and merging, branch management and typical workflows, and also discusses remote branches, and Distributed Git, which talks about distributed workflows in more detail.

I have learned a lot from this book, and hopefully it will help me manage my Lisp libraries better. So far I have been keeping changes on my hard disk between "releases" (updates to master), but now I think that I will make development branches for new features and push them more often.

Maxell pendrive suckage

2009-12-31T01:19:00.000-08:00

I had to reinstall the OS on my parents' computer during the Christmas holidays. I forgot to bring my external hard disk with me, so I decided to buy a pendrive to backup their files.

Unfortunately, I picked a Maxell Venture to do the job. Maxell puts this pendrive in their Business Range line. I learned about this later because this is not indicated on the packaging. If it had been, I wouldn't have touched the product with a ten-foot pole. I consider pendrives a commodity: they should present a standard interface, and the only qualitative differentiation I can imagine is sleek and/or durable design or novelty packaging (not that I care for the latter).

Apparently, some pendrive manufacturers think otherwise. Maxell decided that it would indulge consumers with "extra features", such as "security and file compression software". Unfortunately, this makes the pendrive interface non-standard. The pendrive shows up as two physical devices, one contains a small partition called SECRET, the other has a large partition called PUBLIC. Apparently, this feature is governed by the firmware. There is no way to repartition the device (which shows up as /dev/sdb and /dev/sdc at the same time), and it is impossible to get rid of these "features". An added bonus is that I found it impossible to make this pendrive boot: the BIOS of my computer was understandably confused about this whole arrangement.

Nice job, Maxell. I returned the pendrive to the store the next day. When I googled for a possible solution, I learned about a similar "extension" called U3, which is equally useless but at least it can be removed (albeit only using Windows), and the U3 folks are decent enough to offer removal software on their website. By the way, Maxell support still hasn't answered my e-mail.

I think that companies should be free to offer "features" that break pendrives, but they should be obliged by law to display this warning message:

You are purchasing a pendrive with a non-standard interface.
Generally, this sucks.
Do yourself a favor and buy from one of our competitors.

Syntax highlighting with org-mode

2009-12-25T06:26:00.000-08:00

Blogging is probably the best way to disseminate information about new (features in) libraries in the Lisp community—if you are reading this, you are probably subscribed to Planet Lisp, which nicely aggregates all Lisp-related blogs that are registered. On the other hand, blogging about Lisp is—or was—quite a hassle to me. I am using Google's blogger.com, which has nice features, but I am used to Emacs and prefer typing text there. Including Lisp code snippets was a pain in the butt: I had to keep playing with <pre> tags and it still didn't look right. But now I had a bit of time to explore the issue and found a workflow that is

pretty painless and
does syntax highlighting.

It uses org-mode, which I already use to manage my agenda. I would like to thank EMACS-FU, Blogistic Reflections, Drew Crampsie, Ross Lonstein, and Jānis Džeriņš for their help and/or blog posts on using org-mode.

Here is what you should do:

In Emacs, set org-export-htmlize-output-type to css. This makes org-mode emit formatting with <span> elements instead of inline style directives, which is the default.
Open a source file with org-mode (eg sample.org). Leave it empty, we just need it to generate some CSS. Use the Emacs function org-export (usually C-c C-e), and extract the CSS part. This is the first part of all the CSS styling you need.
Generate the second part with org-export-htmlize-generate-css.
Paste both parts into the CSS section served by your blog engine. For example, on blogger.com you should go to Layout, then Edit HTML, and paste it after the <Variable name=...> section where the CSS formatting starts. There will be some overlap between the two parts and possibly your existing template, but it should not matter. Edit colors, fonts, etc to the style you want. All I did was change the colors for the <pre> tags.
Turn off auto-conversion of line breaks. On blogger.com, you can find Convert line breaks in the Settings/Formatting section. Unless you do this, your blog engine could introduce unnecessary <br/> tags in the HTML.

You are now ready to post. A simple example looks like this in org-mode:

#+TITLE:     Sample blog post
#+AUTHOR:    Your Name
#+EMAIL:     your@email.address
#+LANGUAGE:  en
#+OPTIONS:   H:3 num:nil toc:nil \n:nil @:t ::t |:t ^:t -:t f:t *:tl creator:nil
#+OPTIONS:   TeX:t LaTeX:nil skip:nil d:nil tags:not-in-toc author:nil timestamp:nil
#+INFOJS_OPT: view:nil toc:nil ltoc:t mouse:underline buttons:0 path:http://orgmode.org/org-info.js

Here is some sample source code:
#+BEGIN_SRC lisp
(defun add2 (x)
  (+ x 2))
#+END_SRC
You can include example output:
#+BEGIN_EXAMPLE
CL-USER> (add2 3)
5
#+END_EXAMPLE
See the [[http://orgmode.org/org.html][Org Manual]] for further details.

You can include formatting options as shown in the example.

I use the following snippet in Emacs for settings and keybindings:

(defun org-export-body-as-html ()
  (interactive)
  (org-export-as-html 3 nil nil "blog" t))

(add-hook 'org-mode-hook
          (lambda ()
            (setq org-export-htmlize-output-type 'css)
            (local-set-key (quote [?\C-c ?\C-x]) 'org-export-body-as-html)))

A tour of xarray: part 1

2009-12-20T04:29:00.000-08:00

A tour of xarray

I frequently come across situations which require taking slices from arrays, and sometimes I need other high-level array manipulations, such as index permutations or projections to row- or column major. In an earlier attempt called affi, I handled these things using affine mappings, but now I realize that those are not general enough, and my need for these manipulations to be super-efficient was mostly imaginary. I started working on a library, which evolved to xarray, which is able to do these things (and much more—see the next post!) for any kind of array-like object, provided that they have the required minimal interface, defined as a few CLOS method. This blog post is the first of a series which is meant to give a tour of xarray.

The minimal interface

Xarray handles objects which can be addressed using a rectilinear coordinate system. No assumptions are made about the storage model, and if you want some class to be xarray-compatible, just define methods xdims, which gives a list of dimensions, and xref (also (setf xref), if your object is modifiable, but this is not required for basic functionality), which is a generic function pretty much like aref. Finally, there is the generic function xelttype to query element type. This is all you need to provide.

Based on xdims, reasonable defaults are provided for xrank, which returns an integer for the number of dimensions, xsize, which returns the total number of elements in the object, and (xdim object i), which is defined as (nth (xdims object) i) by default. Feel free to define these, though, if there is a "natural" way to do this for your objects (like it is for arrays, below).

To demonstrate how easy it is to do this for any kind of object, here are the definitions from array.lisp, which defines these methods for Common Lisp arrays:

(defmethod xelttype ((object array))
  (array-element-type object))

(defmethod xrank ((object array))
  (array-rank object))

(defmethod xdims ((object array))
  (array-dimensions object))

(defmethod xdim ((object array) axis-number)
  (array-dimension object axis-number))

(defmethod xsize ((object array))
  (array-total-size object))

(defmethod xref ((object array) &rest subscripts)
  (apply #'aref object subscripts))

(defmethod (setf xref) (value (object array) &rest subscripts)
  (setf (apply #'aref object subscripts) value))

In case a specialized method is not provided for an object, the default fallback methods (in atoms.lisp) just handle objects as atoms, ie arrays of rank 0. After you define the methods xdims, xref and xelttype—and nothing more!—for your class, you can use xarray's views. The (somewhat sloppy) terminology of xarray is to call classes which provide a minimal interface xrefable.

Views

Technically, views are functions mapping a set of rectilinear indexes to a (sub)set of an xrefable object called the ancestor. Practically, they are objects that walk and quack like arrays, but are usually a thin layer on other array-like objects.

Let's see some examples. I will use a Common Lisp array as a starting point, but of course these examples would work with any object as long as it is xrefable.

Slices

Slicing is the most obvious view that you can have for an array:

CL-USER> (defparameter *a* (make-array '(3 4) :initial-contents
                              '((1 2 3 4)
                                (5 6 7 8)
                                (9 10 11 12))))
CL-USER> (slice *a* 2 :all)
#<SLICE-VIEW 
#(9 10 11 12)  {B1025A1}>

Instead of an array, you get a slice-view object. Print-object for views usually just prints the elements as if they were an array, even if the ancestor isn't (this was simple to do, fancy printing may be introduced later at some point, but don't hold your breath). 2 selects the elements of same index along the 0th dimension, while :all selects all elements along the 1st.

You can get an array using take:

CL-USER> (take t (slice *a* 2 :all))
#(9 10 11 12)

The first argument tells take to return an object similar to the ancestor—we will tackle the concept of similarity and object creation in the next post about xarray.

For now, notice how slice dropped a dimension when you asked for a single index. You can avoid that by making it a list:

CL-USER>
(slice *a* '(2) :all)
#<SLICE-VIEW 
#2A((9 10 11 12))  {B9EBF59}>

You can drop unit dimensions with (drop object).

Lists of two elements select ranges (inclusive), which can also reverse elements, for example, ='(2 0)= would select the third, second and first elements along that dimensions. Negative integers count from the largest index (which is -1; think of -i as (- (xdim object d) i)) backwards, and :rev reverses all elements (so it is equivalent to \'(0 -1)). Finally, a vector just picks individual indexes (which can repeat, occur in any order, be negative following the conventions above, etc):

CL-USER> (slice *a* -1 :all)
#<SLICE-VIEW 
#(9 10 11 12)  {AC4FF31}>
CL-USER> (slice *a* :rev '(1 3))
#<SLICE-VIEW 
#2A((10 11 12) (6 7 8) (2 3 4))  {BAC83F9}>
CL-USER> (slice *a* '2 #(1 1 3))
#<SLICE-VIEW 
#(10 10 12)  {BB66859}>

Permutations

A permutation permutes the dimensions of an xrefable object:

CL-USER> (take t (permutation *a* 1 0))
#2A((1 5 9) (2 6 10) (3 7 11) (4 8 12))

Transposing is a special case of permutations, with indexes 1 and 0 (as above). Of course, you can combine views:

CL-USER> (slice (permutation *a* 1 0) :rev :rev)
#<SLICE-VIEW 
#2A((12 8 4) (11 7 3) (10 6 2) (9 5 1))  {AAAC849}>

Miscellaneous views

Two other special views are column-major-projection and flat views. The first one provides a projection of an object as if the elements of the two were arranged in column-major order (note that this may not be the actual storage model, as xarray does not make assumptions the latter but uses xref; however, for some special objects faster methods may be provided):

CL-USER> (column-major-projection *a* 6 2)
#<COLUMN-MAJOR-PROJECTION-VIEW 
#2A((1 3) (5 7) (9 11) (2 4) (6 8) (10 12))  {BE28921}>

Flat views just return an object with a single dimension, with the order of elements unspecified. This is advantageous if the object has a natural representation in some storage model, and we want to perform operations where the order of elements does not matter (eg sum the elements).

Semantics of views

(setf xref), when provided, sets elements in the ancestor of an object: if that is another view, the original ancestor (ie the object which is not a view) is modified. (Thus views always share structure. If you want to avoid this, use take to create a new object.

All the operations shown above are generic functions, you are free to specialize them. These methods

don't have to return subclasses of view, they are free to return any xrefable object as long as it shares structure,
are allowed to combine views.

For example, some CL array slices with contiguous row-major indexes could be implemented as displaced arrays, or a combination of a transpose and a slice can be folded into one view if the object supports that. Currently, these efficiency hacks are not implemented as I don't really need them, but the infrastructure is there.

Next time, I will address object creation and some generic operations on xrefable objects.

first steps with ECL

2009-12-06T07:46:00.000-08:00

I am living in Austria now and my German is very basic, so I use online translators to cope with the occasional e-mail in German that I can't decipher. I am using the mutt mail user agent, and in the past I have configured it to open HTML attachments in Firefox. However, with plain text messages manual copy & paste became tedious, so I decided to write a little script that opens them in Firefox.

This gave me a good excuse to play around with ECL, something that I wanted to do for a while. The choice of CL as a scripting language might seem odd to some people, but I find it is optimal for me. I am aware that there are DSLs for this specific purpose (called "scripting languages") out there, and some even look like Lisp. However, I find that it takes a bit of time to find my way around a new language, and since at this point I am convinced that I will keep using CL as my main programming language, learning a scripting language that gives no additional insight would be a wasted effort.

Here is the end result. The script is really simple, and it benefited quite a bit from the comments of people on comp.lang.lisp. I like using this script, but the greatest benefit I derived from writing it is discovering what a gem ECL is. For example, I only need to use the two simple commands

(compile-file "savebody.lisp" :system-p t)
(c:build-program "savebody" :lisp-files '("savebody.o"))

to compile the script to a small (37K) (I am serious — it is really that small) executable file via C. A nice summary of simple compilation cases can be found here. Reading the ECL manual, I found that there are even more powerful facilities for building programs.

I am very impressed with ECL, and will definitely consider it as a remarkable implementation in the future.

updates to cl-cairo2 and cl-2d

2009-06-15T05:29:00.000-07:00

Following the discussion and the resulting poll, I updated cl-cairo2 and consequently cl-2d to use the special variable *context* as the default context. This does not affect the interface of cl-2d (except for user-defined functions that draw directly on the cairo context, of course), since in cl2d, the context is always saved in the frame and there is no "default" frame. Nevertheless, updating the cl-2d code was beneficial because I was able to see if the new style makes things easier. It appears that it simplifies the code quite a bit: I would like to thank everyone who argued for the change. Enjoy. Bug reports and contributed code are appreciated.

announcing latex-table

2009-05-23T17:00:00.000-07:00

Latex-table is a simple Common Lisp library for writing vectors and matrices into LaTeX tables. It won't allow you to do anything magical that you could not do in LaTeX otherwise, but it simplifies formatting (mostly numerical) tables. Floats are aligned on the decimal dot. Some examples:

(with-open-file (stream "/tmp/horizontal.table" :direction :output
   :if-exists :overwrite :if-does-not-exist :create)
  (labeled-vector-horizontal stream 
        (vector "foo" pi -42)
        (vector "$\\alpha$" "bar" "baz")
        :significant-digits 3))

(with-open-file (stream "/tmp/matrix.table" :direction :output
   :if-exists :overwrite :if-does-not-exist :create)
  (labeled-matrix stream #2A((11.1 112.55 3)
        (9 1345.79 14.72))
    (vector "foo" "bar" "baz")
    (vector "first" "second")
    :hlines '(1 2 -1 1)))

All of these functions use the "raw" interface below, which you can also use directly.

(with-open-file (stream "/tmp/raw.table" :direction :output
   :if-exists :overwrite :if-does-not-exist :create)
  (raw-tabular stream #2A(((:aligned "foo" ""))
     ((:aligned "bar" "baz"))
     ((:aligned "" ".19"))
     ((:left "left"))
     ((:right "right"))
     ((:center "center")))
        #(:aligned)  ; column types
        #(0 0)   ; vertical lines
        #(1 2 0 0 0 0 3))) ; horizontal lines

cl-cairo2 interface poll

2009-05-23T15:08:00.000-07:00

It seems that what I considered a wart is a feature to some people. I would like to make the users of cl-cairo2 happy, so I am considering reverting to the older interface. Also, I experimented with some other code I am using, and I think that wrapping my code in (let ((*context* context1)) ...) is not too much of a hassle anyway. So I am conducting an informal poll: please comment below. If you like the

(move-to context ...)

interface, say explicit, if you prefer the

(move-to ... &key (context *context*))

interface, say global. If you are indifferent, just state that. You can also tell me if you have code that already uses either interface, and whether you it would be a great inconvenience to change that (but I can't imagine that very many people have a lot of code using the explicit interface at this stage). I have listened to your arguments, so you won't need to repeat them, unless you feel that you have something crucual to add. I will take a look at the results on Tuesday, May 26, and update the library (and cl-2d) if necessary. I would rather complete the transition quickly, as I want the API to be relatively stable. I do know that in the previous post I said that there will be no more changes, guess I am dynamically inconsistent :-P

cl-numlib, array-operations and cl-colors migrated to Github; my packages are asdf-installable again

2009-05-21T19:02:00.000-07:00

Looks like I goofed up when releasing cl-2d: it used a few routines which were sitting on my hard disk but not made public yet. I think I corrected that, and pushed the new versions to Github. Also, I think I figured out how to link to tarballs on Github. Using entries like

:(package "http://github.com/tpapp/cl-2d/tarball/master")

ASDF goes to Github, where is it redirected to the latest master tarball, and appears to work fine. If not, let me know and it will be fixed. Still, I would suggest that you use git to keep updating the libraries if you can. Thanks to Peter Mikula for reporting the missing library code.

ffa: complex numbers, license change, migration to Github

2009-05-21T04:38:00.000-07:00

I have done a few minor updates to my FFA library. It now handles complex numbers (to be precise, arrays of (complex simple-float) and (complex double-float)). Because of the extra complexity (haha), I also added some unit tests that use simple C functions to check that FFA does what it claims to do. I have also changed the license to LLGPL (was GPL). And finally, I have migrated the library to Github. Github is proving really user-friendly and reliable, in the long run I plan to put all my libraries there. Thanks to William Halliburton for reminding me that the previous repo was out of date.

announcing cl-2d

2009-05-19T06:21:00.000-07:00

Cl-2d is a two-dimensional graph library for Common Lisp. It builds on cl-cairo2 and thus uses the Cairo library, which provides various backends, including pixel-based (eg PNG, X11) and vector-based (PDF, SVG, PS) ones. It is meant solely for 2-dimensional plotting (hence the name). Cl-2d is available from Github. The license is LLGPL. Cl-2d is designed to be extensible instead of providing a plethora of "canned" functions - the latter of course exist, but the emphasis is on flexibility. Most plots used in scientific visualization are customized, and the purpose of this library is to make customization easy. Plotting happens on frames, which are rectangular areas. A DSL is available for splitting frames. A frame combined with a mapping from plot coordinates to Cairo coordinates is a drawing area. Functions named plot-* take a frame, set up and return a drawing area (on which you can continue drawing), while draw-* functions draw on an existing drawing area. This library is still under development, suggestions and contributions are welcome. I mean to clear up the axes code and add contour plots soon. See the example/ directory for a wide variety of examples. Some of the example plots, converted from PDF, are shown below.

cl-cairo2 context wart fixed

2009-05-15T18:53:00.000-07:00

I pushed an updated version of cl-cairo2 to the repository today. The most important change is the fixing of a major design wart that was the result of a bad initial design choice. Originally, cl-cairo2 functions had an optional context argument as the last argument, which defaulted to *context*. This seemed to make sense at the time, it saved typing, but later on I realized it is very unLispy. So now context is the first argument, and is never optional, *context* is gone. I realize that this might break some code for people who are using cl-cairo2, and for this I apologize. But it had to be done sooner or later, I kept putting it off but finally could not bear it any more. Since I was using macros to generate most of the function definitions, effecting the change was a matter of minutes. I also cleaned up the documentation a bit.

cl-cairo2 migrated to github.com

2009-05-13T08:12:00.000-07:00

I have migrated cl-cairo2 to github.com. If you want to install it, just clone from the repository:

git clone git://github.com/tpapp/cl-cairo2.git

You might have to create a symlink to the asd file in your ASDF systems directory. This is just a migration, no new code added. The package is no longer ASDF-installable. I have began to hate ASDF-install, it is more trouble than it is worth. For those who insist, it is possible to download a tar.gz file from Github, but the name of the link changes with updates, so I can't put one on cliki.net. Believe me, you are just better off pulling it from the git repository. Eventually, I plan to add support for Mudballs, but not soon.

Job market: please go to my website

2008-11-14T08:17:00.000-08:00

I am on the Economics job market this year. If you googled for my name, you might have ended up on my blog instead. You can find my papers and CV on my webpage.

cl-cairo2 updates: win32 and mac extensions

2008-08-13T05:41:00.000-07:00

Thanks to the contributions Kei Suzuki, cl-cairo2 underwent quite a few changes. Most importantly, as Kei contributed Win32 and OS X-specific code, I decided to separate all parts of the library that use a GUI. So now if you load cl-cairo2 (using ASDF), only GUI-independent parts of the library will be loaded. If you need the rest, you will have to load cl-cairo2-x11, cl-cairo2-mac or cl-cairo2-win using ASDF. All of these put their functions in the :cl-cairo2 package, without creating a new one, so the organization of namespaces is simplified. Also, cl-cairo2 and the GUI extensions are still packaged into a single tarball, which you can download or install directly using ASDF-Install. Here are some screenshots contributed by Kei Suzuki: You can find the code for these in tutorial/lissajous.lisp and tutorial/lissajous-win.lisp.

FFA split into two packages

2008-07-29T02:14:00.000-07:00

Besides providing `foreign friendly' arrays, my FFA package contained a lot of functions that implement commonly used array operations, including elementwise algebra operations, array minima and maxima, etc. Because these do not depend on CFFI, I decided I would put them into a separate package, named ARRAY-OPERATIONS, which is also installable with ASDF-Install. It contains a reimplementation of array-range, and also a macro for vectorizing operations, called vectorize:

 (let ((a #(1d0 2d0 3d0))
       (b #(4d0 5d0 6d0))
       (c 0.25d0))
   (vectorize (a b)
              (+ a b c 0.25)))  ; => #(5.5d0 7.5d0 9.5d0)

(vectorize (&rest vectors) expression) sets up symbol macros so that vector names in vectors refer to the appropriate element, then evaluates expression repeatedly and returns the results as a vector. It also has two keyword arguments: result-element-type (which default to 'double-float) determines the element type of this vector, while into places the results in one of the vectors instead (of course the two arguments are mutually exclusive).

 (let ((a (vector 1 2 3)))
   (vectorize (a) (+ 1 (* a 2)) :into a)
   a)  ; => #(3 5 7)

Functions in the new package still strive to create arrays that are foreign-friendly.

changes in cl-cairo2

2008-06-26T05:19:00.000-07:00

Johann Korndoerfer kindly submitted a patch that adds patterns to cl-cairo2, and also includes some code cleanup. Here is the example Johann contributed to the tutorial, a rainbow created with patterns: Thanks for the nice work, Johann! I am happy that others also find cl-cairo2 useful. cl-cairo2 still suffers from the elusive floating point bug (possibly in libcairo), I am still working on that. In the meantime, you can work around that by not generating PS files directly, but converting them from PDF or SVG files. Since common-lisp.net appears to be down, I took the opportunity to migrate the repository to git, which I am now hosting on my webpage. I find git to be much more convenient than SVN, especially when it comes to ease of distribution. As before, the package remains ASDF-installable. Update: the GIT repository is here, but can also be found from the cliki page for cl-cairo2.

announcement: minpack package

2008-06-26T01:48:00.000-07:00

I have been using a simple solver (based on Broyden's method) to finds roots of systems of nonlinear equation, but I encountered an ill-behaving class of problems that required heavier artillery. Numerical methods have made a lot of progress in the last 50 years. Methods presented in introductory textbooks are quite straightforward and very simple to code, but do not cut the mustard when it comes to more difficult situations (eg when you don't have a good initial guess, your function looks like the fjords of Norway, etc). State of the art methods are powerful, but they are tricky to program: the main idea is easy to grasp, but one has to cover a lot of special cases (eg line-search, niceties of trust-region methods) so implementing them from scratch takes a lot of time (and debugging). This is why most researchers rely on Fortran (or most recently, C) packages of these methods. Common Lisp users generally have two alternatives if they don't want to implement these methods from scratch. They can use the foreign code directly via the FFI, or translate the code using f2cl, which is available as part of CLOCC. I found the second option more appealing, for the following reasons:

fewer dependencies (no need to install/compile foreign libraries)
no need to have callbacks (which are a pain in the neck)
better integration into Lisp (eg you can use the condition system)

This is the first time I used f2cl, but it was quite easy to do, especially as CLOCC already has things set up for MINPACK. I think that translating from Fortran is the way to go for some libraries, even though I recognize that for libraries like LAPACK where pure performance matters, FFI is the better option, especially as the functions there have simpler interfaces and don't need callbacks and complex condition handling. MINPACK has already been available as part of CLOCC, but I had a hard time getting the whole thing work in SBCL, and it doesn't use ASDF, so I decided to package it to make it self-contained and ASDF-installable. The extended version of the project I am working on will probably need homotopy methods, and I am looking forward to packaging that too.

announcement: cl-sparsematrix

2008-01-12T15:28:00.000-08:00

Lately I have been working on algorithms that solve Hamilton-Bellman-Jacobi equations (that describe optimal control problems in continuous time) using the methods of Kushner and Dupuis, which involve sparse stochastic matrices. The sparse matrix code has stabilized to the point that I cleaned it up today and decided to make it available as a library, in ASDF-installable form. The package is called cl-sparsematrix, and has the following features:

generalized sparse matrices: elements don't have to be numbers, but can be any object (eg functions for parametrized sparse matrices), of course you have to define what you mean by zero in this case
utility functions for creating, mapping, traversing or copying sparse matrices
numerical operations that make sense for numerical sparse matrices (elementwise addition, subtraction and multiplication, row and column sums, multiplication of rows by corresponding elements in a vector, vector-matrix and matrix-vector products)
a simple interface for UMFpack for solving sparse systems (uses cffi and ffa)

You will find an introduction to the main concepts in the code as a PDF file in the documentation/ directory. As usual, comments and suggestions are appreciated.

announcement: cl-numlib

2007-12-21T12:34:00.000-08:00

cl-numlib is a collection of functions I have been using for numerical methods. I wrote functions for rootfinding, integration, univariate (Brent, Newton) and multivariate (BFGS) optimization, numerical integration, some functions for generating random numbers and a few utility and miscellaneous functions. This is not a translation from Fortan: everything in the library was written from scratch. There are two reasons for doing this: I learned a lot in the process, and I find it much easier to change things in the algorithms when I need to (when working with numerical methods, this is very useful). There is no separate documentation, but all the functions are well-documented with examples and references where appropriate. This library is in alpha stage, this means that I tested all my functions and found no bugs, but that of course doesn't exclude the possibility of there being any. Comments, suggestions and bugreports are welcome.

announcement: ffa

2007-12-20T05:26:00.000-08:00

While CFFI is very useful API for calling C functions, using foreign functions that expect pointers to arrays has always been something that is tricky to do in Common Lisp. The two basic approaches are

allocating a chunk of foreign memory and accessing it from Lisp as needed (as implemented in the fnv package by rif)
using native CL arrays and either copying them to/from foreign memory on demand, or taking advantage of implementation-specific features (eg pinning arrays) for direct access where possible

The first approach has some advantages, but I find that I am more comfortable with the second one, even if it leads to some loss in speed when the arrays are large and the implementation can't provide direct access for foreign functions. My ffa (Foreign Friendly Arrays) package provides some convenience functions and macros that take advantage of implementation-specific features when available. The most important features are the function make-ffa and the macro with-pointer-to-array. The function make-ffa is similar to make-array, except that it recognizes some CFFI types (eg :double, :uint32) and when asked to allocate a multidimensional array, it will do so by displacing a simple array which it creates first. This allows direct access in some implementations, especially SBCL, while providing multidimensional arrays at the same time. The macro (with-pointer-to-array (array pointer cffi-type length direction) body) makes sure that the contents of array will be mapped to a memory area designated by pointer during the execution of body. cffi-type determines the foreign element type, direction tells the macro whether to copy the array to and/or from the memory area (so, for example, if you foreign function needs data but does not modify it, you don't need to copy it back), and by providing length, you ensure that the array contains as many elements as your foreign function needs. When possible, no copying/conversion will take place (eg a double-float array in SBCL with cffi-type :double), but the macro will take care of it automatically when needed (issuing some efficiency warnings when practical). Displacing all arrays from a one-dimensional simple array also allows a few convenience functions, please check the code or the tutorial (provided in the package) for details. Currently, only SBCL-specific code is provided, for all other implementations, the macro defaults to copying/conversion. Contributions for other implementations and suggestions for improvements are welcome. I would like to thank all those who commented on an earlier version of ffa on lisp-matrix-devel.

sub-$40 bicycle light

2007-11-19T19:06:00.000-08:00

As LED technology makes large advances, I decided to see if a simple LED flashlight could serve as a bicycle light. Bicycle lights generally fall into two categories: some only allow you to be seen (red or white, serving as tail- or headlights, respectively), while the more sophisticated ones allow you to see, illuminating the road ahead. Since LED lights are quite powerful at this point, I want the latter kind. Before buying, I set up the following constraints:

price: the light has to be below $40, the cheaper the better. I already have a pair of lithium-ion powered Dinotte lights, the front rated at 200L, I just need something to serve as a spare or when I have guests who want to bike at night (of course I would give the guest my Dinotte)
batteries: it has to take standard batteries, AA or AAA. Chargers and rechargeable batteries are cheap for these, while CR123 is expensive. Also, if I forget to recharge, I can buy these easily at a convenience store anywhere
small form factor and light weight: I don't want to carry something bulky

I ended up getting a 3W LED flashlight from Cabela's, for $20+shipping. The nominal output of these lights is 65 lumens, which comes from a single Luxeon LED. Without further ado, here is a picture of the output (widest setting): The picture was taken at 2m (6.5ft), with the following camera settings: 1/12s exposure, f7.1, focal length 29mm. I took care not to overexpose the photo. If you look at it with a photo-processing application like Adobe Photoshop or the Gimp, you will notice a faint illumination (ranging from 20% to 5% of the peak) even outside the readily apparent white circle. For comparison, here is the light of the Dinotte with the same settings: Of course, the difference is obvious: the Dinotte is rated at 200 lumens, and has a much nicer lens to spread the light wider. Nevertheless, I am satisfied with the flashlight's performance, especially considering its price. Now I am experimenting with different mounting options (Twofish lockblocks should be arriving soon), and will post my experiences.