Talk:Tail call

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

See the discussion at Talk:Tail recursion--Blaisorblade (talk) 19:21, 9 October 2010 (UTC)

Farking verbosity[edit]

JJ Behrens explains it much better:

Tail call optimization is an interesting technique that reduces the use of the stack. If function A calls function B, and then B's last step is to call function C, rather than having a return-to address for A and a return-to address for B, you can just have C return directly to A since there's nothing else in function B that needs to be done.

http://jjinux.blogspot.com/2011/04/call-me-crazy-calling-conventions.html

129.174.190.17 (talk) 08:10, 20 April 2011 (UTC)

Tail recursion modulo cons vs usage of accumulators in general[edit]

Using accumulators is a quite general technique, not limited to handling cons after the call. Is there any reason nowadays to talk about the special case? I moved the text here during the merge, IIRC, but I'm not yet fully convinced. Does anybody know of any study of this folklore technique? We also have a reference to the usage of accumulators in the Example programs section, and it seems the two should be merged. Disclaimer: I've not read the original reference, but I guess the technique was later generalized. --Blaisorblade (talk) 18:38, 15 October 2010 (UTC)

Tail recursion modulo cons inconsistency[edit]

The text says that cons adds elements to the head of a list, but the C code adds elements to the tail of the linked list. --Medinoc (talk) 15:56, 5 July 2011 (UTC)

  • I have noticed however, that for duplicating a list there is little other choice. If we change this, we'd need a function with a completely different purpose. --Medinoc (talk) 19:35, 5 July 2011 (UTC)

Factorial example[edit]

I find using the factorial example to be very misleading. The difference between the tco factorial and the non-tco factorial functions is more of an algorithm change than a tco transformation. The tco version is greatly simplifying the accumulator by multiplying the numbers in a different order! For a demonstration, consider a creating a different function by replacing zero? with null?, * with cons, and -1 with cdr. This gives you a copylist function:

(define (copylist l)
  (if (null? l)
      '()
      (cons (car l)
            (copylist (cdr l)))))

If you try the same transformation that the factorial example uses, you might incorrectly try to implement an accumulator version of copy-list like so:

(define (copylist l) ;;Wrong!  reverses the list
  (let copy ([rest l] [acc '()])
    (if (null? rest)
        acc
      (copy (cdr rest) (cons (car rest) acc)))))

We can however implement a version of copy-list with the copy call in tail position by borrowing ideas from cps. We can make acc a continuation which we build up, and finally execute when we've fully traversed the list.

(define (copy-list l)
  (let copy ([rest l] [acc (lambda (x) x)])
    (if (null? rest)
        (acc '())
      (copy (cdr rest) (lambda (x) (acc (cons (car rest) x)))))))

Which brings me to my suggestion. I believe a much fairer refactoring of the factorial function would be:

(define (factorial n)
  (let fact ([i n] [acc (lambda (x) x)])
    (if (zero? i)
        (acc 1)
      (fact (- i 1) (lambda (x) (acc (* i x)))))))

Here, the order in which the factors are multiplied in the factorial is the same as the non-tco version. Fact is in a tail call position meaning the stack doesn't grow. The acc does grow, not in integer product amounts ie. 1, 2, 6, 24; but by continuations wrapping other continutation ie. for (factorial 3) by the time (zero? i) returns true, acc will be

(lambda (w)
  ((lambda (x)
     ((lambda (y)
        ((lambda (z) z)
         (* 3 y)))
      (* 2 x)))
   (* 1 w)))

I believe the current version of factorial overstates what tce gets you and this less efficient yet more didactic version of factorial defined above would be better suited for this article. — Preceding unsigned comment added by Marty.neal (talkcontribs) 04:50, 19 January 2011 (UTC)


You are correct that the rewriting of the call reverses the order of evaluation (in the case of factorial, multiplying in reversed order). However, your example given above essentially just creates a stack out of lambda expressions. The point of tail recursion is to avoid a stack all together. With lists there's not much difference, but with the factorial example (or even moreso if we had used a simple summation example, like adding from 1 to n) the difference between an accumulator that emulates a stack vs one that just keeps track of a temporary return value is noticeable.Antares5245 (talk) 10:43, 17 May 2011 (UTC)