r5rs-z-h-6.html

scheme 标准（r5rs）。Scheme是MIT发布的基于Lambda运算的语言

An object fetched from a location, by a variable reference or by
a procedure such as <tt>car</tt>, <tt>vector-ref</tt>, or <tt>string-ref</tt>, is
equivalent in the sense of <tt>eqv?</tt> (section&nbsp;<a href="r5rs-Z-H-9.html#%_sec_6.1">6.1</a>)
to the object last stored in the location before the fetch.<p>

Every location is marked to show whether it is in use.
No variable or object ever refers to a location that is not in use.
Whenever this report speaks of storage being allocated for a variable
or object, what is meant is that an appropriate number of locations are
chosen from the set of locations that are not in use, and the chosen
locations are marked to indicate that they are now in use before the variable
or object is made to denote them.<p>

In many systems it is desirable for constants<a name="%_idx_72"></a> (i.e. the values of
literal expressions) to reside in read-only-memory.  To express this, it is
convenient to imagine that every object that denotes locations is associated
with a flag telling whether that object is mutable<a name="%_idx_74"></a> or
immutable<a name="%_idx_76"></a>.  In such systems literal constants and the strings
returned by <tt>symbol-&gt;string</tt> are immutable objects, while all objects
created by the other procedures listed in this report are mutable.  It is an
error to attempt to store a new value into a location that is denoted by an
immutable object.<p>

<a name="%_sec_3.5"></a>
<h2><a href="r5rs-Z-H-2.html#%_toc_%_sec_3.5">3.5&nbsp;&nbsp;Proper tail recursion</a></h2><p>

<p>

Implementations of Scheme are required to be
<em>properly tail-recursive</em><a name="%_idx_78"></a>.
Procedure calls that occur in certain syntactic
contexts defined below are `tail calls'.  A Scheme implementation is
properly tail-recursive if it supports an unbounded number of active
tail calls.  A call is <em>active</em> if the called procedure may still
return.  Note that this includes calls that may be returned from either
by the current continuation or by continuations captured earlier by
<tt>call-with-current-continuation</tt> that are later invoked.
In the absence of captured continuations, calls could
return at most once and the active calls would be those that had not
yet returned.
A formal definition of proper tail recursion can be found
in&nbsp;[<a href="r5rs-Z-H-14.html#%_sec_7.3">8</a>].<p>

<blockquote><em>Rationale:&nbsp;&nbsp;</em><p>

Intuitively, no space is needed for an active tail call because the
continuation that is used in the tail call has the same semantics as the
continuation passed to the procedure containing the call.  Although an improper
implementation might use a new continuation in the call, a return
to this new continuation would be followed immediately by a return
to the continuation passed to the procedure.  A properly tail-recursive
implementation returns to that continuation directly.<p>

Proper tail recursion was one of the central ideas in Steele and
Sussman's original version of Scheme.  Their first Scheme interpreter
implemented both functions and actors.  Control flow was expressed using
actors, which differed from functions in that they passed their results
on to another actor instead of returning to a caller.  In the terminology
of this section, each actor finished with a tail call to another actor.<p>

Steele and Sussman later observed that in their interpreter the code
for dealing with actors was identical to that for functions and thus
there was no need to include both in the language.<p>

</blockquote><p>

A <em>tail call</em><a name="%_idx_80"></a> is a procedure call that occurs
in a <em>tail context</em>.  Tail contexts are defined inductively.  Note
that a tail context is always determined with respect to a particular lambda
expression.<p>

<p><ul>
<li>The last expression within the body of a lambda expression,
shown as &lt;tail expression&gt; below, occurs in a tail context.
<tt><p>(lambda&nbsp;&lt;formals&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;definition&gt;*&nbsp;&lt;expression&gt;*&nbsp;&lt;tail&nbsp;expression&gt;)<br>
<p></tt>
<li>If one of the following expressions is in a tail context,
then the subexpressions shown as &lt;tail expression&gt; are in a tail context.
These were derived from rules in the grammar given in
chapter&nbsp;<a href="r5rs-Z-H-10.html#%_chap_7">7</a> by replacing some occurrences of &lt;expression&gt;
with &lt;tail expression&gt;.  Only those rules that contain tail contexts
are shown here.<p>

<tt><p>(if&nbsp;&lt;expression&gt;&nbsp;&lt;tail&nbsp;expression&gt;&nbsp;&lt;tail&nbsp;expression&gt;)<br>
(if&nbsp;&lt;expression&gt;&nbsp;&lt;tail&nbsp;expression&gt;)<br>
<br>
(cond&nbsp;&lt;cond&nbsp;clause&gt;<sup>+</sup>)<br>
(cond&nbsp;&lt;cond&nbsp;clause&gt;*&nbsp;(else&nbsp;&lt;tail&nbsp;sequence&gt;))<br>
<br>
(case&nbsp;&lt;expression&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;case&nbsp;clause&gt;<sup>+</sup>)<br>
(case&nbsp;&lt;expression&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;case&nbsp;clause&gt;*<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;&lt;tail&nbsp;sequence&gt;))<br>
<br>
(and&nbsp;&lt;expression&gt;*&nbsp;&lt;tail&nbsp;expression&gt;)<br>
(or&nbsp;&lt;expression&gt;*&nbsp;&lt;tail&nbsp;expression&gt;)<br>
<br>
(let&nbsp;(&lt;binding&nbsp;spec&gt;*)&nbsp;&lt;tail&nbsp;body&gt;)<br>
(let&nbsp;&lt;variable&gt;&nbsp;(&lt;binding&nbsp;spec&gt;*)&nbsp;&lt;tail&nbsp;body&gt;)<br>
(let*&nbsp;(&lt;binding&nbsp;spec&gt;*)&nbsp;&lt;tail&nbsp;body&gt;)<br>
(letrec&nbsp;(&lt;binding&nbsp;spec&gt;*)&nbsp;&lt;tail&nbsp;body&gt;)<br>
<br>
(let-syntax&nbsp;(&lt;syntax&nbsp;spec&gt;*)&nbsp;&lt;tail&nbsp;body&gt;)<br>
(letrec-syntax&nbsp;(&lt;syntax&nbsp;spec&gt;*)&nbsp;&lt;tail&nbsp;body&gt;)<br>
<br>
(begin&nbsp;&lt;tail&nbsp;sequence&gt;)<br>
<br>
(do&nbsp;(&lt;iteration&nbsp;spec&gt;*)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&lt;test&gt;&nbsp;&lt;tail&nbsp;sequence&gt;)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;expression&gt;*)<br>
<br>
where<br>
<br>
&lt;cond&nbsp;clause&gt;&nbsp;---&gt;&nbsp;(&lt;test&gt;&nbsp;&lt;tail&nbsp;sequence&gt;)<br>
&lt;case&nbsp;clause&gt;&nbsp;---&gt;&nbsp;((&lt;datum&gt;*)&nbsp;&lt;tail&nbsp;sequence&gt;)<br>
<br>
&lt;tail&nbsp;body&gt;&nbsp;---&gt;&nbsp;&lt;definition&gt;*&nbsp;&lt;tail&nbsp;sequence&gt;<br>
&lt;tail&nbsp;sequence&gt;&nbsp;---&gt;&nbsp;&lt;expression&gt;*&nbsp;&lt;tail&nbsp;expression&gt;<br>
<p></tt>
<li>If a <tt>cond</tt> expression is in a tail context, and has a clause of
the form <tt>(&lt;expression<sub>1</sub>&gt; =&gt; &lt;expression<sub>2</sub>&gt;)</tt>
then the (implied) call to
the procedure that results from the evaluation of &lt;expression<sub>2</sub>&gt; is in a
tail context.  &lt;expression<sub>2</sub>&gt; itself is not in a tail context.<p>

</ul><p><p>

Certain built-in procedures are also required to perform tail calls.
The first argument passed to <tt>apply</tt> and to
<tt>call-with-current-continuation</tt>, and the second argument passed to
<tt>call-with-values</tt>, must be called via a tail call.
Similarly, <tt>eval</tt> must evaluate its argument as if it
were in tail position within the <tt>eval</tt> procedure.<p>

In the following example the only tail call is the call to <tt>f</tt>.
None of the calls to <tt>g</tt> or <tt>h</tt> are tail calls.  The reference to
<tt>x</tt> is in a tail context, but it is not a call and thus is not a
tail call.
<tt><p>(lambda&nbsp;()<br>
&nbsp;&nbsp;(if&nbsp;(g)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((x&nbsp;(h)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(and&nbsp;(g)&nbsp;(f))))<br>
<p></tt>
<blockquote><em>Note:&nbsp;&nbsp;</em>
Implementations are allowed, but not required, to
recognize that some non-tail calls, such as the call to <tt>h</tt>
above, can be evaluated as though they were tail calls.
In the example above, the <tt>let</tt> expression could be compiled
as a tail call to <tt>h</tt>. (The possibility of <tt>h</tt> returning
an unexpected number of values can be ignored, because in that
case the effect of the <tt>let</tt> is explicitly unspecified and
implementation-dependent.)
</blockquote><p>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<p>
<p><div class=navigation>[Go to <span><a href="r5rs.html">first</a>, <a href="r5rs-Z-H-5.html">previous</a></span><span>, <a href="r5rs-Z-H-7.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="r5rs-Z-H-2.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="r5rs-Z-H-15.html#%_index_start">index</a></span>]</div><p>

</body>
</html>