Re: Term Rewriting vs. Functional Programming

Vesa Karvonen <vesa.karvonen@xxxxxxxxxxxxxx> writes:

> Matthias Blume <find@xxxxxxxxxxxxxxxxxxxx> wrote:
>> Vesa Karvonen <vesa.karvonen@xxxxxxxxxxxxxx> writes:
>
>> How so? What does this have to do with portability?
>
> Perhaps it is a false impression, but it seems to me that most SML
> programs assume that tail recursion runs in constant space. I know I've
> written such SML code. I know that others do it too. The CML book, for
> instance, contains several examples that would be totally useless without
> tail call elimination. Who wants a server that is guaranteed to run out of
> space (without tail call elimination)?

Yes. But they would also be useless if Int.+ ate up space. My point
(and Andreas' point) was that the ML definition simply does not extend
into this territory at all. Reasonable implementations, of course,
will eliminate tail calls (i.e., implement them as jumps).

>> If you require anything at all, you must go all the way. Anything less
>> that that is misleading (and therefore a mistake).
>
> Sounds basically reasonable. I'm not totally convinced by the argument
> based on IntInf, though. It is clear that the program will eventually run
> out of space. I find the behavior of the following program more relevant:
>
> fun loop b = loop (not b)
> val () = loop true

Same problem. Only if you specify that "not" does not use space can
you argue that this runs in constant space.

.

Loading