Generators in Python, Icon and Scheme

ol...@pobox.com

unread,

Oct 2, 2001, 11:38:29 PM10/2/01

to

This is a response to two articles discussing "generators" recently
introduced into Python 2.2. Prior to Python, generators enjoyed good
life in Icon. We will show how to translate the newly discovered
generative code into Scheme, almost verbatim.

The first article is
Charming Python : Iterators and simple generators
By David Mertz, Ph.D. (me...@gnosis.cx)
Autodidact, Gnosis Software, Inc.
September 2001
http://www-106.ibm.com/developerworks/linux/library/l-pycon?t=grl,l=252,p=iterators
Abstract:
Python 2.2 introduces a new construct accompanied by a new
keyword. The construct is generators; the keyword is yield.
Generators make possible several new, powerful, and expressive
programming idioms, but are also a little bit hard to get one's
mind around at first glance.

The second article by Ehud Lamm appeared on a discussion thread in
LtU:
http://lambda.weblogs.com/discuss/msgReader$1789

The second article gave a good illustration of generators in Icon:

If the result produced by a generator does not lead to the success
of an enclosing expression, however, the generator is resumed to
produce another value. An example is

if (i := find("or", sentence)) > 5 then write(i)

Here the first result produced by the generator, 3, is assigned to i,
but this value is not greater than 5 and the comparison operation
fails. At this point, the generator is resumed and produces the
second position, 23, which is greater than 5. The comparison
operation then succeeds and the value 23 is written.

This is how the Icon code looks in Scheme (the complete code is given
in Appendix)

(display
(fcar
(lfilter (lambda (val) (> val 5))
(generative (find-str-generator "or" sentence)))))

Almost literal translation.

Here,
; this is the Icon's find generator,
; which searches for occurrences of 'pattern' in str
(define (find-str-generator pattern str)
(lambda (suspend)
(let* ((pat-len (string-length pattern))
(str-len (string-length str))
(last-pos (- str-len pat-len))); last position where match can
occur
(do ((i 0 (+ 1 i)))
((> i last-pos)) ; a naive algorithm
(if (string=? pattern (substring str i (+ i pat-len)))
(suspend i))))))

For the second example, we print indices of all the occurrences of a
pattern in a string

(ffor-each (lambda (val) (display val) (display " "))
(generative (find-str-generator pattern sentence)))
trivial.

Finally, an example Python programmers seem to be proud of: an
in-order traversal of a tree.

; >>>> # A recursive generator that generates Tree leaves in
in-order.
; >>> def inorder(t):
; ... if t:
; ... for x in inorder(t.left):
; ... yield x
; ... yield t.label
; ... for x in inorder(t.right):
; ... yield x

Here's how the same example looks in Scheme

; tree:: '() | (list label tree-left tree-right)

(define (inorder tree)
(lambda (suspend)
(if (pair? tree)
(apply
(lambda (label left right)
(ffor-each suspend (generative (inorder left)))
(suspend label)
(ffor-each suspend (generative (inorder right))))
tree))))

and how it works:

(let ((tree (make-binary-tree 3)))
(display "Original tree\n")
(pp tree)
(display "In-order-traversal: ")
(ffor-each (lambda (val) (display val) (display " "))
(generative (inorder tree))))

Output:
Original tree
(1 (2 (4 () ()) (5 () ())) (3 (6 () ()) (7 () ())))
In-order-traversal: 4 2 5 1 6 3 7

Again, literally literal translation. IMHO Scheme code is more compact
and expressive.

Note, that our suspend is an ordinary, first-class value. An iterator
can operate that value as any other value (for instance, pass it to
ffor-each). This is in stark contrast to Python, where the
corresponding 'yield' keyword is a _keyword_.

Generators are implemented as lazy list. This idea has been discussed
in some detail two years ago,
http://pobox.com/~oleg/ftp/Scheme/enumerators-callcc.html

Appendix. Complete code for the framework and all the examples.

; generative PROC
; where PROC takes one argument: suspend
; PROC does an iteration, and whenever it feels, it calls suspend
; and passes it one value.
; The result of 'generative' is a lazy list made of all values passed
; to suspend
; Note, that suspend is an ordinary, first-class value. PROC can
operate
; that value as any other value. This is in stark contrast to Python,
; where the corresponding 'yield' keyword is a _keyword_.

; Lazy list: a promise, which when applied returns '() or
; (cons value lazy-list)
; data LazyList a = Promise (Nil | (Cons a (LazyList a)))

(define (generative iterator)
(delay
(call-with-current-continuation
(lambda (k-main)
(define (suspend val)
; (pp `("val" ,val) ##stderr)
(call-with-current-continuation
(lambda (k-reenter)
(k-main
(cons val
(delay
(call-with-current-continuation
(lambda (k-new-main)
(set! k-main k-new-main)
(k-reenter #f)))))))))
(iterator suspend)
(k-main '())))))

; this is the Icon's find generator,
; which searches for occurrences of 'pattern' in str
(define (find-str-generator pattern str)
(lambda (suspend)
(let* ((pat-len (string-length pattern))
(str-len (string-length str))
(last-pos (- str-len pat-len))); last position where match can
occur
(do ((i 0 (+ 1 i)))
((> i last-pos)) ; a naive algorithm
(if (string=? pattern (substring str i (+ i pat-len)))
(suspend i))))))

; Some implementations of Scheme can do forcing
implicitly...
(define (fcar x) (car (force x)))
(define (fcdr x) (cdr (force x)))
(define (fnull? x) (null? (force x)))

; A lazy filter
(define (lfilter pred lst)
(delay
(cond
((fnull? lst) lst)
((pred (fcar lst)) (cons (fcar lst) (lfilter pred (fcdr lst))))
(else (force (lfilter pred (fcdr lst)))))))

; A forceful for-each
(define (ffor-each proc lst)
(if (not (fnull? lst))
(begin (proc (fcar lst))
(ffor-each proc (fcdr lst)))))

; test 1
; An example from Icon
; if (i := find("or", sentence)) > 5 then write(i)

(for-each display
'("Test1" #\newline
"Print the index of the first occurrence of \"or\" which is
greater than 5"
#\newline))
(let ((sentence
"More generators, more generators!")
(pattern "or"))
(display
(fcar
(lfilter (lambda (val) (> val 5))
(generative (find-str-generator pattern sentence))))))
(newline)

; test 2
(for-each display
'(#\newline "Test2" #\newline
"Print indices of all occurrences of \"or\" in a sentence"
#\newline))
(let ((sentence
"More generators, more generators!")
(pattern "or"))
(ffor-each (lambda (val) (display val) (display " "))
(generative (find-str-generator pattern sentence))))
(newline)

; test 3
; From Charming Python : Iterators and simple generators
; By David Mertz, Ph.D. (me...@gnosis.cx)
; Autodidact, Gnosis Software, Inc.
; September 2001
; http://www-106.ibm.com/developerworks/linux/library/l-pycon?t=grl,l=252,p=iterators
; >>>> # A recursive generator that generates Tree leaves in
in-order.
; >>> def inorder(t):
; ... if t:
; ... for x in inorder(t.left):
; ... yield x
; ... yield t.label
; ... for x in inorder(t.right):
; ... yield x

; tree:: '() | (list label tree-left tree-right)

(define (inorder tree)
(lambda (suspend)
(if (pair? tree)
(apply
(lambda (label left right)
(ffor-each suspend (generative (inorder left)))
(suspend label)
(ffor-each suspend (generative (inorder right))))
tree))))

(define (make-binary-tree depth)
(let loop ((i 1) (depth depth))
(if (<= depth 0) '()
(list i (loop (* 2 i) (- depth 1)) (loop (+ 1 (* 2 i)) (- depth 1)))
)))

(for-each display
'(#\newline "Test3" #\newline
"in-order traversal of tree" #\newline))
(let ((tree (make-binary-tree 3)))
(display "Original tree\n")
(pp tree)
(display "In-order-traversal: ")
(ffor-each (lambda (val) (display val) (display " "))
(generative (inorder tree))))
(newline)

Ben Escoto

unread,

Oct 3, 2001, 4:46:15 AM10/3/01

to

In article <7eb8ac3e.0110...@posting.google.com>,
"ol...@pobox.com" <ol...@pobox.com> wrote:

> This is a response to two articles discussing "generators" recently
> introduced into Python 2.2. Prior to Python, generators enjoyed good
> life in Icon. We will show how to translate the newly discovered
> generative code into Scheme, almost verbatim.

I agree that lazy lists are nicer than generators in Python. Here are
two specific things which bothered me:

1. An iterator signals that there are no elements left by raising a
StopIteration exception. This is necessary because no value can be
excluded beforehand from being returned by the iterator.next() call.
Still, it can lead to programming errors because many programming
constructs (e.g. the for loop) catch these exceptions, instead of letting
them reach top level so a proper traceback is printed.

2. Reading from an iterator changes it, and there is no builtin way to
stick an element at the top of an iterator. So, for instance, it is
basically impossible to write a function that takes an iterator, returns
1 if the first element is even, and leaves the iterator the way it was.

3. This is less of an issue, but now there are many builtin functions
which work on lists, but have lazy equivalents which could work on
iterators, like len, ==, or, and, filter, map, etc. These are not hard
to define but it seems like someone should have done them for me, and
there perhaps should have been different defaults. For instance, if f()
is an infinite iterator:

def f():
i = 0
while 1:
yield i
i = i+1

then map(lambda x: x, f()) will hang instead of returning an iterator
like f().

Regular Python is not tail-recursive (I think to maintain C
compatibility), so it is awkward to use lazy lists without a stack
overflow. Given this limitation, I think iterators/generators are a good
addition to the language.

j...@itasoftware.com

unread,

Oct 3, 2001, 10:43:28 AM10/3/01

to