Создание итераторов в лисп

[dmitry_vk]

Заинтересовался вопросом создания итераторов в лиспе. В питоне и C# это делается очень удобным образом. В питоне это делается с помощью генераторов, а в C# с помощью iterator blocks.

Пример на питоне:

def make_range(a,b):
    for x in xrange(a,b):
        yield x

for x in make_range(10,20):
    print x

И на C#:

static IEnumerable<int> make_range(int a, int b)
{
    for (i = a; i < b; ++i)
	yield return i;
}

foreach (int x in make_range(10,20))
    Console.WriteLine(x);

В обоих случаях компилятор сам заботится о том, чтобы сохранить состояние функции-генератора и правильно восстановить это состояние при возврате к итератору (правда, имеются некоторые оговорки, связанные с обработкой исключений и прочих нелокальных выходов, например, в C# нельзя yield поместить внутрь try-блока).

В лиспе на уровне языка нет генераторов. Генераторы просто реализуются с помощью продолжений (continuations), но в Common Lisp их нет (хотя они есть в Scheme). С помощью макросов их можно добавить в язык (это делает библиотека cl-cont; к ним тоже применима оговорка насчет того, что нельзя пользоваться продолжениями внутри catch, throw, unwind-protect и progv).

Также, в лиспе есть библиотека iterate, которая добавляет конструкцию iter, которая представляет собой мощную и расширяемую конструкцию для организации всевозможных циклов. Расширения к iterate пишутся в виде макросов, явно организующих нужные действия по перебору элементов чего-либо (или другие действия, не обязательно связанные с перебором элементов). Но это менее удобно, чем написание генераторов, как в питоне, из-за того, чтобы необходимо отдельно сохранять состояние и возобновлять/прерывать перебор. Поэтому, дополним iterate, чтобы можно было использовать итераторы и напишем макрос для создания итераторов.

Вот так будет выглядеть создание и использование итератора:

(defiterator range-iterator (a b)
  (iter (for i from a below b)
	(yield-return i)))

(iter (for i iterating (range-iterator 10 20))
      (format t "~A~%" i))

Собственно, реализация выглядит следующим образом:

(defmacro defiterator (name (&rest args) (&body body))
  `(defun ,name (,@args)
     (macrolet ((yield-return (v) `(let/cc k (values ,v k)))
		(yield-break () '(let/cc k (declare (ignore k)) nil)))
       (lambda ()
	 (with-call/cc
	   ,body)))))

(defmacro-driver (FOR var ITERATING iterator)
  (let ((iterator-name (gensym "ITERATOR-"))
	(th (gensym))
	(nx (gensym))
	(kwd (if generate 'generate 'for)))
    `(progn
       (with ,iterator-name = ,iterator)
       (,kwd ,var next (multiple-value-bind (,th ,nx) (funcall ,iterator-name)
			 (unless ,nx (terminate))
			 (setf ,iterator-name ,nx)
			 ,th)))))

Реализация не является оптимальной и наилучшей, а является лишь proof-of-concept.

Итератор, определенный таким образом, работает следующим образом. Функция, определенная макросом defiterator, возвращает итератор. Итератор — это функция, которая возвращает либо текущее значение и функцию, которую нужно вызвать в следующий раз, либо NIL, что означает, что итерация закончена.

References:

• cl-cont
• Continuations in Common Lisp with cl-cont
• Behind the scenes of the C# yield keyword
• ECMA-334: 15.14 The yield statement
• Python Reference Manual, The yield statement

Comments

[daapp.livejournal.com]

а чем собственно dolist или loop не итераторы?

[dmitry-vk.livejournal.com]

1) dolist нельзя просто остановить
2) loop не расширяем
3) в них нельзя управлять перебором (т.е., остановить перебор, приостановить, скомбинировать различные переборы) и т.п.
4) расширять неудобно.