«Реализация call/cc» на самом деле не имеет смысла для слоя, на котором вы работаете;если вы можете реализовать call/cc на языке, это означает, что он имеет встроенную конструкцию, по крайней мере такую же мощную, как call/cc.На уровне самого языка call/cc по сути является примитивным оператором потока управления, точно так же, как должна быть некоторая форма ветвления.
Конечно, вы можете реализовать язык с call/cc на языке безЭто;это потому, что это на более низком уровне.Вы переводите языковые конструкции особым образом, и вы организуете этот перевод так, чтобы вы могли реализовать call/cc;то есть, как правило, стиль передачи продолжения (хотя для непереносимой реализации в C вы также можете просто скопировать стек напрямую; позже я расскажу о стиле передачи продолжения).Это на самом деле не дает какого-либо большого понимания самой call/cc - понимание модели, с которой вы делаете это возможным.Кроме того, call/cc - это просто оболочка.
Теперь Хаскелл не раскрывает понятие продолжения;это нарушит прозрачность ссылок и ограничит возможные стратегии реализации.Cont реализован в Haskell, как и любая другая монада, и вы можете думать о нем как о модели языка с продолжениями, использующими стиль прохождения продолжения, точно так же, как недетерминированные модели монады списка.
Технически,это определение callCC действительно наберет, если вы просто удалите приложения Cont и runCont.Но это не поможет вам понять, как это работает в контексте монады Cont, поэтому давайте посмотрим на ее определение.(Это определение не используется в текущей библиотеке Monad Transformer Library, поскольку все монады в ней построены поверх своих версий преобразователя, но оно соответствует использованию фрагмента Cont (который работает только с более старой версией).) и значительно упрощает.)
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
ОК, поэтому Cont r a - это просто (a -> r) -> r, а runCont позволяет нам получить эту функцию из значения Cont r a.Достаточно просто.Но что это значит?
Cont r a - это вычисление с прохождением продолжения с конечным результатом r и результатом a.Что означает окончательный результат?Хорошо, давайте напишем тип runCont более явно:
runCont :: Cont r a -> (a -> r) -> r
Итак, как мы видим, «конечный результат» - это значение, которое мы получаем из runCont в конце.Теперь, как мы можем построить вычисления с Cont?Экземпляр монады просветляет:
instance Monad (Cont r) where
return a = Cont (\k -> k a)
m >>= f = Cont (\k -> runCont m (\result -> runCont (f result) k))
Хорошо, хорошо, это просветление, если вы уже знаете, что это значит.Ключевым моментом является то, что когда вы пишете Cont (\k -> ...), k равняется остальной части вычисления - он ожидает, что вы дадите ему значение a, а затем даст вам окончательный результатвычисление (типа r, запомните) назад, которое вы затем можете использовать в качестве собственного возвращаемого значения, потому что ваш тип возврата тоже r.Уф!И когда мы запускаем вычисление Cont с runCont, мы просто указываем окончательный k - «верхний уровень» вычисления, который дает конечный результат.
Что это за остальная частьвычисление "называется? продолжение, , потому что это продолжение вычисления!
(>>=) на самом деле довольно просто: мы запускаем вычисление слева, давая ему собственный остаток вычислений.Этот остаток вычислений просто передает значение в f, который производит свои собственные вычисления.Мы выполняем это вычисление, вводя его в остальную часть вычислений, которая была дана нашему комбинированному действию.Таким образом, мы можем объединить вычисления в Cont:
computeFirst >>= \a ->
computeSecond >>= \b ->
return (a + b)
или, в более привычной записи do:
do a <- computeFirst
b <- computeSecond
return (a + b)
Затем мы можем запустить эти вычисления с помощьюrunCont - в большинстве случаев что-то вроде runCont foo id будет работать просто отлично, превращая foo с тем же результатом и типом конечного результата в его результат.
Пока все хорошо.Теперь давайте запутаемся.
wtf :: Cont String Int
wtf = Cont (\k -> "eek!")
aargh :: Cont String Int
aargh = do
a <- return 1
b <- wtf
c <- return 2
return (a + b + c)
Whздесь происходит ?!wtf - это Cont вычисление с конечным результатом String и результатом Int, но Int в поле зрения нет.
Что происходит, когда мы запускаем aargh, скажем, с runCont aargh show- т.е. запустить вычисление и show его Int результат как String для получения окончательного результата?
Мы получаем "eek!" назад.
Помните, как k это «остальная часть вычислений»?То, что мы сделали в wtf, - это хитро , а не , назовите это и вместо этого предоставьте наш собственный конечный результат - который затем становится, ну, наконец, окончательным!
Это всего лишь продолжение вещейсможет сделать.Что-то вроде Cont (\k -> k 1 + k 2) выполняет остальную часть вычисления, как если бы он возвратил 1, и снова , как если бы он возвратил 2, и складывает два окончательных результата вместе!Продолжения в основном позволяют выразить произвольно сложный нелокальный поток управления, делая их настолько мощными, насколько они сбивают с толку.Действительно, продолжения настолько общие, что в некотором смысле каждая монада является частным случаем Cont.В самом деле, вы можете думать о (>>=) в целом как о некоем стиле прохождения продолжения:
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
Второй аргумент - это продолжение, принимающее результат первого вычисления и возвращающее остальную часть вычислениячтобы бежать.
Но я до сих пор не ответил на вопрос: что происходит с этим callCC?Ну, это вызывает функцию, которую вы даете с текущим продолжением.Но подождите секунду, разве это не то, что мы уже делали с Cont?Да, но сравните типы:
Cont :: ((a -> r) -> r) -> Cont r a
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
Да.Видите ли, проблема с Cont заключается в том, что мы не можем упорядочить действия из внутри функции, которую мы передаем - мы просто производим результат r в чистом виде.callCC позволяет получить доступ к продолжению, обойти его и просто смешать с вычислениями из Cont.Когда у нас есть
do a <- callCC (\cc -> ...)
foo ...
Вы можете представить cc как функцию, которую мы можем вызвать с любым значением внутри функции, чтобы сделать это возвращаемое значение callCC (\cc -> ...) вычисления само по себе .Или, конечно, мы могли бы просто вернуть значение обычным образом, но тогда вызов callCC во-первых, был бы немного бессмысленным:)
Что касается таинственного b, то это просто потому, что вы можетеиспользуйте cc foo для вычисления любого типа, который вы хотите, поскольку он избегает нормального потока управления и, как я уже сказал, сразу же использует его как результат всегоcallCC (\cc -> ...).Таким образом, поскольку ему никогда не нужно создавать значение, ему может быть возвращено значение любого типа.Подлый!
Что приводит нас к фактической реализации:
callCC f = Cont (\k -> runCont (f (\a -> Cont (\_ -> k a))) k)
Сначала мы получим весь остаток вычислений и назовем его k.Но о чем эта f (\a -> Cont (\_ -> k a)) часть?Что ж, мы знаем, что f принимает значение типа (a -> Cont r b), и это то, чем является лямбда - функция, которая принимает значение для использования в результате callCC f, и возвращает вычисление Cont, которое игнорируетего продолжение и просто возвращает это значение через k - «остаток вычисления» с точки зрения callCC f.Итак, результат этого вызова f - это еще одно вычисление Cont, для которого нам потребуется предоставить продолжение, чтобы выполнить.Мы просто пропускаем то же самое продолжение снова, поскольку, если все пойдет нормально, мы хотим, чтобы все возвращаемое вычисление было нашим возвращаемым значением и продолжалось нормально.(Действительно, передача другого значения не имеет смысла смысла - это "вызов с текущим продолжением", а не "вызов с продолжением, отличным от того, с которым вы на самом деле меня запускаете").)
В общем, я надеюсь, что вы нашли это столь же поучительным, как и долго.Продолжения очень мощные, но может потребоваться много времени, чтобы понять, как они работают.Я предлагаю поиграть с Cont (который вам нужно будет назвать cont, чтобы заставить вещи работать с текущим mtl) и выяснить, как вы получаете результаты, которые вы делаете, чтобы почувствовать поток управления.
Рекомендованныйзакончились дальнейшие чтения по продолжениям: