Я просто не получаю продолжения!

Представьте, что каждая строчка в вашей программе была отдельной функцией. Каждый принимает в качестве параметра следующую строку / функцию для выполнения.

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

Вы, вероятно, понимаете их лучше, чем думаете.

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

Пример Python:

try:
    broken_function()
except SomeException:
    # jump to here
    pass

def broken_function():
    raise SomeException() # go back up the stack
    # stuff that won't be evaluated

Генераторы являются примерами продолжений "только вниз". Они позволяют коду повторно входить в цикл, например, для создания новых значений.

Пример Python:

def sequence_generator(i=1):
    while True:
        yield i  # "return" this value, and come back here for the next
        i = i + 1

g = sequence_generator()
while True:
    print g.next()

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

Внимание! Этот пример не является ни кратким, ни исключительно ясным. Это демонстрация мощного применения продолжений. Как программист VB / ASP / C #, возможно, вы не знакомы с концепцией системного стека или состояния сохранения, поэтому цель этого ответа - демонстрация, а не объяснение.

Продолжения чрезвычайно универсальны и позволяют сохранить состояние выполнения и возобновить его позже. Вот небольшой пример совместной многопоточной среды, использующей продолжения в Scheme:

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

(define (fork)
  (display "forking\n")
  (call-with-current-continuation
   (lambda (cc)
     (enqueue (lambda ()
                (cc #f)))
     (cc #t))))

(define (context-switch)
  (display "context switching\n")
  (call-with-current-continuation
   (lambda (cc)
     (enqueue
      (lambda ()
        (cc 'nothing)))
     ((dequeue)))))

(define (end-process)
  (display "ending process\n")
  (let ((proc (dequeue)))
    (if (eq? proc 'queue-empty)
        (display "all processes terminated\n")
        (proc))))

Это предоставляет три глагола, которые может использовать функция: fork, context-switch и end-process. Операция fork разветвляет поток и возвращает #t в одном экземпляре и #f в другом. Операция переключения контекста переключает потоки между потоками, и конечный процесс завершает поток.

Вот пример их использования:

(define (test-cs)
  (display "entering test\n")
  (cond
    ((fork) (cond
              ((fork) (display "process 1\n")
                      (context-switch)
                      (display "process 1 again\n"))
              (else (display "process 2\n")
                    (end-process)
                    (display "you shouldn't see this (2)"))))
    (else (cond ((fork) (display "process 3\n")
                        (display "process 3 again\n")
                        (context-switch))
                (else (display "process 4\n")))))
  (context-switch)
  (display "ending process\n")
  (end-process)
  (display "process ended (should only see this once)\n"))

Результат должен быть

entering test
forking
forking
process 1
context switching
forking
process 3
process 3 again
context switching
process 2
ending process
process 1 again
context switching
process 4
context switching
context switching
ending process
ending process
ending process
ending process
ending process
ending process
all processes terminated
process ended (should only see this once)

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

P.S. - Думаю, я помню нечто подобное в On Lisp, поэтому, если вы хотите увидеть профессиональный код, вам следует почитать книгу.

Один из способов представить продолжение - это стек процессора. Когда вы «call-with-current-continue c», он вызывает вашу функцию «c», а параметр, переданный в «c», является вашим текущим стеком со всеми вашими автоматическими переменными на нем (представлен как еще одна функция, назовите ее «k "). Тем временем процессор начинает создание нового стека. Когда вы вызываете "k", он выполняет инструкцию "возврата из подпрограммы" (RTS) в исходном стеке, возвращая вас обратно в контекст исходного "call-with-current-continue" ("call-cc" from now on) и позволяя вашей программе продолжить работу, как и раньше. Если вы передали параметр в «k», он становится возвращаемым значением «call-cc».

С точки зрения вашего исходного стека, «call-cc» выглядит как обычный вызов функции. С точки зрения «c» ваш исходный стек выглядит как функция, которая никогда не возвращается.

Есть старый анекдот о математике, который поймал льва в клетке, забравшись в клетку, заперев ее и объявив, что находится вне клетки, в то время как все остальное (включая льва) находилось внутри нее. Продолжения немного похожи на клетку, а "c" немного похожи на математика. Ваша основная программа считает, что «c» находится внутри нее, в то время как «c» считает, что ваша основная программа находится внутри «k».

Вы можете создавать произвольные структуры потока управления, используя продолжения. Например, вы можете создать библиотеку потоков. «yield» использует «call-cc», чтобы поместить текущее продолжение в очередь, а затем переходит к продолжению в начале очереди. Семафор также имеет свою собственную очередь приостановленных продолжений, и поток перепланирован путем удаления его из очереди семафоров и помещения его в основную очередь.

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

Я все еще «привыкаю» к продолжениям, но один из способов думать о них, который я считаю полезным, - это абстракции концепции счетчика программ (ПК). ПК «указывает» на следующую инструкцию для выполнения в памяти, но, конечно, эта инструкция (и почти каждая инструкция) указывает, неявно или явно, на следующую инструкцию, а также на любые инструкции, которые должны обслуживать прерывания. (Даже инструкция NOOP неявно выполняет JUMP к следующей инструкции в памяти. Но если происходит прерывание, это обычно включает JUMP к какой-либо другой инструкции в памяти.)

Каждая потенциально «живая» точка в программе в памяти, к которой элемент управления может перейти в любой заданной точке, в некотором смысле является активным продолжением. Другие точки, которые могут быть достигнуты, - это потенциально активные продолжения, но, что более важно, это продолжения, которые потенциально «вычисляются» (возможно, динамически) в результате достижения одного или нескольких текущих активных продолжений.

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

Таким образом, продолжение можно рассматривать как высокоуровневую модель ПК, поэтому оно концептуально включает вызов / возврат обычной процедуры (точно так же, как в древнем железе выполнялся вызов / возврат процедуры через низкоуровневый JUMP, также известный как GOTO, инструкции плюс запись ПК при вызове и его восстановление при возврате), а также исключения, потоки, сопрограммы и т. Д.

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

Конечно, хотя обычно на компьютер (базовый процессор) может приходиться только один ПК, на самом деле существует много «активных» сущностей, подобных ПК, как упоминалось выше. Вектор прерывания содержит группу, стек - группу больше, некоторые регистры могут содержать некоторые и т.д. Они «активируются», когда их значения загружаются в аппаратный ПК, но продолжения являются абстракциями концепции, а не ПК или их точным эквивалентом. (нет неотъемлемой концепции «главного» продолжения, хотя мы часто думаем и кодируем в этих терминах, чтобы все было довольно просто).

По сути, продолжение - это представление того, «что делать дальше при вызове», и, как таковое, может быть (а в некоторых языках и в программах в стиле передачи продолжения часто является) первоклассным объектом, который является создаются, передаются и удаляются, как и большинство других типов данных, и очень похоже на то, как классический компьютер обрабатывает участки памяти по отношению к ПК - как почти взаимозаменяемые с обычными целыми числами.

В C # у вас есть доступ к двум продолжениям. Один, доступ к которому осуществляется через return, позволяет методу продолжить работу с того места, где он был вызван. Другой, доступ к которому осуществляется через throw, позволяет продолжить выполнение метода до ближайшего совпадающего catch.

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

Continuation callback = return;
callMeLater(callback);

Это может быть полезно во многих ситуациях. Один из примеров аналогичен приведенному выше, когда вы хотите приостановить выполняемую работу и возобновить ее позже, когда что-то произойдет (например, получение веб-запроса или что-то в этом роде).

Я использую их в нескольких проектах, над которыми работаю. В одном из них я использую их, чтобы приостановить программу, пока я жду ввода-вывода по сети, а затем возобновить ее позже. С другой стороны, я пишу язык программирования, на котором я даю пользователю доступ к продолжениям как значениям, чтобы они могли писать return и throw для себя - или любой другой поток управления, например, while циклы - без необходимости делать это для их.

Подумайте о нитях. Поток можно запустить, и вы можете получить результат его вычисления. Продолжение - это поток, который вы можете скопировать, поэтому вы можете выполнить одно и то же вычисление дважды.

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