Subject: Re: Was not making tail recursion elmination a mistake?
From: rpw3@rpw3.org (Rob Warnock)
Date: Sat, 12 Jun 2004 22:07:07 -0500
Newsgroups: comp.lang.lisp
Message-ID: <G5adnT_DCeZGWVbdRVn-vA@speakeasy.net>
Marco Baringer  <mb@bese.it> wrote:
+---------------
| >> look into a technique called "trampolining". basically you'd rewrite
| 
| my bad. this technique is used when CPS transforming code, since my
| example wasn't written in a CPS style ... it failed to prove my point.
| 
| here's an example which actually works. it's a recursive function for
| calculating the length of a list. just so it's clear what i'm doing
| i've started with the "normal" recursive version and re-written it
| until it's in trampolined CPS form..
+---------------

But note that even in trampolined CPS form it is not necessary to use
THROW (which, when deeply nested, might be quite slow) to achieve the
desired result. Consider this slight rewrite [which, with no THROW,
allows replacing #'TOPLEVEL-K with #'IDENTITY]:

    > (defun len-tramp (list k)
        (if (null list)
          (lambda () (funcall k 0))
          (lambda ()
            (len-tramp (cdr list) (lambda (v) (funcall k (1+ v)))))))
    LEN-TRAMP
    > (trace len-tramp)
    NIL
    > (defun run-tramp (func)
        (loop for f = func then (funcall f)   
              while (functionp f)
          finally (return f)))
    RUN-TRAMP
    > (run-tramp (lambda () (len-tramp '(a b c d e) #'identity))) 
    0: (LEN-TRAMP (A B C D E) #<Function IDENTITY {1019F481}>)
    0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {48519951}>
    0: (LEN-TRAMP (B C D E) #<Closure Over Function "LAMBDA (LIST K)" {4851A2F9}>)
    0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {4851B9D1}>
    0: (LEN-TRAMP (C D E) #<Closure Over Function "LAMBDA (LIST K)" {4851C379}>)
    0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {4851DA19}>
    0: (LEN-TRAMP (D E) #<Closure Over Function "LAMBDA (LIST K)" {4851E3C1}>)
    0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {4851FA29}>
    0: (LEN-TRAMP (E) #<Closure Over Function "LAMBDA (LIST K)" {485203D1}>)
    0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {485219E9}>
    0: (LEN-TRAMP NIL #<Closure Over Function "LAMBDA (LIST K)" {48522391}>)
    0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {48523921}>
    5
    > 


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607