Don’t return null; use a tail call

Why should an object-oriented programmer care about tail-call elimination? Isn’t that just another esoteric functional programming concept? Maybe not.

Back when dinosaurs roamed the earth, a common technique for performing a subroutine call worked this way:

  1. The caller stored the address at which it wished to resume execution in a known place (e.g. adjacent to the called routine’s code);
  2. The caller branched to the called routine’s entry address;
  3. Upon completion, the called routine branched indirectly to the stored return address.

Of course, this technique precluded both recursive and re-entrant calls, but those were regarded as esoteric, theoretical concepts with little if any practical use (see the “Historical Footnote” below). Times change, but programmers are still living with constraints whose roots go back to the kinds of mechanism described above. We all know that a simple and correct recursive routine can still founder on the stack overflow reef. But I recently saw a blog post by Zachary D. Shaw that rubbed a bit more salt in that wound.

His post on Returning Null discusses an alternative to the common idiom of returning a null result as a way of saying “not found”. In his post, the caller passes itself as an argument (using a suitable interface type, of course), and the callee responds by invoking either a “found” or “not found” method on the caller. This models the interaction as an exchange of specific and appropriate messages, instead of encoding the “not found” case in an abnormal value which the caller must decode in order to determine what to do.

I’m currently enjoying the book Growing Object-Oriented Software, Guided by Tests by Steve Freeman and Nat Pryce, of mock objects fame. That book reminded me of the value of separating the design concept of passing messages from the implementation detail of writing methods. It would be nice to be able to use such a technique without stack depth raising its ugly little head as an issue, however fleeting.

Simon Harris posted on this issue from a Ruby perspective, and Guy Steele’s Fortress blog has an elegant illustration in that language. Of course, Steele’s 1977 paper is the ultimate resource on the subject. Even the name of that paper has had its influence.


Historical Footnote: The November 1963 issue of Communications of the ACM contained a short piece entitled “Recursive programming in Fortran II“. Membership is required to download the PDF, but you can get a sense of the attitudes of the time just by reading the abstract on the linked page.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Comments

  • Steve Freeman  On 2010-04-24 at 08:39

    All of this is true, but Java really doesn’t make it easy. Just recently, I’ve had to back off passing in callbacks so often because Java makes so much noise that the code was unreadable. We really need to move on beyond this (and, ironically, I suspect that C# does).

    And, thanks for the link to the book πŸ™‚

    • Diablo-D3  On 2012-01-10 at 05:24

      Except Java almost already has something like callbacks for this specific usage (error handling): exceptions.

      • joelneely  On 2012-01-12 at 08:17

        First of all, I’m not necessarily talking about errors. For example, absence of a particular key (e.g. in a hash map or database) may be a completely normal alternative.

        In addition, I regard recovery/abandonment logic for a disruptive event (e.g. sudden inability to read from an opened file or socket) very differently from the normal workflow associated with a commonly occurring condition. To continue with the example, I would not want to express this concept:

        If X is in the data store,
        do action Y on its associated data,
        otherwise do action X.

        with the (more complex, to my eye) prescription:

        Try to retrieve the data for X from the data store.
        Call that result D.
        Do action Y on D.
        Oops; if you can’t do the above,
        Do action Z.

        The run-time cost is much higher than “normal” invocation and control structures (the minor objection).

        The extra “noise code” offers many more opportunities for error. Additionally, it creates clutter that the reader must parse, understand, and essentially ignore while trying to understand the underlying intent (the major objections).

  • William Edwards  On 2012-01-10 at 04:55

    Unconvinced (in an imperative language world). This is SAX parsing all overagain, vs an XML-pull API. If you ‘send messages’ rather than return values, you have reenterant code when you consider the object as a whole and you have a lot more complicated state to manage and understand and bugs and races start appearing and you can even have volatile and synchronisation issues in single-threaded code.

    Some languages do make massively message-passing architectures easy, or even the norm. But even then, you use it for big deal stuff or async stuff, and not at a micro level for small functions that might return null or an object or otherwise throw an exception.

    • joelneely  On 2012-01-10 at 20:33

      Thinking in terms of pure functions that consume and produce immutable entities (which can themselves be functions) is a good way to stop worrying about whether the function is re-entrant, what happens to mutable state with concurrent invocation, etc.

      As with any paragraph-sized illustration, the example discussed in this post can certainly be rewritten in a variety of ways. But if we eliminate pointless return stack growth for tail calls, we remove another barrier to thinking more functionally.

      Message-passing as a programming model has been around since Carl Hewitt’s work on actors in the early 70s. I regard the question of whether it is understood and used “in the mainstream” as more of a comment on our programming culture than on what is possible in principle.

      • William Edwards  On 2012-01-10 at 23:11

        I guess I have to think carefully by what you mean by “object oriented programmer” in the first sentence, and the zdsbs blog you link to.

        If you mean, as some of the other comments and links hint, java and using an interface to return a true boolean (http://thedailywtf.com/Articles/What_Is_Truth_0x3f_.aspx ?) by invoking the method immediately rather than putting it into some queue for later processing by the caller i.e. cooperative multi-tasking, then that pattern is making the life of the programmer very much harder than if they just use the stack.

        The obvious language construct that zdsbs is omitting from his contrived example is throwing an exception when the authentication fails.

        In Java I like the anonymous classes pattern but even that means hard work that only pays off in deferred situations or as a way to take an interface that is unnecessarily complex and squash it into a function without sloppy promoting transient state to instance scope and so on.

        I’m just going through some Chrome NaCL boilerplate with its objects having is_null() functions so I guess I’m particularly delicate to all talk about interfaces vs return values vs exceptions right now πŸ˜‰

        Tail calls in a non-functional context are a cool compiler optimisation. GCC, for example, can even remove stack recursion that aren’t pure tail-call signature. As long as the function is static scope or inline and various other gotchas. But its happening.

        I love the whole functional thing, but promoting passing an interface in an imperative language like Java/C++ as in any way a general form of ‘message passing’ which will make code easier to write, understand, debug and see correct-by-inspection is just unconvincing.

        So I must have massively misunderstood you. What have I grokked wrong?

      • joelneely  On 2012-01-12 at 08:29

        I think we’re looking at opposite sides of the coin. We agree that manually constructing in-line anonymous classes and boilerplate, worrying about stack overflow when making nested or recursive invocations, and other such details, are bothersome and a potential source of error.

        I’m simply speculating that in this area Java is too much like assembly code (including C). The explicit emphasis on passing around state-as-data and on implementation mechanisms often makes the underlying intent harder to express when writing the code and harder to see when reading it.

  • Gabriel Claramunt (@gclaramunt)  On 2012-01-10 at 08:51

    Why “Option” is not an option? πŸ™‚
    I mean, instead of a callback, you can return Maybe/Option, granted, Java doesn’t make it easier either…

    • joelneely  On 2012-01-12 at 07:52

      The Maybe monad is an option (pun intended πŸ™‚ ), but I’d like to consider the possibility of not needing a returned value at all. I agree that Java doesn’t make either approach easy (at this point in its life).

      • Gabriel Claramunt (@gclaramunt)  On 2012-01-18 at 06:45

        yes, after I wrote the comment, I’ve realized that you don’t care about the element itself.
        Basically the callbacks are continuations, right? Interesting, is the first time I think about CPS in Java… doesn’t look pretty but it can work πŸ™‚

  • Shawn Neal  On 2012-01-10 at 09:44

    +1 for reading GooS, its a great book with a lot of practical advice for sustaining long term systems.

    • joelneely  On 2012-01-12 at 07:49

      Thanks, Shawn; I agree with your assessment of the book.

  • JJoos  On 2012-01-10 at 11:44

    It doesn’t have to be a method, F# returning none er some is quite elegant imho!

    • joelneely  On 2012-01-12 at 07:48

      I agree with you on the elegance of the Maybe monad. However, I’m questioning the assumption that this scenario needs any kind of return value at all. I’ll post more later.

  • Xavier Dury  On 2012-01-12 at 14:20

    Another benefit of using callbacks is that callbacks are executed in the context of the called method. If that method is transactional, your callback will be part of that transaction. This can be useful when loading a JPA entity for display: if you populate your UI controls inside the callback, you can totally avoid lazy-loading problems.

    I wouldn’t use callbacks everywhere but there are some situations where they can be really useful.

  • Salsa Oudenaarde  On 2012-01-29 at 04:30

    I am so grateful for your article.Really thank you! Cool.

Trackbacks

  • By Blog harvest, May 2010 « Schneide Blog on 2010-05-30 at 13:28

    […] Don’t return null; use a tail call – A blog entry about the billion-dollar-mistake (null pointers) and API design. It got inspired by Steve Freeman’s book “Growing Object-Oriented Software” (see next section for more content by Steve Freeman). The idea of “tail calls” or callbacks isn’t new or revolutionary, but widely underused. Personally, I found the idea of returning empty Iterables (as an abstract commonplace of Collections) useful in some scenarios. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: