Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!snorkelwacker!bloom-beacon!ZURICH.AI.MIT.EDU!jinx
From: jinx@ZURICH.AI.MIT.EDU ("Guillermo J. Rozas")
Newsgroups: comp.lang.scheme
Subject: (none)
Message-ID: <9002081400.AA15746@zurich.ai.mit.edu>
Date: 8 Feb 90 14:00:43 GMT
References: <4782@brazos.Rice.edu>
Sender: daemon@athena.mit.edu (Mr Background)
Reply-To: jinx@zurich.ai.mit.edu
Organization: The Internet
Lines: 48


    "Unfortunately"?  I wouldn't want the compiler to perform this
    optimization, for if you unwind the *-calls, you'll find the
    non-tail-rec version does (* n (* n-1 (* n-2 ... 1))), while the
    tail-rec one does (* 1 (* 2 (* 3 ... (* n 1)))).  The optimization
    hinges too much on the commutativity of * for my comfort.

Commutativity should not be a problem as long as the compiler can
determine that * is really *.  A worse problem is associativity, which
doesn't generally hold for computer arithmetic, although it typically
holds in Lisp systems when restricted to integers.

    (I guess you mean Scheme rather than Lisp, since none of the (other)
    Lisps bother even about tail-call optimization, not to speak of the
    optimizations that Holger and you speak of.)

If I'm not mistaken, the MacLisp compiler handled some purely local
cases of tail-call optimization, and the Lucid compiler handles even
more.  The difference is that Scheme requires that the language be
properly tail recursive, that is, calls in tail position (whether to a
procedure visible at "compile" time or not) should generate no net
growth of storage.  

For example, the following contrived program should be an infinite
loop (no net growth of storage) when given a list with a single
element as an argument, yet it is an infinite recursion when given a
longer list.

(define (tst l)
  (define (flat-apply f original)
    (define (flatten-1 l add-to-what)
      (if (pair? l)
	  (flatten-1 (car l) (flatten-2 (cdr l) add-to-what))
	  (f l add-to-what)))

    (define (flatten-2 l add-to-what)
      (cond ((pair? l) (flatten-1 (car l) (flatten-2 (cdr l) add-to-what)))
	    ((null? l) add-to-what)
	    (else (error "Flatten: Bad list" original))))

    (flatten-2 original '()))

  (define (test-f element ignore)
    (newline)
    (write element)
    (flat-apply test-f l))

  (flat-apply test-f l))