[Mono-devel-list] tailcall support in mcs

[Lloyd Dupont]

ho, I see, thanks for that explanation :-)

If I understand you it's something the user (developer) will never see as it
will done behind the scene by the compiler, is it ?

mmhh...
and do they implement it then ? ;-)

----- Original Message ----- 
From: "Jonathan Pryor" <jonpryor at vt.edu>
To: "Lloyd Dupont" <ld at galador.net>
Cc: "Michal Moskal" <malekith at pld-linux.org>; <mono-devel-list at ximian.com>
Sent: Monday, September 15, 2003 11:25 AM
Subject: Re: [Mono-devel-list] tailcall support in mcs


> Recursive iteration.  Or maybe, recursion implemented by iteration.  :-)
>
> Yes, that's a mix of topics, but it's fairly close to the truth.
>
> The classic problem with recursion is stack space -- you use more stack
> space whenever you recurse, creating increased potential for a Stack
> Overflow error.  This is, of course, bad.  Consider:
>
> // sum 1 .. n and return
> int sum_recursive (int n) {
> if (n == 1) return 1;
> return n + sum1 (n-1);
> }
>
> You need "n" copies of sum_recursive() on the stack to complete the
> computation.  So if "n" is big, you'll run out of stack space.
>
> The classic solution is to use iteration (looping):
>
> int sum_iterative (int n) {
> int sum = 0;
> for (int i = 1; i != (n+1); ++i) {
> sum += i;
> }
> return i;
> }
>
> However, not all languages support iteration, as it requires modifying a
> loop control variable of some form.  (Some Lisp-derived languages are
> the classic example of this form of language, as classical Lisp contains
> no side effects and values are immutable.)
>
> So, how do you use recursion without killing yourself?
>
> The solution is simple: you only need to create a new stack entry when
> you're actually using something from the previous stack entry, as seen
> in sum_recursive.  If you can change the algorithm so that you don't
> need the intermediate results from previous steps, you can just use the
> same stack frame as you currently have.  What looks like a recursive
> function call is transformed into an iterative algorithm, as far as
> stack space is concerned:
>
> int sum_tailcall_impl (int current, int todo) {
> if (todo == 0) return current;
> return sum_tailcall_impl (current+todo, todo-1);
> }
> int sum_tailcall (int n) {
> return sum_tailcall_impl (n, n-1);
> }
>
> That's the jist of it.
>
> (Actually, I just showed an example of "tail recursion," which is a
> subset of "tail calls," and easier for compilers to examine and
> transform.)
>
> You should also lookup "tail call" on google.  The first result
> ("Squawks of the Parrot: What the heck is: A tail call") is decent.
>
>  - Jon
>
> On Sun, 2003-09-14 at 19:14, Lloyd Dupont wrote:
> > just a dumy question...
> > what's a tail call ?
> >
> > ----- Original Message -----
> > From: "Michal Moskal" <malekith at pld-linux.org>
> > To: <mono-devel-list at ximian.com>
> > Sent: Monday, September 15, 2003 6:02 AM
> > Subject: [Mono-devel-list] tailcall support in mcs
> >
> >
> > > Is outputting tallcalls done or planned in mcs? I'm working on
> > > functional language implementation. I'm generating C# (for now, later
> > > I'll switch to ilasm or bytecode), so lack of tailcalls is very
> > > annoying.
> > >
> > > --
> > > : Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a?
!tv
> > > : When in doubt, use brute force. -- Ken Thompson : {E-,w}-- 
{b++,e}>+++ h
> > >
> > > _______________________________________________
> > > Mono-devel-list mailing list
> > > Mono-devel-list at lists.ximian.com
> > > http://lists.ximian.com/mailman/listinfo/mono-devel-list
> >
> > _______________________________________________
> > Mono-devel-list mailing list
> > Mono-devel-list at lists.ximian.com
> > http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list