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

tail recursion *is* semantic

From: gyro@ukulele.reasoning.com (Scott Layson Burson)
Subject: tail recursion

>But I don't think that this is a *semantic* property, for the very simple
>reason that it doesn't affect the *value* computed by any program under any
>circumstances; it only affects whether a given program can be run on a given

Actually it is a semantic issue. If your denotational semantics models a store
(which it must since Scheme has mutable values) then there should be a concept
of signalling an out-of-memory error when you try to allocate a cell but there
is no free memory. Presumably this would be conditional on the amount of memory
that your model is modelling, which would be fixed for a given invocation of
your language implementation on a given machine. Although most denotational
sematics supress this level of detail, to be a fully defined sematics it must be
concrete on this point.

Thus, if there exists a sufficiently large integer for which the value of some
tail-recursive procedure denotes out-of-memory-error (or bottom, or however you
model the notion in your semantics) when made to loop that many times but which
does not denote that same error when made to loop a small number of iterations,
then I would say your implementation is in violation of the Scheme
specification. Of course, this must be a fair tail-recursive loop, i.e. one that
does not otherwise consume memory, like by destructively consing elements onto a
global queue.

Again in defense of tail-recursion (somewhere along the line the discussion
seemed to turn to whether or not it was desireable), if I am not assured tail
recursion then I cannot implement meta-circular evaluators in an elegant,
straightforward way. If you make me resort to TAGBODIES with GOTOs then you
gross me out about as much as Bombin' LISP. I find this no less offensive than
calling for multiple namespaces in Scheme... moby-ick! ;-)