Subject: Re: bug#59140: 29.0.50; iter-yield from lambda

From: Max Brieiev <[email-masked]>
Date: Sat, 16 Sep 2023 22:39:18 +0300

Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of
text editors" <[email-masked]> 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"?