Tail recursion, micromanagement, and naughty bits

On this fine Sunday afternoon, I've been assembling a LinkedList class for the Mongoose standard library (in the Collections module). It's a pretty standard doubly-linked list — a freshman-level chore that I've done in at least a dozen languages through the years. Recently, good high-level languages have saved me the work by bundling an implementation — but when you create your own language, the giants' shoulders are smaller and less comfortable.

So, let's take the task of getting a particular link within the list. (A Link is an object that knows who its neighbors are, and holds a reference to some value.) Once you can get a link, you can get its value, or navigate around it.

In C, Java, and other procedural languages, you would probably do this with a loop and at least one scratch variable. Loops and scratch variables smell funny to me.

Mongoose calls this method linkAt:, and it's implemented like this:

(-- ... in LinkedList ... --)
@method self linkAt: index [
  (_count = 0) ifTrue: [ ^nil ]. (-- no links to return? --)
  ^_head seekForwardBy: index.
].

It checks if the list contains no elements (as indicated by an instance slot named _count), and returns nil if this is so. Otherwise, it tells the head of the list (a Link named _head) to peek ahead some number of elements and return the neighbor it finds.

Of course, _head, like other Links, only knows its immediate neighbors, so it delegates.

(-- ... in Link ... --)
@method self seekForwardBy: offset [
  (offset = 0) ifTrue: [ ^self ]. (-- that's me! --)
  ^_next seekForwardBy: offset - 1.
].

It checks if the offset is zero, and if so, doesn't do any work at all: it simply returns itself. Otherwise, it pawns the work off on its next neighbor (named, appropriately, _next).

When I wrote this code (with the exception of a couple poor name choices), it just felt good, and I wanted to know why. I think it comes down to one thing:

There is no micromanagement.

In a normal LinkedList implementation (and, I admit, in the first draft of my Mongoose class), the list itself examines each Link, checking who its neighbors are. It controls the navigation; it interrogates every Link, leaving it feeling confused and violated.

This implementation does nothing of the sort: it asks the Link to find out a bit of data. Each Link can then ask its neighbors as appropriate. It comes back to one of the principles espoused by Smalltalk, which I refer to as the Politeness Principle: don't micromanage, or, alternatively, ask objects to do things; don't peek at their naughty bits and decide for them. (On that note, it could be considered the gender equality principle as well.)

As I iteratively refactored LinkedList to make it Polite, I tried to improve politeness while still using a traditional while-loop, thinking it would be more readable for most programmers.

I failed.

Which brings me to my next thought on the matter: tail calls are really the only Polite way to do iteration. There's no one object or routine managing the process; instead, each stage successively asks the next, "Do whatever you think we should with this data," and it can decide whether or not to continue.

Mongoose has optimized tail calls since M1 as its fundamental iteration primitive, but I didn't add them because they were Polite — I added them because they were less conceptually nasty than a goto, which is how most other languages iterate.

On the other hand, Smalltalk, the origin of the Politeness Principle, does not mandate tail-call optimization. In my tests on some current Smalltalks, it doesn't seem common. This blows my mind: it's only proper!

Update: I had misstated the Politeness Principle; I'm looking for a concise yet correct definition now.