Why is tail recursion required in all schema implementations?
Tail recursion is defined by the language specification. Quoting from R6RS section 5.11 :
Schema implementations must be correctly recursive. Procedure calls that occur in certain syntactic contexts called tail contexts are tail calls. A schema implementation is correctly tail-recursive if it supports an unlimited number of active tail calls. The call is active if the called procedure can still return. Note that this includes regular returns as well as returns via continuation previously recorded by a continuation-continuation call that is later called. In the absence of captured continuations, calls can be returned no more than once, and active calls will be those that have not yet returned. A formal definition of correct tail recursion can be found in Kliner's paper [5].The rules for identifying tail calls in library constructs (rnrs base (6)) are described in section 11.20.
The practical reason for this is that tail recursion allows for an efficient loop using recursion.
source to share
Not in the schema goto
, so the whole loop is ultimately done with tail recursion. Without proper tail-recursion guarantee, there is no reliable way to enforce a loop in a circuit.
Update: I want to explain what I mean by "ends up using tail recursion". Take a look at the macro do
as @newacct mentioned it. For example:
(do ((i 1 (+ i 1)))
((> i 10))
(display i)
(newline))
As I mentioned, the circuit has no goto
, so it must receive its loop from somewhere. This actually macro expands (something like this):
(let loop ((i 1))
(unless (> i 10)
(display i)
(newline)
(loop (+ i 1))))
Please note that loop
this is not a keyword or built-in function. It is a named function, created with the name let
† and called (via tail recursion) at the bottom of the form unless
.
Indeed, all standard loop forms in Scheme use tail recursion. There is no escape from him.
† Here's what the named let
(fluent ‡ ) macro expands to:
(letrec ((loop (lambda (i)
(unless (> i 10)
(display i)
(newline)
(loop (+ i 1))))))
(loop 1))
‡ Strictly speaking, it macro expands to:
((letrec ((loop (lambda (i)
(unless (> i 10)
(display i)
(newline)
(loop (+ i 1))))))
loop)
1)
source to share
TR call/cc
will be unusable without a guarantee . The cycle itself can be achieved with which is part of the language . do
edit : this turned out to be wrong. See John Clement's comments on the question. The language can have a function call mechanism without TR, but it has a special separate mechanism for calling continuation.
source to share