Joerg Mertens <
joerg-mertens@t-online.de> writes:
Julieta Shem <jshem@yaxenu.org> writes:
What do you mean iterative? For instance, Gerald Sussman and Harold
Abelson classify as `iterative' the procedure
(def (f n [acc 1])
(if (= n 1)
1
(f (dec n) (* acc n)))),
which is self-referential.
Are you sure? IIRC they differentiate between programs and processes.
They do --- between ``procedures'' and processes.
So your function would be a recursive program but it doesn't create a recursive process (assumed the implementation is tail call optimized).
On section 1.2.1, Figure 1.4 is roughly
--8<---------------cut here---------------start------------->8---
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720
Figure 1.4: A linear iterative process for computing 6!.
--8<---------------cut here---------------end--------------->8---
You're right that they don't call it an iterative /procedure/, but they
do call it an iterative /process/. So maybe I can fix my post with
--8<---------------cut here---------------start------------->8---
[They] classify as `iterative' the process generated by the procedure
(def (f n [acc 1])
(if (= n 1)
1
(f (dec n) (* acc n)))),
which is self-referential.
--8<---------------cut here---------------end--------------->8---
Here's their words directly:
--8<---------------cut here---------------start------------->8---
Consider the [linearly recursive naive factorial procedure]. The
substitution model reveals a shape of expansion followed by contraction, indicated by the arrow in figure 1.3. The expansion occurs as the
process builds up a chain of deferred operations (in this case, a chain
of multiplications). The contraction occurs as the operations are
actually performed. This type of process, characterized by a chain of
deferred operations, is called a recursive process. Carrying out this
process requires that the interpreter keep track of the operations to be performed later on. In the computation of n!, the length of the chain of deferred multiplications, and hence the amount of information needed to
keep track of it, grows linearly with n (is proportional to n), just
like the number of steps. Such a process is called a linear recursive
process.
By contrast, the second process [the fact-iter procedure of Figure 1.4]
does not grow and shrink. At each step, all we need to keep track of,
for any n, are the current values of the variables product, counter, and max-count. We call this an /iterative process/. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state
variables should be updated as the process moves from state to state and
an (optional) end test that specifies conditions under which the process
should terminate. In computing n!, the number of steps required grows
linearly with n. Such a process is called a linear iterative process. --8<---------------cut here---------------end--------------->8---
They constrast the two notions:
--8<---------------cut here---------------start------------->8---
In contrasting iteration and recursion, we must be careful not to
confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring
to the syntactic fact that the procedure definition refers (either
directly or indirectly) to the procedure itself. But when we describe a
process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a
procedure is written. It may seem disturbing that we refer to a
recursive procedure such as fact-iter as generating an iterative
process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep
track of only three variables in order to execute the process. --8<---------------cut here---------------end--------------->8---
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)