Продолжение в общем lisp макросами - относительно реализации в OnLisp

Question

В On Lisp, с. 267, Пол Грэм обеспечивает реализацию макроса передачи продолжения:

(setq *cont* #'identity)

(defmacro =lambda (parms &body body)
  `#'(lambda (*cont* ,@parms) ,@body))

(defmacro =defun (name parms &body body)
  (let ((f (intern (concatenate 'string
                "=" (symbol-name name)))))
    `(progn
       (defmacro ,name ,parms
     `(,',f *cont* ,,@parms))
       (defun ,f (*cont* ,@parms) ,@body))))

(defmacro =bind (parms expr &body body)
  `(let ((*cont* #'(lambda ,parms ,@body))) ,expr))

(defmacro =values (&rest retvals)
  `(funcall *cont* ,@retvals))

Следующий код для обхода дерева t2 за каждый лист дерева t1, использует эту реализацию, и мне интересно, что происходит, когда restart называется, особенно после того, как лист t1 изменилось с A (первый элемент) B (второй элемент). когда restart называется, он просто выскакивает лямбда-функцию из *saved*и что лямбда-функции вызывает dft-node с (cdr tree) снова. Но этот вызов сделан вне рамок внешней =bind, а также =bind был ответственным за связывание *cont*, Как происходит связывание *cont* введенный внешним =bind все еще в области, тогда?

(setq *saved* nil)

(=defun dft-node (tree)
    (cond ((null tree) (restart))
          ((atom tree) (=values tree))
          (t (push #'(lambda () (dft-node (cdr tree))) *saved*)
             (dft-node (car tree)))))

(=defun restart ()
    (if *saved*
        (funcall (pop *saved*))
      (=values 'done)))

(setq t1 '(a (b (d h)) (c e (f i) g))
      t2 '(1 (2 (3 6 7) 4 5)))

(=bind (node1) (dft-node t1)
  (if (eq node1 'done)
      'done
    (=bind (node2) (dft-node t2)
      (list node1 node2))))

Последняя форма расширяется до

(let ((*cont* (lambda (node1)
                (if (eq node1 'done)
                    'done
                    (let ((*cont* (lambda (node2)
                                    (list node1 node2))))
                      (dft-node t2))
  (dft-node t1))))))

Это производит (a 1), По словам Грэма, последующие звонки restart должен производить (a 2)и так далее, до (a 5), а затем последующие звонки должны произвести (b 1), (b 2)и так далее, пока, наконец, (g 5):

> (let ((node1 (dft-node t1)))
    (if (eq? node1 ’done)
        ’done
        (list node1 (dft-node t2))))
(A 1)
> (restart)
(A 2)
…
> (restart)
(B 1)

После (a 1)Привязка *cont* установлено let больше не должно быть на месте. Как сделать последующие звонки на restart эти значения? Это сфера let все еще применяется к отдельному вызову restart? Что здесь происходит?

Answer 1

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

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

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

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

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

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

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

Поскольку (=bind …) расширяется до (let ((*cont*…))…), вы абсолютно правы в этом, если *cont*- специальная переменная (то есть с динамическим экстентом), то, как только вы за исключением этого let, исходная привязка *cont*, то есть идентичности, должна быть то, что должно быть в месте для вызовов на перезапуск. Если*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), * сохранено * содержит две функции. Первый - это тот, который будет продолжать проходить по числовому дереву в следующей ветви, а вызываемый *cont* будет глобальным идентификатором #, так как мы теперь вне формы = bind. Вот почему мы получаем 2, 3,... как результаты. Вторая функция в* сохраненная * на данный момент - это функция, которая будет продолжать проходить по алфавитному дереву в точке B.

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

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

В 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, которая ограничивает продолжение для нас.

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