[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

tail recursion

   Date: Fri, 20 Apr 90 15:48:16 PDT
   From: mkatz@garlic.stanford.edu (Morris Katz)

      Date: 20 Apr 90  1316 PDT
      From: Dick Gabriel <RPG@sail.stanford.edu>

      [In reply to message from dyb@iuvax.cs.indiana.edu sent Fri, 20 Apr 90 14:34:47 -0500.]

      I'm not sure it's a well-defined term.

   Based on previous discussion with Luddy, I know that this is exactly the point
   he is trying to make.  His real question is how can one define tail recursion
   without appealing to a specific type of computer architecture.  What would it
   mean for Scheme to be or not to be tail recursive on some novel architecture
   which doesn't even have stacks, etc.  Is there some way that the characteristic
   which is desired can be specified through semantics rather than implementation?

No, of course not.  It's not a semantic property; it's an implementation
property.  As Jonathan Rees points out, it is a concept closely related to
garbage collection, the presence of which is also an implementation property,
not a semantic one.  Both of these implementation properties have indirect
semantic consequences, however, in that they make it possible *in practice* to
write programs in a certain style which some people like; without these
properties, the execution of programs written in that style would make (what is
judged to be) inadequately effective use of the hardware resources available.
Would they be considered important on every imaginable architecture?  Who knows?

-- Scott