This is the mail archive of the
kawa@sourceware.org
mailing list for the Kawa project.
Re: Tail sets
- From: Per Bothner <per at bothner dot com>
- To: Helmut Eller <eller dot helmut at gmail dot com>
- Cc: kawa at sources dot redhat dot com
- Date: Mon, 29 Jun 2009 00:10:15 -0700
- Subject: Re: Tail sets
- References: <87zlfnjhwt.fsf@lifebook.lan> <49BDDA63.6020009@bothner.com> <m2my9fpvm8.fsf@gmail.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/