peval error

peval error

[Andy Wingo]

Hi!

I'm excited about the partial evaluator.  However there is one error
I've found:

  (letrec ((fold (lambda (f x b null? car cdr)
                   (if (null? x)
                       b
                       (f (car x) (fold f (cdr x) b null? car cdr))))))
    (fold * x 1 zero? (lambda (x) x) (lambda (x) (- x 1))))

The expansion ends up with the body including lexical-refs to `car' and
`cdr', but they aren't bound in the letrec body.

Andy
-- 
http://wingolog.org/

Re: peval error

[Ludovic Courtès]

Hi Andy,

Thanks for the report!

Andy Wingo <wingo@pobox.com> skribis:

> I'm excited about the partial evaluator.  However there is one error
> I've found:
>
>   (letrec ((fold (lambda (f x b null? car cdr)
>                    (if (null? x)
>                        b
>                        (f (car x) (fold f (cdr x) b null? car cdr))))))
>     (fold * x 1 zero? (lambda (x) x) (lambda (x) (- x 1))))
>
> The expansion ends up with the body including lexical-refs to `car' and
> `cdr', but they aren't bound in the letrec body.

Ouch.  I’ve reduced it to:

  (letrec ((fold (lambda (f car) (f (car x)))))
    (fold * (lambda (x) x)))

  =>

  (letrec (fold)
    (#{fold 151247}#)
    ((lambda ((name . fold))
       (lambda-case
         (((f car)
           #f
           #f
           #f
           ()
           (#{f 151248}# #{car 151249}#))
          (apply (lexical f #{f 151248}#)
                 (apply (lexical car #{car 151249}#) (toplevel x)))))))
    (apply (primitive *)
           (apply (lexical car #{car 151249}#) (toplevel x))))

Let’s see...

Ludo’.

Re: peval error

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

> I'm excited about the partial evaluator.  However there is one error
> I've found:
>
>   (letrec ((fold (lambda (f x b null? car cdr)
>                    (if (null? x)
>                        b
>                        (f (car x) (fold f (cdr x) b null? car cdr))))))
>     (fold * x 1 zero? (lambda (x) x) (lambda (x) (- x 1))))
>
> The expansion ends up with the body including lexical-refs to `car' and
> `cdr', but they aren't bound in the letrec body.

I believe this is now fixed:

  http://git.sv.gnu.org/cgit/guile.git/commit/?h=stable-2.0&id=61237fa4b96d020e96388cca4fd065ddf43bca60

Thanks!

Ludo’.

Re: peval error

[Andy Wingo]

Hi Ludo,

On Tue 13 Sep 2011 10:04, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> skribis:
>
>> I'm excited about the partial evaluator.

I'm still excited about it!

>>   (letrec ((fold (lambda (f x b null? car cdr)
>>                    (if (null? x)
>>                        b
>>                        (f (car x) (fold f (cdr x) b null? car cdr))))))
>>     (fold * x 1 zero? (lambda (x) x) (lambda (x) (- x 1))))
>>
> I believe this is now fixed:

Unfortunately it is not yet fixed.  The free variable `x' ends up as a
lexical ref, but without a binding.  Try it and see :)

Andy
-- 
http://wingolog.org/

Re: peval error

[Ludovic Courtès]

Hi Andy!

Andy Wingo <wingo@pobox.com> skribis:

> Hi Ludo,
>
> On Tue 13 Sep 2011 10:04, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Andy Wingo <wingo@pobox.com> skribis:
>>
>>> I'm excited about the partial evaluator.
>
> I'm still excited about it!

Thanks for persevering!  :-)

>>>   (letrec ((fold (lambda (f x b null? car cdr)
>>>                    (if (null? x)
>>>                        b
>>>                        (f (car x) (fold f (cdr x) b null? car cdr))))))
>>>     (fold * x 1 zero? (lambda (x) x) (lambda (x) (- x 1))))
>>>
>> I believe this is now fixed:
>
> Unfortunately it is not yet fixed.  The free variable `x' ends up as a
> lexical ref, but without a binding.  Try it and see :)

Indeed.

This time peval uses variables that are in scope.

Apparently the problem stems from the fact that it uses the same gensyms
in different places, which breaks the assumption behind
‘vars->bind-list’, as shown with this excerpt of partial evaluation of
your expression:

  (apply (primitive *)
         (apply (lambda ()
                  (lambda-case
                    (((x1) #f #f #f () (#{x1 85196}#)) ;; 1st occurrence
                     (lexical x1 #{x1 85196}#))))
                (toplevel x))
         (apply (lexical fold #{fold 85183}#)

                [...]

                (const 1)
                (primitive zero?)
                (lambda ()
                  (lambda-case
                    (((x1) #f #f #f () (#{x1 85196}#)) ;; 2nd occurrence
                     (lexical x1 #{x1 85196}#))))

                [...]

I guess peval should do some further renaming upon inlining.

WDYT?

Thanks,
Ludo’.

Re: peval error

[Ludovic Courtès]

Hi,

ludo@gnu.org (Ludovic Courtès) skribis:

> Apparently the problem stems from the fact that it uses the same gensyms
> in different places, which breaks the assumption behind
> ‘vars->bind-list’, as shown with this excerpt of partial evaluation of
> your expression:

Here’s a simpler test case:

  (define andy/tree-il/peval
    '(apply (toplevel fold)
            (lambda ()
              (lambda-case
               (((x2) #f #f #f () (#{x2 2899}#))
                (lexical x2 #{x2 2899}#))))
            (lambda ()
              (lambda-case
               (((x2) #f #f #f () (#{x2 2899}#))
                (lexical x2 #{x2 2899}#))))))

  (define andy/glil*
    (compile (parse-tree-il andy/tree-il/peval) #:from 'tree-il #:to 'glil
             #:opts '(#:partial-eval? #f)))

Compilation yields this error:

In current input:
   1392:2 15 (#<procedure 16223e0 at <current input>:1391:16 ()>)
In module/system/base/compile.scm:
    232:6 14 (compile #<tree-il (apply (toplevel fold) (lambda () (lambda-case (((x2) #f #f #f () (#{x2 2899}#)) (lexical x2 #{…> …)
   178:32 13 (lp (#<procedure compile-glil (x e opts)>) #<tree-il (apply (toplevel fold) (lambda () (lambda-case (((x2) #f #f #…> …)
In module/language/tree-il/compile-glil.scm:
    70:14 12 (compile-glil #<tree-il (apply (toplevel fold) (lambda () (lambda-case (((x2) #f #f #f () (#{x2 2899}#)) (lexical …> …)
    205:6 11 (flatten-lambda #<tree-il (lambda () (lambda-case ((() #f #f #f () ()) (apply (toplevel fold) (lambda () (lambda-c…> …)
    197:4 10 (with-output-to-code #<procedure 1da0680 at module/language/tree-il/compile-glil.scm:206:7 (emit-code)>)
    782:9  9 (comp #<tree-il (lambda-case ((() #f #f #f () ()) (apply (toplevel fold) (lambda () (lambda-case (((x2) #f #f #f (…> …)
    508:9  8 (comp #<tree-il (apply (toplevel fold) (lambda () (lambda-case (((x2) #f #f #f () (#{x2 2899}#)) (lexical x2 #{x2 …> …)
In module/ice-9/boot-9.scm:
   611:17  7 (for-each #<procedure comp-push (tree)> (#<tree-il (lambda () (lambda-case (((x2) #f #f #f () (#{x2 2899}#)) (le…> …))
In module/language/tree-il/compile-glil.scm:
   681:26  6 (comp #<tree-il (lambda () (lambda-case (((x2) #f #f #f () (#{x2 2899}#)) (lexical x2 #{x2 2899}#))))> push #f #f)
    205:6  5 (flatten-lambda #<tree-il (lambda () (lambda-case (((x2) #f #f #f () (#{x2 2899}#)) (lexical x2 #{x2 2899}#))))> #f #)
    197:4  4 (with-output-to-code #<procedure 1da0540 at module/language/tree-il/compile-glil.scm:206:7 (emit-code)>)
   747:13  3 (comp #<tree-il (lambda-case (((x2) #f #f #f () (#{x2 2899}#)) (lexical x2 #{x2 2899}#)))> tail #f #f)
   189:18  2 (emit-bindings #f (x2) (#{x2 2899}#) #<hash-table 7/31> #<tree-il (lambda () (lambda-case (((x2) #f #f #f () (#{x2…> …)
In module/ice-9/boot-9.scm:
   557:23  1 (map #<procedure 25f9120 at module/language/tree-il/compile-glil.scm:179:7 (id v)> (x2) (#{x2 2899}#))
In unknown file:
           0 (scm-error misc-error #f "~A ~S ~S ~S" ("bad var list element" x2 #{x2 2899}# #f) #f)

Renaming one of the #{x2 2899}# fixes the problem.

Thanks,
Ludo’.

Re: peval error

[Andy Wingo]

Hi,

On Fri 16 Sep 2011 03:02, ludo@gnu.org (Ludovic Courtès) writes:

> Renaming one of the #{x2 2899}# fixes the problem.

Yes, whenever you introduce a new binding (for example, by inlining),
you will need to rename the newly bound variable.

Andy
-- 
http://wingolog.org/

Re: peval error

[Ludovic Courtès]

Hi Andy,

Andy Wingo <wingo@pobox.com> skribis:

> On Fri 16 Sep 2011 03:02, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Renaming one of the #{x2 2899}# fixes the problem.
>
> Yes, whenever you introduce a new binding (for example, by inlining),
> you will need to rename the newly bound variable.

OK, I’ll do that.

Thanks,
Ludo’.

Re: peval error

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

> On Fri 16 Sep 2011 03:02, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Renaming one of the #{x2 2899}# fixes the problem.
>
> Yes, whenever you introduce a new binding (for example, by inlining),
> you will need to rename the newly bound variable.

Hopefully fixed!

  http://git.sv.gnu.org/cgit/guile.git/commit/?h=stable-2.0&id=2ae0775e405de414e2da4806588b674c07793b8e

Thanks,
Ludo’.

Re: peval error

[Andy Wingo]

On Sat 17 Sep 2011 07:52, ludo@gnu.org (Ludovic Courtès) writes:

> Hopefully fixed!

Thanks!

Still, though, the results are not great:

  (define exp
    '(define (fact x)
       (letrec
           ((fold (lambda (f x b null? car cdr)
                    (if (null? x)
                        b
                        (f (car x) (fold f (cdr x) b null? car cdr))))))
         (fold * x 1 zero? (lambda (x) x) (lambda (x) (- x 1))))))

  (tree-il->scheme (optimize! (compile exp #:to 'tree-il) (current-module) '()))
  =>
  (define fact
    (lambda (#{x 265}#)
      (letrec*
        ((#{fold 268}#
           (lambda (#{f 269}#
                    #{x 270}#
                    #{b 271}#
                    #{null? 272}#
                    #{car 273}#
                    #{cdr 274}#)
             (if (#{null? 272}# #{x 270}#)
               #{b 271}#
               (#{f 269}# (#{car 273}# #{x 270}#)
                          (#{fold 268}#
                            #{f 269}#
                            (#{cdr 274}# #{x 270}#)
                            #{b 271}#
                            #{null? 272}#
                            #{car 273}#
                            #{cdr 274}#))))))
        (begin
          (if (zero? #{x 265}#)
            1
            (* (let ((#{x 281288}# #{x 265}#)) #{x 281288}#)
               (#{fold 268}#
                 *
                 (let ((#{x 283289}# #{x 265}#))
                   (#{1-}# #{x 283289}#))
                 1
                 zero?
                 (lambda (#{x 281290}#) #{x 281290}#)
                 (lambda (#{x 283291}#) (#{1-}# #{x 283291}#)))))))))

Here we see that `fold' was inlined once, but to no use.  More code for
no more speed.

Waddell and Dybvig report on similar problems in their inlining paper
(Fast and Effective Procedure Inlining, IU CS Dept. TR 484).  See
section 4.4 where they discuss this and similar problems.  We should
figure out what we can do in these cases; and in the case where we can't
fully inline a call site, perhaps we should abort the attempt to inline
it.

Andy
-- 
http://wingolog.org/

bug#9542: peval error

[Ludovic Courtès]

Hi Andy,

Andy Wingo <wingo@pobox.com> skribis:

> Still, though, the results are not great:

[...]

> Here we see that `fold' was inlined once, but to no use.  More code for
> no more speed.

Yes.  OTOH, it was inlined *and* specialized; peval only “inlines”
where’s there’s at least one static argument (known at compile-time), in
which case there’s room for specialization (in this example, *, 1,
zero?, and the anonymous lambdas were propagated/resolved as
primitives.)

In the above example, I agree that we can argue that inlining wasn’t
useful.

> Waddell and Dybvig report on similar problems in their inlining paper
> (Fast and Effective Procedure Inlining, IU CS Dept. TR 484).  See
> section 4.4 where they discuss this and similar problems.  We should
> figure out what we can do in these cases; and in the case where we can't
> fully inline a call site, perhaps we should abort the attempt to inline
> it.

Right.  I think we should avoid inlining when recursive calls appear in
the residual code, as mentioned in the referred section.

WDYT?

Now, the current heuristic in peval is to “inline” procedures only at
call sites with static arguments.  Conversely, a general procedure
inlining algorithm like Waddell’s may inline even when there are only
dynamic arguments.  This puts more pressure on the inlining criteria
because there are many more potential inlining opportunities.

I don’t think an optimization heuristic can be optimal in all cases.

So the question is not whether we can find such pathological cases, but
how frequent they are in practice.  So I think we must keep an eye on
the optimized code, like you did, to find out more.

Thanks for your feedback!

Ludo’.

bug#9542: peval error

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

> Here we see that `fold' was inlined once, but to no use.  More code for
> no more speed.
>
> Waddell and Dybvig report on similar problems in their inlining paper
> (Fast and Effective Procedure Inlining, IU CS Dept. TR 484).  See
> section 4.4 where they discuss this and similar problems.  We should
> figure out what we can do in these cases; and in the case where we can't
> fully inline a call site, perhaps we should abort the attempt to inline
> it.

Fixed in 72b2ca55f6e115927aa4e76401c992f21198681f.

Thanks!

Ludo’.