[Mono-devel-list] tailcall support in mcs

[Jonathan Pryor]

Well, the developer can see it if they disassemble the application. :-)

Or, in the case of CIL code, disassemble the generated machine code.

As for implementation, I've heard that GCC supports tail recursion in C
code, and many functional languages also tend to support it (often by
necessity).

I don't know if mono has implemented support for tail recursion, though.

 - Jon

On Sun, 2003-09-14 at 23:00, Lloyd Dupont wrote:
> 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
> 
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list