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

Question

Что они и для чего они хороши?

У меня нет степени CS, и я имею опыт работы с VB6 -> ASP -> ASP.NET/C#. Кто-нибудь может объяснить это ясно и кратко?

Answer 1

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

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

Answer 2

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

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

Пример 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()

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

Answer 3

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

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

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

(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, поэтому, если вы хотите увидеть профессиональный код, вы должны проверить книгу.

Answer 4

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

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

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

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

Answer 5

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

Answer 6

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

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

Continuation callback = return;
callMeLater(callback);

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

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

Answer 7

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

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

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

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

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

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

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

Answer 8

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

Answer 9

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