Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!comp.vuw.ac.nz!cc-server4.massey.ac.nz!E.Ireland
From: E.Ireland@massey.ac.nz (Evan Ireland)
Newsgroups: comp.lang.scheme
Subject: Tail-calling with Scheme->C translators
Message-ID: <506sis-b@massey.ac.nz>
Date: 20 Feb 91 21:56:18 GMT
Reply-To: E.Ireland@massey.ac.nz
Organization: Information Sciences, Massey University, New Zealand
Lines: 39

Hi,

The recent discussion on tail-calling and garbage collection reminded
me of something I have intended to ask for a while now.

How do the Scheme compilers which compile to C (or "similar"
languages) handle tail recursion?

For example, I imagine that most compilers would generate a "goto"
statement in the C function for the following Scheme procedure.
(Please pardon any minor syntactic errors).

    (define alength (lambda (x n)
		     (if (pair? x) (alength (cdr x) (+ n 1))
		       0)))

But what if I define two mutually tail-recursive procedures?

    (define even? (lambda (n)
		    (if (= n 0) #t
		      (odd? (- n 1)))))

    (define odd? (lambda (n)
		   (if (= n 0) #f
		     (even? (- n 1)))))

If the compiler generates separate C functions for each of these
Scheme procedures, the "goto" statement can no longer be used, and I
don't imagine that setjmp/longjmp are any more useful either.

I know of one solution to this problem, for applicative languages
without call/cc, but I am particularly interested in how the Scheme->C
compilers do it.

	Thanks,

-------------------------------------------------------------------------------
E.Ireland@massey.ac.nz          Evan Ireland, School of Information Sciences,
  (063) 69-099 x8541          Massey University, Palmerston North, New Zealand.