продолжение в common lisp макросами относительно реализации в OnLisp

On Lisp немного старше Common Lisp, поэтому есть некоторые несовместимости.

On Lisp был написан до того, как Common Lisp фактически закрепился как язык, поэтому существуют некоторые несовместимости между кодом, который появляется в On Lisp, и Common Lisp. В записи CLiki в On Lisp отмечается, что эти макросы передачи продолжения на самом деле одно из мест, где есть несовместимость (выделено мной):

При определении макросов, передающих продолжение (стр. 267), Пол Грэм, кажется, предполагает, что глобальная переменная cont имеет лексическую область видимости. Это противоречит стандарту Common Lisp. В современных реализациях Common Lisp вышеупомянутые макросы просто не работают. Кроме того, эта проблема может сбить с толку новичков. Предлагаемые решения для исправления макросов (обратите внимание, что #'values ​​используется вместо #'identity - в соответствии с Errata Пола Грэма):

• эмулировать глобальную переменную cont с лексической областью видимости, используя макрос-символ, который может быть скрыт с помощью let или lambda:
  (defvar actual-cont #'values)
  (define -symbol-macro *cont* *actual-cont*)
• просто опустите (setq *cont* #'identity) и вызовите функцию передачи продолжения "верхнего уровня" как (=somefunc #'values...)
• …

Это довольно краткое описание проблемы, и его стоит изучить немного подробнее, чтобы помочь новичкам, которые столкнутся с этим в будущем. Также может быть полезно просмотреть другие обсуждения этой же проблемы, в том числе:

• стр. 268 из ‹On Lisp›... A Ветка comp.lang.lisp от 2006 года, в которой пользователь спрашивает о разнице между (setq *cont* …) и (defvar *cont* …). В этой теме люди отмечают, что On Lisp предшествует ANSI Common Lisp.

Что на самом деле происходит?

Поскольку (=bind …) расширяется до (let ((*cont* …)) …), вы совершенно правы, если *cont* — это специальная переменная (т. е. с динамическим экстентом), то, как только вы выйдете за пределы этого let, исходная привязка *cont*, т. е. identity — это то, что должно использоваться для вызовов перезапуска. Если *cont* объявлен специальным, вы получите следующее поведение:

CONTINUATIONS> (=bind (node1) (dft-node '(a (b (d h)) (c e (f i) g)))
                 (if (eq node1 'done)
                     'done
                     (=bind (node2) (dft-node '(1 (2 (3 6 7) 4 5)))
                       (list node1 node2))))
(A 1)
CONTINUATIONS> (restart)
2
CONTINUATIONS> (restart)
3
CONTINUATIONS> (restart)
6
CONTINUATIONS> (restart)
7
CONTINUATIONS> (restart)
4
CONTINUATIONS> (restart)
5
CONTINUATIONS> (restart)
B
CONTINUATIONS> (restart)
D

Это имеет смысл, потому что после получения (1) *saved* содержит две функции. Первый — это тот, который продолжит обход числового дерева на следующей ветке, а *cont*, который будет вызываться, является глобальным, #'identity, так как мы теперь вне формы =bind. Вот почему мы получаем 2, 3, … в качестве результатов. Вторая функция в *saved* на данный момент — это та, которая продолжит обход алфавитного дерева в точке B.

Причина, по которой мы не получаем кучу списков (a 1), (a 2), …, (b 1) и т. д. выше, заключается в том, что мы (разумно) предположили, что *cont* является особым, т. е. динамически связанным. Оказывается, Грэм намеревается сделать *cont* не особенным; он хочет, чтобы это была глобальная лексика. Из О Lisp, стр. 268:

Именно манипулируя *cont* мы получим эффект продолжений. Хотя *cont* имеет глобальное значение, оно редко будет использоваться: *cont* почти всегда будет параметром, захваченным =values и макросами, определенными =defun. Например, в теле add1 *cont* является параметром, а не глобальной переменной. Это различие важно, потому что эти макросы не работали бы, если бы *cont* не была локальной переменной. Вот почему *cont* получает свое начальное значение в setq, а не в defvar: последнее также объявило бы его особенным.

On Lisp немного предшествовал Common Lisp, так что это не обязательно было неверным на момент написания, но Common Lisp на самом деле не имеет глобальных лексических переменных, так что это не тот случай, когда использование ( setq *cont* …) на верхнем уровне обязательно создаст глобальную лексическую переменную. В Common Lisp точные результаты не указаны. Некоторые реализации будут рассматривать его как глобальную лексику, другие предполагают, что вы имели в виду defparameter или defvar, и в итоге вы получите глобальный специальный переменная. Как отмечает Грэм, это не сработает. Похоже, у вас есть реализация, которая делает последнее, поэтому ничего не работает.

Некоторые реализации на самом деле будут жаловаться на его код. SBCL, например, справедливо жалуется на (setq *cont* …), печатая "предупреждение: неопределенная переменная: CONTINUATIONS::*CONT*", и выдает предупреждение о стиле, когда используется *cont*, что он "использует лексический привязка символа (CONTINUATIONS::*CONT*), а не динамическая привязка, даже несмотря на то, что имя соответствует обычному соглашению об именовании (имена типа *FOO*) для специальных переменных».

Что должно произойти?

Чтобы понять, как это предполагается работать, вероятно, проще взглянуть на более простую реализацию, в которой нет всей логики, которая есть в версии On Lisp:

(defparameter *restarts* '())

(defun do-restart ()
  (if (endp *restarts*) nil
      (funcall (pop *restarts*))))

(defun traverse-tree (k tree)
  (cond
    ((null tree) (do-restart))
    ((atom tree) (funcall k tree))
    (t (push (lambda () (traverse-tree k (cdr tree))) *restarts*)
       (traverse-tree k (car tree)))))

Здесь мы не скрываем ни механизм передачи продолжения, ни список *restarts*. При этом мы получаем такое поведение:

CL-USER> (traverse-tree 'identity '((1 2) (3 4)))
1
CL-USER> (do-restart)
2
CL-USER> (do-restart)
3
CL-USER> (do-restart)
4
CL-USER> (do-restart)
NIL

Мы также можем воссоздать обход нескольких списков, и я думаю, мы получим ожидаемые результаты:

CL-USER> (let ((k (lambda (num)
                    (traverse-tree (lambda (alpha)
                                     (list num alpha))
                                   '(a (b) c)))))
           (traverse-tree k '((1 2) 3)))
(1 A)
CL-USER> (do-restart)
(1 B)
CL-USER> (do-restart)
(1 C)
CL-USER> (do-restart)
(2 A)
CL-USER> (do-restart)
(2 B)
CL-USER> (do-restart)
(2 C)
CL-USER> (do-restart)
(3 A)
CL-USER> (do-restart)
(3 B)
CL-USER> (do-restart)
(3 C)
CL-USER> (do-restart)
NIL

Разница здесь в том, что нет ссылок на *cont*, значение которых меняется, как только мы выходим из области действия let, ограничивающей для нас продолжение.

На мой взгляд, лучшей реализацией было бы просто использовать обычную лексическую переменную a для хранения продолжения (вроде k выше, но, вероятно, с именем, созданным gensym), и просто потребует, чтобы «вызовы функций передачи продолжения в конечном итоге были заключены в =bind, определяющий самое внешнее продолжение.