Re: [Chicken-users] Re: compiling jbogenturfa'i .scm => .c takes 2.5 hours

[Alan Post]

On Sat, Nov 27, 2010 at 11:55:21PM +0100, Felix wrote:
> > 
> > Reviewing the output from -debug 2, and rereading R5RS's
> > documentation on letrec, I've reworked the compiler and moved
> > the lambda that was being created for each use of a letrec variable
> > to the definition: '(record (lambda () ...)' rather than (record ...).
> > I changed the appearance of 'record' in other letrec definitions to
> > '(record)' rather than '(lambda () record)'.
> > 
> > Essentially, I'm definining a lambda for each element in the letrec
> > (~880 elements) rather than for each usage (many, many more than
> > 880).
> > 
> > The file now compiles in minutes rather than hours, and it is
> > roughly 7MB in size, rather than 61MB.
> > 
> > I haven't checked this change in yet, as my left/right recursion tests
> > now fail and I broke any non-terminal where memoization is turned off:
> > This change was a proof of concept that I now need to clean up.
> > 
> > However, things are looking good.  I'll report back after I've
> > cleanup up and checked in all the code to confirm that everything is
> > working.  So far, this does look like the culprit.
> > 
> 
> Excellent. Please keep us up to date about this.
> 

I've just put together a prototype that I think will work for this
situation.  It allows me to use generators that run only once to
initialize the non-terminal parser productions, and allows me to
recursively define connections between these routines without
generating a lambda expression for every reference to a letrec
record.  The basic idea is that I'll wrap my letrec in a let,
which contains cons cells.  I'll pass these cons cells around,
but only use the car/cdr of the cell, which is defined after the
grammar:

  ; a terminal rule matches input, it doesn't refer to other
  ; records
  ;
  (define (terminal name char)
    (pretty-print `(terminal ,name))
    (lambda ()
      (pretty-print `(terminaling ,name))
      char))

  ; this is a mock-up of a production that calls another rule.
  ;
  (define (generate name rule)
    (pretty-print `(generating ,name))
    (lambda ()
      (pretty-print `(calling ,name))
      (rule)))

  ; rather than generating a lambda for each reference, generate
  ; a fetch routine for each definition of a rule.
  ;
  ; This is the piece that should result in lower compile-time.
  ;
  ; I may need one fetch* routine per record, we'll see.
  ;
  (define (fetch name rule)
    (pretty-print `(fetch ,name))
    (lambda ()
      (pretty-print `(fetching ,name))
      ((cdr rule))))


  (define grammar
    ; create a location for storing references to records.  There
    ; is one -cache for each record.
    ;
    (let ((foo-cache (list '()))
          (bar-cache (list '()))
          (baz-cache (list '())))

      ; generate recursive definitions.  These could be mutually
      ; recursive if I wanted a more complex example.
      ;
      ; note that as I generate rules, I pass the cons cell of
      ; the -cache around.  I really want the car/cdr, but I
      ; don't have that definition yet.
      ;
      (letrec ((foo (generate "foo" (fetch "bar" bar-cache)))
               (bar (generate "bar" (fetch "baz" baz-cache)))
               (baz (generate "baz" (terminal "baz" "0"))))

        ; now that I've defined my grammar, update the -cache
        ; objects with the actual record definition.
        ;
        (set-cdr! foo-cache foo)
        (set-cdr! bar-cache bar)
        (set-cdr! baz-cache baz)

        ; and return the grammar
        ;
        foo)))

  ; as normal, run the parse
  ;
  (pretty-print (grammar))

I haven't modified the compiler yet to test this, but it seems like
it should work to reduce the number of lambda expressions that are
generated.

I may not be able to make this change today, but I'll report back
the result after I do.

Did you have a chance to look at the '-debug bosp' stuff?  I'm
curious to benefit from your expert eye, if you'd still like to do
that.

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