Irate Nate's weblog

banks asking for regulation

Fri, 22 Jan 2010 21:52:00 CDT

If banks are going to continue in their expectations that the government is going to bail them out, then the government is naturally--regardless of arguments from the left for increased regulation or from the right for steering clear of the self-correcting market--going to impose regulations to make it less likely that banks will place themselves in a position in which a bailout is necessary. Simple economics. You can debate back and forth about the popular merits of such a decision and the political maneuvering that comes with that. But the government is acting in its own self-interest in this case, plain and simple. The banks are getting exactly what they asked for.

grouchy c programmer

Fri, 15 Jan 2010 22:05:00 CDT

Whenever possible, feature macros in C should be #define'd to 0 or 1, rather than letting the definedness or lack thereof be the switch for the feature. This convention means that you can talk about the feature macro in conditions, rather than having to jump through hoops to do so. (Doing so also means that you can play clever tricks in code with said feature macros if need be...) Of course, this implies that your compiler needs to be intelligent about dead code elimination in the presence of disabled features, but what compiler isn't?

Also, to all the hotspot rockstar programmers out there who are enormously impressed with their ability to record key routines from the C library using whizbang vector instructions and cache control instructions and show massive speedups: please try to actually test your code to ensure that it has the same correctness properties as the code in the C library. Nobody cares how fast your routines are if they cause buffer overflows on real-world code, rather than the trivial benchmark you threw together.

ice skating

Fri, 01 Jan 2010 23:33:00 CDT

We took the girls ice skating yesterday. Becca liked it so much that she declared that she wanted to go back today. So we did that, with one change: I put on skates today and went out on the ice. Yesterday was mostly holding onto Ally while Becca was on the ice or vice versa. Tricia was going to send me out on my own.

“I'm not sure I've ever been out without holding onto somebody before,” I said.

“How many times have you been ice skating before?”

“Two.”

“How old were you?”

“Twenty-one.”

As you can guess, I haven't had much experience ice skating. By the end of the public skate session, though, I had managed to make it around the rink a couple times at a fair distance from the side. I even managed to take both of the girls out all by myself--and let me tell you, that was about the most fun I've had with my children in a while.

I was so proud of Becca too, for really trying to skate both days. She even managed to travel short distances (a couple of yards) on her own.

a geek's lament

Wed, 30 Dec 2009 22:51:00 CDT

Somebody more skilled in humorish things than I needs to write a piece in the style of A college admission essay. In this piece, the author would set forth his geek credentials. Examples:

I have a four-digit Slashdot user id.
I installed Slackware when it only had 12 diskettes.
I won an argument with Ulrich Drepper.
I -funroll-all-loops.
I taught Chuck Norris everything he knows.
I know Bruce Schneier's password.
I have successfully rickrolled somebody.
I survived the Eternal September.
I have ascended with every character class.

...and so forth, perhaps more outlandishly than I have done above. After a suitably long listing of all these feats of geekdom in suitably stylistic prose, the essay should conclude with:

“But I have not yet figured out the usefulness of Google Wave.”

suitcase parent hack

Tue, 29 Dec 2009 22:03:00 CDT

When we asked the girls what they wanted to buy with their Christmas gift money this year, they responded that they wanted little travel suitcases. Neither one of us wanted to buy a little rickety suitcas with thin vinyl siding plastered with the cartoon character du jour, though. We wanted to buy something that would last for a while and even be useful beyond these next couple of years.

We looked around online, but children's luggage is rather boutique-ish. So it looked like we'd have to go with the cheap plastic luggage or with some boutique luggage that would very nearly break the bank.

We were able to go out on a date today and were wandering around TJ Maxx when we noticed a bright orange Columbia rolling carry-on. It was a standard adult size, but it was definitely on the small side. It was also heavily discounted. We looked around a little more and found a slightly smaller red Wenger rolling carry-on as well as a blue Columbia bag of the same style as the orange one.

The Wenger bag was about half again as much as your standard plastic luggage; the Columbia bag was a little bit more than twice as much. Both were significantly cheaper than the other options we'd seen online, though. Both bags can easily accommodate a week's worth of clothes for several years. Even when the girls get older, they can fit a couple days' worth of clothes in the bags. So they win on the price and practicality fronts.

At this point, however, the girls appreciate the color most. I suppose they appreciate the size of the bags, since they can fit a lot of doll clothes in them. (We got the blue Columbia one and the red Wenger one.)

Anyway, that's the parent hack of the day: discounted adult luggage for children.

clos initialization protocol

Tue, 22 Dec 2009 16:40:00 CDT

Update: Tobias Rittweiler pointed out that I don't need &ALLOW-OTHER-KEYS in my method definitions; &ALLOW-OTHER-KEYS was already declared in the DEFGENERIC and isn't required in individual methods. Furthermore, putting &ALLOW-OTHER-KEYS in your method definitions when it's already been declared in DEFGENERIC inhibits useful argument checking. So don't do that. I've fixed the examples below.

From the last blog post, we saw that REINITIALIZE-INSTANCE is a useful way to reduce consing. You say, “well, sure, that's why I have RESET-FOO functions in the library/application that I'm writing.” I'd like to suggest that if you've written such functions, you ought to be writing REINITIALIZE-INSTANCE methods (if you're resetting structures) or writing :AFTER methods on the usual CLOS initialization protocol methods instead. Doing so is more Lispy than the usual reset functions. Writing to the existing protocol also encourages you to more clearly define what's initialization, what's reinitialization, and what can be shared between them.

“OK,” you say, “but what are these CLOS methods and how do I use them?” Glad you asked.

There are three major generic functions that participate in the protocol:

As you might imagine, INITIALIZE-INSTANCE is called from MAKE-INSTANCE and REINITIALIZE-INSTANCE is called from, well, REINITIALIZE-INSTANCE. SHARED-INITIALIZE is called from both INITIALIZE-INSTANCE and REINITIALIZE-INSTANCE and handles bits common to both methods. We'll focus on SHARED-INITIALIZE because it underpins the other two and because SHARED-INITIALIZE is also called when updating class definitions and changing the class of an instance. You get a lot of things for free when writing methods for SHARED-INITIALIZE.

First things first: you generally only want to write after methods on SHARED-INITIALIZE, viz:

(defmethod shared-initialize :after ((object my-class) slot-names &rest initargs &key)
  ...)

The reason you do this is because the primary method on SHARED-INITIALIZE already does a lot of useful things, like initializing slots from their :INITFORMs and :INITARGs. (For the same reason, you should generally use :AFTER methods for INITIALIZE-INSTANCE and REINITIALIZE-INSTANCE.) You can, of course, write:

(defmethod shared-initialize ((object my-class) slot-names &rest initargs &key)
  (call-next-method)
  ...)

But that's generally not how things are done. I think writing :AFTER methods makes your intent clearer: you're doing extra work after the standard bits have been done. It's also easy to forget to CALL-NEXT-METHOD, which would lead to puzzling behavior and also might lead you to submit spurious bug reports like “CLOS initialization doesn't work with user-defined classes”. Also, method combination is often more useful and more declarative than trying to get CALL-NEXT-METHOD in the right place. That doesn't mean CALL-NEXT-METHOD doesn't have its place, it just means I think method combination should be preferred when possible.

OK, so, onto initializing things. What's this SLOT-NAMES parameter? SLOT-NAMES is a (possibly empty) list of slot names that need to be initialized from their :INITFORMs, or T to stand in for “all slots”. For our purposes here, we are going to assume that SLOT-NAMES is only ever T (for when SHARED-INITIALIZE is called from INITIALIZE-INSTANCE) or NIL (for when SHARED-INITIALIZE is called from REINITIALIZE-INSTANCE). In the T case, the primary method on SHARED-INITIALIZE handles the initialization logic. So we don't have to worry too much about SLOT-NAMES.

You can also mostly ignore INITARGS. Most of the keyword-argument pairs in it will have been handled elsewhere by standard CLOS bits. Any bits that are interesting to you will be pulled out via separate &KEY arguments; we'll get to that use-case in a second.

OK, so what useful things can we do in SHARED-INITIALIZE? We can recompute slots that depend on the values of other slots and therefore can't be usefully initialized with :INITFORM or :INITARG:

(defclass triangle ()
  ((a :initarg :a :reader a)
   (b :initarg :b :reader b)
   (c :initarg :c :reader c)
   (area :reader area)))

(defmethod shared-initialize :after ((o triangle) slot-names &rest initargs &key)
  (let ((area (compute-area-of-triangle (a o) (b o) (c o))))
    (setf (slot-value o 'area) area)))

In cases like this, you might be tempted to write some sort of wrapper (with the appropriate modification to the definition of TRIANGLE):

(defun make-triangle (a b c)
  (let ((area (compute-area-of-triangle a b c)))
    (make-instance 'triangle :a a :b b :c c :area area)))

which is certainly doable (I'll leave the subject of whether to wrap MAKE-INSTANCE or expose it directly to users in your API for a future post). But this sort of wrapper doesn't easily enable reinitialization. Consider what your hand-crafted RESET-TRIANGLE function might look like to handle all the cases the SHARED-INITIALIZE method would handle for free:

(defun reset-triangle (triangle &key a b c)
  (let ((a (or a (a triangle)))
        (b (or b (b triangle)))
        (c (or c (c triangle))))
    (setf (slot-value triangle 'a) a
          (slot-value triangle 'b) b
          (slot-value triangle 'c) c
          (slot-value triangle 'area) (compute-area-of-triangle a b c))
    triangle))

Notice that you've duplicated slot setting (the CLOS internals handle that for you) and you're computing the area of the triangle in two different, but related (both part of initialization) places. You might say that you only want users resetting all three sides of a triangle, so the API should reflect that. Maybe. But in that case, you should be the one calling REINITIALIZE-INSTANCE, and you'd wind up going the SHARED-INITIALIZE route anyway. I think the SHARED-INITIALIZE method also better captures what it means to compute the area: the computation of the area is an integral part of initialization, rather than something that you do beforehand prior to creating the object.

For a less pedagogical example, let's say you have a cool encryption algorithm:

(defclass les () ; the LISP encryption standard
  ((round-keys :reader round-keys)
   (n-rounds :reader n-rounds)))

(defmethod shared-initialize :after ((o les) slot-names &rest initargs &key key)
  (multiple-value-bind (round-keys n-rounds) (schedule-key key)
    (setf (slot-value o 'round-keys) round-keys
          (slot-value o 'n-rounds) n-rounds)))

You may have noticed that SHARED-INITIALIZE takes a KEY keyword argument above, even though there's no :INITARG :KEY in the DEFCLASS form. One cool thing about SHARED-INITIALIZE is that any &KEY arguments to it automatically become candidates for use with MAKE-INSTANCE and the other generic functions that participate in the initialization protocol. This feature enables you to pass keyword arguments to MAKE-INSTANCE that aren't directly connected with slots, but require massaging in some way to produce something suitable for slot values. So using the above, you say:

(defvar *l* (make-instance 'les :key #(#xde #xad #xbe #xef)))
...lots of code...
;; sometime later
(reinitialize-instance *l* :key #(#xca #xfe #xbe #xbe))

Again, you could use wrapper functions. But I think the same arguments cited above for clarity and for not repeating yourself apply here as well. (And if you're really serious about this encryption stuff, you also want to be able to reset the initialization vector/nonce for your encryption mode and possibly even to change the encryption mode entirely. Once you've done that, you've basically rewritten SHARED-INITIALIZE, and you have potentially duplicated logic between your MAKE-INSTANCE wrapper and your reset function.)

Another reason to have SHARED-INITIALIZE methods is because they naturally cooperate with subclassing. Let's say you're dealing with some packaging format and you're creating entries from octet vectors:

(defclass entry ()
  ...slots...)

(defun make-entry-from-buffer (buffer &key (start 0))
  (let (...parse out individual slots from BUFFER...)
    (make-instance 'entry ...initargs for slots...)))

Fine and dandy. Now let's say that your customers tell you about packaging format v2, which mostly retains the format of v1, but adds a way of specifying additional metadata as part of the entries. OK:

(defclass entry-v2 (entry)
  ...more slots...)

(defun make-entry-from-buffer (buffer &key (start 0))
  ;; A `2' at the start of the buffer indicates a version 2 entry.
  (if (= (aref buffer start) 2)
      (make-entry-v2-from-buffer buffer :start start)
      (make-entry-v1-from-buffer buffer :start start)))

Hm. We want to initialize the slots in an entry in a common place, so as to avoid code duplication:

(defun initialize-common-entries (entry buffer &key (start 0))
  (let (...parse out individual slots from BUFFER...)
    (setf ...lots of slots...)
    entry))

(defun make-entry-v2-from-buffer (buffer &key (start 0))
  (let ((entry (make-instance 'entry-v2)))
    (setf ...new slots for ENTRY-V2...)
    (initialize-common-entries entry buffer :start start)))

and so on. Possibly with slight adjustments because parsing the slots for ENTRY-V2 might depend on the values of one or more of the common slots in ENTRY. I claim that this is more elegantly handled by:

(defmethod shared-initialize :after ((o entry) slot-names &rest initargs &key buffer start)
  (let (...parse out individual slots from BUFFER...)
    (setf ...lots of slots...)
    o))

(defmethod shared-initialize :after ((o entry-v2) slot-names &rest initargs &key buffer start)
  (let (...parse out individual slots from BUFFER...)
    (setf ...slots for ENTRY-V2...)
    o))

(defun make-entry-from-buffer (buffer &key (start 0))
  ;; A `2' at the start of the buffer indicates a version 2 entry.
  (if (= (aref buffer start) 2)
      (make-instance 'entry-v2 :buffer buffer :start start)
      (make-instance 'entry :buffer :start start)))

Since :AFTER methods run in least-specific-first order, the :AFTER method on ENTRY will be called first. The :AFTER method on ENTRY-V2 can therefore freely use the value of any slots from ENTRY. Using SHARED-INITIALIZE here not only enables REINITIALIZE-INSTANCE, it also does the right thing in handling common code from a software engineering perspective.

Of course, if you have code that specifically needs to run at MAKE-INSTANCE time, or REINITIALIZE-INSTANCE time, then you can add :AFTER methods to INITIALIZE-INSTANCE or REINITIALIZE-INSTANCE as appropriate. For instance, if all of your objects need to have a unique ID, you surely don't want to assign a unique ID in SHARED-INITIALIZE.

(defclass unique-id-mixin ()
  ((unique-id :reader unique-id)))

(defmethod initialize-instance :after ((o unique-id-mixin) &rest initargs &key)
  (setf (slot-value o 'unique-id) (get-unique-id-for-instance o)))

(You might, however, want to assign a different unique ID if somebody change-class'ed your object. That's a topic for future discussion; I only sort-of understand the protocol involved in CHANGE-CLASS and I have yet to see really pragmatic reasons for adding methods to the generic functions involved.)

I know that my code doesn't always work according to the ideas I've laid out above; it's taken me a while to wrap my head around what goes where and why. But now that I understand, I'm slowly modifying my code to use these ideas. Where can your code benefit from these ideas?

archive release

Fri, 18 Dec 2009 23:11:00 CDT

I've released ARCHIVE 0.8. It features an assortment of bugfixes, including fixes for extraction of tar files and fixes for Lispworks/Win32 users. This version also understands POSIX global headers in tar files, so if you've been getting complaints about “unknown typeflag 103” or similar, now would be a good time to upgrade. It is available from the usual places, including straight from github. (And like a git n00b, I've managed to botch the tagging of 0.8. The tag of 0.8 is almost right, except the version number in the .asd is wrong...sigh.)

surveillance clock

Fri, 18 Dec 2009 20:24:00 CDT

One of the more interesting (and frightening) pieces I've read in a while is Jeff Jonas's Six Ticks till Midnight: One Plausible Journey from Here to a Total Surveillance Society. He explains the ACLU's Surveillance Society Clock and exactly why it's set where it is by laying out the rough sketches of what needs to happen before the activities of everybody can be tracked 24-7. (Aside: the ACLU utterly failed at this. If you look at their site without reading Jonas's post, it looks like general fear-mongering, since they don't provide any explanation of why the clock is where it is.) Also note the clock has moved up one minute since Jonas's post two years ago.

The really amusing/interesting/chilling part is this:

Oh yeah, one more thing, no more need for facial recognition (a very hard problem many years off anyway). In this coming world, all that useless video being collected can now be efficiently recalled because GPS data provides the missing link … who was where when?
While the exact technologies or the exact sequence of events may unfold quite differently, nonetheless such a future is coming. And this future is being created by us consumers, not the government!
Consumers are funding the surveillance economy, with the blistering pace of this extraordinary surveillance being driven by ordinary people who relish all the technological advances and willing to entirely trade in their information and privacy as they optimize their life.

One of the reasons I've become very interested in reading about history--a subject which I disliked in school--is this idea of unintended consequences. (The same principles come up in economic/political discussions too, except nobody seems to care...wait, that's exactly how history works, too.) Luther, for instance, almost certainly had no intention of producing the individualistic evangelical culture we have today--but you can trace a pretty convincing path between the two. Or economists making decisions based on some particular model of things and convincing themselves that said decisions will have the desired effect--without realizing that those same decisions are changing fundamental assumptions undergirding the model. (William Greider's Secrets of the Temple, which discusses the Federal Reserve's actions under Paul Volcker, has several examples of this.) There's no grand cabal of people, no portly, mustached executives and bureaucrats carefully designing a system to track everybody everywhere--we are doing this to ourselves.

using reinitialize-instance

Wed, 16 Dec 2009 13:28:00 CDT

In my “code that will eventually go into Ironclad” directory, I had the following function:

(defmethod derive-key ((kdf pbkdf1) passphrase salt iteration-count key-length)
  (unless (plusp iteration-count)
    (error 'invalid-iteration-count))
  (loop with digest-name = (kdf-digest kdf)
     with digest-length = (ironclad:digest-length digest-name)
     with key = (make-array 20 :element-type '(unsigned-byte 8))
     initially
       (let ((d (ironclad:make-digest digest-name)))
         (update-digest d passphrase)
         (update-digest d salt)
         (produce-digest d :digest key))
     for i from 1 below iteration-count
     do
       (ironclad:digest-sequence digest-name key :end digest-length :digest key)
     finally
       (return (subseq key 0 (min key-length (length key))))))

This snippet implements the algorithm of section 5.1 of RFC 2898. (We don't have to worry about the hardcoded length of 20 for the key, since PBKDF1 is specified to only work with MD2, MD5, or SHA1; the validation to make sure we do so happens elsewhere.) It's a fine implementation, except that profiling indicates entirely too much time is being spent in digest allocation/initialization. It'd be nice if we could just construct the required digest once (since we're using the same digest algorithm throughout the loop) and reset it to its original state each time we needed to hash something.

Fortunately, the designers of Common Lisp anticipated this situation and built in a standard way of addressing it: the reinitialize-instance generic function. The idea behind it is very simple. When you create new instances of a class, you say:

(defparameter *c* (make-instance 'myclass [...initargs...]))

At some later point, when you decide that you really need *C* to be slightly different, but you don't want to allocate another instance of MYCLASS, you say:

(reinitialize-instance *c* [...other initargs...])

and the appropriate computations take place to make it as if you had said:

(setf *c* (make-instance 'myclass [...other initargs...]))

except without the extra allocation and with the benefit that anybody holding references to *C* now sees the updated version.

reinitialize-instance will automagically work with all CLOS instances. You do have to pay careful attention to how it works if you do fancy things with object initialization; I'll write about playing nice with reinitialize-instance in a future post. Also, since it's a generic function, you can define methods on it for structures as well as classes. (One of the fun things about Common Lisp is that you can use classes without using generic functions and vice versa.) Which is handy for Ironclad, since all of its digest objects are implemented as structures for speed.

All this is to say that the above code can be rewritten to be more efficient:

(defmethod derive-key ((kdf pbkdf1) passphrase salt iteration-count key-length)
  (unless (plusp iteration-count)
    (error 'invalid-iteration-count))
  (loop with digest-name = (kdf-digest kdf)
     with digest = (ironclad:make-digest digest-name)
     with digest-length = (ironclad:digest-length digest-name)
     with key = (make-array 20 :element-type '(unsigned-byte 8))
     initially
       (ironclad:update-digest digest passphrase)
       (ironclad:update-digest digest salt)
       (ironclad:produce-digest digest :digest key)
     for i from 1 below iteration-count
     do
       (reinitialize-instance digest)
       (ironclad:update-digest digest key :end digest-length)
       (ironclad:produce-digest digest :digest key)
     finally
       (return (subseq key 0 (min key-length (length key))))))

It's not a huge difference, but making sure to use reinitialize-instance and defining appropriate methods on it did make a huge difference for PBKDF2, whose less-consy definition looks like:

(defmethod derive-key ((kdf pbkdf2) passphrase salt iteration-count key-length)
  (unless (plusp iteration-count)
    (error 'invalid-argument))
  (unless (plusp (length passphrase))
    (error 'invalid-argument))
  (loop with count = 1
     with hmac = (ironclad:make-hmac passphrase (kdf-digest kdf))
     with hmac-length = (ironclad:digest-length (kdf-digest kdf))
     with key = (make-array key-length :element-type '(unsigned-byte 8)
                            :initial-element 0)
     with key-position = 0
     with count-buffer = (make-array 4 :element-type '(unsigned-byte 8))
     with hmac-out = (make-array hmac-length :element-type '(unsigned-byte 8))
     while (plusp key-length)
     do (let ((size (min hmac-length key-length)))
          (reinitialize-instance hmac :key passphrase)
          (ironclad:update-hmac hmac salt)
          (setf (ironclad:ub32ref/be count-buffer 0) count)
          (ironclad:update-hmac hmac count-buffer)
          (ironclad:hmac-digest hmac :buffer hmac-out)
          (ironclad::xor-block size hmac-out key key-position key key-position)
          (loop for i from 1 below iteration-count
             do
               (reinitialize-instance hmac :key passphrase)
               (ironclad:update-hmac hmac hmac-out)
               (ironclad:hmac-digest hmac :buffer hmac-out)
               (ironclad::xor-block size hmac-out key key-position key key-position)
             finally
               (decf key-length size)
               (incf key-position size)
               (incf count)))
     finally (return key)))

Reinitializing the HMAC instances in the loops versus simply reallocating them is a huge win, since HMAC instances also include digest instances; those digest instances don't have to be reallocated when the instance is reinitialized, but can instead be reinitialized themselves.

gone to github

Fri, 13 Nov 2009 22:13:00 CDT

I've opened an account at github and opened repositories for two libraries: Ironclad and binascii. binascii is a library for doing “ASCII-armoring” of data (base64 and similar); I've been working on it for the past two weeks and am pleased with the results so far, both in the elegance of the code and the (untuned) performance. I do plan on making my other libraries available there as well; Ironclad was the most-requested library for DVCS visibility, so I thought I'd start with that.

prescient words

Tue, 10 Nov 2009 09:55:00 CDT

Two quotes from The Soul of Capitalism by William Greider.

The standard assumptions of efficiency, however, are regularly mocked by real life outcomes. The faith in efficiency was shaken most recently by the horrendous disintegration of stock prices that destroyed somewhere between $6 and $8 trillion in capital, including especially the retirement savings of working families. The financial system's managers shrugged this off as an unfortunate occurrence and lamely explained that these things are to be expected in the tides of free-market capitalism...The system, remember, arduously accumulates its surplus and savings by imposing painful sacrifices and brutal dislocations on innocent participants such as workers or communities Then it artificially inflates the supposed value of those savings as invested in the assets of financial markets. Then it abruptly collapses those assets, leaving millions of families with devastating losses and a much bleaker future. The savvier big players are able to accumulate still larger fortunes while the ignorant herds experience the bracing tonic of free-market insecurity.

This book was written in 2003. Have we learned anything?

A couple of pages later, we find the following. (Please note that this is written at the beginning of a section; I think that knowledge brings some added punch.)

The federal government cannot do this for people. That is hard for many to digest, but anyone who takes seriously the possibility of reforming capitalism in fundamental ways has to start by abandoning some inherited political reflexes. The government has the power to articulate society's larger aspirations, but it is not equipped to execute this deeper kind of economic transformation nor, at this point, even lead the way. If the political community were so inclined (and obviously it's not), legislative leaders would not know where to being, what new arrangements to command by law or to encourage with subsidy. If an activist president set out with good intentions to rewire the engine of capitalism--to alter its operating values or reorganize the terms of employment and investment or tamper with other important features--the initiative would very likely be chewed to pieces by the politics. Given the standard legislative habits of modern government, not to mention its close attachments to the powerful interest defending the status quo, the results would be marginal adjustments at best and might even make things worse.
Government's handicaps are more substantial than the conservative mood. Washington, as we explore later on, has itself become a principal barrier to reformulating the economic system, and it regularly acts as unwitting collaborator in much of the social damage...

Again, this book was written in 2003. Eerie.

copyright control

Fri, 06 Nov 2009 19:37:00 CDT

A thought-provoking passage from The Late Age of Print:

In contrast to the present day, where intellectual property and intellectual property laws are among its leading exports, the United States refused to sign onto or abide by any international copyright treaties until March 1891. Its position thus diverged sharply from that of its European counterparts, virtually all of whom had acceded to various copyright unions in the preceding decades...
Until 1891, therefore, publishers, printers, and booksellers in the United States were relatively free to produce, distribute, and sell their own--some would say pirated--editions of foreign works to American readers. ..
Between 1850 and 1891, the hands-off approach of the United States to international copyright produced not only an explosion of printed books but also a bevy of book publishing houses. Among these publishers were the Harper Brothers as well as other firms that today constitute the center of the book industry, plus lesser-known firms that have been all but forgotten. The persistent refusal of the United States to endorse international copyright agreements empowered these upstarts to challenge the practical oligopoly, and thus the financial well-being, of already established firms like Henry Holt and others. The former did so mainly by underselling the latter. In addition to refusing to pay royalties to foreign authors and publishers, they typically ignored the informal agreements--the so-called courtesy principle--that had kept the price of books produced by more established firms artificially high. Older publishing houses responded in kind by slashing their prices, leading to the collapse of the courtesy system by the end of the 1870s.
As far as the more established publishing firms were concerned, the ultracompetitive environment ushered in by this new crop of book publishers destabilized the book industry. As such, they found themselves forced to rethink their position on international copyright. If the success of this putatively reckless group of upstarts hinged on its ability to produce and sell large quantities of printed books, and if doing so depended on the refusal of the United States to recognize foreign copyrights, then it followed that tightening copyright laws would return stability to the book industry...

new chipz release

Mon, 26 Oct 2009 17:19:00 CDT

I've released Chipz 0.7.4; it can be downloaded from the usual place. This release fixes a brown-bag bug in the CRC32 code. It also implements read-sequence on Gray streams, which should improve performance there significantly.

units fail

Tue, 13 Oct 2009 16:54:00 CDT

I picked up Changing Metropolitan America: Planning for a Sustainable Future by William H. Hudnut III the other day at the library. Lots of charts and graphs about how urban centers have developed and lots of discussion on the right way to develop further. But I have to take issue with a statistic that appears at the beginning:

During the [years between now at 2043], the homebuilding industry anticipates that the United States will need 100 billion square feet (9.3 billion square meters) of new residential space.

You read that and at first, you say, “WOW! 100 billion square feet! A crisis!” I understand that square feet is how we measure our dwellings, but I feel that presenting such big numbers with such little units is slightly misleading.

So how big is 100 billion square feet? About 3,500 square miles. Which is slightly smaller than Rhode Island and Delaware put together. So yes, lots of space...but it looks slightly less dire presented in (well, what I think) are more realistic numbers. (I'm also curious if that's “we need to build that much space,” ignoring re-using existing buildings, or if it's including renovations. Given that the statistic is from the homebuilding industry, it's probably the latter...which makes me wonder how reasonable it would be to renovate spaces instead and cut that space required down.)

Now, if you say we should multiply that number by other factors--for instance, assuming that most of that number is two-story, 2,000 square foot homes with a quarter-acre lot, which means we'd need to multiply the space needed by six or so--then the number starts to sound a little scarier. You're at least approaching top 25 states territory rather than last two. Plus it starts people thinking about other factors besides just raw space requirements: what's necessary to support that space, etc. It's all well and good to fling statistics at people, but you need to provide a little context for people to get a handle on it and to make your point clearly.

tthsum

Sat, 10 Oct 2009 20:49:00 CDT

I promised recently that I would discuss an implementataion of tree hashing. Without further ado, here is the version I whipped up as a candidate for inclusion into Ironclad:

(defparameter *leaf-byte* (make-array 1 :element-type '(unsigned-byte 8)
                                      :initial-element 0))
(defparameter *internal-byte* (make-array 1 :element-type '(unsigned-byte 8)
                                          :initial-element 1))

(defun tree-hash (digest-name stream block-size)
  (let ((digest (crypto:make-digest digest-name))
        (buffer (make-array block-size :element-type '(unsigned-byte 8)))
        (stack nil)
        (n-blocks 0))
    (labels ((leaf-hash (amount)
               (reinitialize-instance digest)
               (crypto:update-digest digest *leaf-byte*)
               (crypto:update-digest digest buffer :end amount)
               (crypto:produce-digest digest))
             (internal-hash (b1 b2)
               (reinitialize-instance digest)
               (crypto:update-digest digest *internal-byte*)
               (crypto:update-digest digest b1)
               (crypto:update-digest digest b2)
               (crypto:produce-digest digest))
             (create-internal-node ()
               (let* ((b2 (pop stack))
                      (b1 (pop stack)))
                 (push (internal-hash b1 b2) stack))))
    (loop for amount = (read-sequence buffer stream)
       while (plusp amount)
       do (let ((leaf (leaf-hash amount)))
            (incf n-blocks)
            (push leaf stack)
            (loop for b = n-blocks then (truncate b 2)
               while (evenp b)
               do (create-internal-node)))
       finally
         (return
           (if (null stack)
               (crypto:digest-sequence digest-name *leaf-byte*)
               (loop until (null (cdr stack))
                  do (create-internal-node)
                  finally (return (car stack)))))))))

I leave it as an exercise for the reader to improve the function in several ways:

Doing I/O in larger blocks;
Allocating fewer intermediate results by allocating more up-front; and
Retaining all intermediate hashes for verifying individual blocks.

Along with some of the obvious improvements given above, the reason this isn't going into Ironclad immediately is because it exposes a flaw in Ironclad's API that should be fixed.

In the beginning, Ironclad had its digest interface. You can either do “one-shot” digests from various sources (files, streams, or sequences), or you can create digest objects and incrementally compute digests by feeding in sequences, as done above. These functions are straightforward enough and are consistent with the interfaces for crypto packages in other languages. A minor quibble is that the “one-shot” functions (DIGEST-SEQUENCE, DIGEST-FILE, and DIGEST-STREAM) could be combined into a generic function with different methods.

Along the way, Ironclad picked up an HMAC implementation. The HMAC functions (MAKE-HMAC, UPDATE-HMAC, and PRODUCE-HMAC) are remarkably similar to the digest interface (MAKE-DIGEST, UPDATE-DIGEST, and PRODUCE-DIGEST). This similarity suggests that there's some underlying generic functions that should be used for both interfaces--at least for the update/produce bits. I didn't change the interface because I suspected the HMAC functionality would be somewhat less used than the digest functionality. The same argument was used when the CMAC bits were added.

But I found as I added other bits and pieces that missing those generic functions was unfortunate. I've also found that having the digest functions be so specific produced slightly wonky code: you can see above where I've written (update-digest digest ...). I don't think that reads particularly well. So I've been considering the idea of unifying the HMAC and digest interfaces for some time.

I think it was in Martin Fowler's Refactoring that I heard this rule: if you need to do something twice, you cut-and-paste and grit your teeth about it. If you wind up needing the same thing a third time, then you should refactor. The tree hash stuff above is very similar to the existing digest interface and we already have the *MAC interfaces that could benefit from similar treatment. That's the three cases staring us in the face. So we should do some renaming/reworking of the existing interface.

But what should the names of the new generic functions be? I'd prefer to not have them be just UDPATE and PRODUCE. When I named the functions originally, I was attempting to follow the guidelines in the Tutorial on Good Lisp Programming Style (which you should read about once a year, if not more often), specifically the bit on using verb-object conventions for functions. While I think using UPDATE and PRODUCE would result in readable code--especially for UPDATE--it's not so obvious what you're producing. We need some kind of object for our generic function name. I have not thought about the problem intensely, so the best I've been able to come up with is something lame like UPDATE-STATE, which gets the idea across, but doesn't translate nicely to PRODUCE-STATE. The underlying functions in the digest interface for the individual digests use FINALIZE-FOO-STATE, which conveys the idea that the digest can't be used anymore after calling this function (correct), but it sounds like you're not getting anything back from the function. So I'm not overly fond of it for an external interface.

Suggestions welcome. Naming is hard! Maybe I should just be calling things “hashes” and then I could follow Python's hashlib module and use UPDATE and simply DIGEST, with no concern for mixing my metaphors, as it were. (If I'm going to modify the external API, I'd likely also change things so that &optional arguments get used instead of &key arguments where appropriate; UPDATE-DIGEST really acts more like subseq than, say find. But that's orthogonal to the naming discussion above.)

urns and caskets

Sun, 04 Oct 2009 21:20:00 CDT

I came upon these Star Trek urns and caskets this week. Fine, trekkies can represent in death. But the Precious Moments urns and caskets, sold by the same company...I understand the sentiment behind them, but they creep me out a little bit.

base32

Thu, 01 Oct 2009 20:37:00 CDT

Faré was asking me the other day on #lisp whether Ironclad supported Tiger Tree Hashes. I said that I didn't even know what those were, and he pointed me to the Tree Hash Exchange Format; Tiger is commonly used for the underlying hash algorithm. I thought it would be easy enough to implement, so I fiddled around with an implementation.

When I went to try to verify my implementation against the test vectors given in the above specification, however, I ran into trouble. The test vectors are given as some weird jumble of letter and numbers and it's not indicated exactly how they are encoded. Apparently hex was considered too obvious. Googling for other implementations indicated that the encoding was probably Base32, so I set out to implement at least a Base32 encoder in Lisp.

If you've ever tried to implement Base32 (or close relatives, such as Base64 or uuencode), you know there there's a lot of bit-fiddling. I attempted to make it as pretty as possible with ldb and dpb, but midway through the main encoding loop, I found myself unable to read my own code. Debugging all those magical constants wasn't going to be any fun either.

I sat back and reconsidered the problem. What you're really doing in Base32 and similar encodings is combining bytes into a big integer and then slicing that integer up in a slightly different way. Judging from implementations I have seen, stuffing all the bytes into one big integer is done for efficiency reasons, avoiding extraneous operations, and all that. But I didn't really care about efficiency (that could come later); I just wanted to make sure my implementation worked so I could get to the business of comparing to oddly-specified test vectors. And this is Lisp, anyway; we always say we can tune things for efficiency later.

After a moment of savoring the thought of giving myself permission to do things in a reasonably inefficient way and avoiding lots of bit-fiddling, I turned out:

(defun octets-to-base32 (octets)
  (let ((base32-chars "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567"))
    (with-output-to-string (stream)
      (flet ((gather (start n)
               (loop with bits = 0
                  for j from 0 below n
                  do (setf bits (logior (ash bits 8)
                                        (aref octets (+ start j))))
                  finally (return bits)))
             (output (blob n-bits)
               (loop for i from (- n-bits 5) downto 0 by 5
                  do (write-char (aref base32-chars (ldb (byte 5 i) blob))
                                 stream))))
        (loop with length = (length octets)
           for i from 0 by 5
           for j from 0 below (truncate length 5)
           do (output (gather i 5) 40)
           finally
           (unless (= i length)
             (let* ((remaining-octets (- length i))
                    (remaining-bits (* remaining-octets 8))
                    (blob (gather i remaining-octets))
                    (n-bits (* (ceiling remaining-bits 5) 5)))
               (output (ash blob (- n-bits remaining-bits)) n-bits))))))))

which was about three times shorter than other Base32 implementations I'd seen. Who cares if it was three times slower? (I didn't benchmark it to check.)

Next time: implementing the tree hasher with Ironclad and some thoughts on problems with Ironclad's API design.

ruining songs

Thu, 24 Sep 2009 21:10:00 CDT

Nothing ruins a good, catchy song like a creepy music video.

library praise

Tue, 18 Aug 2009 20:14:00 CDT

I went to the library with Becca yesterday and picked up two books: Refactoring by Martin Fowler and Why Programs Fail by Andreas Zeller. I was particularly pleased to get the last book because I had requested that the library purchase it, figuring that I could read the book before buying it. I thought that being able to request that the library purchase books is pretty neat.

I requested a book yesterday and received an unexpected email from the library today concerning that request. The body of the email:

Thank you for your recent suggestion for purchase. We have decided not to purchase 'The Collapse of Complex Societies' for a number of reasons, including high price for a paperback, and the fact that it was published over 20 years ago and we haven't had a request for it until now. If you would like, we can try to borrow a copy of this book from a library system that owns it. You can initiate an interlibrary loan request for this item through our website (http://www.imcpl.org) by logging into your account through the My Account area and select the Interlibrary Loans link, or you can call the Central Library at 275-4100. Another option is to check it out directly from IUPUI Library. It currently shows on the shelf there, and as a resident of Indiana, you can check books directly out from their library as it's state-supported. Their phone number is 274-0469.

So, a couple of points about the email. The first is that, despite being signed “Selection Services”, the email came from what appears to be a non-automated address. Points for a personal response. The second thing to notice is that the criteria for rejecting the book are stated; not a complete list, but good enough to give some insight into what the library considers a “good book”. Thirdly, the email indicates other avenues to find the book, even going so far as to check the IUPUI library before sending the email out and confirming that it could be found there.

All of these things are above and beyond the call of duty. The response to my initial request could have been a completely automated email. The email could have simply stated that they have decided not to purchase the book without giving any rationale. They didn't have to tell me about other ways to find the book, nor did they have to run a search for the book in other libraries.

My only quibble is that the “high price for a paperback” must be dependent on other factors (such as the publishing date), since Why Programs Fail is a paperback and I believe it cost more than The Collapse of Complex Societies (although it's possible the library received a discount of some sort). But this is a minor thing; I was pleased with the selection of the library prior to this, I was delighted to find that I can request books and they actually get purchased, and I was equally delighted to receive such a detailed response to purchase requests that didn't get acted upon. Hats off to the Indianapolis Marion County Public Library!

android ebooks

Sat, 15 Aug 2009 20:22:00 CDT

I found FBReader today, which also has a version for Android. I was pleased with this discovery, as it enables me to start using my G1 for book reading, which was one of the motivating reasons for buying it. Even better, Project Gutenberg provides its books in a format (EPUB) that FBReaderJ understands.

The good: I have Austen, Augustine, Dickens, Chesterton, Dostoyevsky, Doyle, Gibbon, and de Tocqueville on my phone, ready to pull up at a moments notice. I have read six chapters of Pride and Prejudice already.

The bad: The formatting on some of the books is only so-so. Some of them were clearly not designed for ebook reading, but rather for viewing in a text editor or something similar. The footnotes in The Decline and Fall of the Roman Empire are particularly bad. I am sad that I'm not going to have Stephenson or Wolfe or whoever on my phone anytime soon, but that's the way things work at the moment.

The ugly: For reasons unknown to me, each text in Project Gutenberg receives its own private URL, but each author links into the middle of a page listing all the works by authors whose last names begin with the same letter (so “Dickens” links into the middle of the “D” page and so forth). This scheme may have worked well when the project was somewhat smaller and may still work well for examining an author's works on a desktop machine...but it's truly awful to attempt to view one of these alphabet pages on a mobile phone. I suppose I could download the texts to my SD card from my desktop...even so, the current scheme does not scale and will only get worse as relatively less powerful devices than desktops become a predominant way of accessing the web.

Now we just need the Christian Classics Ethereal Library to offer EPUB books and we'll be all set. (Some works are offered in Palm's PDB format--a reader exists for the Android platform--but not all, and the PDB files are not downloadable from the G1's web browser. FAIL.)