doc tail calls

* doc tail calls
@ 2005-02-11 22:21 Kevin Ryde
  2005-02-28  2:28 ` Marius Vollmer
  0 siblings, 1 reply; 2+ messages in thread
From: Kevin Ryde @ 2005-02-11 22:21 UTC (permalink / raw)

This is some words about tail calls, with I don't think are otherwise
described.  I'm thinking of this for a new section just after the
"Evaluating" node.

3.1.5 Tail calls
----------------

Scheme is "properly tail recursive", meaning that tail calls or
recursions from certain contexts do not consume stack space or other
resources and can therefore be used on arbitrarily large data or for an
arbitrarily long calculation.  Consider for example,

     (define (foo n)
       (display n)
       (newline)
       (foo (1+ n)))

     (foo 1)
     -|
     1
     2
     3
     ...

   `foo' prints numbers infinitely, starting from the given N.  It's
implemented by printing N then recursing to itself to print N+1 and so
on.  This recursion is a tail call, it's the last thing done, and in
Scheme such tail calls can be made without limit.

   Or consider a case where a value is returned, a version of the SRFI-1
`last' function (*note SRFI-1 Selectors::) returning the last element
of a list,

     (define (my-last lst)
       (if (null? (cdr lst))
           (car lst)
           (my-last (cdr lst))))

     (my-last '(1 2 3)) => 3

   If the list has more than one element, `my-last' applies itself to
the `cdr'.  This recursion is a tail call, there's no code after it,
and the return value is the return value from that call.  In Scheme
this can be used on an arbitrarily long list argument.

   A proper tail call is only available from certain contexts, namely
the following special form positions,

   * `and' -- last expression

   * `begin' -- last expression

   * `case' -- last expression in each clause

   * `cond' -- last expression in each clause, and the call to a `=>'
     procedure is a tail call

   * `do' -- last result expression

   * `if' -- "true" and "false" leg expressions

   * `lambda' -- last expression in body

   * `let', `let*', `letrec', `let-syntax', `letrec-syntax' -- last
     expression in body

   * `or' -- last expression

The following core functions make tail calls,

   * `apply' -- tail call to given procedure

   * `call-with-current-continuation' -- tail call to the procedure
     receiving the new continuation

   * `call-with-values' -- tail call to given procedure

   * `eval' -- tail call to evaluate the form

   * `string-any', `string-every' -- tail call to predicate on the last
     character (if that point is reached)

   The above are just the core functions and special forms, tail calls
in other modules are described with the relevant documentation, for
example SRFI-1 `any' and `every' (*note SRFI-1 Searching::).

   It will be noted there are a lot of places which could potentially be
tail calls, for instance the last call in a `for-each', but only those
explicitly described are guaranteed.

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

^ permalink raw reply	[flat|nested] 2+ messages in thread