Сегодня мы реализуем на scheme аналог генераторов из питона. Наш коллега palm mute уже приводил пример реализации в своем блоге: http://palm-mute.livejournal.com/12291.html, и сегодня мы не сильно выйдем за рамки этого поста.

В качестве ленивых списков мы будем использовать потоки из srfi-41. Возможно, это не самая хорошая идея, однако для демонстрации возможностей — вполне подойдет.

Главным нашим инструментом будет shift/reset. Reset, подобно begin, выделяет группу выражений. Shift позволяет прервать выполнение этой группы выражений и сразу выскочить за пределы reset.

В plt scheme, которой мы будем пользоваться, как shift/reset, так и потоки уже реализованы. Нам будет достаточно подключить два модуля.

(require scheme/control)
(require srfi/41)

Ну а теперь — небольшой пример

(display (reset
          (display 1)
          (display 2)
          (shift k 3)
          (display 4)))

>123

Основной профит shift заключен в его первом параметре. Первый параметр shift — континуация, невыполненная часть блока reset. С этой континуацийе можно обращаться как с любой другой функцией: вызывать, сохранять где-нибудь на будущее или (как в предыдущем примере) просто выкинуть.
Таким образом понятно, что должен делать yield — захватывать континуацию генератора с помощью shift и сохранять ее в stream-cdr.

(stream->;list (reset
               (shift k (stream-cons 1 (k (void))))
               (shift k (stream-cons 2 (k (void))))
               (shift k (stream-cons 3 (k (void))))
               stream-null))

>(1 2 3)

Стоит заметить, что при данной семантике yield последним выражением в reset (если, конечно, генератор вообще предполагает выход из блока reset) должен быть stream-null.

Итак, для определения генератора мы напишем такой вот несложный макрос. Во-первых, он заключает тело функции в reset, а во-вторых, заставляет ее всегда возвращать stream-null.

(define-syntax define-generator
  (syntax-rules ()
    ((_ (name args ...) body ...)
     (define (name args ...)
       (reset body ... stream-null)))))

А yield тогда будет обычной функцией.

(define (yield value)
  (shift k (stream-cons value (k (void)))))

Вуаля

(define-generator (make-123)
  (yield 1)
  (yield 2)
  (yield 3))

(stream->;list (make-123))

>(1 2 3)

Ну и последний на сегодня штрих. Определим хелпер, который позволит из генератора обращаться к другим генераторам (и к себе рекурсивно) и встраивать их выхлоп в собственный.

(define (yield-splice stream)
  (shift k (stream-append stream (k (void)))))

(define-generator (make-0-4)
  (yield 0)
  (yield-splice (make-123))
  (yield 4))

(stream->;list (make-0-4))

>(0 1 2 3 4)

На сегодня все, однако с питоновскими генераторами мы еще не закончили. Ведь что делает их по-настоящему интересными — так это возможность извне влиять на выполнение генератора с помощью send(). Send() позволяет указать значение, которое внутри генератора вернет yield. У нас yield возвращает то, что в качестве параметра передается в пойманную шифтом континуацию. То есть мы должны научиться вместо (void) передавать туда что-то полезное. Но это в следующий раз.