RFC: Generators v2

RFC: Generators v2

[Daniel Colascione]

[-- Attachment #1: Type: text/plain, Size: 591 bytes --]

At https://github.com/dcolascione/elisp-generators, I've updated my
elisp generator support. Please take a look.

Since the last version, I've added documentation, cl-loop
integration, a few more testcases, and a lexical-binding assertion.

I'd eventually like to integrate this package into
the Emacs core, so I've laid claim to a few symbols in the
global namespace, like next. This package actually defines a generic
iterator protocol, and it'd be useful eventually to define iterator
objects for things like buffers and windows instead of relying on
enumeration callbacks.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: RFC: Generators v2

[Nic Ferrier]

dancol@dancol.org writes:

> At https://github.com/dcolascione/elisp-generators, I've updated my
> elisp generator support. Please take a look.
>
> Since the last version, I've added documentation, cl-loop
> integration, a few more testcases, and a lexical-binding assertion.
>
> I'd eventually like to integrate this package into
> the Emacs core, so I've laid claim to a few symbols in the
> global namespace, like next. This package actually defines a generic
> iterator protocol, and it'd be useful eventually to define iterator
> objects for things like buffers and windows instead of relying on
> enumeration callbacks.

First you should package it and put it on marmalade (and melpa?)

If you can do this perhaps the CPS style could just be integrated into
the emacs-lisp interpreter/compiler? then yield could be implemented at
a lower level?

I'm personally uncomfortable about claiming `next'. At least use a
better name, like `gen-next'?

Perhaps it would be possible to avoid grabbing next by making it an
argument to the object returned by yield:

(defgenerator y (x)
   (while (> x 1)
     (setq x (- x 1))
     (yield x)))

(let ((g (y 10)))
  (funcall g :next)
  (funcall g :next)
  (funcall g :next)) => 7


The only thing nicer than that would be to have generators be real
lisp-1 functions:

(let ((g (y 10)))
  (g)
  (g)
  (g)) => 7

this would obviously be a lower level implementation of generators than
some macros can provide.



Other than that it's pretty neat stuff. Definitely this will be useful
for implementing actors/CSP/go routines a la clojure core.async (and Go,
of course).

Re: RFC: Generators v2

[Stephen J. Turnbull]

Nic Ferrier writes:

 > I'm personally uncomfortable about claiming `next'. At least use a
 > better name, like `gen-next'?

Another possible name is `pop', I think.  `pop' being a macro anyway
it should be able to handle Yet Another Type of argument.  `pop',
because when applied to arguments, a generator returns an iterator
whose API is like a list restricted to being consumed by iteration.  I
like `next', though.  `next' is used in Python, at least, and it seems
like the natural name to use.  `gen-next'?  No, thank you.

 > Perhaps it would be possible to avoid grabbing next by making it an
 > argument to the object returned by yield:
 > 
 > (defgenerator y (x) [...])
 >
 > (let ((g (y 10)))
 >   (funcall g :next)
 >   (funcall g :next)
 >   (funcall g :next)) => 7

I think the package is misusing the name "generator".  If `g' is a
function (which it seems it indeed is in this package), it's already
possible to create closures in various ways, so that a function
carries its state with it.  So this is just syntactic sugar for
closures.

Indeed this syntactic sugar is *very* useful for coroutines and the
like, but it's not really useful for generators.  The point of a
generator is that it returns an iterable, ie, an object which looks
like a sequence in an iteration context.  In particular, code that can
iterator over the value of a generator should be able to use an
ordinary list in the same place, *without* knowing which it's going to
get in advance.  I don't see how you make that work generically if
generators return functions.  You have to alter *every* iteration
construct to recognize generators.  And then what happens if you hand
it an ordinary function?  Is it possible to distinguish between a
function created with defun, and the value of a generator created with
defgenerator?  I don't see how (without introspecting the code for
yields).

 > The only thing nicer than that would be to have generators be real
 > lisp-1 functions:

Too bad that Emacs Lisp is a Lisp-2, I guess.

You actually could do that Lisp-2-fully in a specific syntactic
context, though:

    ; pass the syntactic sugar, plz
    ; oh, yeah, the gencinnamon, too!  then you can omit the fmakunbound
    (prog2
      (define-function 'g (y (10)))
      (g)
      (fmakunbound 'g))
=> 9

It should be easy enough to do that with a macro, though I don't see
how to make it very general.

Steve

Re: RFC: Generators v2

[Daniel Colascione]

[-- Attachment #1: Type: text/plain, Size: 3356 bytes --]

On 8/25/13 6:56 AM, Stephen J. Turnbull wrote:
> Nic Ferrier writes:
> 
>  > I'm personally uncomfortable about claiming `next'. At least use a
>  > better name, like `gen-next'?
> 
> Another possible name is `pop', I think.  `pop' being a macro anyway
> it should be able to handle Yet Another Type of argument.  `pop',
> because when applied to arguments, a generator returns an iterator
> whose API is like a list restricted to being consumed by iteration.  I
> like `next', though.  `next' is used in Python, at least, and it seems
> like the natural name to use.  `gen-next'?  No, thank you.


I also like the idea of using pop, but you'd have to determine at
runtime whether you were popping from an iterator or a list, and I'm not
really comfortable adding that overhead. I'd prefer 'next' over
'gen-next' or other alternatives: we're talking about a generic
iteration protocol. The chief problem with using generic names is that
they're often tied to concepts that are too specific. In this case,
though, we're giving a generic concept a generic name, and I think
that's fine.

> 
>  > Perhaps it would be possible to avoid grabbing next by making it an
>  > argument to the object returned by yield:
>  > 
>  > (defgenerator y (x) [...])
>  >
>  > (let ((g (y 10)))
>  >   (funcall g :next)
>  >   (funcall g :next)
>  >   (funcall g :next)) => 7
> 
> I think the package is misusing the name "generator".  If `g' is a
> function (which it seems it indeed is in this package), it's already
> possible to create closures in various ways, so that a function
> carries its state with it.  So this is just syntactic sugar for
> closures.

The package uses a tree walker to rewrite swaths of code into
continuation passing style. If you think that's sugar, I'd love to see
what you consider meat. :-)

> Indeed this syntactic sugar is *very* useful for coroutines and the
> like, but it's not really useful for generators.  The point of a
> generator is that it returns an iterable, ie, an object which looks
> like a sequence in an iteration context.  In particular, code that can
> iterator over the value of a generator should be able to use an
> ordinary list in the same place, *without* knowing which it's going to
> get in advance.  

Ideally, yes, and in something like Clojure, we'd be able to do that
with existing languages primitives --- but here, our options for runtime
polymorphism are limited. Providing ways to conveniently iterate over
iterators (and making these constructs also handle today's sequences)
would be sufficient.

I don't see how you make that work generically if
> generators return functions.  You have to alter *every* iteration
> construct to recognize generators.

There are only a few. What's the alternative: a special kind of cons
cell that lazily generates its car and cdr? I suppose that could work,
but I'd be worry about unintended side effects.

> And then what happens if you hand
> it an ordinary function?  Is it possible to distinguish between a
> function created with defun, and the value of a generator created with
> defgenerator?  I don't see how (without introspecting the code for
> yields).
> 

I suppose it's possible to wrap the returned function in some
easily-distinguishable wrapper, but why would you want to?



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: RFC: Generators v2

[Stephen J. Turnbull]

Daniel Colascione writes:

 > I also like the idea of using pop, but you'd have to determine at
 > runtime whether you were popping from an iterator or a list, and
 > I'm not really comfortable adding that overhead.

Well, yeah, true iterators would have to be implemented at the C level
to be efficient, or you'd need to use an iterator-only function to
iterate one.  But almost 10 years of Python experience shows that
Python-style iterators and generators (especially genexps) beat pretty
much everything users actually write instead.

 > The package uses a tree walker to rewrite swaths of code into
 > continuation passing style. If you think that's sugar, I'd love to
 > see what you consider meat. :-)

I have no idea what you're talking about.  Meat isn't *sweet*,
generators are. :-)

 > Ideally, yes, and in something like Clojure, we'd be able to do
 > that with existing languages primitives --- but here, our options
 > for runtime polymorphism are limited.

Only if you restrict yourself to implementing your iterators as
"dotted lists of vectors with the last cdr being
'supercalifragilisticexpialidocious".

 > What's the alternative: a special kind of cons cell that lazily
 > generates its car and cdr?

No.  A new iterator type.  A lazy cons is an interesting idea, but
it's different and not very Lisp-y IMO (since Lisp doesn't have
laziness built in elsewhere).  (car iterator) doesn't really make
sense, to me, anyway.  Merely accessing an iterator should mutate it,
that's what it's for.

 > Providing ways to conveniently iterate over iterators (and making
 > these constructs also handle today's sequences) would be
 > sufficient.  There are only a few.

I suppose that's true, since `while' doesn't provide enough syntax to
take advantage of iterators.  But I worry more about uses which pass
an iterator accidentally to an unprepared iteration, or call it as a
function and corrupt the internal state, than about strange behavior
of a new type.  New types are expected to behave strangely!

 > I suppose it's possible to wrap the returned function in some
 > easily-distinguishable wrapper, but why would you want to?

Well, for one thing, iterating an ordinary function is an infloop
waiting to happen.

Steve

Re: RFC: Generators v2

[Stefan Monnier]

> At https://github.com/dcolascione/elisp-generators, I've updated my
> elisp generator support. Please take a look.

I like generators, and your package looks interesting.  I'd be very
happy to put it in GNU ELPA at least.

> integration, a few more testcases, and a lexical-binding assertion.

The top-level (assert lexical-binding) checks that lexical-binding is
true at run-time, whereas you only care about its value at
macro-expansion time.

> I'd eventually like to integrate this package into the Emacs core,

As I said, I like the idea.  But I'm wondering how well it works
in practice.  The code it generates seems to be extremely inefficient
(not that I know an easy way to make it more efficient, mind you).

> so I've laid claim to a few symbols in the global namespace, like
> next.

IIUC `yield' can only appear lexically within `defgenerator', so whether
its namespace-cleanliness is not much of a problem.

I see we already have `next' in Emacs's core, which we call `funcall'.
I agree that `funcall' is not an intuitive name, but I'm not sure I like
the idea of claiming `next' for it, right now.  If/when generators move
to the core, I might change my mind, of course.

We could do away with the funcall altogether using an flet-like macro:

   (flet-like ((g (y 10)))
     (g)
     (g)
     (g)) => 7

> This package actually defines a generic iterator protocol, and
> it'd be useful eventually to define iterator objects for things like
> buffers and windows instead of relying on enumeration callbacks.

Agreed,


        Stefan