bug#59140: 29.0.50; iter-yield from lambda

bug#59140: 29.0.50; iter-yield from lambda

[Michael Heerdegen]

Hello,

In emacs-help (Okamsn <okamsn@protonmail.com>) it has been pointed to
the issue that `iter-yield' (from generator.el) is not supported in some
contexts - contexts where yielding happens from inside a lambda
expression or directly (like here when mapping over a sequence), e.g.

     (setq iter-maker (iter-lambda (x)
                        (seq-doseq (item x)
                          (iter-yield item))))
     (setq my-iter (funcall iter-maker '(1 2 3)))
     (iter-next my-iter)

  ~~> (void-function cps-internal-yield)

(seq-doseq expands to more or less just mapc+lambda) or

     (setq iter-maker (iter-lambda (x)
                        (seq-do #'iter-yield x)))
     (setq my-iter (funcall iter-maker '(1 2 3)))
     (iter-next my-iter)
  ~~> (error "‘iter-yield’ used outside a generator")

These examples are written correctly but seem to hit an undocumented
limitation of the implementation in generator.el

I quote Stefan Monnier answering what should be done:

> IIRC, one of the main limitations of `generator.el` is that it doesn't
> handle `lambda` (and neither should you use `#'iter-yield`, IIRC).
> 
> I don't really know how to go about fixing it.
> 
> A good first step would be to make sure it emits an error (or a warning)
> when you use `#'iter-yield` or when you call `#'iter-yield` from with
> a lambda expression.

TIA,

Michael.

bug#59140: 29.0.50; iter-yield from lambda

[Max Brieiev]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Hello,
>
> In emacs-help (Okamsn <okamsn@protonmail.com>) it has been pointed to
> the issue that `iter-yield' (from generator.el) is not supported in some
> contexts - contexts where yielding happens from inside a lambda
> expression or directly (like here when mapping over a sequence), e.g.
>
>      (setq iter-maker (iter-lambda (x)
>                         (seq-doseq (item x)
>                           (iter-yield item))))
>      (setq my-iter (funcall iter-maker '(1 2 3)))
>      (iter-next my-iter)
>
>   ~~> (void-function cps-internal-yield)
>
> (seq-doseq expands to more or less just mapc+lambda) or
>
>      (setq iter-maker (iter-lambda (x)
>                         (seq-do #'iter-yield x)))
>      (setq my-iter (funcall iter-maker '(1 2 3)))
>      (iter-next my-iter)
>   ~~> (error "‘iter-yield’ used outside a generator")
>
> These examples are written correctly but seem to hit an undocumented
> limitation of the implementation in generator.el
>
> I quote Stefan Monnier answering what should be done:
>
>> IIRC, one of the main limitations of `generator.el` is that it doesn't
>> handle `lambda` (and neither should you use `#'iter-yield`, IIRC).
>> 
>> I don't really know how to go about fixing it.
>> 
>> A good first step would be to make sure it emits an error (or a warning)
>> when you use `#'iter-yield` or when you call `#'iter-yield` from with
>> a lambda expression.

Is this unfixable in principle or the fix is just hard (non-obvious)?

If iter-yield is lexically scoped within lambda expression, then could
the lambda possibly be replaced with the iter-lambda?

For example, this:

    (iter-defun my-generator ()
      (funcall (lambda () (iter-yield 5))))

would be expanded by iter-defun macro into this:

    (...
      (let ((gen (iter-lambda () (iter-yield 5))))
        (iter-next (funcall gen))))

Does it make sense?

bug#59140: 29.0.50; iter-yield from lambda

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>>> IIRC, one of the main limitations of `generator.el` is that it doesn't
>>> handle `lambda` (and neither should you use `#'iter-yield`, IIRC).
>>> 
>>> I don't really know how to go about fixing it.
>>> 
>>> A good first step would be to make sure it emits an error (or a warning)
>>> when you use `#'iter-yield` or when you call `#'iter-yield` from with
>>> a lambda expression.
>
> Is this unfixable in principle or the fix is just hard (non-obvious)?

To do its job, `generator.el` performs a kind of CPS (continuation
passing style) conversion.  Such a conversion can be made to handle "the
whole language" fairly easily, but at the cost of being unable to
interact seamlessly with code which has not gone through the same
transformation.

So, yes, in principle it can be fixed *if* we make every single chunk of
ELisp code go through that transformation (plus adjust accordingly all
the primitives implemented in C).

Since that's not an option, `generator.el` uses a "local CPS conversion"
but these can't handle higher-order functions in general because they
need to be able to determine easily what is "local" and first-class
functions give you way to much power to play with the control flow.

So in practice it's not fixable.

> If iter-yield is lexically scoped within lambda expression, then could
> the lambda possibly be replaced with the iter-lambda?

Yes, if you can determine *all* the places from where this lambda can be
called and if you can then also change all the other lambdas that can be
called from one of those places, plus all the places where those other
lambdas can be called, plus all the other lambdas that can be called
from those other places, etc....  :-(


        Stefan

bug#59140: 29.0.50; iter-yield from lambda

[Max Brieiev]

Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of
text editors" <bug-gnu-emacs@gnu.org> writes:

> Since that's not an option, `generator.el` uses a "local CPS conversion"
> but these can't handle higher-order functions in general because they
> need to be able to determine easily what is "local" and first-class
> functions give you way to much power to play with the control flow.

So if I understand it correctly, "local CPS conversion" can't handle
higher-order functions, because "locality" of the lambda function must
be completely known (but it can't practically be known), otherwise we
will have to traverse the whole language.

I should had said that "plain lambdas" is not my concern though. I am
fine with the fact that yielding from the lambda is illegal.

My concern is that with the current state of affairs it is impossible to
use many macros inside generator functions. Namely, `named-let` and
`pcase` are an excellent examples of this: they are perfect companions
for a generator to implement an infinite/lazy looping construct to match
against incoming data, like a streaming parser and things like that. For
example,

    (iter-defun iter-sum-string ()
      (named-let sum ((result 0) (chunk ""))
        (pcase chunk
          ((rx string-start
               (let num (+ digit))
               " "
               (let tail (* anything)))
           (sum (+ result (string-to-number num)) tail))
    
          ((rx string-start "\n") result)
    
          (_ (sum result (iter-yield nil))))))
    
    (setq it (iter-sum-string))
    (iter-next it) ; advance it
    (iter-next it "5 17 8 ")
    (iter-next it "4 2 \n") 

Notice, that the above code does not visually appear to use any lambdas,
but it fails, because internally it expands to lambdas, causing
(void-function cps-internal-yield).

Now, let's get back to the original problem - the fact that in "local
CPS" the "locality" of the lambda must be completely known. If we look
at `named-let` it appears to be completely self-contained: the control
flow and the usage of higher order functions that it expands to is fully
known due to the way it is encoded into the macro. So provided with this
information, do we have enough information to perform a CPS conversion
of the `named-let`?

Similarly, in pcase, unless the handler is provided as a lambda by the
user, the internal/expanded lambdas might be "local enough" to perform
CPS conversion.

What I am trying to say is that, if "local CPS conversion" of higher
order functions is impossible to perform in general, then could we
possibly make conversions on a macro per macro basis, when the macro is
"local enough"?

bug#59140: 29.0.50; iter-yield from lambda

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> Notice, that the above code does not visually appear to use any lambdas,
> but it fails, because internally it expands to lambdas, causing
> (void-function cps-internal-yield).
>
> Now, let's get back to the original problem - the fact that in "local
> CPS" the "locality" of the lambda must be completely known. If we look
> at `named-let` it appears to be completely self-contained: the control
> flow and the usage of higher order functions that it expands to is fully
> known due to the way it is encoded into the macro.

For `named-let` we don't have such a guarantee.  You can do:

    (named-let my-foo ((x 1) (y 2))
      [...]
      (mapcar #'my-foo ...)
      [...]
      (set-process-filter proc #'my-foo)
      [...])

In most use cases, tho, we do, indeed.

> So provided with this information, do we have enough information to
> perform a CPS conversion of the `named-let`?

Usually, there is enough info to do it locally, yes.
[ We don't currently analyze enough of the code to have that
  information, OTOH.  ]

> Similarly, in pcase, unless the handler is provided as a lambda by the
> user, the internal/expanded lambdas might be "local enough" to perform
> CPS conversion.

For `pcase`, yes, definitely (and indeed, we'd want to compile those
lambdas into something more efficient).  It's more: we know they're
always called in a "tail call" position, so they can (in theory) be
treated by the CPS as continuations rather than arbitrary functions.

> What I am trying to say is that, if "local CPS conversion" of higher
> order functions is impossible to perform in general, then could we
> possibly make conversions on a macro per macro basis, when the macro is
> "local enough"?

Yes, that would be very welcome.  The easiest might be to make
`generator.el` operate on the code before macro-expansion (so it
gets to see `pcase` and `named-let` and can dispatch to ad-hoc code like
it does for special forms).  Another option is to improve `generator.el`
to the point where it can recognize the kind of code generated by macros
like `pcase` and `named-let` loops and treat it correctly.
Yet another option might be to arrange for macros like `named-let` and
`pcase` to leave hints in their code that make it easier for
`generator.el` to do its work.


        Stefan

bug#59140: 29.0.50; iter-yield from lambda

[Michael Heerdegen]

Max Brieiev <max.brieiev@gmail.com> writes:

> For example, this:
>
>     (iter-defun my-generator ()
>       (funcall (lambda () (iter-yield 5))))
>
> would be expanded by iter-defun macro into this:
>
>     (...
>       (let ((gen (iter-lambda () (iter-yield 5))))
>         (iter-next (funcall gen))))
>
> Does it make sense?

Does it?  Isn't the `let' expression equivalent to just `5'?  With other
words: you don't yield from an outside generator, as far as I
understand (or am I wrong? what's the content of your "..."?).

Michael.

bug#59140: 29.0.50; iter-yield from lambda

[Max Brieiev]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Max Brieiev <max.brieiev@gmail.com> writes:
>
>> For example, this:
>>
>>     (iter-defun my-generator ()
>>       (funcall (lambda () (iter-yield 5))))
>>
>> would be expanded by iter-defun macro into this:
>>
>>     (...
>>       (let ((gen (iter-lambda () (iter-yield 5))))
>>         (iter-next (funcall gen))))
>>
>> Does it make sense?
>
> Does it?  Isn't the `let' expression equivalent to just `5'?  With other
> words: you don't yield from an outside generator, as far as I
> understand (or am I wrong? what's the content of your "..."?).
>
> Michael.

You are right, the code is wrong, it should probably return a generator
instead. What I attempted to show is how lambda would be turned into
`iter-lambda`, conceptually. "..." is some expansion performed by
`iter-defun`. In my intuition, if `iter-yield` is encountered inside a
lambda, then it would be converted into generator, and then advance the
created generator to the first yield expression, such that the following
`iter-next` would resume execution from the suspnension point. But I
might be wrong, the topic of generators is new to me, and I need to
study it.