Re: finite state machines in guile

[Greg Troxel <gdt@fnord.ir.bbn.com>]

   Explain exactly what ``properly tail recursive language'' means.

It means that an implementation must execute a program with tail
recursive calls in constant space (with respect to nesting depth),
where tail recursive calls means operationally that the value of the
procedure is the value of some procedure call in the procedure.

So, if hobbit translates this

(define (triangle a b)
  (if (= a 0)
     b
     (triangle (- a 1) (+ b a))))

to C as

triangle(int a, int b)
{
  if ( x == 0 )
    return b;
  else
    return triangle(a - 1, a + b);
}

and the C compile does not turn this into a loop, then the hobbit/C
combination is not a proper Scheme implementation.

If it does instead (blowing off numeric type issues)

triangle(int a, int b)
{
  int atmp, tmp;

begin:
  if ( x == 0 )
    return b;

  atmp = a - 1
  btmp = a + b;
  a = atmp; b = btmp;
  goto begin;
}

then this particular kind of tail recursion (self) will be properly
implemented.

Also, if there are multiple procedures in a tail-recursive loop (a
tail-calls b, and b tail-calls c, and c tail-calls a), then that must
also be executed in constant space.

I would argue that it doesn't strictly make sense to ask the question
"Is hobbit a proper implementation of Scheme" but only "Is hobbit and
C compiler foo a proper implementation".  I'd have to interpret the
first question as "Is hobbit together with any ANSI-C-conforming
compiler a proper implementation".  In that case an implementation
like the above is not.  (Which doesn't mean it isn't very useful, of
course.)

        Greg Troxel <gdt@ir.bbn.com>