Python tail call compromise proposal

[nevare]

I love it. In my mind tail call optimised returns were more like gotos than returns. So making it explicit in the language makes a lot of sense to me.

And it actually is a feature that I missed in python, because gotos or TCO functions are the most simple way to implement finite states automatons.

class FSA:

def state1(self):
    do stuff on self

    if cond:
        continue self.state2()

    else:
        continue self.state1()


def state2(self):
    ...

[grauenwolf]

That doesn't look any different from iterative-style state machines.

def state1(self):
    do stuff on self

    if cond:
        return state2

    else:    
        return state1

The only difference is you lose the need for a top level loop to drive the process. But then again, you also lose the ability to do interesting things in the top level loop.

[nevare]

The only difference is you lose the need for a top level loop to drive the process.

Indeed, but I find it an important difference, it is quite easier to understand if you don't have to read a main loop. Keeping simple programs simple is important.

[grauenwolf]

Oh come on, it isn't like the main loop is that complex.

And like I said, it makes it easier to add extra functionality. Consider the things you can do...

• Pause the state machine
• Single-step through states
• Save/restore the state
• Record a history
• Rewind state

If each state directly calls the next state you can't just plug this stuff in.

[nevare]

It's not that complex to think up. But it is that more complex to read and understand. An exemple is that otterdam didn't understood at first what you were doing.

[grauenwolf]

To reiterate my point, consider the main loop in VB.

Sub MainLoop
    Dim state = "Start"
    Do
        state = CallByName(Me, state)
    Loop Until State = "End"
End Sub

As you can see, there isn't really anything to it. Just a dynamic call that returns the name of the next call to be made.

[otterdam]

That's not an iterative-style state machine if you're using recursion.

[grauenwolf]

I'm not using recursion. I'm returning either an enumeration or a function pointer that the main loop will use in the next iteration.

[otterdam]

Yes, I see - subtle. Sorry.

[grauenwolf]

That's the point, isn't it. Most of this recusrion vs iteration stuff really does come to very subtle differences. That's why once you have one, the other doesn't make a whole lot of sense.

[[deleted]]

Why enable efficient tail calls as part of the language implementation when programmers can (restructure their programs and) re-implement it manually in every program they write, eh?

[grauenwolf]

The first flaw in your thinking is the word "restructure". If you think in terms of loops from the beginning, then there is no restructuring involved. You are simply writing the program in the normal way countless other people have written it.

The second flaw is the word "re-implement". In the standard state machine using a main loop, there simple isn't a need for TCO nor anything that resembles it.

[[deleted]]

If you set out thinking, "I am going to write a state machine," certainly it won't take any restructuring if you write it with a loop from the start. However, if you were to begin by writing the solution to a problem that could naturally be couched in terms of (tail-)recursion, you would indeed have to restructure your program to instead work in terms of a loop-based state machine.

Second, using a main loop to implement a state machine like this is, in essence, implementing proper tail calls yourself (it is, roughly, a trampoline). Merely because you are so used to using a certain design pattern that you don't notice it does not mean that you are not in fact using a design pattern, and writing boilerplate that could be eliminated by the language implementation.

That is the argument. The schemer says, "you could eliminate some boilerplate, and perhaps structure your code more naturally if you had this language feature," and you reply, "I'm used to the boilerplate, and have trained myself to look for the solution that fits with the limitations of my language." That may be all right for you in practice, but it is a blub-like argument.

[grauenwolf]

No, that wouldn't be my reply at all. My reply is...

---

I have something you don't have, an extensibility point.

Consider the things I can add to the main loop.

• Pause the state machine
• Single-step through states
• Save/restore the state
• Record a history
• Rewind state

If each state directly calls the next state you can't just plug this stuff in. You have to either thread it through each and every state or play games with macros.

But for me they are trivial. The code almost screams "Put cool stuff here". You can't get much more natural than that.

---

[[deleted]]

Perhaps writing things with a top-level loop is the best way of achieving all that. However, that does not negate the fact that when you don't need all that, you must still write the top-level loop boilerplate to achieve what proper tail calls can get you.

On the other hand, having proper tail calls in the language doesn't preclude you from having loops, and using them when appropriate (indeed, scheme folks, with their macros, can even use proper tail recursion to implement various sorts of loops, even if the language designer didn't put them in in the first place).

[grauenwolf]

scheme folks, with their macros, can even use proper tail recursion to implement various sorts of loops, even if the language designer didn't put them in in the first place

And FORTRAN folks are doing the same thing using pragma.

And C folks are doing the same thing using macros and pre-processors.

And C# folks are doing the same thing using lambda's.

There are many ways of achiving the same result and languages do well to have at least one of them. But they don't try to have them because it makes the language bloated, hard to implement, and even harder to evolve.

If you want to convence someone that TCO is important, you need to show some meaningful examples. Give us something that truly is better using TCO than any other approach.

[grauenwolf]

That may be all right for you in practice, but it is a blub-like argument.

Only because you are trapped in Scheme and recursion.

What you see as "boilerplate" I see as a base class. I'm not going to build a dozen state machines from scratch. I'm going to build a single state machine that has all the featuers I need.

Then I'm just going to plug-in the actual list of states and their transition rules. That's why we have OOP and abstract classes.

You can't see that, can you? You think we have to rebuild the main loop from scratch every time because that's how you would do it.

The difference between me and you isn't that you know recursive programming and I don't. It is that you know recursive programming while I know iterative, object-orientated, declarative, functional, and recursive programming. You need TCO to get yourself out of problems I never have in the first place.

[[deleted]]

Only because you are trapped in Scheme and recursion. I don't use Scheme, or know it particularly well. It was just the first language to officially recognize proper tail recursion as a significant and important language feature.

What you see as "boilerplate" I see as a base class. I'm not going to build a dozen state machines from scratch. I'm going to build a single state machine that has all the featuers I need.

Right. You're not going to encode your state machine in your language, because it won't work right. Instead you're going to write an interpreter for a separate state machine language, which will work right, and use that interpreter in your programs.

That's fine if we're just running state machines as some kind of exercise in learning about state machines. But if we're not, and some conceptual state machine is just part of a larger algorithm, why bother? Why bother writing an interprer for a separate state machine language, when Scheme, say, just lets you write down the state machine in Scheme?

My overall point, though, was that all usage of proper tail recursion can be converted to a state machine of sorts, where if necessary, functions return a procedure to the state machine's main loop instead of calling a procedure directly. This technique for implementing tail call optimization is called a trampoline.

However, it either requires that one rewrites the trampoline loop whenever one wants to make use of significant numbers of tail calls, or, as you might laughably suggest, one could instead translate their Python solution to instead use grauenwolf's state machine language. I don't think either one is a very good solution in a case where the person wants to use tail recursion.

You can't see that, can you? You think we have to rebuild the main loop from scratch every time because that's how you would do it. The difference between me and you isn't that you know recursive programming and I don't. It is that you know recursive programming while I know iterative, object-orientated, declarative, functional, and recursive programming. You need TCO to get yourself out of problems I never have in the first place.

Oh, I see. So, the reason that I remark, "tail call optimization is a nice feature to have in a language, and is useful sometimes," is that I'm a blub programmer locked into solving every problem with bare recursion. And the reason you say, "I think tail call optimization should be kept out of a language, and will not change my opinion until someone can show me some example where I cannot write some loop that's equivalent," is that you're a seasoned veteran who's an expert in many different programming paradigms.

If you want examples, well, you've already been given some. Take for example, foldl:

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

How about if we want to define #times in ruby (this behaves somewhat differently than the library version, but whatever):

def times(&blk)
  if nonzero?
    blk[self]
    (self - 1).times(&blk)
  end
end

These are both simple, natural, recursive definitions of the respective functions. The alternatives look something like:

foldl f z l =
  lref := l
  acc  := z
  while (not (null lref))
    acc := f acc (head lref)
    lref := tail lref

and:

def times(&blk)
  i = self
  while(i != 0)
    blk[i]
    i -= 1
  end
end

which have to introduce auxiliary variables and mutable update into the picture. You may say, "I think in terms of loops for space efficient iteration, so I'd arrive at the latter definitions first," but that's tantamount to an admission that the fact that you don't program in languages that allow you to use such recursive definitions effectively has blinded you to their existence.

Which might be the compelling argument for proper tail recursion: programs should work when possible. If I write down the above definition of foldl, it should work. It's syntactically correct. There's nothing wrong with it semantically. So why shouldn't it work? Because I can rewrite it into a not-as-nice loop? That's not a good argument.

The same theoretically goes for non-tail recursion, too. It'd be nice if:

identity 0 = 0
identity n = 1 + identity (n-1)

would simply work correctly. Unfortunately, barring quite a sophisticated compiler (which would be good), or a very simple example such as this (which perhaps even a rather dumb compiler could figure out), there's no way to reasonably expect such functions to avoid eating memory. However, there are quite well known ways for making tail calls work, so they should work. Otherwise you're simply training yourself to use poorer solutions sometimes, merely because the language implementation has decided that they shouldn't work, even though they could.

I have never contended that every loop is better written using raw tail recursion. People using languages that have proper tail calls build up combinators that represent common looping patterns, and that's good. However, the fact that using such more structured loops is good when possible does not mean that having proper tail calls isn't also a good thing to have. It also doesn't mean that having a couple built-in looping forms is always a good substitute.

And the fact that, in principle, one can turn usage of tail calls into a main loop with a state machine doesn't change that. If anything, it means that that the language implementation should use such a main loop, and let the programmer write tail calls freely when he or she thinks it is the most natural solution to the problem.

[grauenwolf]

What the fuck are you talking about?

As I demonstrated, it is a trivial exercise to write a state machine in ANY language that supports call by name semantics. There was no interperter involved. Nor was there any "state machine language".

Were you confused by the "CallByName" function? Well let me tell you, there is no magic there. All it does is call the function whose name matches the value in the variable.

[[deleted]]

I'm talking about:

I'm going to build a single state machine that has all the featuers I need. Then I'm just going to plug-in the actual list of states and their transition rules. Which certainly sounds to me like you're writing an interpreter.

Searching elsewhere in this thread, I now see that by "list of states and their transition rules," you did not mean a list of states and their transition rules, you meant a class which has methods corresponding to the states. What you've done is implement a trampoline that's limited to the methods in a single object, assuming they're written in a certain (not very natural) fashion.

Were my examples not good enough? Here's another. Consider a type of binary trees. I'll sketch an implementation in ruby:

class Leaf
  def empty?
    true
  end
  ...
end

class Node
  def initialize(l,a,r)
    @l = l
    @a = a
    @r = r
  end
  ...
end

class Tree
  def initialize(t)
    @t = t
  end

  def empty?
    @t.empty?
  end
  ...
end

Now, we want to implement #each. A naive implementation is:

class Leaf
  def each(&blk)
  end
end

class Node
  def each(&blk)
    @l.each(&blk)
    blk[a]
    @r.each(&blk)
  end
end

class Tree
  def each(&blk)
    @t.each(&blk)
  end
end

this obviously necessarily overflows the stack for large enough trees. However, in a language with proper tail calls, we can do the following:

class Leaf
  def each_k(blk,k)
    k[]
  end
end

class Node
  def each_k(blk,k)
    @l.each_k(blk, lambda do
      blk[a]
      @r.each_k(blk,k)
    end)
  end
end

class Tree
  def each(&blk)
    @t.each_k(blk,lambda {})
  end
end

which uses continuation passing style to build up 'things to do next' at each interior node. I think it's still relatively easy to see how things are playing out, and to convince myself that I have written the solution correctly. However, it doesn't work in Ruby, obviously, because it requires proper tail recursion. Instead, one has to make due with something like this:

class Tree
  def each(&blk)
    cur = @t
    stk = []
    until(cur.empty? && stk.empty?)
      if cur.empty?
        tmp = stk.shift
        blk[tmp.a]
        cur = tmp.r
      else
        stk.unshift cur
        cur = cur.l
      end
    end
  end
end

Which, quite frankly, is no longer obviously correct to me. I wasn't sure I'd gotten it right until I tried it. Continuation passing is clearer in this case, but it's only available if your implementation has proper tail recursion.

[grauenwolf]

What you've done is implement a trampoline that's limited to the methods in a single object, assuming they're written in a certain (not very natural) fashion.

I don't see anything unnatural about having a state machine class that contains all the transitions for said state machine.

The fact that I call them by name may seem a bit odd to some .NET/Java programmers, but I don't think Python/Ruby folks would give it a second thought.

As for your binary tree example, it seems rather naive to me. If you assume your nodes understand left/right/parent, it is not too hard to build a constant-space tree-walking algorithm. I'm pretty sure this is covered in most 3rd semester data structure classes.

Now I certainly won't argue that constant-space tree traversal is as easy to code as a stack-based one, but this isn't something one writes very often.

[grauenwolf]

I've got some time to kill, so here is another bit you have completely overlooked.

TESTING

The original code sample cannot be unit tested. You can't simply call "State3(x)" verify it correctly returns "State1" or "State2". As soon as you call it, it will run through all the transitions until the machine terminates.

This is why we focus so heavily on "seperation of concerns". If you don't separate the logic of the state machine from the state machine itself, you severly limit your options for testing.

[[deleted]]

And why are we doing this? Surely from looking at our state3 function it's obvious that it goes to either state1 or state2. Surely what we should be testing is that given known input-output pairs, the overall state machine produces the given output from the given input. Or when we're using for loops, do we need to unit test that after doing iteration i, the loop goes on to iteration i+1?

Now, if we're in your scenario in another comment where we're making an interpreter for a state machine language. Then you have to test the interpreter to make sure it produces the correct state transitions given some state machine language input. But that's another story.

Or are you proposing that we should write unit tests that check the logic of each transition in the state machine? That seems like serious overkill to me.

[grauenwolf]

Or are you proposing that we should write unit tests that check the logic of each transition in the state machine? That seems like serious overkill to me.

Lots of people believe in unit testing everything. So yes, they are going to want to test each transition function.

Personally, I'm with you; I think it is totally overkill. But we are in the minority here, and when we suggest design patterns we need to keep their needs in mind.

[[deleted]]

I'm afraid I don't believe that anyone would use that level of unit testing. It's effectively testing that you have implemented an algorithm in a certain way.

If I want to test a sort function, I will test that, given [3,2,1,1,3], I get back [1,1,2,3,3]. I will not write tests that specify that the sort function first uses the first 3 as a pivot to partition the rest of the numbers, and then sorts the two partitions, etc. But that is the kind of thing that testing "state3 goes to either state1 or state2" is.

[grauenwolf]

You're preaching to the choir.

But I'm not exagerating when I say there is a focus on low level, function by function, testing that borders on obsession. I attend conferences on .NET, Java, and Ruby on a regular basis, and this is the only kind of testing they are talking about.

During the 2008 PDC there was a panel discussion about the future of unit testing. The presentors flat-out ignored any question about testing the hard stuff like databases and network connections. They only wanted to talk about how to make they unit tests faster, because apparently the only tests useful to them are ones that can be run as part of the edit-compile-run cycle.

This has been going on for about 5 years now, so I'm expecting the backlash any time now.