semantics of recursion

[Tril]

Here's a clean (non-circular) way to do it in a book I'm reading.
Tennet, R.D., _Principles of Programming Languages_, Prentice-Hall, 1981.

The idea is a recursive definition is represented by the limit of a
sequence of longer and longer procedures. (see p. 132)

Example with a recursive procedure definition:
D(0) = procedure I { while 0<1 do NOOP }.
D(N) = procedure I { D(N-1), command }.

"command" is the body of the procedure, after left-factoring the
recursion.  Then the exact meaning of D is the limit as N goes to infinity
in D(N), because if N is sufficiently large, D(N) behaves the same as the
procedure we want (the limit) if it terminates before reaching D(0). If it
reaches D(0) it fails to terminate (I don't know why the author needs it
to fail to terminate, but seems to suggest that it's required for the
limit to work properly)...?

Likewise, for infinite domains, "The infinite domain that is the smallest
solution to a recursive domain definition is the <italic>limit</italic> of
a sequence of domain that 'approximates' it." (p. 39) 

I'll skip the example because I would have to explain the data model used
in the book.

The final place in this book with infinity is the semantics of iterations.
(p. 87)

The syntax of an arbitrary loop is "while E do C", which has the same
meaning as "if E then { C; while E do C }."  So,

C(0) = while 0<1 do NOOP
C(N) = if E then { COMMAND; C(N-1) }.

"The sequence of meanings C(0), C(1), C(2), ... is a sequence of better
and better approximations to the intended meaning of the while loop, in
that they represent the effect of more and more computation. [Take the
limit as N goes to infinity].  It can be proved that this limit is equal
to the meaning of [the command desired]."  (p. 88) 

David Manifold <dem@tunes.org>
This message is placed in the public domain.