Re: [Chicken-users] jbogenturfa'i: "Error: stack overflow"

[Alan Post]

On Sat, Dec 04, 2010 at 09:51:51AM -0500, Mario domenech Goulart wrote:
> Hi Alan
> 
> On Sat, 4 Dec 2010 07:33:04 -0700 Alan Post <address@hidden> wrote:
> 
> > Is there a way to increase the length of the call history?  I looked
> > for it by grepping around chicken core, but I couldn't find it.  I'd
> > like to see a much larger call history, as if I do have runaway
> > recursion, I think it is happpening over a >10 length call sequence.
> 
> You can use the -:a<num> command line option, where <num> is a number
> indicating the size of the call trace in lines.  The full documentation
> for runtime options is at
> http://wiki.call-cc.org/man/4/Using%20the%20compiler#runtime-options
> 
> 

I'm confused by what I'm seeing.

I have narrowed down my problem to my memoization code for rule
generation.  The code works like this:

  a <- b c
  b <- spaces? #\b
  c <- spaces? #\c
  spaces <- [[:whitespace:]]

In this case, the 'spaces?' rule in non-terminal 'b' and 'c'
consists of two productions, the non-terminal 'spaces' and the
operator '?', indicating the rule is optional.

When the genturfa'i parser generator runs, I knows to only make one
definition for 'spaces' while it is emitting code.  I've added a
memoization routine to the generated code that detects that the '?'
operator has been called with 'spaces' as the argument, and it
returns the same production in both places it is called in the code.
This avoids creating two identical rules for the 'spaces?'
production.

Conceptually, that is how things should work.  jbogenturfahi is crashing
during initialization with a stack overflow error.  I've narrow this
down to this memoization code.

If I comment out the routine that calls set! in the memoization code
(so that every time the memoization code is run, a new rule is
generated, delivering two identical pieces of code for 'spaces?')
jbogenturfahi runs fine.

I've written two versions of the memoization routine, one using
association lists, the other using hashes, and they both behave the
same way: if I try to memoize, I get a stack error, if I comment out
set!, I don't get a stack error.  This means I'm not seeing a weird
error in the hash table code or in the code to handle association
lists.

The frustrating thing is that in jbogenturfa'i, I'm not actually
getting positive results from the memoizer yet.  The error is happening
too early in the code to find any common subtrees.  I'm not returning
anything from the cache, and always executing the cache-miss code. 
It seems that trying to *store* the result causes the overflow, it
doesn't seem to be a side-effect from sharing common subtrees in the
parse graph.  Remember also that storing the cache as an association
lists or a hash has the same effect.

When I look at my extended stack trace, I see that I'm not
actually dealing with runaway recursion.  The stack trace is
proceeding like normal, executing one rule, then another, but
crashes on a rule that is less complex (fewer operators and lower
call depth) than the rule before it.

What additional information could I look at to better understand why
Chicken is detecting a stack overflow?


PS:

If I rewrite the memoization code so that it works like this:

  (let ((rule (generate-rule)))
    (if (not (hash-table-exists? cache key))
        (hash-table-set! cache key rule))
    rule)

Basically, I store the generated rule in the cache, but I always return
a fresh rule of that rule, as if there was no memoization code.  I do this
because in the above code it seem that storing the result causes the problem,
so what if I try to store the result, but never actually use it?

I get a stack error compiling genturfa'i, this time at |hash-table-exists?|!
I can't in this case test jbogenturfa'i: the problem shows up too earlier!
This shows that the problem isn't in the particular grammar I'm trying to
compile in jbogenturfa'i, but some way the parser code in genturfa'i is
structured or interacting with the compiler.

If I comment-out that (if (not (hash-table-exists? ...)) ...) statement in
the 'never use the cache result' version of the memoizer, the code runs
without a stack overflow.  Does that seem odd to you?

-Alan
-- 
.i ko djuno fi le do sevzi