Scheme - Is it important to try to write tail calls?

Author

Is it important to try to write tail calls?

Griff

2007-02-22, 10:09 pm

Is it important to try to write tail calls if necessary?

Whenever folks talk about functional programming, they say that
optimization doesn't matter. What matters is to "get it right". What
I've found is more to get it right, and if you get it right, then
optimize :)

Joe Marshall

2007-02-23, 7:14 pm

On Feb 22, 7:07 pm, "Griff" <gret...@gmail.com> wrote:
> Is it important to try to write tail calls if necessary?

That's a tough question!

The answer depends on what you mean by `necessary', and that
in turn depends on your understanding of the `Order of Growth'
of a program or algorithm. If you practice, you can become
proficient in estimating the order of growth of your program.
Order of growth should be one of the things you take into
account when designing a program (other things might be
simplicity or ease of making changes).

If we compare two language implementations, one of which
supports tail recursion and the other not, we'll find that
some recursive algorithms will exhibit different orders of
growth in the two implementations. The tail recursive
implementation may use dramatically less space than the
non-tail-recursive implementation.

But this doesn't mean that you'll solve your programming
tasks by forcing yourself to use tail recursion. It means
that *if* there is an *option* to use tail recursion, and
by choosing that option you can expect a reduction in
order of growth, then you ought to take advantage of it.

As you become a more experienced programmer, you'll find that
you won't be constantly dwelling on whether you can write
something tail-recursively or not. You'll almost never think
about it. What happens is that you learn to expect the
language implementation to be parsimonious in its use of space
and let *it* figure out whether it can optimize the tail calls.
You'll find yourself thinking about tail recursion *more* when
you have to switch to a language that doesn't support it.
You'll notice that obvious, elegant algorithms that you want
to express via recursion can't be used simply because the
implementation is too stupid to free the stack resources when
they are no longer needed.

Ultimately, the answer is something like this:

If you are a beginner, you should compare some programs that
use tail calls to some that do not and get in the practice of
estimating order of growth. Then, as you program, you should
use the order of growth as one of the considerations in your
design.

When you are more experienced, then no, you don't
have to try to write tail calls. But when you are using a
dumb language, you *do* have to try to *not* write tail calls.

Nathan Thern

2007-02-23, 7:14 pm

Griff wrote:
> Is it important to try to write tail calls if necessary?

If it's "necessary" then the program doesn't work unless you do it. I
would call that "important" :-)

Seriously, though...

Tail calls are scheme's way of doing iteration ("do" is usually just a
syntactic form that really creates a tail recursive function. I almost
never use "do" myself.)

Suppose you have a very long list of integers and you want a function to
(non-destructively) increment each integer by 1 and return a new list.
Here is a naive first cut at it:

(define (inc-list lst)
(if (null? lst) lst
(cons (+ 1 (car lst)) (inc-list (cdr lst)))))

The memory this function requires to process a list is directly
proportional to the size of the list. That's in addition to the memory
required for the original list and the memory required for the result!

Here is one way of making the above function tail recursive:
(define (inc-list2 lst)
(letrec
((rslt (cons '() '()))
(inc-lst-hlpr
(lambda (lst rslt)
(if (null? lst) #t
(begin
(set-cdr! rslt (cons (+ 1 (car lst)) '()))
(inc-lst-hlpr (cdr lst) (cdr rslt)))))))
(inc-lst-hlpr lst rslt)
(cdr rslt)))

Of course, most implementations will have a tail-recursive reverse; so
here is another tail-recursive version that is shorter, clearer, and
likely faster:

(define (inc-list3 lst)
(let helper ((lst (reverse lst)) (rslt '()))
(if (null? lst) rslt
(helper (cdr lst) (cons (+ 1 (car lst)) rslt)))))

regards,
Nate T

Conrad

2007-02-23, 7:14 pm

Tail calls offer not only benefits in terms of optimization, but are
also easier to debug- Since there's no data stored on the stack while
you're debugging, all your data is "right there"- I find it often
easier to follow...

Tail calls also constrain your style in a way that different parts of
your program will have a similar "shape"- If you get used to this
shape, it again aids in reading/debugging

So I would argue that you'll save yourself some trouble if you can use
this style right from day one- But nothing "bad" will happen if you
ignore this detail for now, either.

-Conrad

Sponsored Links