Why OO Languages Need Tail Calls

http://www.eighty-twenty.org/index.cgi/tech/oo-tail-calls-20111001.html

by swannodette • 15 years ago

19 5 15 years ago

ggchappell• 15 years ago

Previous HN discussion:

http://news.ycombinator.com/item?id=2640537

IMHO, this is worth a repost, though. It takes some time to read through and understand. Those who didn't have the time for the last post, might have the time for this one.

P.S. I'm still wishing I had gotten a proper response to my comment (#11) on the original article. <sigh>

IvoDankolov• 15 years ago

I have two issues with the article (notwithstanding that I had to look it up in google cache because the server wasn't responding).

First, while it's true that in this particular case iterating exposes gritty implementation details (because, to even define "iteration", you need to know about all the possible implementations and how they store items). However, that doesn't mean that the design of the interface can't be changed so that iteration is possible. The fastest I can come up with is adding a concept of inner set (that might or might not be null) and a method containsOuter, that by contract should not dig into the inner set. Then, for the adjoint set implementation you would have (in a more C-family style)

  bool contains(T item)
  {
    bool res = containsOuter(item);
    IntSet next = getInnerSet();
    while(!set && next != null)
    {
      res |= next.containsOuter(item);
      next = next.getInnerSet();
    }
  }

And we have iteration, without having to resort to implementation details. Barring any argument about aesthetic appeal of having this innerSet thingy, the code itself is simple enough to manage (heck, you could have that as a virtual method without any problems if you were in the frame of mind of class inheritance as opposed to interfaces).

Second, I don't see why we can't abstract this iteration business into an iterator. Fine, Java's iterators may or may not be a sprawling mess, but add lazy evaluation to the mix and you have a very, very powerful system. In particular, LINQ and Haskell handle collections quite nicely, and nothing stops you from implementing it in the OO language of your choice (if there aren't already some).

So how do lazy iterators help? Well, infinite sets become stupidly easy to handle. Heck, you can even self reference in C#:

  static IEnumerable<int> Nats()
  {
    yield return 1;
    foreach (var n in Nats().Select(x => x + 1))
      yield return n;
  }

Not that I recommend mapping your collection to itself, mind, but if you wished you could go all out with it. The point is, you can transform an infinite list, filter elements out of it, combine it with another infinite list and then take 10. It won't even take infinite time to compute.

So no, lack of tail recursion is not a detrimental problem to the OO abstraction. An annoying problem, yes, but no more than that.

tonyg• 15 years ago

Sigh. The server should be back now. That'll teach me a lesson about TSTTCPW.

kenjackson• 15 years ago

One problem I have with tail calls in OO languages is that they're fragile. Simple things, like adding a print statement for debugging, can break your code. I think these things are more apparent in functional languages.

With that said, I'd love to see it implemented in OO languages, but I'd tell those to be wary where correctness relies upon it (and as blasphemous as this may sound -- use iteration in places where it doesn't destroy the code).

pelotom• 15 years ago

Some related material (in the order it should be read) for those interested:

On understanding types, data abstraction, and polymorphism: http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf

On Understanding Data Abstraction, Revisited: http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf

LtU discussion: http://lambda-the-ultimate.org/node/3668

LtU discussion of Steele's post: http://lambda-the-ultimate.org/node/3702

Why OO Languages Need Tail Calls

Related Stories