call / cc реализация?

«Реализация call/cc» на самом деле не имеет смысла на уровне, на котором вы работаете; если вы можете реализовать call/cc на языке, это просто означает, что он имеет встроенную конструкцию, по крайней мере, столь же мощную, как call/cc. На уровне самого языка call/cc в основном является примитивным оператором потока управления, как и должно быть в некоторой форме ветвления.

Конечно, вы можете реализовать язык с call/cc на языке без него; это потому, что он находится на более низком уровне. Вы переводите конструкции языка определенным образом и оформляете этот перевод так, чтобы можно было реализовать call/cc; то есть, как правило, стиль передачи продолжения (хотя для непереносимой реализации на C вы также можете просто скопировать стек напрямую; позже я более подробно расскажу о стиле передачи продолжения). На самом деле это не дает сколько-нибудь глубокого понимания call/cc самого - понимание заключается в модели, с помощью которой вы делаете это возможным. Вдобавок call/cc - это просто оболочка.

Итак, Haskell не раскрывает понятия продолжения; это нарушит ссылочную прозрачность и ограничит возможные стратегии реализации. Cont реализована в Haskell, как и любая другая монада, и вы можете рассматривать ее как модель языка с продолжениями, использующими стиль передачи продолжения, точно так же, как монада списка моделирует недетерминизм.

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

Что подводит нас к фактической реализации:

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
• Быстрая и грязная реинверсия управления (демонстрирует "реальное" использование продолжений)
• Раздел продолжения и разграниченный контроль сайта Олега Киселева