Python generators in various languages

Question

How do you emulate Python style generators in your favorite language? I found this one in Scheme. It must be interesting to see other implementations, especially in those languages that don't have first-class continuations.

Answer 1

I wouldn't use yield at all in Lisp/Scheme.

'yield' requires some kind of co-routine or continuation facility in the language. Many uses of yield can be implemented in a simpler functional way.

YIELD is basically related to the famous COME-FROM operator. ;-) Here, a call in some place can lead to different places in some other routine, depending on its execution context. So a routine suddenly has multiple entry points whose order is determined at runtime. For simple uses this may be fine, but I would argue that for more complex code reasoning about the code would get harder.

Take the Scheme example linked in the question:

(define/y (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

(list (step) (step) (step))

Calling (step) multiple times returns different values then.

I would just create a closure:

(define step
  (let ((state '(1 2 3 finished)))
    (lambda ()
      (pop state))))

This breaks above function with a yield into two different things: a variable that carries the state and a simple function that changes the state. The state is no longer implicitly coded into the execution sequence.

 (list (step) (step) (step))))

One can imagine similar solutions for other uses of yield.

Compare that with the generators from the Common Lisp SERIES library:

(let ((x (generator (scan '(1 2 3 finished)))))
  (list (next-in x)
        (next-in x)
        (next-in x)))

If we look at this Python example from another answer

def simpleRange(n):
    for i in xrange(n):
        yield i

for n in simpleRange(5):
     print(n)

we can see that it duplicates the control structure. Both the calling place and the generator use a FOR iteration control structure. Using closures, we can get rid of the use of control structures inside the generator, by only providing the state transition code.

Answer 2

Here is an example in C++ that simulates generators using fibers:

Yield Return Iterator for Native C++ Using Fibers

The "yield return" iterator is a language feature that was created for one reason: simplicity. It is generally much easier to iterate across whole collectionl, storing all context needed in local variables, rather than crafting a complicated, custom iterator object that stores its state across subsequent retrieval operations.

There are also the primitive C routines setjmp, longjmp to achieve similar results.
(Lua coroutines are implemented with the above method)

Answer 3

In JavaScript 1.7+ I usually only have to add a few parentheses and brackets. Everything else is about the same. JavaScript 1.7 introduced pythonic generators and iterators among other things.

Generator expressions:

# Python
(x + 1 for x in y if x > 100)

// JavaScript 1.8+
(x + 1 for (x in y) if (x > 100))

Generators

# Python
def simpleRange(n):
    for i in xrange(n):
        yield i

for n in simpleRange(5):
     print(n)


// JavaScript 1.7+
function simpleRange(n) {
    for (let i = 0; i < n; i++)
        yield i;
}

for (n in simpleRange(5))
    print(n);

List/Array comprehensions

# Python
[x + 1 for x in y if x > 100]

// JavaScript 1.7+
[x + 1 for (x in y) if (x > 100)]

Answer 4

C++, using Generators

Declaration of simple range generator:

$generator(range)
{
   int i;
   int _max;
   int _min;

   range(int minv, int maxv):_max(maxv),_min(minv) {}

   $emit(int) // will emit int values. Start of body of the generator.
      for (i = _min; i <= _max; ++i)
         $yield(i); 
   $stop;
};

Its usage:

range r10(1,10);
for(int n; r10(n);) 
   printf("%d\n",n);

Will output

1
2 
...
10

Answer 5

To @dmitry_vk answer about Common Lisp I would add that in Lisp, actually, generators are not really needed. Their use cases are fully covered by different applications of closures, special variables and macros - without the additional conceptual overhead of learning a new construct.

Sometimes even the built-in constructs will work. Let's look at the example from the Python wiki:

# add squares less than 100
from itertools import count, takewhile

sum = 0
square = (i*i for i in count())
bounded_squares = takewhile(lambda x: x < 100, square)
for i in bounded_squares:
   sum += i

Using loop it can be implemented in a much more straightforward manner:

CL-USER> (loop :for i :from 0 :while (< i 100) :sum (expt i 2))
328350

As loop is much more versatile, than Python's for there's no need to introduce special syntax here.

Let's consider another use case - iteration over some custom tree. Suppose the tree is represented by nodes pointing to their children.

(defstruct node
  data
  children)

We can walk over any tree/subtree with a rather small and simple macro.

(defmacro dotree ((var root &optional result-form) &body body)
  `(block nil
     (labels ((traverse (node)
                (let ((,var node))
                  ,@body
                  (dolist (child (children node))
                    (traverse child))
                  ,result-form)))
       (when-it ,root
         (traverse it)))))

(Warning: for the sake of more clarity I didn't use gensym in it, but you should).

Here's the example of its usage - getting a list of all the leaf nodes:

(let (rez)
  (dotree (node tree (reverse rez))
    (when (leafp node)
      (push node rez))))

This looks and works just like the standard dolist macro. And, as with dolist you can stop the iteration at any time, by calling return.

Overall, I'm yet to see a practical example of generator usage that can't be implemented in Lisp in some less complex way.

P.S. You can also take a look at the SERIES Lisp library, that implemented a similar concept to generators in the 90's. Or CLAZY - from the late 2000's.

Answer 6

Monads can be used to represent generators (even if the semantics are little different).

So any language allowing us to define monadic operations within a special syntax can be used here.

• VB.NET/C# (Linq - but C# already got yield return)
• Scala (For-comprehensions)
• Haskell (do-notation)
• F#/OCaml (Computation expressions/Perform)

Ruby can emulate generators through its builtin continuation capabilities.

Answer 7

Common Lisp, although does not have native continuations, allows to create delimited continuations using CPS transformers like cl-cont. So generators in Common Lisp can be written in pretty much the same way as Scheme generators.

By the way, continuation-based generators have one trait that Python and C# generators lack: the yield may be called in the dynamic extent of the generator function call. Python and C# generators allow yield to be placed only inside the body of a generator.

Answer 8

In general yield is redundant in languages that have first class functions. For example in TIScript you can do generators this way:

Generator. Note, it returns inner function.

function range( from, to )
{
  var idx = from - 1;
  return function() { if( ++idx <= to ) return idx; } // yields value on call
}

And its usage:

for( var item in range(12,24) )
  stdout << item << " ";

for(elem in source) in TIScript is slightly different from JS. If source is a function it gets called and its return value is assigned to the elem until the function will not return void (default return value of empty function).

Answer 9

Ruby:

Generator function:

def simple_range(n)
    Enumerator.new do |y|    
        (0..n).each { |v| y.yield(v) }
    end
end