Re: finite state machines in guile

[Glenn Moloney <glenn@physics.unimelb.edu.au>]

> > What is wrong is that scheme is defined as a properly tail recursive
> > language and that most C compilers will not optimize tail
> > recursion. (Some will, but that isn't the point.)
> 
> Explain exactly what ``properly tail recursive language'' means.

r4rs says: Implementations of Scheme are required to be properly
  tail-recursive. This allows the execution of an iterative
  computation in constant space, even if the iterative computation is
  described by a syntactically recursive procedure. Thus with a
  tail-recursive implementation, iteration can be expressed using the
  ordinary procedure-call mechanics, so that special iteration
  constructs are useful only as syntactic sugar.

Though r4rs is vague about where exactly tail-recursiveness is
required. R5rs includes a specificaion of exactly where scheme is
"required" to be tail-recursive.

r5rs says: Implementations of Scheme are required to be *properly
  tail-recursive*. Procedure calls that occur in certain syntactic
  contexts defined below are `tail calls'. A Scheme implementation is
  properly tail-recursive if it supports an unbounded number of active
  tail calls. A call is *active* if the called procedure may still
  return. Note that this includes calls that may be returned from
  either by the current continuation or by continuations captured
  earlier by `call-with-current-continuation' that are later invoked.
  In the absence of captured continuations, calls could return at most
  once and the active calls would be those that had not yet returned.

  (and proceeds to explicitly specify in what contexts a call is
  required to be tail-recursive)

As tail-recursion is *required*, you can't rely on some C compilers to
maybe handle some of these tail calls for you. Tail recursion is not
an optional optimisation - it is part of the language.

> One further point is that Hobbit's output should be as readable as possible
> and trying to build optimisations into the C code is guaranteed to produce
> unreadable code. Yes, you should give the C compiler every chance by setting
> things up in a way that encourages optimisation but no you shouldn't make
> a messy hack.

It doesn't need to be a messy hack.

I can see the point that is is appealing to leverage off the egcs
effort. But so long as C is not required to be tail-recursive and
scheme is, then I think the tail recursion has to be implemented by
the interpreter (or compiler) and not left to be maybe handled by the
C compiler.

					cheers,
					glenn.