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

tail recursion

    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.

However you map my definition into the resource model for your machine
there are still two possibilities:

- Your implementation never runs out of resources (I find this hard to
believe).  Since I can't tell the difference between your
implementation and a properly tail-recursive one, the issue is moot.

- Your machine can run out of resources.  Then the requirement imposes
that the mapping between your resources and M0 be such that the
resource requirement is at worst linear with respect to the storage
requirement of M0.  If your implementation doesn't do this, then it is
not a real Scheme.  Call it non-tail-recursive-scheme, or whatever,
and I may even like it and use it, but it is not Scheme (as currently

A deeper question is whether Scheme (with it's applicative semantics
and imperative constructs, etc.) is an appropriate language for such a
machine.  You may find that tail recursion is not the problem, but the
whole model of the language, and that you have to scrap it then.
Until parallelism is understood better, I don't think you'll be able
to convince me that such a restriction is better or worse than any
other (such as the restrictions imposed by applicative order

    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.

All semantics are just restrictions on how an implementation of the
language may not behave.  How much you want to restrict it or not is a
matter of style or taste.

I think that the definition that I sent is valid, but you don't like
it.  On the other hand, I think that what you really don't like is the
restriction, not the way in which I phrased it.  We can argue forever
on whether it is a good restriction or not, but perhaps we can agree
on what the restriction is interpreted to mean, which is what I
thought your original question was about.