Ответ 1
"Реализация 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)
Что здесь происходит?! 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 -> ...). Поэтому, поскольку он никогда не должен действительно давать значение, он может уйти с возвратом ценности любого типа, который он хочет. Sneaky!
Что приводит нас к фактической реализации:
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) и выработать то, как вы получаете результаты, которые вы делаете, чтобы почувствовать поток управления.
Рекомендуем продолжить чтение на продолжениях:
- Мать всех Монад (ранее связанная)
- продолжение стиля прохождения глава Haskell Wikibook
- Быстрая и грязная реверсия управления (показывающая "реальное" использование продолжений)
- раздел продолжения и ограниченный контроль раздела сайта Олега Киселева