Is this a taill call ?!

On Thu, Jan 06, 2011 at 09:28:58PM +0200, Alin Popa wrote:
> I have this piece of code and doesn't seems to be a tail position call
> (line 4 to be more exact):

It looks like a bug. Please open a ticket.

Also, questions like this are sooo much easier to deal with when you
supply a) code which compiles and b) code which is not disfigured with a
bunch of line numbers.

That is not a tail-recursive call.  If there isn't already a bug report on this, you should probably file one.  You should, however, include code that compiles in the report, rather than relying upon the maintainers to figure out what Element and such ought to be.  For example:

class TailOrNot {
  abstract class Element[T]
  case class ListElement[T](ts: List[Element[T]]) extends Element[T]
  case class SingleElement[T](t: T) extends Element[T]
  @annotation.tailrec private def test[T](list: List[Element[T]], acc: List[T]): List[T] = {
    list match {
      case ListElement(elements) :: tail => test(tail, test(elements, acc).reverse)
      case SingleElement(element) :: tail => test(tail, element :: acc)
      case Nil => acc.reverse
    }
  }
}

When compiled with 2.8.1, this shows recursive (not tail-recursive) call on line 55 of the bytecode of the test method when looked at with javap -c -private

  --Rex

On Thu, Jan 6, 2011 at 2:28 PM, Alin Popa <alin.popa@gmail.com> wrote:

Hey guys,
I have this piece of code and doesn't seems to be a tail position call (line 4 to be more exact):
1. @tailrec2. private def test[T](list: List[Element[T]], acc: List[T]): List[T] = { 3.    list match {4.      case ListElement(elements) :: tail => test(tail, test(elements, acc).reverse)5.      case SingleElement(element) :: tail => test(tail, element :: acc) 6.      case Nil => acc.reverse7.    }8.  }
When compiling this, everything seems fine, no exception, no warning, no nothing.It doesn't seems to be a tail call ? Or is it ?
Thanks,Alin 

i'm not really a recursion expert, but i'd say it's both :)
the inner call is not a tail call, the outer one is.

Am 06.01.2011 20:28, schrieb Alin Popa:

uK62ukhRpo-uNh1mwz8S3vY-4G22P5iGp6788 [at] mail [dot] gmail [dot] com" type="cite">Hey guys,
I have this piece of code and doesn't seems to be a tail position call (line 4 to be more exact):
1. @tailrec 2. private def test[T](list: List[Element[T]], acc: List[T]): List[T] = { 3.    list match { 4.      case ListElement(elements) :: tail => test(tail, test(elements, acc).reverse) 5.      case SingleElement(element) :: tail => test(tail, element :: acc) 6.      case Nil => acc.reverse 7.    } 8.  }
When compiling this, everything seems fine, no exception, no warning, no nothing. It doesn't seems to be a tail call ? Or is it ?
Thanks, Alin 

On Thu, Jan 06, 2011 at 02:45:05PM -0500, Rex Kerr wrote:
> That is not a tail-recursive call. If there isn't already a bug
> report on this, you should probably file one. You should, however,
> include code that compiles in the report, rather than relying upon the
> maintainers to figure out what Element and such ought to be.

No, it was perfect the way it was! Why waste your time on work the
servants could be doing?

Date: Thu, 6 Jan 2011 21:44:54 +0200
From: Alin Popa
To: Paul Phillips
Subject: Re: [scala-user] Is this a taill call ?!

Sorry, but I thought that giving you exact hints will help.

Alin

On Thu, Jan 6, 2011 at 9:44 PM, Paul Phillips wrote:

>
> On Thu, Jan 06, 2011 at 09:28:58PM +0200, Alin Popa wrote:
> > I have this piece of code and doesn't seems to be a tail position call
> > (line 4 to be more exact):
>
> It looks like a bug. Please open a ticket.
>
> Also, questions like this are sooo much easier to deal with when you
> supply a) code which compiles and b) code which is not disfigured with a
> bunch of line numbers.
>

i'd say the outer call is optimized and the inner isn't. you should be able to check that with a debugger, it's show the stack

Am 06.01.2011 20:28, schrieb Alin Popa:

uK62ukhRpo-uNh1mwz8S3vY-4G22P5iGp6788 [at] mail [dot] gmail [dot] com" type="cite">Hey guys,
I have this piece of code and doesn't seems to be a tail position call (line 4 to be more exact):
1. @tailrec 2. private def test[T](list: List[Element[T]], acc: List[T]): List[T] = { 3.    list match { 4.      case ListElement(elements) :: tail => test(tail, test(elements, acc).reverse) 5.      case SingleElement(element) :: tail => test(tail, element :: acc) 6.      case Nil => acc.reverse 7.    } 8.  }
When compiling this, everything seems fine, no exception, no warning, no nothing. It doesn't seems to be a tail call ? Or is it ?
Thanks, Alin 

On Thu, Jan 06, 2011 at 02:45:05PM -0500, Rex Kerr wrote:
> That is not a tail-recursive call.

Yeah... anyone who has been skipping around town feeling fine because
@tailrec is on the case might want to go check on the kids. See

https://lampsvn.epfl.ch/trac/scala/changeset/23941

if you care about details. You could sneak by @tailrec with a 6 char
body until now.

@annotation.tailrec final def f(x: Int): Int = f(f(x))

That's a long time to go without anyone finding this. I guess most
people don't nest multiple recursive calls in a method they mark
@tailrec because it's obviously not going to be tail recursive. I'm
glad that didn't stop everyone.

What can I say? I'm usually just happy to have the compiler confirm my own beliefs about the code by saying nothing.

On Mon, Jan 10, 2011 at 05:36, Paul Phillips <paulp@improving.org> wrote:

On Thu, Jan 06, 2011 at 02:45:05PM -0500, Rex Kerr wrote:
> That is not a tail-recursive call.

Yeah... anyone who has been skipping around town feeling fine because
@tailrec is on the case might want to go check on the kids.  See

 https://lampsvn.epfl.ch/trac/scala/changeset/23941

if you care about details.  You could sneak by @tailrec with a 6 char
body until now.

 @annotation.tailrec final def f(x: Int): Int = f(f(x))

That's a long time to go without anyone finding this.  I guess most
people don't nest multiple recursive calls in a method they mark
@tailrec because it's obviously not going to be tail recursive.  I'm
glad that didn't stop everyone.

--
Paul Phillips      | Every election is a sort of advance auction sale
In Theory          | of stolen goods.
Empiricist         |     -- H. L. Mencken
pull his pi pal!   |----------* http://www.improving.org/paulp/ *----------

--
Daniel C. Sobral

I travel to the future all the time.

On 2011-01-10, Paul Phillips wrote:
> That's a long time to go without anyone finding this. I guess most
> people don't nest multiple recursive calls in a method they mark
> @tailrec because it's obviously not going to be tail recursive. I'm
> glad that didn't stop everyone.

Surely the point of @tailrec is to flag calls that look like they
should be tail-recursive but aren't because the method isn't
final/private/etc., not to flag any random self-call? That inner call
to f doesn't doesn't look like it's in tail position, so I would be
surprised if @tailrec would complain about it. It's not unusual to,
for example, want TCO to be assured on the second branch of a binary
tree walk. Or as a more concrete example, taken from some real code I
have at work which creates nodes in Apache Zookeeper:

@tailrec
private def createNode(path: String) {
zk.create(path) match {
case NoPath =>
createNode(path.substring(0, path.lastIndexOf('/')))
createNode(path)
case .. bunch of irrelevant other cases, some of which also loop..
}
}

Going back to the original bug report / feature request in trac, it
also seems to have been written under the assumption that the
annotation would only flag calls that are in tail position but can't
be optimized:

Originally posted by dragos in issue #343434:
> A warning should be generated for tail recursive methods that can't
> be optimized.

On Mon, Jan 10, 2011 at 09:54:21PM +0000, Robert Macomber wrote:
> Surely the point of @tailrec is to flag calls that look like they
> should be tail-recursive but aren't because the method isn't
> final/private/etc., not to flag any random self-call?

It had not occurred to me that anyone would expect such a thing. Does
this imply you were aware before recently that the compiler might
optimize only a subset of the recursive calls?

I don't contest the legitimacy of what you want, but I would speculate
(and maybe this is just me projecting my subpar intellect) that there
are a lot more people who need an absolute, no two ways about it, this
can run in constant space forever (or it can't) answer from the compiler
than there are people who would ever use @tailrec with the expectation
that the compiler will remain mum about "obvious" not-tail-calls.

There was another guy who took the position that the compiler should
warn about EVERY recursive call which isn't a tail call. For now, I
guess you will find too many warnings and he will find too few. Of
course we can start throwing options at it, but there are hundreds of
tickets open so it's not all that high on my list.

On 2011-01-11, Paul Phillips wrote:
> On Mon, Jan 10, 2011 at 09:54:21PM +0000, Robert Macomber wrote:
>> Surely the point of @tailrec is to flag calls that look like they
>> should be tail-recursive but aren't because the method isn't
>> final/private/etc., not to flag any random self-call?
>
> It had not occurred to me that anyone would expect such a thing. Does
> this imply you were aware before recently that the compiler might
> optimize only a subset of the recursive calls?

Absolutely. I always took @tailrec as "warn me if I've forgotten that
some methods can be overridden by subclasses".

> For now, I guess you will find too many warnings and he will find
> too few.

Possibly -- though I can always remove the annotation to silence the
warning when 23941 arrives in release, since it'll get optimized the
way I expect whether or not I ask for the check on it.

If only the JVM would grow a tailcall opcode!

I don't contest the legitimacy of what you want, but I would speculate
(and maybe this is just me projecting my subpar intellect) that there
are a lot more people who need an absolute, no two ways about it, this
can run in constant space forever (or it can't) answer from the compiler
than there are people who would ever use @tailrec with the expectation
that the compiler will remain mum about "obvious" not-tail-calls.

Assuming I've parsed that sentence correctly, I would agree. Personally, I would be extremely surprised if @tailrec thought I knew all about the "obvious" not-tail-calls. Aside from the fact that machines can check this sort of thing a lot better than humans can (even the so-called "subpar" ones like paulp), it could be very easy to write something that was once "obviously" tail-recursive and mistakenly modify things so that it should be "obvious" it is no longer such.
Donna

On Tue, Jan 11, 2011 at 10:46 PM, Donna Malayeri <lindydonna@gmail.com> wrote:

I don't contest the legitimacy of what you want, but I would speculate
(and maybe this is just me projecting my subpar intellect) that there
are a lot more people who need an absolute, no two ways about it, this
can run in constant space forever (or it can't) answer from the compiler
than there are people who would ever use @tailrec with the expectation
that the compiler will remain mum about "obvious" not-tail-calls.

Assuming I've parsed that sentence correctly, I would agree. Personally, I would be extremely surprised if @tailrec thought I knew all about the "obvious" not-tail-calls. Aside from the fact that machines can check this sort of thing a lot better than humans can (even the so-called "subpar" ones like paulp), it could be very easy to write something that was once "obviously" tail-recursive and mistakenly modify things so that it should be "obvious" it is no longer such.
Donna

Given the *name* of the annotation, I would expect it to only flag tail recursions -- those recursive calls in a method whose return value is the return value of the method -- that cannot be implemented as iterations. I would consider it  a bug if any other recursive call were flagged. If the intent is to flag any instance of recursive flag growth -- which quite different from *tail* recursion -- then it ought to be named differently. Wasn't the whole point of this annotation the fact that the tail recursion guarantee of languages like Scheme and Haskell cannot be made by Scala because the JVM doesn't provide the required support? Turning this into a more generalized "don't grow the stack" check (which it can't really be because of mutual recursion) is feeping creaturism.

On Mon, Jan 10, 2011 at 10:09 PM, Paul Phillips <paulp@improving.org> wrote:

On Mon, Jan 10, 2011 at 09:54:21PM +0000, Robert Macomber wrote:
> Surely the point of @tailrec is to flag calls that look like they
> should be tail-recursive but aren't because the method isn't
> final/private/etc., not to flag any random self-call?

It had not occurred to me that anyone would expect such a thing.  Does
this imply you were aware before recently that the compiler might
optimize only a subset of the recursive calls?

I don't contest the legitimacy of what you want, but I would speculate
(and maybe this is just me projecting my subpar intellect) that there
are a lot more people who need an absolute, no two ways about it, this
can run in constant space forever (or it can't) answer from the compiler
than there are people who would ever use @tailrec with the expectation
that the compiler will remain mum about "obvious" not-tail-calls.

There was another guy who took the position that the compiler should
warn about EVERY recursive call which isn't a tail call.  For now, I
guess you will find too many warnings and he will find too few.  Of
course we can start throwing options at it, but there are hundreds of
tickets open so it's not all that high on my list

That would be a good reason *not* to file a ticket for this -- it appears to be working correctly, flagging only *tail recursive* calls that can't be optimized, not other recursive calls. Since the compiler was able to do the tail recursive optimizations on the example code, I'm at a loss as to why this should be considered a bug. The OP seems to want the compiler to tell him something he already knows, while breaking useful functionality -- e.g., binary traversals, such as quicksort, that contain both tail and non-tail recursions, would with this "fix" always get a warning with the annotation, whereas what we want is only to be warned if the second -- tail-recursive -- call can't be optimized.

On Thu, Jan 6, 2011 at 11:28 AM, Alin Popa <alin.popa@gmail.com> wrote:

Hey guys,
I have this piece of code and doesn't seems to be a tail position call (line 4 to be more exact):
1. @tailrec2. private def test[T](list: List[Element[T]], acc: List[T]): List[T] = { 3.    list match {4.      case ListElement(elements) :: tail => test(tail, test(elements, acc).reverse)5.      case SingleElement(element) :: tail => test(tail, element :: acc) 6.      case Nil => acc.reverse7.    }8.  }
When compiling this, everything seems fine, no exception, no warning, no nothing.It doesn't seems to be a tail call ? Or is it ?
Thanks,Alin 

There are two tail recursive calls and one non-tail recursive call, and the compiler did what it was supposed to do -- it optimized the two tail recursive calls. That's what @tailrec is for -- to tell you if the compiler was not able to do that optimization. It is not for telling you that your method contains non-tail recursive calls, which you can determine by inspection. So there's no bug here.
Consider this passage from Structure and Interpretation of Computer Programs:

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.

You see, "tail recursion" refers to an *iterative implementation* of an in-principle iterative process expressed as a recursion. Abelson and Sussman refer to the failure of the compiler to implement such recursive expressions of iterations *as* iterations as a "defect". The point of @tailrec is to identify instances of this defect in the implementation, not to tell you something that you can plainly see -- that you passed the value of a recursive call to another method rather than directly returning it, so it is not in-principle iterative.

Well, now I'm thoroughly confused. :)  This page on stackoverflow (http://stackoverflow.com/questions/3114142/what-is-the-scala-annotation-to-ensure-a-tail-recursive-function-is-optimized) seems to imply that people are expecting different behavior than what Jim is saying here. 
At any rate, perhaps someone (and that someone can be me!) could better document what @tailrec does and does not do.

Donna

On Wed, Jan 12, 2011 at 10:32 AM, Jim Balter <Jim@balter.name> wrote:

On Mon, Jan 10, 2011 at 10:09 PM, Paul Phillips <paulp@improving.org> wrote:

I don't contest the legitimacy of what you want, but I would speculate (and maybe this is just me projecting my subpar intellect) that there
are a lot more people who need an absolute, no two ways about it, this
can run in constant space forever (or it can't) answer from the compiler
than there are people who would ever use @tailrec with the expectation
that the compiler will remain mum about "obvious" not-tail-calls.

That would be a good reason *not* to file a ticket for this -- it appears to be working correctly, flagging only *tail recursive* calls that can't be optimized, not other recursive calls. Since the compiler was able to do the tail recursive optimizations on the example code, I'm at a loss as to why this should be considered a bug. The OP seems to want the compiler to tell him something he already knows, while breaking useful functionality -- e.g., binary traversals, such as quicksort, that contain both tail and non-tail recursions, would with this "fix" always get a warning with the annotation, whereas what we want is only to be warned if the second -- tail-recursive -- call can't be optimized.

I include a specific section about @tailrec in my book.  I think better documentation needs to exist, as people seem to think it works similarly to 'inline' in C++.

On Wed, Jan 12, 2011 at 8:53 AM, Donna Malayeri <lindydonna@gmail.com> wrote:

Well, now I'm thoroughly confused. :)  This page on stackoverflow (http://stackoverflow.com/questions/3114142/what-is-the-scala-annotation-to-ensure-a-tail-recursive-function-is-optimized) seems to imply that people are expecting different behavior than what Jim is saying here. 
At any rate, perhaps someone (and that someone can be me!) could better document what @tailrec does and does not do.

Donna

On Wed, Jan 12, 2011 at 10:32 AM, Jim Balter <Jim@balter.name> wrote:

On Mon, Jan 10, 2011 at 10:09 PM, Paul Phillips <paulp@improving.org> wrote:

I don't contest the legitimacy of what you want, but I would speculate (and maybe this is just me projecting my subpar intellect) that there
are a lot more people who need an absolute, no two ways about it, this
can run in constant space forever (or it can't) answer from the compiler
than there are people who would ever use @tailrec with the expectation
that the compiler will remain mum about "obvious" not-tail-calls.

That would be a good reason *not* to file a ticket for this -- it appears to be working correctly, flagging only *tail recursive* calls that can't be optimized, not other recursive calls. Since the compiler was able to do the tail recursive optimizations on the example code, I'm at a loss as to why this should be considered a bug. The OP seems to want the compiler to tell him something he already knows, while breaking useful functionality -- e.g., binary traversals, such as quicksort, that contain both tail and non-tail recursions, would with this "fix" always get a warning with the annotation, whereas what we want is only to be warned if the second -- tail-recursive -- call can't be optimized.

The thing is that it is obvious that it's not a tail position (the initial example), and indeed, it's very hard to do something like that and not realize that no optimization will be done; but I said to myself "what will happen if I'll call again the 'test' method inside of itself (test(test...))" and I expected to have a compilation error (that's because was so obvious), but it didn't. So, I thought that Scala can do some tricks under the hood in order to optimize such a method call.To me, seems very clear that @tailrec annotation will say if the compiler can guarantee or not the optimization (I would expect to say nothing if everything is fine).
Bottom line, I wanted to be sure that I'm not missing something in that @tailrec usage, and didn't want to create one more "What is @tailrec ?" topic.
Alin

On Wed, Jan 12, 2011 at 5:24 PM, Josh Suereth <joshua.suereth@gmail.com> wrote:

I include a specific section about @tailrec in my book.  I think better documentation needs to exist, as people seem to think it works similarly to 'inline' in C++.

On Wed, Jan 12, 2011 at 8:53 AM, Donna Malayeri <lindydonna@gmail.com> wrote:

Well, now I'm thoroughly confused. :)  This page on stackoverflow (http://stackoverflow.com/questions/3114142/what-is-the-scala-annotation-to-ensure-a-tail-recursive-function-is-optimized) seems to imply that people are expecting different behavior than what Jim is saying here. 
At any rate, perhaps someone (and that someone can be me!) could better document what @tailrec does and does not do.

Donna

On Wed, Jan 12, 2011 at 10:32 AM, Jim Balter <Jim@balter.name> wrote:

On Mon, Jan 10, 2011 at 10:09 PM, Paul Phillips <paulp@improving.org> wrote:

I don't contest the legitimacy of what you want, but I would speculate (and maybe this is just me projecting my subpar intellect) that there
are a lot more people who need an absolute, no two ways about it, this
can run in constant space forever (or it can't) answer from the compiler
than there are people who would ever use @tailrec with the expectation
that the compiler will remain mum about "obvious" not-tail-calls.

That would be a good reason *not* to file a ticket for this -- it appears to be working correctly, flagging only *tail recursive* calls that can't be optimized, not other recursive calls. Since the compiler was able to do the tail recursive optimizations on the example code, I'm at a loss as to why this should be considered a bug. The OP seems to want the compiler to tell him something he already knows, while breaking useful functionality -- e.g., binary traversals, such as quicksort, that contain both tail and non-tail recursions, would with this "fix" always get a warning with the annotation, whereas what we want is only to be warned if the second -- tail-recursive -- call can't be optimized.

On Wed, Jan 12, 2011 at 5:04 AM, Jim Balter <Jim@balter.name> wrote:

On Thu, Jan 6, 2011 at 11:28 AM, Alin Popa <alin.popa@gmail.com> wrote:

Hey guys,
I have this piece of code and doesn't seems to be a tail position call (line 4 to be more exact):
1. @tailrec2. private def test[T](list: List[Element[T]], acc: List[T]): List[T] = { 3.    list match {4.      case ListElement(elements) :: tail => test(tail, test(elements, acc).reverse)5.      case SingleElement(element) :: tail => test(tail, element :: acc) 6.      case Nil => acc.reverse7.    }8.  }
When compiling this, everything seems fine, no exception, no warning, no nothing.It doesn't seems to be a tail call ? Or is it ?
Thanks,Alin 

There are two tail recursive calls and one non-tail recursive call, and the compiler did what it was supposed to do -- it optimized the two tail recursive calls. That's what @tailrec is for -- to tell you if the compiler was not able to do that optimization. It is not for telling you that your method contains non-tail recursive calls, which you can determine by inspection. So there's no bug here.

You can determine by inspection whether or not your types are correct, so why do we annotate anything with types?  Furthermore, you can determine by inspect whether your code is correct, so why have unit tests?

Because, of course, people make mistakes.  In particular, people make mistakes when figuring out whether something is called in a fashion that could conceivably be converted to tail-recursive form.  Note that an inner call to f(f(x,a),b) is not necessarily _in principle_ not convertable to tail recursive form since there is a chance that if you do loop unrolling (well, recursion unrolling) first, the the call would end up with only traditional tail recursion.  So it makes much more sense for the compiler to not assume that you and it are working off the same precise assumptions about what is a candidate for tail-recursion conversion and what is not.  It can't read your mind about whether you (rightly or wrongly) believe a recursive call can be made tail-recursive.  Instead, if _any_ recursive call in the function _cannot_ be made tail-recursive, then it should let you know.

  --Rex

On Wed, Jan 12, 2011 at 11:26:05AM -0500, Rex Kerr wrote:
> So it makes much more sense for the compiler to not assume that you
> and it are working off the same precise assumptions about what is a
> candidate for tail-recursion conversion and what is not. It can't
> read your mind about whether you (rightly or wrongly) believe a
> recursive call can be made tail-recursive. Instead, if _any_
> recursive call in the function _cannot_ be made tail-recursive, then
> it should let you know.

I endorse the above. In regards to what was intended, I feel qualified
to speculate (although I can't speak with the authority of some others
in this thread) if only because I wrote it. It was intended to require
them all. That it didn't was a bug. The bug is fixed. Fin.

The community thanks you once again.

On 12 Jan 2011 18:29, "Paul Phillips" <paulp@improving.org> wrote:

On Wed, Jan 12, 2011 at 11:26:05AM -0500, Rex Kerr wrote:
> So it makes much more sense for the comp...

I endorse the above.  In regards to what was intended, I feel qualified
to speculate (although I can't speak with the authority of some others
in this thread) if only because I wrote it.  It was intended to require
them all.  That it didn't was a bug.  The bug is fixed.  Fin.

--
Paul Phillips      | We act as though comfort and luxury were the chief
Analgesic          | requirements of life, when all that we need to make us
Empiricist         | really happy is something to be enthusiastic about.
ha! spill, pupil   |     -- Charles Kingsley

Some facts: the original enhancement request was

"Right now there is no way to know if a method has been tail call optimized without inspecting compiler output (either printing trees after a certain phase, or looking at bytecode). A warning should be generated for tail recursive methods that can't be optimized. This is most likely what the user wants, and because the method was not final.... An method with [either] annotation will trigger a warning if a tail recursive call can't be optimized."

It's important to understand what the request is referring to. Tail-position calls (or "tail calls") are those calls, and *only* those calls, where the value of the called method is used directly as the value of the calling method (see http://en.wikipedia.org/wiki/Tail_call). These are unambiguously discernible just by looking at the syntax -- quite unlike either type correctness (which is *always* enforced except for casts, not only when there's an optional annotation) or tail call elimination. The request was certainly not "if _any_ recursive call in the function _cannot_ be made tail-recursive, then it should let you know" -- which really doesn't make sense; functions are tail-recursive if they make recursive tail-position calls. The request is to be told if tail recursion can't be *eliminated* through a transformation to iteration.

The motivation here, of course, is the well-known fact that the JVM lacks the functionality to *generally* implement tail recursion as looping, so the Scala compiler "manually" does this in highly restricted cases: self calls known to be such at compile time -- so, no overriding (a side issue is that in some languages, calls to non-protected methods wisely default to the current class). *If* the JVM had a "jump to method" opcode, then Scala could use that for *all* tail calls, not just recursive ones. In the case of recursion, tail calls would produce iteration, even if it's mutual recursion or the method being called depends on the dynamic type. If the JVM had such an opcode, there would be no cases where tail calls would not be optimized, and no motivation for @tailrec.

Consider the use cases for @tailrec as requested and for @tailrec as you have now implemented it. As requested, one can usefully apply it to methods that contain recursive calls in non-tail positions as well as tail positions: e.g., binary tree traversals, or the OP's example; only failures to optimize recursive calls in tail positions would produce warnings, and one could eliminate the warnings by using iteration. The recursive calls in non-tail positions would be left alone (and no warnings would be produced), because they are generally not rewritable to eliminate recursion (except by implementing one's own stack). In the version as you have implemented it, you could add a @tailrec annotation to a method to get the compiler to tell you that you have non-tail position recursive calls -- but that's something that you can see by looking at the code, so there's no need to add an annotation in that case. If you do add the annotation and get the warning, you can't generally eliminate the recursion, so the only thing to do is remove the annotation. It's not much of a feature to be able to be told that your method grows stack space when you can see that and can't really do anything about it. OTOH, a feature that tells you that methods that need not grow stack space and wouldn't grow stack space if run on a platform that supported tail calls as jumps is quite valuable, and that's what was requested.

But hey, you hold the keys to the kingdom because you're the implementer and @tailrec isn't described in the SLS (AFAIK; I haven't looked at the latest version),  and I guess you're free to implement whatever enhancement you see fit. It would be nice, though, if there were some unambiguous documentation somewhere that told people what *exactly* @tailrec does or doesn't do -- something that "speaks with authority". In far too many cases, discussion on these mailing lists has supplanted the role of accurate documentation, with the authority being whatever the implementers say it does. As Scala grows, this will become less and less acceptable. Or inversely, this will limit Scala's growth.

BTW, I found Rex's comments about loop unrolling and "recursion unrolling" fascinating. Somehow I was under the impression that loop unrolling reduces the number of branches but does not (unless the loop count is constant) eliminate them. Likewise I thought that "recursion unrolling", imagining that anyone has implemented such a thing (partial recursive inlining of recursive functions) can reduce the amount of recursion (the max stack depth), but it cannot eliminate it. I was under the impression that tail recursion being implementable as iteration is analogous to the fact that one can write an iterative regular expression "a*" to recognize the recursively defined language l := 'a' l | <empty>, whereas saying that non-tail recursion can be implemented as iteration is analogous to there being a regular expression that recognizes the language l: = '(' l ')' | <empty>, which, I thought, was provably not possible. But no doubt Rex speaks with some authority on these matters.

-- Jim


On Wed, Jan 12, 2011 at 9:28 AM, Paul Phillips <paulp@improving.org> wrote:

On Wed, Jan 12, 2011 at 11:26:05AM -0500, Rex Kerr wrote:
> So it makes much more sense for the compiler to not assume that you
> and it are working off the same precise assumptions about what is a
> candidate for tail-recursion conversion and what is not.  It can't
> read your mind about whether you (rightly or wrongly) believe a
> recursive call can be made tail-recursive.  Instead, if _any_
> recursive call in the function _cannot_ be made tail-recursive, then
> it should let you know.

I endorse the above.  In regards to what was intended, I feel qualified
to speculate (although I can't speak with the authority of some others
in this thread) if only because I wrote it.  It was intended to require
them all.  That it didn't was a bug.  The bug is fixed.  Fin.

--
Paul Phillips      | We act as though comfort and luxury were the chief
Analgesic          | requirements of life, when all that we need to make us
Empiricist         | really happy is something to be enthusiastic about.
ha! spill, pupil   |     -- Charles Kingsley

Jim, 
Regardless of what the original enhancement request was, a decision was made by the implementors of the annotation and the associated compiler passes to give what you consider spurious warnings. We could debate issue this ad infinitum, but the discussion here is not "what should @tailrec do" but rather "what does @tailrec do."  I think everyone on this thread agrees that @tailrec is insufficiently documented. I have volunteered to add the documentation to the scaladoc, and probably also the SLS. Note that the scaladoc for @tailrec is far more useful than the spec, as most people don't read the spec when determining what an annotation does. 
The problem is not that mailing lists have supplanted the authority of documentation, but rather that documentation is lacking in some places, and so people who have played with things can tell you how things work. This is something everyone has been aware of for quite some time, but resources are scarce. If you would like to help by submitting patches for the documentation (or wait until the collaborative scaladoc app is up), that would certainly be much appreciated.
Additionally, if you would like to provide an implementation for an additional annotation that only gives the warnings you would like, the Scala team would be very happy to review the patch and consider its inclusion.
Donna

On Thu, Jan 13, 2011 at 6:32 PM, Jim Balter <Jim@balter.name> wrote:

<snip>
But hey, you hold the keys to the kingdom because you're the implementer and @tailrec isn't described in the SLS (AFAIK; I haven't looked at the latest version),  and I guess you're free to implement whatever enhancement you see fit. It would be nice, though, if there were some unambiguous documentation somewhere that told people what *exactly* @tailrec does or doesn't do -- something that "speaks with authority". In far too many cases, discussion on these mailing lists has supplanted the role of accurate documentation, with the authority being whatever the implementers say it does. As Scala grows, this will become less and less acceptable. Or inversely, this will limit Scala's growth.

On Thu, Jan 13, 2011 at 10:07 AM, Donna Malayeri <lindydonna@gmail.com> wrote:

Jim, 
Regardless of what the original enhancement request was, a decision was made by the implementors of the annotation and the associated compiler passes to give what you consider spurious warnings. We could debate issue this ad infinitum, but the discussion here is not "what should @tailrec do" but rather "what does @tailrec do."

That is, frankly, absurd. In any case, it doesn't address any of the substance of my post.

In such a case, perhaps the discussion should be moved to scala-debate.

Donna

On Thu, Jan 13, 2011 at 7:50 PM, Jim Balter <Jim@balter.name> wrote:
 

That is, frankly, absurd. In any case, it doesn't address any of the substance of my post.

On Thu, Jan 13, 2011 at 12:32 PM, Jim Balter <Jim@balter.name> wrote:

BTW, I found Rex's comments about loop unrolling and "recursion unrolling" fascinating. Somehow I was under the impression that loop unrolling reduces the number of branches but does not (unless the loop count is constant) eliminate them. Likewise I thought that "recursion unrolling", imagining that anyone has implemented such a thing (partial recursive inlining of recursive functions) can reduce the amount of recursion (the max stack depth), but it cannot eliminate it.

Depends on the details:

final inline def tailed(x: Int): Int = {
  if (x < 0) x*x + x*x*x*x
  else if (x < 100) taily(x*x + x*x*x*x)
  else taily(x*x)
}

final inline def tailless(x: Int): Int = {
  if (x < 0) x*x + x*x*x*x
  else if (x < 100) taily(taily(-x))
  else taily(x*x)
}

I would want my compiler to at least have the option of optimizing the second to the first.  And it had better not yell at me about it not being tail recursion, because it is after the optimization.  It should only yell if it doesn't (or can't) do the optimization.

  --Rex

I didnt't follow this thread. Sorry if it was discussed before:

Why don't we put the annotation on the call site?

def halftail(x: Int): Int = {
if (x < 0) x*x + x*x*x*x
else if (x < 100) 3 * (halftail(-x))
else @tailrec halftail(x*x)
}

Daniel

On Thu, Jan 13, 2011 at 9:37 PM, Rex Kerr wrote:
> On Thu, Jan 13, 2011 at 12:32 PM, Jim Balter wrote:
>>
>> BTW, I found Rex's comments about loop unrolling and "recursion unrolling"
>> fascinating. Somehow I was under the impression that loop unrolling reduces
>> the number of branches but does not (unless the loop count is constant)
>> eliminate them. Likewise I thought that "recursion unrolling", imagining
>> that anyone has implemented such a thing (partial recursive inlining of
>> recursive functions) can reduce the amount of recursion (the max stack
>> depth), but it cannot eliminate it.
>
> Depends on the details:
>
> final inline def tailed(x: Int): Int = {
>   if (x < 0) x*x + x*x*x*x
>   else if (x < 100) taily(x*x + x*x*x*x)
>   else taily(x*x)
> }
>
> final inline def tailless(x: Int): Int = {
>   if (x < 0) x*x + x*x*x*x
>   else if (x < 100) taily(taily(-x))
>   else taily(x*x)
> }
>
> I would want my compiler to at least have the option of optimizing the
> second to the first.  And it had better not yell at me about it not being
> tail recursion, because it is after the optimization.  It should only yell
> if it doesn't (or can't) do the optimization.
>
>   --Rex
>

On Thu, Jan 13, 2011 at 12:47 PM, Daniel Kröni <daniel.kroeni@gmail.com> wrote:

I didnt't follow this thread. Sorry if it was discussed before:

Why don't we put the annotation on the call site?

def halftail(x: Int): Int = {
 if (x < 0) x*x + x*x*x*x
 else if (x < 100) 3 * (halftail(-x))
 else @tailrec halftail(x*x)
}

That would be sensible, although it might have to be (halftail: @tailrec)(x*x)

 

Daniel

On Thu, Jan 13, 2011 at 9:37 PM, Rex Kerr <ichoran@gmail.com> wrote:
> On Thu, Jan 13, 2011 at 12:32 PM, Jim Balter <Jim@balter.name> wrote:
>>
>> BTW, I found Rex's comments about loop unrolling and "recursion unrolling"
>> fascinating. Somehow I was under the impression that loop unrolling reduces
>> the number of branches but does not (unless the loop count is constant)
>> eliminate them. Likewise I thought that "recursion unrolling", imagining
>> that anyone has implemented such a thing (partial recursive inlining of
>> recursive functions) can reduce the amount of recursion (the max stack
>> depth), but it cannot eliminate it.
>
> Depends on the details:
>
> final inline def tailed(x: Int): Int = {
>   if (x < 0) x*x + x*x*x*x
>   else if (x < 100) taily(x*x + x*x*x*x)
>   else taily(x*x)
> }
>
> final inline def tailless(x: Int): Int = {
>   if (x < 0) x*x + x*x*x*x
>   else if (x < 100) taily(taily(-x))
>   else taily(x*x)
> }
>
> I would want my compiler to at least have the option of optimizing the
> second to the first.  And it had better not yell at me about it not being
> tail recursion, because it is after the optimization.  It should only yell
> if it doesn't (or can't) do the optimization.

An easier way to avoid getting yelled at than such silly point-missing contrived examples is to only generate the warning for tail-position calls.

On Tue, Jan 11, 2011 at 04:28, Robert Macomber <xbz126@rojoma.com> wrote:

On 2011-01-11, Paul Phillips <paulp@improving.org> wrote:
> On Mon, Jan 10, 2011 at 09:54:21PM +0000, Robert Macomber wrote:
>> Surely the point of @tailrec is to flag calls that look like they
>> should be tail-recursive but aren't because the method isn't
>> final/private/etc., not to flag any random self-call?
>
> It had not occurred to me that anyone would expect such a thing.  Does
> this imply you were aware before recently that the compiler might
> optimize only a subset of the recursive calls?

Absolutely.  I always took @tailrec as "warn me if I've forgotten that
some methods can be overridden by subclasses".

So you have to remember to use an annotation to warn you if you forgot to use a qualifier? That doesn't seem like a particularly useful thing to me.

It's useful because the only reason the qualifier is needed to get tail recursion is because/if the implementation has hobbled support for tail recursion (and because the language lacks the ability to call methods of the current class, even if overridden). Once the JVM supports tail recursion (it is now known how to do this consistent with its security model), we won't need the final qualifier and this should all become moot.
 

On Fri, Jan 14, 2011 at 2:50 AM, Daniel Sobral <dcsobral@gmail.com> wrote:

On Tue, Jan 11, 2011 at 04:28, Robert Macomber <xbz126@rojoma.com> wrote:

On 2011-01-11, Paul Phillips <paulp@improving.org> wrote:
> On Mon, Jan 10, 2011 at 09:54:21PM +0000, Robert Macomber wrote:
>> Surely the point of @tailrec is to flag calls that look like they
>> should be tail-recursive but aren't because the method isn't
>> final/private/etc., not to flag any random self-call?
>
> It had not occurred to me that anyone would expect such a thing.  Does
> this imply you were aware before recently that the compiler might
> optimize only a subset of the recursive calls?

Absolutely.  I always took @tailrec as "warn me if I've forgotten that
some methods can be overridden by subclasses".

So you have to remember to use an annotation to warn you if you forgot to use a qualifier? That doesn't seem like a particularly useful thing to me.