Proper non-tail recursion?

[brendan]

Scheme implementations are required to have proper tail recursion. Racket goes further and lets the programmer make recursive calls from any position without fear because, to paraphrase Dr. Flatt, it's the 21st century and stack overflows should not be a thing. My questions are: Is there a name for this feature? And do any other major languages or implementations have it? Thanks.

[John Clements]

> On Apr 25, 2017, at 3:37 PM, brendan <bre...@cannells.com> wrote:
>
> Scheme implementations are required to have proper tail recursion. Racket goes further and lets the programmer make recursive calls from any position without fear because, to paraphrase Dr. Flatt, it's the 21st century and stack overflows should not be a thing. My questions are: Is there a name for this feature? And do any other major languages or implementations have it? Thanks.

Sadly, there are *many* names for this feature.

But first, a correction! Like Racket, Scheme implementations are also required to have the desired memory behavior (specifically, they must not grow without bound on a class of programs that makes only tail calls). It’s true that the standard uses the phrase “tail recursion,” but if you check it out, you’ll see that it’s not just recursive calls that are covered.

In answer to your actual question, the most common name is “Tail Call Optimization,” which many people correctly object to because it’s not an optimization, it’s a change to the meaning of terms in the language, at least if you can distinguish stack overflows from programs that run forever.

I once invented the name “tail-cursion” for this, which everyone hated.

Finally, I’m moderately fond of Dave Herman’s phrase “properly tail-calling,” though I admit that it’s not as short as it could be.

John Clements

[Robby Findler]

I think the question is about non-tail calls and limits on them. 

Robby

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[brendan]

Indeed; I should have clarified that I didn't mean only recursion per se. Not the first time I've stumbled on that misnomer.

[John Clements]

> On Apr 25, 2017, at 4:05 PM, brendan <bre...@cannells.com> wrote:
>
> Indeed; I should have clarified that I didn't mean only recursion per se. Not the first time I've stumbled on that misnomer.

Forgive me. In that case, I’m not sure exactly what property it is you’re looking for a name for.

:)

John

[Matthew Butterick]

> On Apr 25, 2017, at 4:05 PM, brendan <bre...@cannells.com> wrote:
>

> Indeed; I should have clarified that I didn't mean only recursion per se. Not the first time I've stumbled on that misnomer.
>
> On Tuesday, April 25, 2017 at 6:53:59 PM UTC-4, Robby Findler wrote:
>> I think the question is about non-tail calls and limits on them.

FWIW you can definitely trigger a stack overflow with non-tail calls. In DrRacket, go to Racket → Limit Mem­ory and change the limit to 8 MB. Then try this:

(define (sum n)
(if (zero? n)
n
(+ n (sum (sub1 n)))))

(sum 100000000) ; boom

[Jon Zeppieri]

On Tue, Apr 25, 2017 at 6:37 PM, brendan <bre...@cannells.com> wrote:
> Scheme implementations are required to have proper tail recursion. Racket goes further and lets the programmer make recursive calls from any position without fear because, to paraphrase Dr. Flatt, it's the 21st century and stack overflows should not be a thing. My questions are: Is there a name for this feature? And do any other major languages or implementations have it? Thanks.

I don't know if there's one particular term for this. A resizable (or
growable) call stack, maybe?

It's very different from proper tail calls, though, because a non-tail
call still accumulates space, and you can still run out of space. It's
just that many language implementations use a fixed-size stack,
whereas Racket will increase the size of the stack at runtime. I'm not
sure what other language implementations do this.

[Robby Findler]

Ah, lucky you. This is not a "stack overflow". This is a "all of memory overflow". The cool thing about racket is that there is not separate limit on some mysterious PL-internal data structure called a "stack".

Robby

[brendan]

Good points: It wasn't strictly true to say that you can make non-tail calls "without fear." Rather, your memory for continuation frames is shared with, and just as large as, any other kind of data.

[Matthias Felleisen]

Brendan,

you’re correct in attributing the idea that the proper implementation of tail calls is far less important to the Scheme and Racket community. Dybvig expressed this idea first in a talk titled a Bag of Hacks in the early 90s. Matthew then at some point said that the true goal is to never run out of stack space (other than run out of memory period); once we have that proper tail-call implementation might just be of secondary value.

As for terminology, I think I would say that a language ought to support ‘unbounded recursion depth’. Unwieldy name.

How is it implemented? When a call is about to exhaust the available stack space, grab the stack, move it into the heap, start a new one with a frame that links to the moved stack. If you now also want to implement continuation-grabing control operators (call/cc, C, F, prompt, etc) you can do so with one extra bit per stack frame and lazy copying of heap-moved stacks to the stack proper.

While I am at it, let me advocate PITCH as the slogan for Proper Implementation of Tail Calls. (Where does the H come from? I added it to make a complete word.) What many people fail to see is that every language with function calls has tail positions. The syntax may obscure those with various superfluous keywords but that does not invalidate the idea. A tail-call position is a ‘return’ place in a function body. Period. So when people say “we implement tail calls”, it’s basically nonsense because every language with function calls must implement tail calls. The question is whether the evaluation of arguments or the evaluation of function calls consumes space. And if you love OO design patterns — which is where Scheme comes from — you must opt into the former not the latter, which means you must implement tail calls properly.

— Matthias

> On Apr 25, 2017, at 7:32 PM, brendan <bre...@cannells.com> wrote:
>
> Good points: It wasn't strictly true to say that you can make non-tail calls "without fear." Rather, your memory for continuation frames is shared with, and just as large as, any other kind of data.
>

[Jordan Johnson]

On Apr 25, 2017, at 6:09 PM, Matthias Felleisen <matt...@ccs.neu.edu> wrote:
> While I am at it, let me advocate PITCH as the slogan for Proper Implementation of Tail Calls. (Where does the H come from? I added it to make a complete word.)

Proper Implementation of Tail Call Handling? :)

Cheers,
Jordan

[Robby Findler]

"..., Hooray!" ? :)

Robby

[Jay McCarthy]

+1 to Robby's idea :P

--
-=[ Jay McCarthy http://jeapostrophe.github.io ]=-
-=[ Associate Professor PLT @ CS @ UMass Lowell ]=-
-=[ Moses 1:33: And worlds without number have I created; ]=-

[Norman Gray]

Greetings.

On 25 Apr 2017, at 23:51, 'John Clements' via Racket Users wrote:

> In answer to your actual question, the most common name is “Tail
> Call Optimization,” which many people correctly object to because
> it’s not an optimization, it’s a change to the meaning of terms in
> the language

I've seen the phrase 'Tail Call Elimination' used, for precisely this
reason, that it's not merely an optimisation.

While it's not as cute as Proper Implementation of Tail Call Handling,
it's possibly more descriptive (saying 'proper' is rather begging the
question), and close enough to the more widespread TCO to be
intelligible.

All the best,

Norman


--
Norman Gray : https://nxg.me.uk
SUPA School of Physics and Astronomy, University of Glasgow, UK

[brendan]

Dr. Felleisen,

Thanks for the informative response. Is Racket the only language with unbounded recursion depth as far as you know? And with respect to implementation, can you explain the role of the one extra bit that you mention?

A number of functional languages targeting platforms like the JVM and browsers are compromised by the lack of proper tail calls. I often wonder how much of a performance penalty you would have to pay if those languages were implemented by CPS-transforming the whole program and running on a trampoline, except where the compiler could prove constant-bounded call depth.

[Raoul Duke]

i should think any "real" fp would support it. where real is a bijection with having such support.  well, at least necessary if not sufficient.

> > To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscribe@googlegroups.com.

> > For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscribe@googlegroups.com.

[Jon Zeppieri]

On Thu, Apr 27, 2017 at 7:10 PM, Raoul Duke <rao...@gmail.com> wrote:
> i should think any "real" fp would support it. where real is a bijection
> with having such support. well, at least necessary if not sufficient.

That would be a rather contentious claim, as it rules out OCaml, for example.

[Hendrik Boom]

I really thought OCaml did tail-recursion properly. Its tutorial
literature goes th some trouble to explain that it's OK to recurse
tailfully. What is the truth here?

-- hendrik

[Jon Zeppieri]

OCaml does handle tail calls properly. But proper tails calls are not
the subject of this discussion. The original post was explicitly about
non-tail calls and how, in Racket, you cannot exhaust the stack
without exhausting all of the memory available to the program.
(Whereas in OCaml you can, because it uses a fixed-size stack.)

[Scott Moore]

On the other hand, if I recall correctly SML has the same behavior as racket. I think the implementation uses a chain of "stacklets" that are heap allocated.

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

[Justin Zamora]

On Thu, Apr 27, 2017 at 8:06 PM, Jon Zeppieri <zepp...@gmail.com> wrote:

OCaml does handle tail calls properly. But proper tails calls are not
the subject of this discussion. The original post was explicitly about
non-tail calls and how, in Racket, you cannot exhaust the stack
without exhausting all of the memory available to the program.
(Whereas in OCaml you can, because it uses a fixed-size stack.)

How common is it to have a fixed-size stack? I thought it was normal practice for the heap and stack to be on opposite ends of memory and to grow towards each other, so that either can use all available memory.

Justin

[Jon Zeppieri]

It's the norm, and it's typically enforced by the OS. (Of course, you
could ignore the system's stack and build your own stack in the heap,
but you will pay a performance price.) That's why the technique that
Matthias described involves detecting overflows and copying the
current stack to the heap.

[Matthias Felleisen]

As some have pointed out downstream from here, SML is definitely a language that does it (but see Appel’s articles on why stacks are superfluous from years ago and weep).

I suspect that all faithful Scheme implementations get close or satisfy this property.

But as others have mentioned, many languages fail this property. Their implementors will argue that deep recursions don’t exist or shouldn’t be supported. Sadly, this is even true for languages that support call/cc or similar control operators, with which you could easily achieve this (through internal uses). And when I read their arguments, I recall the tales of my first programming course which told us of IBM’s objections to Algol because it dynamically allocated memory (on the stack) and how inefficient this would be, and that Algol 60 had to be stopped etc. It reminds me of C++’s limits on template expansions. It was 7 or 8, it might be 20 now. It reminds me of Scala’s prelude which defines the function class for up to 5, 8, 22 arguments.

When will we learn and implement the elegant solution so that we can strive for good performance for it?

[Daniel Bastos]

On Fri, Apr 28, 2017 at 11:19 AM, Matthias Felleisen
<matt...@ccs.neu.edu> wrote:
> [...] Their implementors will argue that deep recursions don’t exist or shouldn’t be supported. [...]

Python's argument for not supporting tail-call optimization (if I
should call it that way after this thread) is that it makes it fail to
produce an informative ``Traceback''. That's what I remember from an
interview done with Guido van Rossum. (I don't recall any other
reasons.)

[Ben Greenman]

On Fri, Apr 28, 2017 at 11:08 AM, Daniel Bastos <dba...@toledo.com> wrote:

interview done with Guido van Rossum

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

Related:

lexical scope is interesting *theoretically*, but its inefficient to implement; dynamic scope is the fast choice

 http://www.paulgraham.com/thist.html

[Matthias Felleisen]

> On Apr 28, 2017, at 11:12 AM, Ben Greenman <benjamin...@gmail.com> wrote:
>
>
> On Fri, Apr 28, 2017 at 11:08 AM, Daniel Bastos <dba...@toledo.com> wrote:
> interview done with Guido van Rossum
>
> http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

Guys, this conversation is really not about PITCH per se.

[Ben Greenman]

Right ... it's about "growable stack languages" or "infinite stack languages" or "heapful languages" or something like that.

[Daniel Bastos]

Thanks for pointing that out. I failed to recognize the subject was
beyond my knowledge, so I totally misunderstood everything. Thank
you!