Продолжения дают программисту возможность управлять потоком программы. Хотя сама концепция существует в любом языке программирования, продолжения наиболее эффективны в языках, которые относятся к ним как к гражданам первого класса и включают оптимизацию хвостовых вызовов. Этот пост является введением в продолжение и не будет касаться стиля прохождения продолжения (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