Re: [racket-users] Proper non-tail recursion?

[Daniel Bastos]

On Fri, Apr 28, 2017 at 12:29 PM, Matthias Felleisen
 wrote:
>> On Apr 28, 2017, at 11:12 AM, Ben Greenman  
>> wrote:
>>
>> On Fri, Apr 28, 2017 at 11:08 AM, Daniel Bastos  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.

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

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[Ben Greenman]

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

On Fri, Apr 28, 2017 at 11:29 AM, Matthias Felleisen 
wrote:

>
> > On Apr 28, 2017, at 11:12 AM, Ben Greenman 
> wrote:
> >
> >
> > On Fri, Apr 28, 2017 at 11:08 AM, Daniel Bastos 
> 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.

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[Matthias Felleisen]

> On Apr 28, 2017, at 11:12 AM, Ben Greenman  
> wrote:
> 
> 
> On Fri, Apr 28, 2017 at 11:08 AM, Daniel Bastos  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. 

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[Ben Greenman]

On Fri, Apr 28, 2017 at 11:08 AM, Daniel Bastos  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

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[Daniel Bastos]

On Fri, Apr 28, 2017 at 11:19 AM, Matthias Felleisen
 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.)

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[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? 





> On Apr 27, 2017, at 7:01 PM, brendan  wrote:
> 
> 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.
> 
> On Tuesday, April 25, 2017 at 9:09:10 PM UTC-4, Matthias Felleisen wrote:
>> 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  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.
>>> 
>>> -- 
>>> 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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[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

--
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[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

On Tue, Apr 25, 2017 at 6:13 PM Matthew Butterick  wrote:

>
> > On Apr 25, 2017, at 4:05 PM, brendan  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 1) ; boom
>
> --
> 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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[Jon Zeppieri]

On Tue, Apr 25, 2017 at 6:37 PM, brendan  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.

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[Matthew Butterick]

> On Apr 25, 2017, at 4:05 PM, brendan  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 1) ; boom

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

['John Clements' via Racket Users]

> On Apr 25, 2017, at 4:05 PM, brendan  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



-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[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.

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. 
> 
> 
> Robby
> 
> 
> 
> On Tue, Apr 25, 2017 at 5:52 PM 'John Clements' via Racket Users 
>  wrote:
> 
> 
> > On Apr 25, 2017, at 3:37 PM, brendan  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
> 
> 
> 
> 
> 
> 
> 
> --
> 
> 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.

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

[Robby Findler]

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

Robby

On Tue, Apr 25, 2017 at 5:52 PM 'John Clements' via Racket Users <
racket-users@googlegroups.com> wrote:

>
> > On Apr 25, 2017, at 3:37 PM, brendan  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
>
>
>
> --
> 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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Proper non-tail recursion?

['John Clements' via Racket Users]

> On Apr 25, 2017, at 3:37 PM, brendan  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



-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[racket-users] 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.

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.