Subject: Re: bug#29520: peval leaves behind dangling lexical reference

From: Mark H Weaver <[email-masked]>
Date: Sun, 03 Dec 2017 19:43:45 -0500

Mark H Weaver <[email-masked]> writes:

> So, peval is optimizing this:
>
>   (define (f-scope f)
>     (define (g f x3)
>       (define (h x2 n m)
>         (lambda xx (apply (f-skip n m) x2)))
>       (lambda (a b cc d c)
>         (f x y z c)
>         (let ((n N) (m M)) ((h x3 n m) x y z c2))))
>     (lambda x (apply (g f x) x)))
>
> into this:
>
>   (define (f-scope f)
>     (lambda (a b cc d c)
>       (f x y z c)
>       (let ((n N) (m M))
>         (begin x y z c2 (if #f #f))
>         (apply (f-skip n m) x-1))))

I believe the problem is most likely in 'lift-applied-lambda' in
peval.scm.  When transforming:

  (lambda args (apply (lambda ...) args)) => (lambda ...)

it does not appear to check whether 'args' is referenced within the
inner lambda.

Assuming for the moment that it fails to do this check, here's an
example sequence of transformations that could lead to this situation:

Starting with:

  (define (f-scope f)
    (define (g f x3)
      (define (h x2 n m)
        (lambda xx (apply (f-skip n m) x2)))
      (lambda (a b cc d c)
        (f x y z c)
        (let ((n N) (m M))
          ((h x3 n m) x y z c2))))
    (lambda x (apply (g f x) x)))

inline the call to h:

  (define (f-scope f)
    (define (g f x3)
      (lambda (a b cc d c)
        (f x y z c)
        (let ((n N) (m M))
          ((lambda xx (apply (f-skip n m) x3))
           x y z c2))))
    (lambda x (apply (g f x) x)))

inline the call to (lambda xx ...):

  (define (f-scope f)
    (define (g f x3)
      (lambda (a b cc d c)
        (f x y z c)
        (let ((n N) (m M))
          (begin x y z c2 (if #f #f))
          (apply (f-skip n m) x3))))
    (lambda x (apply (g f x) x)))

alpha-rename the 'x' to 'x-1' in the final lambda above:

  (define (f-scope f)
    (define (g f x3)
      (lambda (a b cc d c)
        (f x y z c)
        (let ((n N) (m M))
          (begin x y z c2 (if #f #f))
          (apply (f-skip n m) x3))))
    (lambda x-1 (apply (g f x-1) x-1)))

inline the call to g:

  (define (f-scope f)
    (lambda x-1
      (apply (lambda (a b cc d c)
               (f x y z c)
               (let ((n N) (m M))
                 (begin x y z c2 (if #f #f))
                 (apply (f-skip n m) x-1)))
             x-1)))

if we erroneously replace (lambda x-1 (apply FOO x-1)) with FOO here
(even though FOO contains a reference to x-1) then we would get:

  (define (f-scope f)
    (lambda (a b cc d c)
      (f x y z c)
      (let ((n N) (m M))
        (begin x y z c2 (if #f #f))
        (apply (f-skip n m) x-1))))

which is what 'peval' returns, although I don't know if these were the
exact steps taken.

      Mark