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.