Syntax bugs in 2.1.7 cause non-tail-recursive behavior.

From: Lars Thomas Hansen <lth_at_cs.uoregon.edu>
Date: Fri, 23 Jun 1995 11:12:53 -0700

[In case this has already been posted, I apologize for the repetition:
I've only been on the list for a couple of days.]

I found code in 2.1.7 that causes erroneous non-tail-recursive behavior
in the case of the syntactic forms BEGIN, AND, and OR. The errors are in
three procedures in Src/syntax.c: STk_syntax_and(), STk_syntax_or(), and
STk_syntax_begin(). In all cases the procedures terminate with

  SYNTAX_RETURN(EVALCAR(l), Ntruth);

but unless CAR(l) is a symbol, the above expression causes a
non-tail-recursive call to STk_eval, which is wrong (and significant;
see below for an example). Instead, the code should read

  SYNTAX_RETURN(CAR(l), Truth);

which does not have that problem.

To see why this is an error, consider the simple loop:

        (define loop
          (lambda (i v)
            (if (< i 10000)
                (begin (if (zero? (remainder i 1000))
                           (display v))
                       (loop (+ i 1) v)))))

which grows the stack because to the bug in STk_syntax_begin(), even
though the loop can clearly run in constant space. Similar examples can
be constructed for AND and OR.

[I discovered this problem because I have been implementing a preemptive
multitasking system on top of STk. This system uses continuations.
However, since the stacks grow very rapidly in certain loops (the above
code was a test program for the timer interrupt) the continuations grow
very large very rapidly, and the system becomes hideously inefficient,
spending all its time in GC. Some trace code exposed the large size of
the continuations, from which non-tail-recursiveness was discovered and
the above bugs found.

If anyone is interested in the tasking system: I'll probably be making
available the patches and extra code in a few days, when it's reasonably
clean and debugged. Watch this space.]

--lars
Received on Fri Jun 23 1995 - 20:17:35 CEST