Subject: Re: how to validate input?
From: Erik Naggum <>
Date: 2000/04/26
Newsgroups: comp.lang.lisp
Message-ID: <>

* Joe Marshall <>
| This is one way of looking at it, but the notion of a `call frame' and
| whether it is `heap-based' or `stack-based' is very much implementation.

  I also said "this is not an implementation issue _alone_".  therefore, I
  would appreciate if you argued against the semantic issues that I think
  exist in the design (and requirements) of both of these mechanisms.

| Consider looking at it from a denotational semantic viewpoint.  ...  Tail
| recursion doesn't appear *at all* in the  denotational equations.

  function calls don't appear as such in denotational equations, either, so
  that's really no surprise.

  rewriting a self-tail call to a jump affects recursion.  _requiring_ all
  tail function calls to be jumps affects the entire system adversely, and
  does affect the semantics of the language, even if it should vanish along
  with many other important issues in denotational semantics.

| If the stack were of infinite size, tail recursion would be unnecessary.

  unfortunately, language design has to be performed in the real world.
  contrary to popular belief in some quarters, programming language design
  is not pure mathematics.  there are _severe_ constraints on what we can
  do, and programming language pragmatics do enter the picture.  there are
  times when you can ignore these issues to great benefit, and there are
  times when you can't lest you do something terribly stupid.  confusing
  these times is perhaps the worst thing you can do when you design a
  language.  I maintain that Scheme does exactly that with both the proper
  tail call _requirement_ and with the continuations, for the same reason:
  they have a different function call notion than other languages.

  in my view, it doesn't make much sense to _require_ tail call recursion
  unless you do something that would otherwise make this expensive to add
  as an obvious option.  the reason is that there is a huge difference
  between a self-tail (recursive) call and a normal call, but a requirement
  must make them behave identically.  it would make _much_ more sense to
  require only that self-tail calls be syntactic sugar for a loop.