[Mono-devel-list] tailcall support in mcs

[Jonathan Pryor]

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