another Q on tail calls

another Q on tail calls

[Matt Wette]

[-- Attachment #1: Type: text/plain, Size: 683 bytes --]

Here is another one Q on tail recursion.  Is this a tail call?   The result of (foo) is 10.

At each iteration the loop captures the local variable "n" in a lambda and saves in a list.  At the end of the iteration "+" is applied to the evaluation of all the lambdas.  It looks to me like the capture of the binding has to invalidate tail-recursion.  Is that true?  

(define (foo)
  (let iter ((proc-list '()) (n 4))
    (if (zero? n) (apply + (map (lambda (proc) (proc)) proc-list))
	(iter (cons (lambda () n) proc-list) (1- n)))))


Motivation: I have been looking into streams programming (from SICP) and thinking about delay/force and future/touch.

Thanks,
Matt


[-- Attachment #2: Type: text/html, Size: 1266 bytes --]

Re: another Q on tail calls

[Taylan Ulrich Bayırlı/Kammer]

Matt Wette <mwette@alumni.caltech.edu> writes:

> Here is another one Q on tail recursion. Is this a tail call? The
> result of (foo) is 10.
>
> At each iteration the loop captures the local variable "n" in a lambda
> and saves in a list. At the end of the iteration "+" is applied to the
> evaluation of all the lambdas. It looks to me like the capture of the
> binding has to invalidate tail-recursion. Is that true? 
>
> (define (foo)
>   (let iter ((proc-list '())
>              (n 4))
>     (if (zero? n)
>         (apply + (map (lambda (proc) (proc)) proc-list))
>         (iter (cons (lambda () n) proc-list)
>               (1- n)))))
>
> Motivation: I have been looking into streams programming (from SICP)
> and thinking about delay/force and future/touch.
>
> Thanks,
> Matt

The 'iter' loop uses tail-calls, so it doesn't grow the stack.  The
procedure capturing the variable 'n' (actually it's likely to capture
the value 'n' holds in that moment, because the optimizer should be able
to notice that 'n' is never mutated) resides on the heap (and if 'n'
were mutable/mutated it would also reside in a "box" on the heap), so no
stack usage due to the creation of those procedures.

(Maybe the optimizer might do even crazier things and somehow use stack
space for the procedures after all, but it's guaranteed to uphold the
semantics of using constant stack frames for the iteration.)

If you're keen on reading academic papers, I can recommend AI Memo #199,
titled FUNARG, and AI Memo #349 which is the original specification of
Scheme ("R0RS" if you will).

Taylan