From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Kevin Ryde Newsgroups: gmane.lisp.guile.devel Subject: doc tail calls Date: Sat, 12 Feb 2005 09:21:43 +1100 Message-ID: <87ll9uybyg.fsf@zip.com.au> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1108160481 18865 80.91.229.2 (11 Feb 2005 22:21:21 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Fri, 11 Feb 2005 22:21:21 +0000 (UTC) Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Feb 11 23:21:19 2005 Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1Czj9w-0002Hr-E9 for guile-devel@m.gmane.org; Fri, 11 Feb 2005 23:21:08 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1CzjOx-0001x1-39 for guile-devel@m.gmane.org; Fri, 11 Feb 2005 17:36:39 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1CzjO2-0001KK-PR for guile-devel@gnu.org; Fri, 11 Feb 2005 17:35:42 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1CzjO1-0001Jk-Rt for guile-devel@gnu.org; Fri, 11 Feb 2005 17:35:42 -0500 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1CzjO1-0001JX-Mw for guile-devel@gnu.org; Fri, 11 Feb 2005 17:35:41 -0500 Original-Received: from [61.8.0.84] (helo=mailout1.pacific.net.au) by monty-python.gnu.org with esmtp (Exim 4.34) id 1CzjAd-0004tF-Qn for guile-devel@gnu.org; Fri, 11 Feb 2005 17:21:52 -0500 Original-Received: from mailproxy1.pacific.net.au (mailproxy1.pacific.net.au [61.8.0.86]) by mailout1.pacific.net.au (8.12.3/8.12.3/Debian-7.1) with ESMTP id j1BMLmA6005160 for ; Sat, 12 Feb 2005 09:21:48 +1100 Original-Received: from localhost (ppp2880.dyn.pacific.net.au [61.8.40.128]) by mailproxy1.pacific.net.au (8.12.3/8.12.3/Debian-7.1) with ESMTP id j1BMLliN003402 for ; Sat, 12 Feb 2005 09:21:47 +1100 Original-Received: from gg by localhost with local (Exim 3.36 #1 (Debian)) id 1CzjAV-0000a0-00; Sat, 12 Feb 2005 09:21:43 +1100 Original-To: guile-devel@gnu.org Mail-Copies-To: never User-Agent: Gnus/5.110003 (No Gnus v0.3) Emacs/21.3 (gnu/linux) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org X-MailScanner-To: guile-devel@m.gmane.org Xref: main.gmane.org gmane.lisp.guile.devel:4774 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:4774 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