# semantics of recursion

**RE01 Rice Brian T. EM2**
BRice@vinson.navy.mil

*Thu, 10 Dec 1998 13:49:32 +0800*

>* 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 }.
*>*
*non-circular definition? The last time that I checked, finite systems could
only define integers by recursion, and your 'N' would be an inscrutable
entity to any system _without_ a non-circular definition.
>* 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)
*>*
*well, that is an _enumerable_ domain, but how do you deal with arbitrarily
infinitary structures?
>* 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)
*>*
*too vague. personally, i'd prefer to strart with a clean slate (without
COMMANDs). the arrow development is moving in the right direction. that's
enough for me.