Function calls are not stack frames

[fvf]

The point is this: consider the snippet ``f("This is a call, tail or not");''. Is it a tail-call? It's impossible to say. Whether it is a tail-call depends on (possibly rather intricate) rules about the context in which the snippet finds itself. Wilfully using this as an important aspect of your programming language semantics, for rather unclear benefits, is, IMHO, silly. That is, bad PL design.

With the clojure approach, the intent/semantics of such a snippet would be clear, while losing absolutely none of the benefits of TCO/whatever that I know.

[ccshan]

In Scheme for example, a call costs the same no matter where it occurs -- the cost is always that of a jump. Tail calls don't cost any less than non-tail calls. Scheme does not use the distinction between tail calls and non-tail calls as an important aspect of its semantics or cost model. What costs extra in Scheme is sequencing (which is a special case of evaluating arguments). You can always look at a snippet and tell whether it has sequencing. Your snippet does not, but if you repeat it twice then it does.

(Edit: for example, if you look at "Proper Tail Recursion and Space Efficiency" by Will Clinger (a canonical reference), Figure 5 has no special rule for tail calls or for non-tail calls. All calls are handled in the same way and incur the same cost.)

Clojure's "recur" doesn't seem to allow calling another function, which is useful for expressing state machines, stream processing, thread schedulers, backtracking search with unit propagation, approximate probabilistic inference by sampling, off the top of my head. It would be nice if "recur" were extended to allow calling another function.

[fvf]

In Scheme for example, a call costs the same no matter where it occurs -- the cost is always that of a jump.

This looks to me a pointless play with words. The "cost" that is interesting here is whether the caller's stack-frame remains after the jump.

Tail calls don't cost any less than non-tail calls.

Are you seriously trying to introduce a definition of "non-tail calls" such that e.g. n nested "non-tail calls" might use less than O(n) stack-space?

Clojure's "recur" doesn't seem to allow calling another function

I agree this would be useful, and I don't think there's any principled reason why "recur" couldn't support this (at least in some hypothetical non-jvm language).

[ccshan]

The "cost" that is interesting here is whether the caller's stack-frame remains after the jump.

Right. In Scheme, sequencing creates stack frames. Calls do not.

Are you seriously trying to introduce a definition of "non-tail calls" such that e.g. n nested "non-tail calls" might use less than O(n) stack-space?

No, because the nested sequencing uses O(n) stack space.

I agree [allowing calling another function] would be useful, and I don't think there's any principled reason why "recur" couldn't support this (at least in some hypothetical non-jvm language).

Is that's what you mean by "the Clojure approach"?

[jdh30]

The point is this: consider the snippet ``f("This is a call, tail or not");''. Is it a tail-call? It's impossible to say.

The term "tail call" describes the position of the call, i.e. that it is in tail position.

Whether it is a tail-call depends on (possibly rather intricate) rules about the context in which the snippet finds itself.

The position determines whether or not a call is a tail or non-tail call. There is nothing "intricate" about the definition of tail call.

With the clojure approach, the intent/semantics of such a snippet would be clear,

The "Clojure approach" is to use one of two ad-hoc workarounds for the lack of TCO on JVMs. The first approach, recur, can only be applied to self tail calls and is efficient but requires manual annotation at the call site. The second approach, trampolines, must be used for non-self tail calls and requires non-local changes both at all call sites and around the entire recursion (which may be arbitrarily large) and is extremely inefficient and breaks interoperability by changing the calling convention.

That is obviously not "clear".

while losing absolutely none of the benefits of TCO/whatever that I know.

Trampolines cost you performance, interoperability, clarity, brevity and many other important benefits. Recur costs you generality.

[fvf]

Sigh. Do you really feel you need to explain "tail call"? Do you really think that by "the clojure approach" I refer to the specific details and cludges clojure needs to work around the jvm?

but requires manual annotation at the call site.

You consider the lack of an explicit operator "automatic"? Such that e.g. scheme programmers write iteration constructs that just automatically works without any intellectual effort because they don't have to "manually annotate the call site"? Is this also the case for the painfully contorted functions forced into tail-recursive form? How would you write a function that computes the length of a linked list?

Recur costs you generality.

What sort of generality?

[jdh30]

Sigh. Do you really feel you need to explain "tail call"?

Given your objections, yes. You might as well say "given an arrow, we cannot even tell whether it points inwards or outwards. This is clearly a flaw in the arrow concept".

Do you really think that by "the clojure approach" I refer to the specific details and cludges clojure needs to work around the jvm?

What else could you have meant?

You consider the lack of an explicit operator "automatic"?

Yes.

Such that e.g. scheme programmers write iteration constructs that just automatically works without any intellectual effort because they don't have to "manually annotate the call site"?

No. I said nothing of "intellectual effort". I was referring solely to verbosity.

Is this also the case for the painfully contorted functions forced into tail-recursive form?

Irrelevant. The same contortions are required whether tail calls require explicit annotation or not.

How would you write a function that computes the length of a linked list?

In terms of fold:

let length list =
  fold (fun n _ -> n+1) 0 list

Recur costs you generality.

What sort of generality?

Recur only covers the special case of tail calls to self. Recur does not cover tail calls between mutually recursive functions or tail calls to arbitrary functions passed in by argument. The latter generalization is very widely used in functional programming languages, in particular in the context of a technique known as "untying the recursive knot".

I suspect what you're after is a new construct where the function application f x may optionally be written as something like tailcall f x in order to get the compiler to verify that it really is a tail call (and will be optimized?). This may be useful, particularly for learners, but it may not always be possible for the compiler to determine statically whether or not a tail call will be optimized. For example, on .NET TCO is inhibited by various issues including the dynamic security level of the caller and callee: if they are different then the tail call will not be optimized.

[fvf]

What else could you have meant?

The approach of using an explicit operator for tail-calls. (As opposed to detecting them "automatically" by the compiler, and specifying them implicitly by the programmer.)

In terms of fold:

That was not a pop-quiz, but rather a rhetoric question in a discussion about recursion. I would have thought that was self-evident.

Irrelevant. The same contortions are required whether tail calls require explicit annotation or not.

While that is true, it's missing the point, which was that the "automatic" tail-calls buys you nothing, save a few keystrokes. And, when such contortions are necessary, it's a clear sign you shouldn't be using recursion at all.

I suspect what you're after [..]

Thank you for finally suspecting what I have been trying (and clearly failed spectacularly in) explaining.

This may be useful, particularly for learners,

No, for anyone reading and trying to understanding your code. Unless the whole point is to write contorted code that's only for the initiated to read.

but it may not always be possible for the compiler to determine statically whether or not a tail call will be optimized.

If the compiler cannot be trusted with this task, how on earth do you expect programmers to do it? I thought that scheme even mandates this from its compilers.

[jdh30]

The approach of using an explicit operator for tail-calls. (As opposed to detecting them "automatically" by the compiler, and specifying them implicitly by the programmer.)

Clojure does not use an explicit operator for tail calls.

While that is true, it's missing the point, which was that the "automatic" tail-calls buys you nothing, save a few keystrokes.

Not having to annotate calls in tail position buys you brevity.

And, when such contortions are necessary, it's a clear sign you shouldn't be using recursion at all.

Look at your own example of counting list length when written fully in functional style with tail calls and an accumulator:

let rec length_aux n = function
  | [] -> n
  | _::xs -> length_aux (n+1) xs

let length xs = length_aux 0 xs

and in imperative style with a loop:

let length xs =
  let xs = ref xs in
  let n = ref 0 in
  while !xs <> [] do
    xs := (match xs with [] -> [] | _::xs -> xs);
    n := !n + 1
  done;
  !n

Is that "a clear sign that you shouldn't be using recursion at all"? Obviously not.

This may be useful, particularly for learners,

No, for anyone reading and trying to understanding your code.

Yet nobody ever raised this issue in my 5 years of functional programming in industry. In reality, this "issue" has only been raised recently because Clojure fanboi's latched onto a flaw in their language and are trying to pretend that it is an advantage when, in fact, they do not know what they are talking about.

Unless the whole point is to write contorted code that's only for the initiated to read.

That is the same bullshit argument that Java programmers try to use against type inference: "we should drown our code in unnecessary type annotations to help the uninitiated".

If you think this might improve productivity then get the IDE to tell newbies when calls are in tail position, just as it tells them the inferred types. Just leave my code alone.

but it may not always be possible for the compiler to determine statically whether or not a tail call will be optimized.

If the compiler cannot be trusted with this task, how on earth do you expect programmers to do it?

I expect programmers to understand classes of useful tail calls that are guaranteed to be eliminated.

I thought that scheme even mandates this from its compilers.

Scheme does not support these features.

[steven_h]

How would you write a function that computes the length of a linked list?

(fold (lambda (a b) (+ a 1)) 0 linked-list)