Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!mcgill-vision!bloom-beacon!eru!luth!sunic!mcsun!unido!tub!tubopal!opal!simon
From: simon@opal.tu-berlin.de (Simon Leinen)
Newsgroups: comp.lang.scheme
Subject: Re: (none)
Message-ID: <SIMON.90Feb7120454@viking.cs.tu-berlin.de>
Date: 7 Feb 90 11:04:54 GMT
References: <9002051741.AA03862@heike.informatik.uni-dortmund.de>
Sender: news@tubopal.UUCP
Organization: TU Berlin, Fachbereich 20 (Informatik)
Lines: 62
In-reply-to: muenx@heike.informatik.uni-dortmund.de's message of 5 Feb 90 17:41:57 GMT
To:

In article <9002051741.AA03862@heike.informatik.uni-dortmund.de> muenx@heike.informatik.uni-dortmund.de (Holger Muenx) writes:

	  (define (dummy x)
	     (if (< x 10)
		  (dummy (1+ x))
		  'DONE))

     Here you cannot immediately see if (dummy ...) is the last
     evaluated expression. In some way you have to analyze the meaning
     of the procedure.

What you have is almost THE CLASSICAL EXAMPLE of tail recursion.  A
function call is a tail call if it occurs last *in an execution path*
of the calling function, and this is the case for the call to `dummy'.

In the example, the if form is known to be the last form in the
function body.  Either the `then' or the `else' branch is taken.  The
else branch just returns a constant, which cannot be optimized very
much.  The then part calls a function and returns the result of this
call.  Call and return can be transformed into a jump, and the jump
can be transformed into a branch, since the called function is the
same as the calling function.  Thus the tail-recursive call can be
eliminated, and this is what you can expect from any decent Lisp or
Scheme compiler.

     To my opinion it is not enough to test additional in special
     forms like 'if' or 'cond' if the application is the last
     evaluated expression in this form because after the 'if' or
     'cond' clause there can be other expressions to be evaluated.

If there were other forms after the if, you could only optimize
tail-recursion in those forms.  Tail calls only occur at the end of a
sequence (hence the word `tail').

This is why Lisp (or Scheme) programmers change a definition like

	(define fac (lambda (n)
	  (if (= n 0)
	      1
	    (* n (fac (- n 1)))))) ; tail-call to *, but not to fac

into the less obvious, but more efficient

	(define fac (lambda (n)
	  (letrec ((fac-aux (lambda (n acc)
	             (if (= n 0)
	                 acc
	               (fac-aux (- n 1) (* n acc)))))) ; tail-call to fac-aux
	    (fac-aux n 1))))

Unfortunately, most existing compilers don't perform this optimization
themselves.

     Today I asked a professsor and a doctor here at UniDo but both
     couldn't help me.

Don't expect any professor in this country to be able to help you.
Lisp wird in Deutschland einfach nicht ernstgenommen.

Viele Gruesse und happy LISPing,
-- 
Simon Leinen.