I guess I’ve defected to Tumblr. It feels more casual, which means I’ll probably use it more.
(Of course, I’m not trying to convince anyone that it’s rational.)


Thoughts and feelings that ache for another to know;
frigid memories blowing with nowhere to go;
strong and silent, eluding my lips when I speak,
stand and smoulder in silence,
and shout when I’m weak.

Frigid air in my heart, wanting freely to roam,
never cling to the words, though I’m waiting to know
the release of the pressure of dominant thought,
steeped in hardships and pictures
I wish I’d forgot.

To the plea from my knees, no reciprocal word,
though I know that the “please” you undoubtedly heard;
after hardship, you let an omission befall,
left the ones that remain
an unscalable wall.

And the hardship once shared left a vacuum in me;
they would know it if only my thoughts they could see;
but the words of compassion I seek never come,
so, as far as they see,
my compassion is done.

Into the flames, you lowly saint;
you know their end,
        and you know yours.

Your end will purge the hated taint;
from ash to phoenix,
        live once more!

Hey guys, more automatic memory management!

So, this one excites me because, assuming changes to the (soon to be introduced) linked lists are atomic, this algorithm can be run in parallel with the main computation(s), and even other garbage collection threads.

Note: I seem to have regurgitated Baker’s “treadmill” algorithm without knowing it.

– Every object, as it is created is added to the “live” data structure, or “live pool”. Purely for example, I am going to assume the data structure is a doubly-linked list. If you want some other arrangement, make whatever adaptations you need.

Anyways. The main deal is that the “live pool” holds references to all objects the garbage collector considers “live”, that objects can be inserted and deleted, and that a record is somehow kept of which objects in the pool have been scanned during the current pass. In the case of the doubly-linked list, we can just keep a reference to the first unscanned item in the list. (Regardless of how references are really implemented, this will be called the “scan pointer”.) In addition to the scan pointer, in out example, every object will also contain a “has-been-scanned” property that marks whether or not the object has been scanned. This could, for example, be just a bit in a header.

– Every object, when it is created, is inserted into the “live pool”, and marked as scanned. In the case of the doubly-linked list, the object is inserted anywhere in the linked list that precedes the location of the scan pointer. (Meaning that, as the scan pointer is moved down the doubly-linked list, the given object will NOT be encountered.)

– Scanning is a generalization on Cheney’s algorithm. Some unscanned object is selected from the “live pool”; every object that the scanned object references (each target object) is (if necessary) deleted from the (later described) “limbo pool”, inserted into the “live pool” , and marked as unscanned. In the case of the doubly-linked list, the target object is unlinked from wherever it is, and inserted into the “live pool” anywhere AFTER the scan pointer, unless the target object is marked as already having been scanned. (That is, unless the object’s “has-been-scanned” property says that the given object has already been scanned during this pass. This is why that property was defined. This way is more efficient than traversing the entire “scanned” portion of the “live pool”, looking to see if the target object makes an appearance.)

– When an object is changed to refer to some object, if the target object is marked as not having been scanned, it is added to the “live pool”. In the case of the doubly-linked list, see above.

– When no more unscanned objects remain in the “live pool”. The “limbo pool” becomes the “dead pool”; the “live pool” becomes the next pass’ “limbo pool”; if applicable, all objects in the “limbo pool” are marked as unscanned; a new “live pool” is started; the storage of all objects in the “dead pool” is reclaimed. As you might now guess, the “limbo pool” is every object that may or may not be live. In the case of the doubly-linked list, the meanings of the linked lists are changed. The list that was the “limbo pool” is scavenged for storage space; the list that was the “live pool” becomes the “limbo pool”; NULL (the empty list) becomes the “live pool”; the “scan pointer” is reset. For convenience, rather than changing the “has-been-scanned” property of all objects in the new limbo pool, the meaning of the property can be can be changed. (For example, if the property being set to True meant that the object has been scanned during the last pass, the property being set to False would mean the same thing during the next pass. This sort of meaning-changing is common with mark&sweep collectors.)

So, that’s that. But what’s this business about having to store two extra pointers per object to implement my linked list example? Well, that isn’t strictly necessary. What if each, say, 4kB page of allocated memory had its own mini linked lists, which were a subset of the full pools? Every object in that page could then be referenced in 12 bits. We would the only need 24 bits per object. Assuming a 32-bit architecture, and 4-byte alignment, we could get that down to 20 bits per object. This, as a bonus, leaves plenty of bits for flags, tags, and so on.

Fun! Thanks God! :)

I swim in words too lofty
  for the life I have yet led,
too few in years to truly
  understand, despite
Contrary estimates,
  both mine and thine.

The depth of word,
  though known as deep,
Is lost on such a one
  as me, who’ve yet to reap
A lifetime’s worth of
  wisdom, work,
    and pain.

Gentle waves along the shore,
as sunlight warms you, pained no more.
Shire grass you knew again,
but home was not as warm as when
we two set out so long ago.

I love the Shire, and married another,
but even joys were shadowed by
the hurt I knew to haunt my brother —
you — and greyed your once-blue eyes.

I guess you’ll never see these words I wrote,
since you’re off westward in that boat,
but, still, I much want you to know:
good Frodo, sir, I miss you so.


I came across the following multi-method strategy while reading about the implementation of prototype-based object systems. It is written with that domain in mind, but it would not be difficult to adapt to a more traditional class-based language.

Section 3 details it, and figure 5 is a useful diagram. The idea is that each object (or class, perhaps) that can be dispatched on has its own method table. (In that sense, it is comparable to C++.) Each method that dispatches on that object (or class) is put into the table. The clever part is that the table is separated into subsections, which correspond to parameter positions.

To clarify: imagine that you have a method that specializes on class “Foo” for the first argument, and class “Quux” for the second argument. Section 1 of class Foo’s dispatch table would contain a pointer to the method. And, section two for class Quux’s dispatch table would also have a pointer to the method. To do dispatch, then, the arguments’ classes’ dispatch tables are consulted. If the method pointers match (like in our example), that is the method to call.

The paper is called “Prototypes with Multiple Dispatch”. http://lee.fov120.com/ecoop.pdf

I posted this as a rather substantial answer to a question on StackOverflow. I figured that it makes a better technical blog post than the ones I have tried to write in the past. So here it is!

This post is Lisp-centric. If you don’t know anything at all about the Lisp programming language, you will be mostly baffled.

The elementary function to return the length of a list, written in Lisp — my favourite programming language — is something like this:
(define (length lst)
    (if (null? lst) 0 (+ 1 (length (cdr lst)))))

The original question was why getting the length of a Lisp list takes a time proportional to the length of the list. In Big-O notation, the asker wanted to know why the length function was O(n), rather than O(1).

The reason is the “traditional” implementation of lists in Lisp. Elsewhere, lists are sometimes implemented similarly to an array. So, when you create a list, it’s a single, self-contained thing.

An array-like list: [ 1 2 3 4 5 6 ]

If you wanted to tack an item — ‘0’, for example — to the beginning of that list (and assuming the list implementation is simplistic), all the items in the list would be shifted up (to the right). Then, the ‘0’ would be installed in the new spot.

Step 0. [ 1 2 3 4 5 6 ]
Step 1. [   1 2 3 4 5 6 ] (Shift Right)
Step 2. [ 0 1 2 3 4 5 6 ] (Insert)

That is not how (traditional) Lisp lists are at all. Every item of the list is a separate piece that points to the next item. The parts of the list are called “conses”. (This is called a linked-list.)

[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

Huh? Well, each of those items is a cons cell. And each cons cell holds two values: car and cdr. (When cons cells are used with lists, it’s nicer to think of “car” and “cdr” as “first” and “rest”. “First” holds whatever data you want the list to hold, like numbers, or even links to other lists. “Rest” holds the rest of the list. You can actually put whatever you want into the “rest” part, too, but we’ll ignore that here.) “Nil” is the “empty list”, which basically means “the list has ended!”

So, what if we wanted to tack a ‘0’ onto the front again?

[0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

See? We just created a new cons cell that pointed to the beginning of the old list. You’ll hear people call this “consing” a value onto the front. But, you’ll notice that the rest of the list is untouched.

Okay, but why does anyone want this? You can share lists. Imagine you wanted two basically identical lists. Only now you wanted one list to start with a ‘7’, and the other with a ‘4’? Well, with the array-like way, we’d have to have two lists.

[ 7 0 1 2 3 4 5 6 ]
[ 4 0 1 2 3 4 5 6 ]

What if you replaced the ‘5’ with ’14’, and share the change?

[ 7 0 1 2 3 4 14 6 ]
[ 4 0 1 2 3 4 5 6 ]

You have two totally separate lists. If you want to share the change, you’ll have to make the change in both lists.

What happens with traditional Lisp lists? First, sticking a ‘7’ and a ‘4’ to the front:

   ----> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

Yup. We just made two conses that both point to the old list. The rest of the list is shared. And, if we replace ‘5’ with ’14’:

   ----> [0] -> [1] -> [2] -> [3] -> [4] -> [14] -> [6] -> nil

Both lists get the change, because the rest is shared.

The point of all this is that, unlike what many folks expect, traditional Lisp lists aren’t a single thing. They are a bunch of little things (conses) that point to each other to form a chain, which is the list. If you want to get the length of the chain, you have to follow all the little links until you get to the end, nil. Thus, O(n) length.

Lisp lists could be made O(1) if they were done like arrays. I’m sure some obscure Lisps do this, and get rid of linked lists (conses) altogether. But, conses seem to be one of the things that makes its way into basically every popular Lisp dialect. If you want O(1) length and lookup, most of them provide arrays or vectors, too.

Linked-list fun:

 |                                                     |
 --> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] --->

This linked list eventually points to itself. If you use the original length function, it will loop forever, looking for the end, but never finding it.

In the darkness echoed each metallic
In the solitude rang each oppressive
Each petition answered only by a
and , “asketh not wherefore the iron tolls;
its purpose, though, is soon to be fulfilled.”

“Good morning, Master; was this night as ill
as is the norm?” The door he opened with
the breakfast tray he held, and entered in.

The sharp reply came swift, “and what if I,
as you arrived in here not lacking noise,
had finally acquainted with shut-eye?”

“I knew it would have been no harm; the joys
of pleasant sleep and dreams you know no more;
to wake you up is nearly merciful.
And your ‘what-if ‘ betrays this night was so.
How long have you been up, alone in thought?”
He set the tray upon a little stool.

“I know not if I slept at all this night,
or if my nightly visitation vexed
me even in the near-sleep twilight that,
in times no longer here, would comfort me.”

“I did not hope, but did expect as much.
I let you lie, for ’tis now after-noon.”

The Leper took the tray upon his bed.
“I knew; I hear each clock-bell chime, each day.”

“I pray you’ll soon not hear a few each night.”

“As I pray, too.”

A narrow maple corridor;
a rabbit in the underbrush;
a rolling field of amber grass;
The smell of dirt after a rain
along a pathway bordered by
a field of grass,
and untamed flowers,
all painted joy by the sun
as it goes down
in the cool of the day.

My love, I’ll meet you soon,
and bring you here.


Get every new post delivered to your Inbox.