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

[Alan Post]

On Mon, Dec 06, 2010 at 05:15:40AM -0500, Felix wrote:
> From: Alan Post <address@hidden>
> Subject: Re: [Chicken-users] jbogenturfa'i: "Error: stack overflow"
> Date: Sun, 5 Dec 2010 16:15:26 -0700
> 
> > On Sun, Dec 05, 2010 at 06:34:44PM +0100, Felix wrote:
> >> From: Alan Post <address@hidden>
> >> Subject: Re: [Chicken-users] jbogenturfa'i: "Error: stack overflow"
> >> Date: Sun, 5 Dec 2010 08:30:50 -0700
> >> 
> >> > 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?
> >> 
> >> It certainly does. Does this happen in compiled code only, or in both
> >> interpreted and compiled code? Can you provide me with instructions to
> >> reproduce this error?
> >> 
> > 
> > It happens in both interpreted and compiled code.  I've provided
> > instructions on how to reproduce this error here, with instructions
> > for creating the problem in compiled and interpreted code:
> > 
> >   https://bugs.call-cc.org/ticket/440
> > 
> 
> Thanks a lot, Alan. The problem is that the key used in the hashtable
> lookup contains circular data, which causes `equal?' to recurse
> endlessly (I have changed the error message to something more
> helpful). You seem to use lists containing closures, and these
> closures hold circular data or refer indirectly to themselves.
> 
> Now, what to do? I'm not sure whether using procedures in equality
> tests (even if implicit, like when used as hash-table keys) is a great
> idea, since procedure-quality is a bit of a subtle thing.  I'm also
> not sure how we should handle this in the hash-table libraries.
> 
> Should `equal?' descend into procedures, or just do an `eq?' test?
> R5RS only requires a structural equivalence test for pairs and
> vectors, but being able to contain (say) records is something that's
> too handy not to have.
> 

I was hoping, I guess, for procedures to be compared with 'eq?'.  I
presumed that a procedure was an atomic entity, or if it wasn't it
was (conceptually) a pair containing an environment and code, which
are themselves eq? or not.

After I read your e-mail, I thought about my problem some, and I
realize I need the following:

 1) I need to compare a list of procedures for pointer-equivalence.
 2) I need to compare a #!key argument for string? and string=?.

I selected equal? in this case because the *lists* aren't going to
be pointer-equal, just their contents, and the contents fall into
two distinct classes, procedures and strings, and the strings won't
be eq? for the same reason the lists aren't.

I've reworked the code to separate these two comparison classes and
tried running the code.  It certainly works (by not crashing), but it
doesn't find all of the shared sub-trees.  I'm not sure yet if my
assumption that my procedures are pointer-equal is false, or whether
I have a bug whose side-effect I'm seeing.

genturfa'i works without executing this code, it was an optimization
for memory usage and provides some useful information to me when I
later add threading to the parser.

I'm considering now removing the code and moving on, perhaps
addressing it later or perhaps abandoning the idea.

Thank you Felix for determining why the code was generating a stack
overflow, I realize that Scheme equivalence operators have a lot of
unspecified behavior, and that unspecified means it could format my
hard drive and still be standard-compliant--yet I hadn't quite
understood that it meant I could try to compare a circular structure
and that could result in a stack overflow.  :-/

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