Tail recursion, micromanagement, and naughty bits
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
nilif 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.
_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
offsetis 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,
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.
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.