Re: Term Rewriting vs. Functional Programming

Matthias Blume <find@xxxxxxxxxxxxxxxxxxxx> wrote:
> Vesa Karvonen <vesa.karvonen@xxxxxxxxxxxxxx> writes:

> One reason is that without a more thorough account for _all_ space
> usage, there is not much point in specifying it. Consider the
> following program:

> let fun f x = f (1 + x)
> in f 0
> end

> You would expect that with the requirement for tail-call elimination
> in place, this code would run in constant space (until it overflows
> the integer range), right?

Like you say, it depends on the function that + is bound to.

Frankly, I find this "hidden assumption" argument a bit silly. It is quite
clear to me (and I assume to most) that you can write programs that are
tail recursive, but will always consume arbitrary amounts of space. Here
is a much clearer example:

val bs : bool list ref = ref []
fun loop b = (bs := b :: !bs ; loop (not b))
val () = loop true

> In SML/NJ, "stack overflow" and "heap overflow" are the same thing.

I know, but I can't see how it would make the case for tail call
elimination (or space safety in general) any less important. I find it
crucial to be able to reason about space requirements. The difference
between O(1) and O(n) space usage is not insignificant.

> You seem to assume that the stack of the abstract machine implied by
> the OpSem in the definition is meant to have a manifest counterpart

[No, I don't.]

> Those are assumptions about implementations which are likely true, but
> which, if you want to require them, would take a whole lot more
> specification work.

I would personally be happy with a semi-formal specification. "I know tail
call elimination when I see it." (-:

-Vesa Karvonen
.

Relevant Pages

  • Re: "The reason...is because..."
    ... If the grammar is wrong but the error overlooked because of the ... close connection between 'reason' and 'because', ... subordinating conjunctions and serving as predicate nominatives ... usage books, both on and off the Web. ...
    (alt.usage.english)
  • Re: Term Rewriting vs. Functional Programming
    ... the compiler optimizes tail calls. ... > quite happy with a simple syntactic definition of tail calls, ... > reason about the space usage of their programs. ... - Don't specify unless you specify completely enough so that the ...
    (comp.lang.functional)
  • Re: Gender and sex
    ... I think this is for the same reason it's bad as a Scrabble ... current state of the language. ... on gender makes no reference to anything but grammatical gender. ... usage, and protect them from the whim of the hoi polloi. ...
    (talk.origins)
  • Re: [Q] Heli tail rotor direction T-rex vs. the real thing
    ... Nearly all pictures of a real heli ... Cobra's from Bell had the tail rotor on one side, ... blade moving forwards or low blade moving backwards), ... I don't no the reason for this but its a interesting topic. ...
    (rec.models.rc.helicopter)
  • Re: "The reason...is because..."
    ... If the grammar is wrong but the error overlooked because of the ... close connection between 'reason' and 'because', ... noun.") Such structures are quite grammatical and can make perfectly ... usage books, both on and off the Web. ...
    (alt.usage.english)