I think this discussion is getting off-topic, and doesn't really apply
to the point I was trying to make.

But I enjoy nit-picking about semantics, and will gladly join you.

BM> The only reason that terminates is if there's a stack overflow.
BM> That's an implementation limitation, not part of the semantics.
BM> Nowhere in the CL specification does it require that the stack
BM> must have a limited size.

There are two ways of understanding a specification ``assuming
unbounded resources'':

(i) assuming availability of potentially unbounded resources, said
program does FOO; and

(ii) there exists a finite (but arbitrarily large) amount of resources
within which said program does FOO.

Obviously, you're thinking in terms of (i), while I'm thinking in
terms of (ii).  (Exercice for the reader: specify a class of
properties FOO such that (i) and (ii) coincide.)

BM> The virtual machine described by the standard has infinite memory,

I will grant you that most well-known formal semantic frameworks do
not deal with resource tracking at all, and therefore use model (i).
It is not clear to me, however, which model is used by the CL
standard, or whether the CL standard is explicit about the issue in
the first place.  Perhaps Kent can enlighten us?

Fair enough.

I think we're back to a rather fundamental problem, which is that of
program equivalence.

In practical terms, would you accept a definition of program
equivalence that identifies a program which runs in constant space
with one which runs in linear space?

I think that one can fairly argue for both answers.  (``Fairly,'' in
this context, means ``without invoking Adam Smith's Invisible Appendages.'')

I don't purport to be a mathemetician, but my understanding is that
the question of a discontinuity than a mere question of resources.
That is, a function whose value goes to infinity at a certain point is
different than "gee, that function goes off my page of graph paper"
and different even than "gee, I'll never be able to buy enough graph
paper to show where that function tops out" to the point of "If I set
out to buy graph paper sufficient to try to show where that function
tops out, I would never do anything afterward because there is no end
to it."  Also, I don't think it's the same to say "I recognize that
pursuing that purchase of graph paper is not worth doing; I'd better stop
here and do something else." (which is what I'm saying, with emphasis
on "STOP", meaning the program is done) and "I recognize that
pursuing that purchase of graph paper is not worth doing, so I'll just
blythely continue with the next step as if it didn't matter that I
skipped an instruction and I'll pretend nothing that followed was contingent
on my successful completion of the prior step" which is a very "C-language"
thing to do but which is NOT what I see Lisp as being about.

  If there is no upper bound on the consumption of resources of a program,
  it is ipso facto _broken_, and no silly quibbling over which resource is
  exhausted _first_ can possibly change any semantics of said program.

  It is _typical_ that this has to come up in relation to a Scheme concept.

Given some problem with a well-defined notion of input size, and given
two (correct) programs that solve this problem, one of which does so
in bounded space, the other in linear space, can the two programs be
considered as equivalent?

I think one can argue both ways.  (Or else: the correct notion of
equivalence depends on the application.)

KMP> my understanding is that the question of a discontinuity than a
KMP> mere question of resources.

Both Barry and I have been very careful to avoid the term ``infinite''.
We were speaking of unbounded resources.

When modelling a finitary process such as deterministic computation,
infinity can only appear as the limit of an unbounded process.  Thus,
the question of whether the process is continuous cannot even be
formulated: the very assumption that leads us to introduce the notion
of infinity is that the process is continuous.

If you prefer, we were not even considering the notion of actual
infinity.  The largest (in some intuitive sense) notion we were
willing to consider was that of potentially unbounded usage of
resources: a usage that remains finite at any time, but with no a
priori bound.

This modern form of mysticism, ``the market's invisible hand.''

Yes, we fully agree about that.  There is no such thing as an actually
infinite amount of work.  This was emphatically not the issue I was
trying to get you to comment on.

We agree about that, I am definitely not.

As you say, there is no ambiguity.  With any reasonable semantics, the
programs (loop) and (progn (loop) (error "Foo!")) are equivalent.

On the other hand, consider the following:

  (defun foo ()
    (foo))

and suppose that you compile FOO without tail-call elimination.  Does
FOO terminate?

The obvious answer is that my machine has finite memory, hence FOO
will run out of stack at some point, hence FOO terminates on my
machine.  This answer invokes a specific maximum stack size, and so is
not acceptable as part of a language definition.

The answer that the best-known formal semantic frameworks give is that
assuming a potentially unbounded stack, FOO will never run out of
resources, hence FOO doesn't terminate.  I claim that this answer is
not realistic.

Finally, you can say that, assuming any arbitrarily large but finite
amount of stack, FOO will terminate.  As FOO terminates in all finite
models, FOO terminates.  I claim that this last answer is more
realistic than the second one while avoiding mentioning a specific
amount of available resources.

The point I'm trying to make is that FOO terminates when compiled
without tail call elimination, and that FOO does not terminate if
compiled with tail call elimination.  Thus, tail call elimination is
not a mere optimisation, but a semantic feature.

And, incidentally, a feature that I miss in my favourite programming
language.

Regards,

  Again, it is typical that this discussion centers around a Scheme feature.

It's been a long time since I had to deal with these.  Is "normal
order" the one where you don't have to do things in order?  If so, you
should remember that "reasonableness" is like "goodness"--it depends
on context and is not a universal property of the universe.  In CL,
evaluation works left to right, so you have to first dispense with one
form to get to the next. If you are unable to dispense with a certain
form, you're done.

[...]

EN>   This is just plain wrong.  Your semantic feature rests on an
EN>   equivocation between termination and crashing.

No.  It rests on *distinguishing* between non-termination and
the signalling of STORAGE-CONDITION.

Suppose you identify signalling a condition and not terminating, i.e.

  (loop)

and

  (error "Foo!")

are equivalent.

Then (assuming a compositional semantics) you have to identify

  (progn (ignore-errors (loop)) t)

and

  (progn (ignore-errors (error "Foo!")) t)

If you choose to identify the latter program with T (a rather natural
hypothesis), and the former one with (LOOP), then you've just identi-
fied (LOOP) with T.  With a little more work (and some similarly
natural hypotheses), you've just identified all Lisp programs.

Not a very interesting semantics.

                                        Juliusz

P.S. Okay, I've cheated.  Whether a stack overflow generates a
STORAGE-CONDITION or causes a nuclear holocaust is ``implementation-
defined'' in ANSI Common Lisp.  Still, I think it's natural to
distinguish between a ``crash'' and non-termination.

I understand that.  I wasn't complaining about the vendors' behaviour,
but about the guarantees given by the standard being too weak for my
personal programming style.

People like you have taught me to program by the book, not for the
implementation.  The lack of strong guarantees about tail-call
elimination in the book forces me to program for the implementation
(or to give up on a number of techniques that I happen to find useful).

Of course, I am not implying that you (plural) have done anything
wrong when designing ANSI Common Lisp.  I am quite willing to believe
that this was the right compromise at the time (possibly for the very
same reasons as the ones you gave recently for the omission of a MOP).

Regards,

We specifically chose English because it was democratic and accessible to
the programming community we needed to reach, such as myself, for example.
I am far from the "guiding force" behind CL. I was there, I had a lot of
opinions that got incorporated, and I was the "neutral editor" once votes
were taken.  But people like Steele and Gabriel were there and fully
aware of enough issues of formal semantics that they could have objected at
any time if we were too far afield.  My own personal understanding of
semantics says that something is "semantically well-formed" if I think I can
read it and understand it and implement it without ambiguity.  I'm sorry
that's probably not very scientific, but I've found it operationally
useful over the years.  The things I intuitively see as semantically
well-formed seem to be exactly the set of things the math guys are happy
describing, given that they ever take the patience to properly describe
it and don't just dive in with prefab scaffolding of some system they like
to use and hope it works in the current situation.

The system we use describes BOTH a virtual semantics in which you can recurse
indefinitely and not worry about stack, in which you can cons indefinitely
and not worry about heap, etc.  AND a practical semantics in which you can
limit these things and still be a correct implementation.  A conforming
implementation must not tell the user he has made a semantic violation if
he depends on stack to be too deep--SERIOUS-CONDITION is ok, but ERROR is
not. Ditto for consing too much, though handling that case is going to be
hard for other reasons.  Still, it doesn't make an implementation
non-conforming.

(ignore-errors (loop)) does not terminate.

neither does

(defun foo () (foo))
(ignore-errors (foo))

The latter, though, creates a resource violation in some (but not all)
implementations.  This is permitted.  And Lisp is reflective, so the
resource violation is permitted to be signaled.  It would be an unuusal
Lisp that signaled a resource violation for (ignore-errors (loop)) but
technically I think signalling a TIME-EXHAUSTED situation would be
permissible, as long as it was a serious condition and not an error.
It should not be trapped by IGNORE-ERRORS.

Lisp does allow even resource limitations to be trapped, so any formal
semantics you apply must be one that deals not only with bottom and its
infections nature compositionally, but also with some operator that can
trap bottom and keep it in check, at least some of the time.  My intuitive
sense is that this is overpowerful and probably gets messy becuase it's
got analogies to a system with both an unstoppable force and an
infinite barrier.  One has to give.  Probably it will be the unstoppable
force, since writing infinite barriers probably can't keep lisp from
stopping.  But conceptually, Lisp creates a reflective battleground in
which the struggle is permitted to take place.  And if it's uncomputable
who will win, that's too bad, because in practice it's still worth trying
to navigate this space in the name of robustness.  I would not want a weaker
language just becuase it promised more deterministic behavior.

ERROR is trapped because it involves a semantic violation.

(defun common-lisp ()
  (write-string "Resources exhausted."))

It probably also dumps out into a killer-small hello world, by the way, for
those who like to optimize such things and worry that CL has missed that boat.

CL has the notion of an ideal semantics separate from the notion of an
implemented semantics.  I'm sorry if the semantics community doesn't
like that, but they'll just have to deal.  We describe arbitrary
precision integers but we don't require all conforming processors to
have the memory needed to house them.  We assume describe programs
that can have arbitrary stack depth but we leave it to implementations
to sort out how deep the stacks really are and whether they are
extensible.  We SAY that these are not to be identified as errors but
as resource limitations.

bye,
Jochen

Sure.

The question is the other way around: would it make sense for a
hypothetical future standard to require that a given piece of code is
*not* allowed to signal STORAGE-CONDITION or crash?  In other words,
is there a technically correct way to *mandate* tail-call elimination
in a (hypothetical) standard of the quality of ANSI CL.

My claim is that there is; but this claim relies fundamentally on the
fact that STORAGE-CONDITION *is* different from looping.

In the rest of the discussion, you would appear to have dualised my
position: I am claiming that non-termination and signalling a
condition (or crashing) *are* different results...

...which you would appear to at least partly agree with.

Regards,

I will say that I have in the past advocated that the standard would
be more useful if it told you things like "the worst case time in
doing a AREF will be O(1)" vs "the worst case time in doing ELT will
be O(n) for lists of length n or O(1) for arrays".  There are places
where we've left it open and as a consequence an implementation can do
really stupid things that are baffling to users.  SET-FILE-POSITION
was discussed recently; some people expect it to be O(1) and if it's
O(n) [for n=filepos], that's pretty scary.  But the consensus was that
this should be left to an implementation.

To some extent, one might characterize my position as "there are
bigger fish to fry than tail recursion" or one might say "it's just
not consistent with the overall design to talk about memory use when
nothing really does".  You might appeal back to the "infinity" vs "finite"
argument and say it was particularly important for the tail call case;
I don't know.  I'd rather tail call elimination be under OPTIMIZE
declaration control and not a required feature of the language, so that
kind of issue would need to get factored in, too.

And then there's the practical matter that the current climate is that none
of this rises to the level of it being worth it to the community to change
the standard.  Merely opening the standard for the fixing of ANY technical
item exposes the process to the risk of major politicking; it is not allowed
to just make a work item to make a small correction under ANSI rules, I
believe.  I think you have to just open the spec for change and then other
things you didn't expect might creep in.  Stability is best maintained by
not touching it, and there's nothing now that cries out as needing fixing.

I'd almost say that if something DID come up that required fixing, ANSI would
not be the vehicle of choice to do it.

The reason I think people wanted to leave speed issues entirely out of the
standard is that the market is really better at sorting things out.  Let's
take the example of the MOP.  It's not standard either, but consensus seems
to me to be that it's ok to use because most implementations do have it.
Other things, like tail call elimination, haven't even been voluntarily
adopted by implementations even though they are allowed to.  If this came back
to ANSI and we operated as we have done in the past, the first thing that
would be asked when your hypothetical proposal to define this came to the
table would be "what is the current practice?" and the answer would be "no
one does it".  And that would immediately be translated to statements like
"sounds dicey" and "sounds like it will impose cost on all vendors that they
don't feel a need for" and "sounds like there is no call for it".

The first stage of making the change is not to look to the standard  unless
the standard forbids the change.  The first stage is to get vendors to
experiment, and then to drive the wedge by asking that code that runs in
one vendor run in another.  Best, I think, would be to operate under a switch
so that code that did this had to self-identify and other compilers could
minimally say "I don't support that option, your code will likely lose" rather
than quietly compiling the code and then losing on it at runtime...

In the abstract of this article he says: "Proper tail recursion is not
the same as ad hoc tail call optimization in stack-based
languages. Proper tail recursion often precludes stack allocation of
variables, but yields a well-defined asymptotic space complexity that
can be relied upon by portable programs."

 (defun (factorial x n)
   (if (zerop x) n
       (let ((result (factorial (- x 1) (* x n))))
         result)))

As should be obvious, this affects the whole issue of how the language
treats variables--i.e., is it just "allowed" or is it actively "required"
to fold uses of variables, because this in turn forces implementations to
do some code analysis that they might not be prepared to do, especially in
an interpreter, the major point of which is to have lazy application of
semantics by analyzing things only locally as they are encountered; this
would effectively push an interpreter closer to a compiler, almost calling
into question whether an interpreter was even allowed.

Of course, you could just say it wasn't a tail call, but some people are
apparently offended by that because they want (let ((x y)) x) and y to be
semantically the same thing.  If introducing such bindings creates
unwanted additional effects (beyond just naming a quantity), it inhibits
the usefulness of code transformations--or, at least, makes such
transformations a lot harder to write.

[Note that I often beat people up for wanting to apply certain optimizations
that are not part of the language and complaining that they can't, but this
is different:  we're not in the context of "how do I optimize the fixed
language?" but rather "how should I define the language such that optimizations
I know of will be applicable?".]

Yours freely,

I suppose someone could write macros that transformed these tail-apply
and tail-funcall -containing forms into DO or LOOP forms, but that
sounds to me like part of the process of writing a compiler. :)

(defun my-fun (stack-frames-left)
  (if (not (zerop stack-frames-left))
      (my-fun (1- stack-frames-left))
      (tail-call (foo stack-frames-left))))