RECURSION SCHEMES

More specifically, the basic notions of a Turing Machine, of computable functions and of undecidable properties are needed for Chapter VI (Decision Problems) the definitions of recursive, primitive recursive and partial recursive functions are helpful for Section F of Chapter IV and two of the proofs in Chapter VI. The basic facts regarding regular sets, context-free languages and pushdown store automata are helpful in Chapter VIII (Monadic Recursion Schemes) and in the proof of Theorem 3.14. For Chapter V (Correctness and Program Verification) it is useful to know the basic notation and ideas of the first order predicate calculus a highly abbreviated version of this material appears as Appendix A. 

We shall return to the concept of value languages later in our study of monadic recursion schemes this concept is a powerful tool in studying the relative power of monadic program schemes and monadic recursion schemes. For the present we need only the following simple fact. 

In this chapter we start the discussion of an alternative model for programs, designed to reflect recursive properties of programming languages. We shall see that this model does indeed represent an augmentation of the flowchart model we have been studying up to now. One topic of concern will be when recursion equations can be translated into flowchart form - when recursion schemes are flowchartable. 

Our general results on the comparison of flowchart schemes and recursion schemes will be ... 

All flowchart schemes can be translated into recursion schemes. 

There are recursion schemes not translatable into flowchart schemes. 

It is undecidable whether a recursion scheme is translatable into a flowchart scheme. 

Every recursion scheme can be translated into a flowchart scheme augmented by one pushdown store. 

Recursion schemes are equivalent to procedure augmented flowchart schemes. 

In the special case of monadic recursion schemes, we shall see in Chapter VIII that The classes of monadic recursion schemes and monadic flowchart schemes are incomparable. 

DEFINITION A recursion scheme is a finite set of recursion equations and a designated initial defined function letter F such that ... 

An interpretation of a recursion scheme is defined similarly to an interpretation of a flowchart scheme. The interpretation assigns meanings to constants, predicate letters and basis function letters found in the scheme but does not, of course, assign meanings to defined function letters. A free interpretation is likewise defined as usual, to have as domain the set of all terminal terms over the set of variables, constants and basis function letters found in the scheme. 

The definition of computation in a recursion scheme is a little more complicated than for a flowchart scheme. Computations are defined from the inside out when the equation has nested defined function letters. It has been shown by B. Rosen that evaluating recursion equations from the inside out produces a system with the... 

DEFINITION Let S be a recursion scheme with initial equation Fg(x, ...,x ). ... 

We can prove the same relationship between computations under arbitrary interpretations and computations under free interpretations that we did for flowchart schemes, defining U(S) for a recursion scheme S in the same way as for a program scheme. We state it without proof. 

THEOREM 7.1 Let S be a recursion scheme and I an interpretation with input a. Let I be the free interpretation obtained from I by setting for each predicate letter T... 

We first illustrate our definitions with a computation under a free interpretation, Consider the recursion scheme with one equation ... 

As we did for program schemes, one can establish the following result for recursion schemes ... 

THEOREM 7.2 Recursion schemes 3 and S are strongly equivalent if and only if (S,I) is strongly equivalent (S, I) for every free (Herbrand) interpretation I. ... 

If we try to define a "free" recursion scheme in the same way we defined a free program scheme - every path is an execution sequence - we find that although the intuitive meaning is clear, it is very hard to formalize this concept. Exactly how should one define a "path" in a recursion scheme Or an "execution sequence" It is possible to do so by a moderately complex tree recursion. argument. Instead we will give a "syntactic" definition akin to the one we established as a theorem for program schemes. 

DEFINITION A recursion scheme S is free if for every free interpretation I and every m-place test T in S, T is never applied twice to the same m-tuple (t-, ...,t ) of members of U(S) during the computation (S,I, X). ... 

There are various ways we can extend or restrict the definition of recursion scheme without affecting computing power. Some of these are very useful. We shall give two such results, leaving the proof to the reader. 

LEMMA 7.3 Let R be the family of recursion schemes. Let R be the family of schemes obtained by extending R to allow equations... 

DEFINITION A recursion scheme S with initial function Fg is simple if... 

DEFINITION A recursion scheme is linear if all its equations are linear. 

DEFINITION A recursion scheme is monadic if all its functions, basis, predicate and defined, are monadic. 

LEMMA 7.H The classes of recursion schemes and of simple recursion schanes are effectively intertranslatable. Furthermore, every recursion scheme S can be effectively translated into a simple recursion scheme S such that if S is linear, monadic or linear monadic, then S is linear, monadic or linear monadic. 

In this section we show that recursion schemes are more powerful than flowchart or program schemes. Our first result is the effective translatability of program schemes into recursion schemes. In section D we shall see a stronger form of this result, when we augpsnt our flowchart schemes with procedures. 

THEOREM 7.5 The class of program schemes with one output variable is effectively translatable into the class of recursion schemes. 

This result should be compared with the next one which exhibits a recursion scheme which cannot be converted to flowchart form. 

---