Re: Tail sets

[Per Bothner <per at bothner dot com>]

It took longer than expected, but I finally checked
in something based on your prototype.

For example this test runs in constant space:

(define (check-even (x :: int))
  (letrec ((even?
	    (lambda ((n1 :: int))
	      (if (= n1 0)
		  #t
		  (odd? (- n1 1)))))
	   (odd?
	    (lambda ((n2 :: int))
	      (if (= n2 0)
		  #f
		  (even? (- n2 1))))))
    (even? x)))

(I added type specifiers to your example to make
it fast and compact for better testing.)

I generalized the idea, so that (for example) in:

(define (inline-two-calls (x :: int)) :: int
  (define (f (w :: int)) :: int (+ w 10))
  (if (> x 0)
      (let ((y1 :: int (+ x 1)))
	(f y1))
      (let ((y2 :: int (+ x 2)))
	(f y2))))

f gets inlined (without bytecode duplication) by inlining the
bytecode in the first call-site.  Then the second-call
site is just a jump to the first - which works because both call-sites
have the same continuation - i.e. return address.

While not much of your patch remains in what got checked in,
it did get me started, and help me understand the issues better.
Thanks!
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/