tail recursion

[harrison@sp21.csrd.uiuc.edu (Luddy Harrison)]

>> An implementation M of the language is properly tail-recursive if
>> there exists a constant K (dependent only on M), such that any program
>> running on M requires at most K times the amount of storage that the
>> same program would require to run on M0 (for the same inputs/state,
>> etc.).

>> By requiring X storage I mean that if the implementation is given X
>> units of storage, an out-of-memory condition does not arise during the
>> execution of the program.

Suppose that I implement Scheme for a dataflow machine, or for another
machine in which there is no notion of "storage".  (I would argue that
as complex as the memory systems of modern machines are becoming, this
is not as far-fetched as it might seem.)  It might be quite difficult
to make an analogy between M0 and my implementation.

>>I don't agree with you.  You can have semantics at different levels,
>>depending only on how much magnification you want out of the semantics
>>microscope.  It should not be hard to write a semantics with explicit
>>memory management where both of these properties are explicit.  Of
>>course, the semantics would be (in most ways) much less informative
>>than the usual semantics that ignores such aspects.

I disagree; the problem with a more operational semantics is not that
it is less informative, but precisely that it is too informative; that
is, it overspecifies the meaning of programs.  A (more nearly) fully
abstract semantics has the advantage of giving a "minimal"
characterization of program meanings, without resort to notions of
stacks, heaps, program counters, etc.

-Luddy Harrison