Generator Examples

Generator Examples

[raman]

[-- Attachment #1: message body text --]
[-- Type: text/plain, Size: 380 bytes --]

I'm attaching a short texinfo file containing a couple of examples of
using generators in Emacs Lisp.

The texinfo manual contains one example which I found confusing in
parts:

1. The example has  a nested call to iter-yield -- not sure why
2. I still dont quite understand the purpose of the optional argument
to iter-next, an example that leverages  it would be good to have.


[-- Attachment #2: Generator Examples in texinfo --]
[-- Type: application/octet-stream, Size: 1554 bytes --]

\input texinfo    @c -*- texinfo -*-
@c %**start of header
@setfilename ./generators.info
@settitle Generators In Emacs Lisp
@documentencoding UTF-8
@documentlanguage en
@c %**end of header

@finalout
@titlepage
@title Generators In Emacs Lisp
@author raman
@end titlepage

@ifnottex
@node Top
@top Generators In Emacs Lisp
@end ifnottex

@menu
* Define a Fibonacci generator::
* Iterate Over A List:: Iterate Over A List. 
@end menu

@node Define a Fibonacci generator
@chapter Define a Fibonacci generator

@lisp
(iter-defun fibonacci-iter ()
  "Return a Fibonacci sequence generator."
  (let ((a 1)
        (b 1))
    (while t
      (iter-yield a)
      (cl-psetq a b b (+ a b )))))
@end lisp

Instantiate a Fibonacci generator and use it to collect the first 10
numbers in the sequence.

@lisp
(setq f (fibonacci-iter))
;;; The first 10 Fibonacci numbers:
(cl-loop for i from 1 to 10 collect (iter-next f))
@end lisp

@node Iterate Over A List
@chapter Iterate Over A List:

A generator that takes a list and returns an iterator over that list:

@lisp
(iter-defun list-iter (l)
  "Return an iterator that iterates over list `l'."
  (let ((local(copy-sequence l)))
    (while local (iter-yield (pop local)))))
@end lisp


Test the above by iterating over a list. This example is mostly for
illustration  demonstrates the use of @code{cl-loop} clause @code{iter-by}.

@lisp
;;; Create a list iterator:

(setq l-iter (list-iter '(a b c d e)))
;;; Loop  through the iterator, collecting values:
(cl-loop for e iter-by   l-iter collect e)
@end lisp

@bye

[-- Attachment #3: .signature --]
[-- Type: text/plain, Size: 5 bytes --]


-- 

Re: Generator Examples

[Michael Heerdegen]

Hey raman,

> I'm attaching a short texinfo file containing a couple of examples of
> using generators in Emacs Lisp.

Great.  This would be an improvement for the manual indeed.

> The texinfo manual contains one example which I found confusing in
> parts:

Yeah, the current doc is more for people already familiar with the
concept.

> 1. The example has a nested call to iter-yield -- not sure why

Just to demonstrate how it behaves, I think.  It's probably not very
common/useful in practise.

> 2. I still dont quite understand the purpose of the optional argument
> to iter-next, an example that leverages it would be good to have.

I think it's more useful if you think of generators as coroutines.  A
simple real life example would be: you have implemented a counter as a
generator (generating 1, 2, ...), and when you restart it, you want to
add a certain increment to its count so far before continuing.

> @lisp
> (iter-defun fibonacci-iter ()
>   "Return a Fibonacci sequence generator."
>   (let ((a 1)
>         (b 1))
>     (while t
>       (iter-yield a)
>       (cl-psetq a b b (+ a b )))))
> @end lisp
 
Looks good (but could we get rid of the a bit uncommon `cl-psetq').  I
remember that the suggested convention was to call the iter-defun a
generator, and the return value an iterator (in this regard, the
docstring would be wrong).

FWIW, some time ago a had posted a similar example, implementing a
generator of the prime numbers:


(iter-defun cross-through-multiples-of (n)
  "Repeat indefinitely: Return `t' N-1 times, then return `nil' once."
  (let ((i (1- n)))
    (while t
      (if (zerop i)  (progn (setq i (1- n)) (iter-yield nil))
        (iter-yield t)
        (cl-decf i)))))
   
(iter-defun make-prime-gen ()
  "Return a generator of the prime numbers."
  (let ((n 2) (sieve '()))
    (while t
      (when (cl-every #'identity (mapcar #'iter-next sieve))
        ;; a new prime!
        (push (cross-through-multiples-of n) sieve)
        (iter-yield n))
      (cl-incf n))))


> A generator that takes a list and returns an iterator over that list:
> 
> @lisp
> (iter-defun list-iter (l)
>   "Return an iterator that iterates over list `l'."
>   (let ((local(copy-sequence l)))
>     (while local (iter-yield (pop local)))))
> @end lisp

Isn't the `copy-sequence' redundant (popping the local variable doesn't
alter the original list)?

> @lisp
> ;;; Create a list iterator:
> 
> (setq l-iter (list-iter '(a b c d e)))
> ;;; Loop  through the iterator, collecting values:
> (cl-loop for e iter-by   l-iter collect e)
> @end lisp
> 
> @bye


To improve the doc even further, I think it would be good if we could as
well:

- Underline the difference between generators and its "instances"
(iterators), and that multiple iterators of the same "type" have
independent inner states.

- Have an example that doesn't create lists at the end, to underline
that it is a different concept, and/or

- Have a real life example (something like tree traversal, e.g. a
generator of directory files or so) that is an improvement compared to
using list.


Regards,

Michael.

Re: Generator Examples

[raman]

I'm familiar with generators as a concept across multiple languages --
but I still found the  elisp docs confusing:-)

We explicitly say the interface is similar to that in languages like
Python -- which is why i coded up the Fibonacci example.

The cl-psetq is the right idiom here in that sense -- if you use plain
setq, you'd have to use a temporary variable?

Thanks for the coroutine example, again that would do well in the
manual -- there is a reference to coroutines either in the manual or in
code comments in generators.el that is presently "intriguing".

Finally, I  still dont understand the nested call to iter-yield in the
manual and  if it is correct, it would be good to have it better
explained there.


-- 

Re: Generator Examples

[Michael Heerdegen]

raman <raman@google.com> writes:

> The cl-psetq is the right idiom here in that sense -- if you use plain
> setq, you'd have to use a temporary variable?

Sure, but I want to avoid to confront people with functions they
potentially don't know in these examples, so that they can concentrate
on the gist.  A minor issue, sure.

> Thanks for the coroutine example, again that would do well in the
> manual -- there is a reference to coroutines either in the manual or
> in code comments in generators.el that is presently "intriguing".

AFAIK the original author wanted to add some code for working with
coroutines.

> Finally, I still dont understand the nested call to iter-yield in the
> manual and if it is correct, it would be good to have it better
> explained there.

I think it is correct (behaves exactly as described, and the behavior is
what I expect).  What in particular don't you understand?

I think the thing that this part wants to demonstrate is that
`iter-yield' behaves normally wrt when it is evaluated (function
arguments before function calls etc.; so the inner `iter-yield' is
called first, and the outer not before the iterator has been restarted).
And the outer `iter-yield' yields a value that is computed from the
"return value" of the inner, which is the second argument of the
according `iter-next' call.


Michael.

Re: Generator Examples

[T.V Raman]

The bit you wrote in response to my "dont understand why nested
iter-yield" might do well in the manual. Also, it might do what it
claims, but why it does it is opaque -- and examples that do something
useful are usually easier to learn from.

Michael Heerdegen writes:
 > raman <raman@google.com> writes:
 > 
 > > The cl-psetq is the right idiom here in that sense -- if you use plain
 > > setq, you'd have to use a temporary variable?
 > 
 > Sure, but I want to avoid to confront people with functions they
 > potentially don't know in these examples, so that they can concentrate
 > on the gist.  A minor issue, sure.
 > 
 > > Thanks for the coroutine example, again that would do well in the
 > > manual -- there is a reference to coroutines either in the manual or
 > > in code comments in generators.el that is presently "intriguing".
 > 
 > AFAIK the original author wanted to add some code for working with
 > coroutines.
 > 
 > > Finally, I still dont understand the nested call to iter-yield in the
 > > manual and if it is correct, it would be good to have it better
 > > explained there.
 > 
 > I think it is correct (behaves exactly as described, and the behavior is
 > what I expect).  What in particular don't you understand?
 > 
 > I think the thing that this part wants to demonstrate is that
 > `iter-yield' behaves normally wrt when it is evaluated (function
 > arguments before function calls etc.; so the inner `iter-yield' is
 > called first, and the outer not before the iterator has been restarted).
 > And the outer `iter-yield' yields a value that is computed from the
 > "return value" of the inner, which is the second argument of the
 > according `iter-next' call.
 > 
 > 
 > Michael.

-- 

-- 

Re: Generator Examples

[raman]

P.S. In my  quick tests, the copy-sequence was necessary --  
If it weren't generators would get inefficient quickly because you'd
have to do a deep copy of the variable you were snapshotting in the closure.
-- 

Re: Generator Examples

[Michael Heerdegen]

raman <raman@google.com> writes:

> P.S. In my quick tests, the copy-sequence was necessary -- If it
> weren't generators would get inefficient quickly because you'd have to
> do a deep copy of the variable you were snapshotting in the closure.

I don't understand what you mean, but it's already late (an example,
maybe?)


Regards,

Michael.