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

Что такое продолжение?

Продолжение можно рассматривать как остаток вычисления. Это утверждение не имеет большого смысла само по себе; это лучше всего понять на примере.

Возьмем, к примеру, следующее вычисление:

5 + (6 * 3) - 12

текущее вычисление: (6 * 3) . Продолжением в этот момент является оставшаяся часть вычислений, то есть все вычисления, исключая текущие вычисления, то есть «добавь пять и вычти двенадцать». Это можно представить как 5 + _ — 12, где _ — это дыра в продолжении, которое будет заполнено результатом текущего вычисления. Продолжение будет меняться на протяжении цикла вычислений. Как только вычислено (6 * 3), вычисление фактически становится 5 + 18 — 12. Текущее вычисление в этот момент становится (5 + 18), а продолжение становится _ — 12. Затем текущее вычисление становится 23 — 12, а продолжение в этот момент пусто, так как после того, как текущее вычисление вернет значение, нет никакого вычисления, которое нужно выполнить.

Другой способ думать о продолжениях состоит в том, что они предоставляют способ сослаться на состояние программы в произвольный момент ее выполнения. Мне особенно нравится описание, представленное в журнале электронной почты от профессионала по программированию на Perl Люка Палмера:

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

Предположим, вы находитесь на кухне перед холодильником и думаете о
сэндвиче (так в оригинале). Берешь продолжение тут же и суешь в карман
. Затем вы достаете из холодильника индейку и хлеб и
делаете себе бутерброд, который сейчас стоит на прилавке. Вы
вызываете продолжение в кармане и снова оказываетесь
стоящим перед холодильником и думая о сэндвиче (sic). Но
к счастью, на прилавке есть сэндвич (sic), и все материалы,
из которых он был сделан, исчезли. Итак, вы едите это. :-)

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

Чем полезны продолжения?

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

Начало работы с продолжениями в Scheme

Вот функциональное представление первого продолжения в примере из введения, записанное на схеме. (текущее вычисление — (6 * 3), а текущее продолжение — 5 + _ — 12.

((lambda (v)
  (- (+ 5 v) 12)) 
 (* 6 3))

Лямбда-выражение представляет собой продолжение. Лямбда-выражение применяется к умножению 6 и 3, что является представлением текущего вычисления.

Однако Scheme позволяет вам «захватить» текущее продолжение с помощью процедуры call-with-current-continuation или call/cc.

(- (+ 5 (call/cc 
         (lambda (k) 
           (begin
             (set! *k* k)
             (k (* 6 3))))))
 12)

В схеме продолжения являются объектами первого класса, а это означает, что мы можем установить переменную *k*, чтобы захватить текущее продолжение. Таким образом, мы можем применить захваченное продолжение к любому произвольному значению вне контекста, в котором оно было захвачено (например, (*k* (* 3 4)) оценивается как 5 ). Хотя это простой пример, этот метод открывает двери для некоторых очень интересных и мощных парадигм программирования.

Другой пример использования call/cc можно найти в главе 3 книги Язык программирования схемы Кента Дайбвига.

(define product
  (lambda (ls)
    (call/cc
      (lambda (break)
        (let f ([ls ls])
          (cond
            [(null? ls) 1]
            [(= (car ls) 0) (break 0)]
            [else (* (car ls) (f (cdr ls)))]))))))
;(product '(1 2 3 4 5)) => 120
;(product '(7 3 8 0 1 9 5)) => 0

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

Как только вы начнете осваивать продолжения, вы сможете изучить продолжения с разделителями, которые позволят вам реализовать практически любую управляющую структуру в программировании. Я бы указал вам на работу Кеничи Асаи, программиста и профессора Университета Очаномидзу в Японии.

ПРИМЕЧАНИЕ. Большинство идей в этом посте были взяты у Уильяма Берда. Я настоятельно рекомендую изучить его доклады, видео, гугл-тусовки и книги. Этот пост основан в основном на его видео в гугл-тусовках о продолжениях. Я намерен поделиться с вами этими идеями и поразмышлять над концепциями, которые я изучил.

Другие источники:

http://matt.might.net/articles/by-example-continuation-passing-style/
https://www.youtube.com/watch?v=2GfFlfToBCo
http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines/
https://www.scheme.com/tspl4/further .html#g63
https://www.youtube.com/watch?v=QNM-njddhIw
https://marijnhaverbeke.nl/cps/
http ://www.cs.toronto.edu/~david/courses/csc324_w15/extra/choice.html
https://groups.google.com/forum/#!msg/perl.perl6.language /-KFNPaLL2yE/_RzO8Fenz7AJ