Продолжение схемы для чайников

Ответ 1

Забудьте о call/cc на мгновение. Каждое выражение /statement на любом языке программирования имеет продолжение - то есть, что вы делаете с результатом. В C, например,

x = (1 + (2 * 3)); 
printf ("Done");

имеет продолжение математического присваивания printf(...); продолжением (2 * 3) является 'add 1; присваивать x; Е (...)". Концептуально продолжение есть ли у вас доступ к нему. Подумайте на мгновение, какая информация вам нужна для продолжения - информация 1) состояние памяти кучи (в общем), 2) стек, 3) любые регистры и 4) счетчик программ.

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

В Схеме и на нескольких других языках у вас есть доступ к продолжению. По существу, за вашей спиной компилятор + среда выполнения объединяет всю информацию, необходимую для продолжения, сохраняет ее (как правило, в куче) и дает вам ручку. Рукояткой, которую вы получаете, является функция "k" - если вы вызываете эту функцию, вы будете продолжать точно после точки call/cc. Важно отметить, что вы можете вызывать эту функцию несколько раз, и вы всегда будете продолжать после точки call/cc.

Посмотрим на некоторые примеры:

> (+ 2 (call/cc (lambda (cont) 3)))
5

В приведенном выше результате результат call/cc является результатом lambda, который равен 3. Продолжение не было вызвано.

Теперь добавим продолжение:

> (+ 2 (call/cc (lambda (cont) (cont 10) 3)))
12

Вызывая продолжение, мы пропускаем что-либо после вызова и продолжаем прямо в точке call/cc. При (cont 10) продолжение возвращает 10, который добавляется к 2 для 12.

Теперь сохраним продолжение.

> (define add-2 #f)
> (+ 2 (call/cc (lambda (cont) (set! add-2 cont) 3)))
5
> (add-2 10)
12
> (add-2 100)
102

Сохраняя продолжение, мы можем использовать его, как нам нравится, для "перехода к" любому вычислению, следующему за точкой call/cc.

Часто для нелокального выхода используются продолжения. Подумайте о функции, которая будет возвращать список, если не возникнет какая-либо проблема, в которую будет возвращена точка '().

(define (hairy-list-function list)
  (call/cc
    (lambda (cont)
       ;; process the list ...

       (when (a-problem-arises? ...)
         (cont '()))

       ;; continue processing the list ...

       value-to-return)))

Ответ 2

Вот текст из примечаний к классу: http://tmp.barzilay.org/cont.txt. Он основан на нескольких источниках и значительно расширен. У этого есть мотивы, основные объяснения, более подробные объяснения того, как это делается, и большое количество примеров, которые идут от простого к продвинутому и даже быстрое обсуждение ограниченных продолжений.

(Я попытался воспроизвести весь текст здесь, но, как я и ожидал, 120k текста не является чем-то, что делает SO счастливым.

Ответ 3

Я не буду пытаться объяснить все места, где продолжения могут быть полезны, но я надеюсь, что я могу привести краткие примеры основного места, где я нашел продолжение, полезное в моем собственном опыте. Вместо того, чтобы говорить о Схеме call/cc, я бы сосредоточил внимание на стиле продолжения прохождения. В некоторых языках программирования переменные могут обладать динамическим охватом, а на языках без динамического охвата можно использовать шаблон с глобальными переменными (при условии, что нет проблем с многопоточным кодом и т.д.). Например, предположим, что есть список активных в настоящее время потоков ведения журнала, *logging-streams* и мы хотим вызвать function в динамической среде, где *logging-streams* дополняется logging-stream-x. В Common Lisp мы можем сделать

(let ((*logging-streams* (cons logging-stream-x *logging-streams*)))
  (function))

Если у нас нет динамически ограниченных переменных, как в схеме, мы все еще можем сделать

(let ((old-streams *logging-streams*))
  (set! *logging-streams* (cons logging-stream-x *logging-streams*)
  (let ((result (function)))
    (set! *logging-streams* old-streams)
    result))

Теперь давайте предположим, что на самом деле мы даем древовидное дерево, у которых не nil листья являются потоками ведения журнала, все из которых должны находиться в *logging-streams*, когда вызывается function. У нас есть два варианта:

• Мы можем сгладить дерево, собрать все протоколирующие потоки, расширить *logging-streams*, а затем вызвать function.
• Мы можем, используя стиль продолжения прохождения, пересечь дерево, постепенно расширяя *logging-streams*, наконец, называя function, когда больше не нужно tree.

Вариант 2 выглядит примерно так:

(defparameter *logging-streams* '())

(defun extend-streams (stream-tree continuation)
  (cond
    ;; a null leaf
    ((null stream-tree)
     (funcall continuation))
    ;; a non-null leaf
    ((atom stream-tree)
     (let ((*logging-streams* (cons stream-tree *logging-streams*)))
       (funcall continuation)))
    ;; a cons cell
    (t
     (extend-streams (car stream-tree)
                     #'(lambda ()
                         (extend-streams (cdr stream-tree)
                                         continuation))))))

С этим определением имеем

CL-USER> (extend-streams
          '((a b) (c (d e)))
          #'(lambda ()
              (print *logging-streams*)))
=> (E D C B A) 

Теперь, было ли что-нибудь полезное в этом? В этом случае, вероятно, нет. Некоторые незначительные преимущества могут заключаться в том, что extend-streams является хвостовым рекурсивным, поэтому у нас нет большого количества использования стека, хотя промежуточные затворы составляют его в кучном пространстве. У нас есть тот факт, что возможное продолжение выполняется в динамической области любого промежуточного материала, который настроен extend-streams. В этом случае это не все, что важно, но в других случаях это может быть.

Возможность абстрагироваться от некоторого потока управления, а также иметь нелокальные выходы или быть в состоянии подобрать расчет где-то с некоторого времени назад, может быть очень удобной. Это может быть полезно, например, для поиска в обратном направлении. Здесь продолжителющий алгоритм пропозиционального исчисления предложений для формул, где формула является символом (пропозициональным литералом) или списком формы (not formula), (and left right) или (or left right).

(defun fail ()
  '(() () fail))

(defun satisfy (formula 
                &optional 
                (positives '())
                (negatives '())
                (succeed #'(lambda (ps ns retry) `(,ps ,ns ,retry)))
                (retry 'fail))
  ;; succeed is a function of three arguments: a list of positive literals,
  ;; a list of negative literals.  retry is a function of zero
  ;; arguments, and is used to `try again` from the last place that a
  ;; choice was made.
  (if (symbolp formula)
      (if (member formula negatives) 
          (funcall retry)
          (funcall succeed (adjoin formula positives) negatives retry))
      (destructuring-bind (op left &optional right) formula
        (case op
          ((not)
           (satisfy left negatives positives 
                    #'(lambda (negatives positives retry)
                        (funcall succeed positives negatives retry))
                    retry))
          ((and) 
           (satisfy left positives negatives
                    #'(lambda (positives negatives retry)
                        (satisfy right positives negatives succeed retry))
                    retry))
          ((or)
           (satisfy left positives negatives
                    succeed
                    #'(lambda ()
                        (satisfy right positives negatives
                                 succeed retry))))))))

Если найдено удовлетворяющее присваивание, то succeed вызывается с тремя аргументами: список положительных литералов, список отрицательных литералов и функция, которая может повторить поиск (т.е. попытаться найти другое решение). Например:

CL-USER> (satisfy '(and p (not p)))
(NIL NIL FAIL)
CL-USER> (satisfy '(or p q))
((P) NIL #<CLOSURE (LAMBDA #) {1002B99469}>)
CL-USER> (satisfy '(and (or p q) (and (not p) r)))
((R Q) (P) FAIL)

Второй случай интересен тем, что третий результат не является FAIL, а некоторой вызываемой функцией, которая попытается найти другое решение. В этом случае мы можем видеть, что (or p q) выполнимо, если либо p, либо q true:

CL-USER> (destructuring-bind (ps ns retry) (satisfy '(or p q))
           (declare (ignore ps ns))
           (funcall retry))
((Q) NIL FAIL)

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

(defun satisfy-all (formula &aux (assignments '()) retry)
  (setf retry #'(lambda () 
                  (satisfy formula '() '()
                           #'(lambda (ps ns new-retry)
                               (push (list ps ns) assignments)
                               (setf retry new-retry))
                           'fail)))
  (loop while (not (eq retry 'fail))
     do (funcall retry)
     finally (return assignments)))

CL-USER> (satisfy-all '(or p (or (and q (not r)) (or r s))))
(((S) NIL)   ; make S true
 ((R) NIL)   ; make R true
 ((Q) (R))   ; make Q true and R false
 ((P) NIL))  ; make P true

Мы могли бы немного изменить бит loop и получить только n заданий, вплоть до некоторого n или вариантов этой темы. Зачастую стиль продолжения прохождения не нужен или может сделать код сложным для поддержания и понимания, но в тех случаях, когда он полезен, он может сделать некоторые другие очень сложные вещи довольно легко.

Ответ 4

TL; DR: продолжения только что захвачены GOTO со значениями более или менее.

Экзамен, о котором вы спрашиваете,

(call/cc
  (lambda (k)
    ;;;;;;;;;;;;;;;;
    (* 5 (k 4))                     ;; body of code
    ;;;;;;;;;;;;;;;;
    )) => 4 

может быть приблизительно переведена, например, Общий Lisp, как

(prog (k retval)
    (setq k (lambda (x)             ;; capture the current continuation:
                    (setq retval x) ;;   set! the return value
                    (go EXIT)))     ;;   and jump to exit point

    (setq retval                    ;; get the value of the last expression,
      (progn                        ;;   as usual, in the
         ;;;;;;;;;;;;;;;;
         (* 5 (funcall k 4))        ;; body of code
         ;;;;;;;;;;;;;;;;
         ))
  EXIT                              ;; the goto label
    (return retval))

Это просто иллюстрация; в Common Lisp мы не можем вернуться в тег PROG после того, как мы вышли из него в первый раз. Но на Схеме, с реальными продолжениями, мы можем. Если мы установим некоторую глобальную переменную внутри тела функции, называемой call/cc, скажем (setq qq k), в Scheme мы можем вызвать ее в любое более позднее время, из любого места, повторно вступая в один и тот же контекст (например, (qq 42)).

Точка состоит в том, что тело формы call/cc может содержать выражение if или cond. Он может вызывать продолжение только в некоторых случаях, а в других - нормально, оценивая все выражения в теле кода и возвращая последнее значение, как обычно. Там может быть глубокая рекурсия. Вызывая завершенное продолжение, достигается немедленный выход.

Итак, мы видим здесь, что k определено. Он определяется вызовом call/cc. Когда вызывается (call/cc g), он вызывает свой аргумент с текущим продолжением: (g the-current-continuation). the current-continuation "процедура побега" , указывающая на точку возврата формы call/cc. Чтобы вызвать это, нужно указать значение, как если бы оно было возвращено формой call/cc.

Таким образом, приведенные выше результаты в

((lambda(k) (* 5 (k 4))) the-current-continuation) ==>

(* 5 (the-current-continuation 4)) ==>

; to call the-current-continuation means to return the value from
; the call/cc form, so, jump to the return point, and return the value:

4