Programming Forums - View Single Post

derzok · May 15th, 2008, 10:10 AM

After having just completed two semesters of Scheme programming, I can tell you that it is indeed possible to transform any algorithm into Tail-Recursion if you use the Continuation Passing Style algorithm.

http://lambda-the-ultimate.org/node/2673#comment-40136

Notes from one of my class's lectures:

(Toggle Plain Text)

; Basics:
; - initial value of k is (lambda (v) v)
; - apply k to base case value
; - new value of k is (lambda (v) (k (doSomething v)))
; - Imagine that the result of your recursive call (say, for n-1) is v.  
;   What should be done to get the proper result for this call (say, for n)?
;   That's what "doSomething" is.

(define length-cps
  (lambda (ls)
    (let loop ((ls ls)
               (k (lambda (v) v)))
      (if (null? ls)
          (k 0)
          (loop (cdr ls)
                (lambda (cdrLen) (k (add1 cdrLen))))))))

May 15th, 2008, 10:10 AM	#6
derzok Newbie Join Date: Jan 2008 Posts: 3 Rep Power: 0	Re: Anyone a genius? After having just completed two semesters of Scheme programming, I can tell you that it is indeed possible to transform any algorithm into Tail-Recursion if you use the Continuation Passing Style algorithm. http://lambda-the-ultimate.org/node/2673#comment-40136 Notes from one of my class's lectures: (Toggle Plain Text) ; Basics: ; - initial value of k is (lambda (v) v) ; - apply k to base case value ; - new value of k is (lambda (v) (k (doSomething v))) ; - Imagine that the result of your recursive call (say, for n-1) is v. ; What should be done to get the proper result for this call (say, for n)? ; That's what "doSomething" is. (define length-cps (lambda (ls) (let loop ((ls ls) (k (lambda (v) v))) (if (null? ls) (k 0) (loop (cdr ls) (lambda (cdrLen) (k (add1 cdrLen)))))))) ; Basics: ; - initial value of k is (lambda (v) v) ; - apply k to base case value ; - new value of k is (lambda (v) (k (doSomething v))) ; - Imagine that the result of your recursive call (say, for n-1) is v. ; What should be done to get the proper result for this call (say, for n)? ; That's what "doSomething" is. (define length-cps (lambda (ls) (let loop ((ls ls) (k (lambda (v) v))) (if (null? ls) (k 0) (loop (cdr ls) (lambda (cdrLen) (k (add1 cdrLen))))))))