Лекция
Привет, Вы узнаете о том , что такое продолжение, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое продолжение, yield, await, callcc, call-with-current-continuation , настоятельно рекомендую прочитать все из категории Алгоритмизация и программирование. Структурное программирование. Язык C.
продолжение (англ. continuation) — абстрактное представление состояния программы в определенный момент, которое может быть сохранено и использовано для перехода в это состояние. Продолжения содержат всю информацию, чтобы продолжить выполнения программы с определенной точки; состояние глобальных переменных обычно не сохраняется, однако для функциональных языков это несущественно (например, выборочное сохранение и восстановление значений глобальных объектов в Scheme достигается отдельным механизмом dynamic-wind). Продолжения похожи на goto Бейсика или макросы setjmp и longjmp в Си, так как также позволяют перейти в любое место программы. Но продолжения, в отличие от goto, позволяют перейти только в участок программы с определенным состоянием, которое должно быть сохранено заранее, в то время, как goto позволяет перейти в участок программы с неинициализированными переменными.
Первый язык, реализовавший концепцию продолжений — Scheme, позднее встроенная поддержка продложений появилась в ряде других языков.
Самое раннее описание продолжений было сделано Адрианом ван Вейнгаарденом в сентябре 1964 года. Вейнгаарден выступал на Рабочей конференции IFIP по языкам описания формальных языков, проходившей в Баден-бай-Вена, Австрия. В рамках лекарственной формы для в Алгол 60 препроцессором, он призвал к трансформации соответствующих процедур в продолжение обходя стиле , , хотя он не использовал это имя, и его намерение состояло в том, чтобы упростить программу и тем самым сделать его результат более Чисто.
Кристофер Стрэчи , Кристофер П. Уодсворт и Джон С. Рейнольдс выдвинули термин « продолжение» на видное место в своей работе в области денотационной семантики, которая широко использует продолжения, позволяя анализировать последовательные программы с точки зрения семантики функционального программирования .
Стив Рассел изобрел продолжение в своей второй реализации Лиспа для IBM 704 , хотя и не назвал его.
Рейнольдс (1993) дает полную историю открытия продолжений.
Формально, callcc — это функция высшего порядка, позволяющая абстрагировать динамический контекст имеющейся функции в виде другой функции, которая и называется «продолжением».
Более наглядно, продолжение — это «вся оставшаяся часть программы от данной точки», или «функция, которая никогда не возвращает управление в точку своего вызова» . В курсах функционального программирования объяснение понятия продолжения часто сводится к «расширению (усложнению) понятия сопрограммы», но в дидактическом смысле такое объяснение считается бесполезным . Причина трудности объяснения концепции заключается в том, что продолжения фактически являются альтернативным обоснованием понятия «поведения» («вызова» в самом широком понимании), то есть несут иную семантическую модель, и в этом смысле начальный переход от «обычного» функционального программирования к программированию с интенсивным использованием продолжений можно сравнить с начальным переходом от императивного программирования к функциональному.
Продолжения обеспечивают математическое обоснование всего порядка выполнения программы, от goto и циклов до рекурсии, исключений, генераторов, сопрограмм и механизма возврата . Как следствие, они позволяют реализовать все эти элементы в языке посредством единой конструкции.
Первоклассные продолжения - это способность языка полностью контролировать порядок выполнения инструкций. Их можно использовать для перехода к функции, которая вызвала вызов текущей функции, или к функции, которая ранее завершилась. Можно думать о первоклассном продолжении , как сохранение выполнения состояния программы. Важно отметить, что настоящие первоклассные продолжения не сохраняют данные программы - в отличие от образа процесса - только контекст выполнения. Это иллюстрируется описанием "бутерброда продолжения":
Допустим, вы находитесь на кухне перед холодильником и думаете о бутерброде. Вы тут же берете продолжение и кладете в карман. Затем вы достаете из холодильника индейку и хлеб и делаете себе бутерброд, который теперь стоит на прилавке. Вы вызываете продолжение в кармане и снова стоите перед холодильником, думая о бутерброде. Но, к счастью, на прилавке есть бутерброд, и все материалы, из которых он сделан, исчезли. Итак, вы его съедите. :-)
В этом описании, сэндвич является частью программы данных (например, объект в куче), и вместо вызова «сделай бутерброд» рутину , а затем возвращается, человек называется «грим бутерброд с текущим продолжением» рутиной, которая создает бутерброд, а затем продолжает с того места, где было остановлено выполнение.
Scheme была первой полноценной производственной системой (1969-1970), обеспечивающей сначала «отлов» , а затем вызов / cc . Брюс Дуба ввел call / cc в SML .
Продолжения также используются в моделях вычислений, включая денотационную семантику , модель актора , исчисления процессов и лямбда-исчисления . Эти модели полагаются на программистов или инженеров-семантиков, которые пишут математические функции в так называемом стиле передачи продолжения . Это означает, что каждая функция потребляет функцию, которая представляет остальную часть вычислений относительно этого вызова функции. Чтобы вернуть значение, функция вызывает эту «функцию продолжения» с возвращаемым значением; чтобы прервать вычисление, он возвращает значение.
Функциональные программисты, которые пишут свои программы в стиле продолжения, получают выразительную способность манипулировать потоком управления произвольными способами. Цена заключается в том, что они должны поддерживать инварианты управления и продолжения вручную, что может быть очень сложной задачей (но см. «Стиль передачи продолжения» ниже).
Программирование в стиле передачи продолжений (англ. continuation-passing style, CPS) — это стиль программирования, при котором передача управления осуществляется через механизм продолжений. Стиль CPS впервые представили Джеральд Джей Сассман и Гай Стил-младший , одновременно с языком Scheme.
Программу в «классическом стиле» зачастую можно переписать в стиле передачи продолжений. Например, для задачи вычисления гипотенузы прямоугольного треугольника с «классическим» кодом на Haskell:
pow2 :: Float -> Float
pow2 a = a ** 2
add :: Float -> Float -> Float
add a b = a + b
pyth :: Float -> Float -> Float
pyth a b = sqrt (add (pow2 a) (pow2 b))
можно добавить один аргумент типа F, где F означает функцию из возвращаемого значения исходной функции в произвольный тип x, а возвращающим значением сделать этот произвольный тип x:
pow2' :: Float -> (Float -> a) -> a
pow2' a cont = cont (a ** 2)
add' :: Float -> Float -> (Float -> a) -> a
add' a b cont = cont (a + b)
-- типы a -> (b -> c) и a -> b -> c эквивалентны, поэтому CPS-функцию можно
-- рассмотреть как функцию высшего порядка от одного аргумента
sqrt' :: Float -> ((Float -> a) -> a)
sqrt' a = \cont -> cont (sqrt a)
pyth' :: Float -> Float -> (Float -> a) -> a
pyth' a b cont = pow2' a (\a2 -> pow2' b (\b2 -> add' a2 b2 (\anb -> sqrt' anb cont)))
В функции pyth' вычисляется квадрат от a, и в качестве продолжения передается функция (лямбда-выражение), принимающую единственным аргументом a в квадрате. Об этом говорит сайт https://intellect.icu . Далее таким же образом вычисляются все последующие промежуточные значения. Для того, чтобы произвести вычисления в качестве продолжения необходимо передать функцию от одного аргумента, например функцию id, которая возвращает любое переданное ей значение. Таким образом выражение pyth' 3 4 id эквивалентно 5.0.
Стандартная haskell-библиотека в модуле Control.Monad.Cont содержит тип Cont, позволяющий использовать CPS функции в монаде. Функция pyth' будет выглядеть следующим образом:
pow2_m :: Float -> Cont a Float
pow2_m a = return (a ** 2)
-- функция cont поднимает обычные CPS функции в монаду
pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = do
a2 <- pow2_m a
b2 <- pow2_m b
anb <- cont (add' a2 b2)
r <- cont (sqrt' anb)
return r
Также данный модуль содержит функцию callCC, имеющую тип MonadCont m => ((a -> m b) -> m a) -> m a. Из типа видно, что она принимает единственным аргументом функцию, которая в свою очередь также имеет единственным аргументом функцию, прерывающую дальнейшие вычисления. Например, мы можем прервать дальнейшие вычисления, если хотя бы один из аргументов отрицательный:
pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = callCC $ \exitF -> do
when (b < 0 || a < 0) (exitF 0.0) -- when :: Applicative f => Bool -> f () -> f ()
a2 <- pow2_m a
b2 <- pow2_m b
anb <- cont (add' a2 b2)
r <- cont (sqrt' anb)
return r
Примеры CPS в Scheme:
|
Direct style |
Continuation passing style |
|---|---|
(define (pyth x y)
(sqrt (+ (* x x) (* y y))))
|
(define (pyth& x y k)
(*& x x (lambda (x2)
(*& y y (lambda (y2)
(+& x2 y2 (lambda (x2py2)
(sqrt& x2py2 k))))))))
|
(define (factorial n)
(if (= n 0)
1 ; NOT tail-recursive
(* n (factorial (- n 1)))))
|
(define (factorial& n k)
(=& n 0 (lambda (b)
(if b ; продолжение растет
(k 1) ; в рекурсивном вызове
(-& n 1 (lambda (nm1)
(factorial& nm1 (lambda (f)
(*& n f k)))))))))
|
(define (factorial n)
(f-aux n 1))
(define (f-aux n a)
(if (= n 0)
a ; tail-recursive
(f-aux (- n 1) (* n a))))
|
(define (factorial& n k) (f-aux& n 1 k))
(define (f-aux& n a k)
(=& n 0 (lambda (b)
(if b ; продолжение сохраняется
(k a) ; в рекурсивном вызове
(-& n 1 (lambda (nm1)
(*& n a (lambda (nta)
(f-aux& nm1 nta k)))))))))
|
В «чистом» CPS фактически не существует самих продолжений — всякий вызов оказывается хвостовым. Если язык не гарантирует оптимизацию хвостовых вызовов (англ. Tail call optimization, TCO), то при каждом вложенном вызове callcc растет и само продолжение, и стек вызовов. Обычно это нежелательно, но временами используется интересным способом (например, в компиляторе Chicken Scheme[en]). Совместное использование стратегий оптимизации TCO и CPS позволяет полностью устранить динамический стек из исполнимой программы. Ряд компиляторов функциональных языков работает именно таким образом, к примеру компилятор SML/NJ для языка Standard ML.
Существует несколько разновидностей продолжений. Наиболее распространенная из них — неограниченные продолжения (undelimited continuations), реализуемые с помощью функции call/cc или ее аналогов. Такие продолжения действительно представляют собой состояние всей программы (или одной ее нити) в определенный момент. Вызов такого продолжения не похож на вызов функции, поскольку он соответствует «прыжку» в сохраненное состояние программы и не возвращает никакого значения; такое продолжение обычно нельзя вызвать несколько раз. Ограниченные продолжения (delimited continuations) абстрагируют зависимость результата некоторого блока программы от результата некоторого подвыражения этого блока. В определенном смысле они соответствуют некоторому сегменту стека вызовов, а не всему стеку. Такие продолжения могут использоваться как функции, вызываться несколько раз и так далее. Они абстрагируются с помощью механизма shift/reset: reset оборачивает внешний блок, shift действует как call/cc, но получает в качестве аргумента не глобальное продолжение, а ограниченное — зависимость значения блока reset от значения на месте блока shift. Существуют и другие разновидности, к примеру prompt/control.
Одна из областей практического использования продолжений - это веб-программирование . Использование продолжений защищает программиста от природы протокола HTTP без сохранения состояния . В традиционной модели веб-программирования отсутствие состояния отражается в структуре программы, что приводит к созданию кода, основанного на модели, которая очень плохо подходит для выражения вычислительных проблем. Таким образом, продолжения позволяют коду, который имеет полезные свойства, связанные с инверсией управления , избегая при этом его проблем. Инвертирование инверсии управления или продолжения по сравнению с программированием, ориентированным на страницыэто статья, которая представляет собой хорошее введение в продолжения, применяемые в веб-программировании.
Некоторые из наиболее популярных веб-серверов, поддерживающих продолжение, - это Racket Web Server , UnCommon Web Framework и Weblocks Web framework для Common Lisp , Seaside framework для Smalltalk , Ocsigen / Eliom для OCaml , Continuity для Perl , Wee для Ruby , Tales Framework. для Fantom и фреймворка Nagare для Python , Wt для C ++ ,MFlow для Haskell . Apache Cocoon рамки веб - приложение также предоставляет продолжений (см инструкцию Кокон ).
Многие языки программирования предоставляют эту возможность под различными именами, например:
call/cc (краткая запись для
call-with-current-continuation );SMLofNJ.Cont.callcc, также реализовано в Concurrent ML;setcontext и аналоги (UNIX System V и GNU libc);callcc;Continuation currentDo:, в большинстве современных реализаций продолжения могут быть реализованы на чистом Smalltalk, не требуя специальной поддержки в виртуальной машине;await и yield;Continuation;callCC (в модуле Control.Monad.Cont);callcc0 и callcc1;yield;_continuation.continulet;suspend, на основе которого реализованы async, await, yield и некоторые другие сопрограммные конструкции.yield;yield return и await.В любом языке, поддерживающем замыкания, можно писать программы в стиле передачи продолжений и вручную реализовать call/cc. В частности, это принятая практика в Haskell, где легко строятся «монады, передающие продолжения» (для примера, монада Cont и трансформер монад ContT библиотеки mtl).
Поддержка продолжений сильно различается. Язык программирования поддерживает повторно вызываемые продолжения, если продолжение можно вызывать повторно (даже после того, как оно уже было возвращено). Повторно вызываемые продолжения были введены Питером Дж. Ландином с помощью оператора J (для перехода), который мог передавать поток управления обратно в середину вызова процедуры. Повторно вызываемые продолжения также называются «возвращающимися» на языке Racket . Однако такое использование термина «повторно входящий» можно легко спутать с его использованием при обсуждении многопоточности .
Более ограниченный вид - это продолжение перехода, которое можно использовать для перехода от текущего контекста к окружающему. Многие языки, которые явно не поддерживают продолжения, поддерживают обработку исключений , которая эквивалентна escape-продолжениям и может использоваться для тех же целей. C setjmp/longjmpтакже эквивалентны: их можно использовать только для раскрутки стека. Экранированные продолжения могут также использоваться для реализации исключения хвостового вызова .
Одно из обобщений продолжений - это продолжения с ограничениями . Операторы продолжения, такие как call/ccзахват всех оставшихся вычислений в заданной точке программы, не дают возможности ограничить этот захват. Операторы продолжения с разделителями решают эту проблему, предоставляя два отдельных механизма управления: приглашение , ограничивающее операцию продолжения, и оператор реификации, такой как shiftили control. Таким образом, продолжения, записанные с использованием операторов с разделителями, представляют собой лишь часть контекста программы.
Продолжения являются функциональным выражением оператора GOTO , и здесь применяются те же предостережения. Хотя они и являются разумным вариантом в некоторых особых случаях, таких как веб-программирование, использование продолжений может привести к созданию кода, за которым трудно следовать. Фактически, эзотерический язык программирования Unlambda включает вызов с текущим продолжением как одну из своих функций исключительно из-за его сопротивления пониманию. [ необходима цитата ] Внешние ссылки ниже иллюстрируют концепцию более подробно.
В статье «Продолжение и природа количественной оценки» Крис Баркер представил «гипотезу продолжения», согласно которой
некоторые лингвистические выражения (в частности, QNP [количественные словосочетания с существительными]) имеют обозначения, которые манипулируют своими собственными продолжениями. [10]
Баркер утверждал, что эту гипотезу можно использовать для объяснения таких явлений, как двойственность значения NP (например, тот факт, что QNP «все» ведет себя совершенно иначе, чем неколичественная именная фраза «Боб», внося свой вклад в значение такого предложения, как «Алиса видит [Боба / всех]»), смещение прицела (например, «капля дождя упала на каждую машину» обычно интерпретируется как
а не как 
) и неоднозначность области действия (предложение типа «кто-то видел всех» может быть двусмысленным между
и 
). Он также заметил, что эта идея в некотором роде является естественным продолжением подхода Ричарда Монтегю в «Правильном подходе к количественной оценке в обычном английском» (PTQ), написав, что «с точки зрения ретроспективы ограниченная форма передачи продолжения - это четко прослеживается в основе трактовки PTQ Монтегю (1973) NP как обобщенных кванторов ".
Степень, в которой продолжения могут быть использованы для объяснения других общих явлений на естественном языке, является темой текущих исследований.
Данная статья про продолжение подтверждают значимость применения современных методик для изучения данных проблем. Надеюсь, что теперь ты понял что такое продолжение, yield, await, callcc, call-with-current-continuation и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмизация и программирование. Структурное программирование. Язык C
Комментарии
Оставить комментарий
Алгоритмизация и программирование. Структурное программирование. Язык C
Термины: Алгоритмизация и программирование. Структурное программирование. Язык C