Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!samsung!spool2.mu.edu!news.cs.indiana.edu!sjohnson@iuvax.cs.indiana.edu
From: sjohnson@iuvax.cs.indiana.edu (Steve Johnson)
Newsgroups: comp.theory
Subject: Re: recursive =?=> iterative ?
Message-ID: <1991Jan22.154803.10217@news.cs.indiana.edu>
Date: 22 Jan 91 20:47:26 GMT
References: <1991Jan17.160716.292@lth.se> <1991Jan19.182618.7727@sbcs.sunysb.edu> <2665@wn1.sci.kun.nl>
Organization: Computer Science, Indiana University, Bloomington
Lines: 64

In article <2665@wn1.sci.kun.nl> eerke@cs.kun.nl (Eerke Boiten) writes:
>General linear recursive functions, of the form
>	f(x) = if P(x) then H(x) else E(x,f(K(x))) fi
>cannot, in general, be translated into iterative form without using
>stacks. This is proved by Paterson and Hewitt [Pat70].

As I'm sure many will point out, the result in Paterson&Hewitt states
that NON-linear recursion schemes cannot be translated to iterative form
(i.e. expressed as a flow chart).  The proof is done by showing the scheme

  f(x) = if P(x) then x else H(f(L(x)), f(R(x)))

cannot be so translated.  The tree-pebbling argument is reproduced
in several places, including Manna's book [1].  Theorem 2 of [Pat70]
states that linear schemes are translatable and gives a construction
(in the form of a flow chart).  Strong developed a stronger notion
of translatability (between recursion schemes and flowcharts)--- I
think he called it "operational translatability"---which isolates the
iterative schemes from the linear schemes.

For the case of linear schemes, it is helpful to look at the simpler
case:

  f(x) = if P(x) then x else E(f(K(x))

The difference is that the value of `x' is not saved in the call to E.
A iterative system of two functions computes this value, which
is f(a) = E^n(K^n(a)) for some n.

   g(x, y) = if P(x) then h(x, y) else g(K(x), y)

   h(x, y) = if P(y) then x else h(E(x), K(y))

g(a, a) first computes K^n(a) while saving the original value of a for later.
h(K^n(a), a) computers E^n(K^(a)).  Applications of P are serving as
a counter.  Intuitively, g and h take twice as long to computer their result
as f takes (if you count defined-function calls, say, or applications of
P).  The more general linear scheme given earler is trickier to write
and, by the intuitive measure, takes quadratic time.

A couple of other good references to these topics are Greibach's lecture
notes [2] and Cohen's doctoral thesis [3].  I should also mention an
article by Wand [4] in which he explores using analysis of continuations
to determine whether control could be represented in something simpler
than a stack (e.g. an accumulator, a bit, a counter, etc.).

I hope that the originator of this note will post the collection of
references accumulated.

[Pat70] {from the original note}
   Paterson, M.S. and Hewitt, C.E., Comparative Schematology,
   Record of the Project MAC Conf. on Conc.Syst. Par.Comp.,
   Woods Hole, Mass., 1970, ACM, New York, 119--127

[1] Zohar Manna, Theory of Computation. McGraw Hill, New York, 1974

[2] Sheila A. Greibach. Theory of Program Structures: Schemes, Semantics,
    Verification.  Springer LNCS vol. 36, Springer, Berlin, 1975.

[3] Norman H. Cohen. Source-to-source Improvement of Recursive Programs,
    Ph.D. Dissertation, Harvard Univ., Cambridge, Mass. (USA), 1980

[4] Mitchell Wand, Continuation based program transformations strategies,
    JACM 27(1):164-180 (January 1980)