[Chicken-users] subtle (and obvious) bugfix in genturfa'i

[Alan Post]

I've been working on a mysterious bug in genturfa'i where, after
changing my memoization routine, a very few of my grammars would
run forever--looping between two rules for no reason I could see.

It wasn't all my grammars by a long shot, and when I turned off
memoization the problem would go away.

Tonight I discovered what happened.  In the process of reworking the
way memoization worked, I converted the code to return a closure
rather than return the parameters to a routine I would call.  All
of this was in a set of mutually defined functions, which I had
mentally be treating as a unit.

I didn't think twice about changing the return to be a closure, but
it turns out I was doing the following:

; pretend this is my memoization routine
;
(define (memoize)

  ; which generates this routine
  ;
  (define (foo a b)

    ; pretend this is called when the memoization has the rule in
    ; it's cache.
    ;
    (define (bar c)
      `(,a ,b ,c))

    ; I used to do this every single time
    ;
    (bar 'inside)

    ; but then I started doing this.
    ;
    bar)

  ; this of course worked just fine
  ;
  (set! bar1 (foo 0 1))
  (bar1 'bar1-outside)

  ; but when this case came around, I was
  ; actually calling bar1, so I get |0 1|
  ; rather than |#\a #\b|.
  ;
  ; it also turns out this only happens
  ; under fairly rare circumstances.
  ;
  (set! bar2 (foo #\a #\b)
  (bar1 'bar2-outside)


Writing out the code like this makes it stupidly obvious where the
mistake was, but hidden in a bunch of other code, all of it "local."
Making this one really subtle for me.  I hadn't really considered the
consequence of returning a routine rather than the parameters for
the routine, since in effect I was only returning it to another part
of this set of mutually defined functions. 

Of course, this doesn't matter for the purpose of determining scope!

One of the things I really appreciate about Scheme is that I can
change when and where something is executed in a way that fits very
naturally with the language.  If I'm not ready to run some code, I
wrap it up in a closure and ship it out, without ever really having
to refactor code.  The ability to control execution like this--and
change my mind about when it happens--is probably my #1 most-loved
thing about Scheme.

Today was the first day that flexibility *caused* a problem for me
rather than solving it.

The good news is that, with this fix, one of my programs went from
30 minutes to run to 20 seconds.  Apparently my previous memoization
routine was *really* bad.

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