Is there a straightforward lisp equivalent of Python's generators?

Question

In Python you can write this:

def firstn(n):
     num = 0
     while num < n:
         yield num
         num += 1

What is the lisp equivalent of this?

Gentian

Answer 1

Existing package

Download, install and load the GENERATORS system with Quicklisp. Then, use package :generators (or preferably, define your own package first).

(ql:quickload :generators)
(use-package :generators)

Define an infinite generator for random values:

(defun dice (n)
  (make-generator ()
    ;; repeatedly return a random value between 1 and N
    (loop (yield (1+ (random n))))))

Use the generator:

(loop
   with dice = (dice 6)
   repeat 20
   collect (next dice))

=> (1 2 6 1 1 4 4 2 4 3 6 2 1 5 6 5 1 5 1 2)

Note however what the author of the library says:

This library is more of an interesting toy, though as far as I know it does work. I dont think I have ever used this in application code, though I think that with care, it could be.

See also

• The ITERATE package provides a way to define generators for use inside its iteration facility.

• The SERIES package provide stream-like data structures and operations on them.

• The Snakes library (same approach as GENERATORS as far as I know).

• Iterators in generic-cl

Closures

In practice, CL does not rely that much on generators as popularized by Python. What happens instead is that when people need lazy sequences, they use closures:

(defun dice (n)
  (lambda ()
    (1+ (random n))))

Then, the equivalent of next is simply a call to the thunk generated by dice:

(loop
   with dice = (dice 6)
   repeat 20
   collect (funcall dice))

This is the approach that is preferred, in particular because there is no need to rely on delimited continuations like with generators. Your example involves a state, which the dice example does not require (there is a hidden state that influences random, but that's another story) . Here is how your counter is typically implemented:

(defun first-n (n)
  (let ((counter -1))
    (lambda ()
      (when (< counter n)
        (incf counter)))))

Higher-order functions

Alternatively, you design a generator that accepts a callback function which is called by your generator for each value. Any funcallable can be used, which allows the caller to retain control over code execution:

(defun repeatedly-throw-dice (n callback)
  (loop (funcall callback (1+ (random n)))))

Then, you can use it as follows:

(prog ((counter 0) stack)
  (repeatedly-throw-dice 6 
    (lambda (value)
      (if (<= (incf counter) 20)
        (push value stack)
        (return (nreverse stack))))))

See documentation for PROG.

do-traversal idiom

Instead of building a function, data sources that provides a custom way of generating values (like matches of a regular expressions in a string) also regularly provide a macro that abstracts their control-flow. You would use it as follows:

 (let ((counter 0)  stack)
   (do-repeatedly-throw-dice (value 6)
     (if (<= (incf counter) 20)
       (push value stack)
       (return (nreverse stack))))))

DO-X macros are expected to define a NIL block around their body, which is why the return above is valid.

A possible implementation for the macro is to wrap the body in a lambda form and use the callback-based version defined above:

(defmacro do-repeatedly-throw-dice ((var n) &body body)
  `(block nil (repeatedly-throw-dice ,n (lambda (,var) ,@body))))

Directly expanding into a loop would be possible too:

(defmacro do-repeatedly-throw-dice ((var n) &body body)
  (let ((max (gensym)) (label (make-symbol "NEXT")))
    `(prog ((,max ,n) ,var)
        ,label
        (setf ,var (1+ (random ,max)))
        (progn ,@body)
        (go ,label))))

One step of macroexpansion for above form:

(prog ((#:g1078 6) value)
 #:next
  (setf value (1+ (random #:g1078)))
  (progn
   (if (<= (incf counter) 20)
       (push value stack)
       (return (nreverse stack))))
  (go #:next))

Bindings

Broadly speaking, building a generator with higher-order functions or directly with a do- macro gives the same result. You can implement one with the other (personally, I prefer to define first the macro and then the function using the macro, but doing the opposite is also interesting, since you can redefine the function without recompiling all usages of the macro).

However, there is still a difference: the macro reuses the same variable across iterations, whereas the closure introduces a fresh binding each time. For example:

(let ((list))
  (dotimes (i 10) (push (lambda () i) list))
  (mapcar #'funcall list))

.... returns:

(10 10 10 10 10 10 10 10 10 10)

Most (if not all) iterators in Common Lisp tend to work like this¹, and it should not come as a surprise for experienced users (the opposite would be surprising, in fact). If dotimes was implemented by repeatedly calling a closure, the result would be different:

(defmacro my-dotimes ((var count-form &optional result-form) &body body)
  `(block nil
     (alexandria:map-iota (lambda (,var) ,@body) ,count-form)
     ,result-form))

With the above definition, we can see that:

(let ((list))
  (my-dotimes (i 10) (push (lambda () i) list))
  (mapcar #'funcall list))

... returns:

(9 8 7 6 5 4 3 2 1 0)

In order to have the same result with the standard dotimes, you only need to create a fresh binding before building the closure:

(let ((list))
  (dotimes (i 10) 
    (let ((j i))
      (push (lambda () j) list))))

Here j is a fresh binding whose value is the current value of i at closure creation time; j is never mutated so the closure will constantly return the same value. If you wanted to, you could always introduce that inner let from the macro, but this is rarely done.

---

1: Note that the specification for DOTIMES does not require that bindings are fresh at each iteration, or only mutates the same binding at each step: "It is implementation-dependent whether dotimes establishes a new binding of var on each iteration or whether it establishes a binding for var once at the beginning and then assigns it on any subsequent iterations." In order to write portably, it is necessary to assume the worst-case scenario (i.e. mutation, which happens to be what most (all?) implementations do) and manually rebind iteration variables if they are to be captured and reused at a later point.

Keely

Closures is what I was going for. Thank you! – Gentian

bonus: iterators in generic-cl: github.com/alex-gutev/generic-cl#iterator – Knighthood

Awesome detailed response. Thanks! – Ey