Как интерпретировать callCC в Haskell?
На схеме выполнение продолжения, полученного из call/cc эффективно возвращается к этому начальному вызову /cc и восстанавливает сохраненный стек вызовов.
Я только начал изучать Хаскель, и я пытаюсь понять, как понять callCC, То есть попытаться понять callCC с точки зрения понимания схемы call/cc, Реализация callCC является
callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h
Насколько я могу судить, ничего не упомянуто о сохраненных или восстановленных стеках вызовов. Как можно интерпретировать callCC в Haskell исходя из знакомства с Scheme's call/cc,
Редактировать: Может быть, если бы кто-то мог перевести следующее на Haskell, это помогло бы мне понять.
(define (f return)
(return 2)
3)
(display (f (lambda (x) x))) ; displays 3
(display (call-with-current-continuation f)) ; displays 2
2 ответа
Это работает очень похоже на вызов схемы / CC. Вы должны принять во внимание, что он находится в монаде Cont.
Фактическая функция определяется с помощью ContT. ContT - это преобразователь монад, который позволяет добавлять продолжения в другие монады, но давайте сначала посмотрим, как это работает с монадой Identity, и ограничимся Cont.
Cont r a = Cont {runCont :: (a->r)->r}
Вот, Cont r a представляет функцию, которая может вычислить некоторое значение типа a, поскольку дана функция типа a->r он может вычислить значение типа r,
Это явно монада
return x = Cont $ \f -> f x
(тривиальное "вычисление" значения типа a)
ma >>= h = Cont $ \f -> runCont ma $ \a -> runCont (h a) f
(Вот ma :: Cont r a, а также h :: a -> Cont r b)
(вычисление значения типа a, ма, может превратиться в вычисление значения типа b - runCont ma дано h, который, учитывая значение типа a, "знает", как произвести вычисление значения типа b - которые могут быть снабжены функцией f :: b -> r вычислить значение типа r)
По сути, h является продолжением ma, а также >>= связывает ma и его продолжение, чтобы произвести продолжение композиции функций (функция "скрыта" внутри ma производить a и функция "спрятана" внутри h производить b). Это тот "стек", который вы искали.
Давайте начнем с упрощенного типа (не используя ContT):
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
Здесь callCC использует функцию, которая создает продолжение по данному продолжению.
Есть важный момент, который вы, похоже, тоже упускаете. callCC имеет смысл только если есть продолжение после callCC - т.е. есть продолжение, чтобы пройти. Давайте рассмотрим, что это последняя строка do-блок, это то же самое, что сказать, что оно должно быть связано с чем-то >>=:
callCC f >>= return "blah"
Сделаю. Важным моментом здесь является то, что операция callCC легче понять, когда вы видите этот контекст, когда вы видите, что он находится на левой стороне >>=,
Зная, как >>= работает, и с учетом право-ассоциативности >>=, ты это видишь h в callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h на самом деле построен с использованием текущего продолжения - он построен с использованием h появляется справа от >>= - целиком do-блок от линии, следующей за callCC до конца:
(callCC f) >>= h =
Cont $ \g -> runCont
(cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h) $
\a -> runCont (h a) g =
[reduction step: runCont (Cont x) => x]
Cont $ \g -> (\h -> runCont (f (\a -> Cont $ \_ -> h a)) h) $
\a -> runCont (h a) g =
[(\h -> f) (\a -> ...) => f [h/(\a -> ...)] -- replace
occurrences of h with (\a -> ...)]
Cont $ \g -> runCont (f (\a -> Cont $ \_ -> (\b -> runCont (h b) g) a)) $
\a -> runCont (h a) g =
[(\b -> runCont (h b) g) a => runCont (h a) g]
Cont $ \g -> runCont (f (\a -> Cont $ \_ -> runCont (h a) g)) $
\a -> runCont (h a) g
Вы можете увидеть здесь, как \_ -> runCont (h a) g по сути, будет игнорировать продолжение после вызова функции, переданной f - и "переключить стек", переключиться на текущее продолжение h места, где callCC вызывается.
(Аналогичные рассуждения могут применяться, если callCC является последним в цепочке, хотя не так ясно, что "текущее продолжение" в этом случае является функцией, переданной runCont)
Последнее, что runCont (f...) h на самом деле не использует этот последний h, если фактический вызов h происходит изнутри продолжения, вычисленного fесли это когда-нибудь случится.
Чтобы понять, что означает callCC в Haskell, вы, возможно, захотите взглянуть на его тип, а не на его реализацию:
callCC :: MonadCont m => ((a -> m b) -> m a) -> m a
Первая и самая важная вещь здесь - это MonadCont m. Это означает, что callCC работает только в монадах, которые реализуют MonadCont - и это может вас разочаровать, но IO не является экземпляром MonadCont. В этом отношении callCC работает не так, как в схеме.
В любом случае, параметр для callCC ((a -> m b) -> m a): это вычисление, которое требует (a -> m b) в качестве его параметра, который является продолжением, которое захватывает callCC. Итак, давайте попробуем написать что-то, что использует callCC:
import Control.Monad.Cont
fun _ = return "hi"
main = print $ runCont (callCC fun) id
Теперь это довольно скучно, так как мы никак не используем продолжение. Давайте попробуем с другим весельем:
fun' escape = do escape "ahoy"
return "die die die"
Когда вы запустите код, вы увидите, что "вызов" для выхода никогда не "возвращается" - он вызвал продолжение, как в схеме. Вы, наверное, знаете, что "возвращение" не работает таким образом в Haskell: это не операция короткого замыкания. Вы могли бы подумать, что callCC дает вам возможность завершить вычисления раньше.
На уровне реализации cont и runCont являются функциями, которые преобразуются в / из стиля продолжения передачи. Вы хотите изучить монаду продолжения более подробно, чтобы узнать, как она на самом деле работает. Попробуйте, например. http://www.haskellforall.com/2012/12/the-continuation-monad.html
(Во многих реализациях схем call/cc на самом деле не работает путем "сохранения стеков вызовов"). Если вы конвертируете программу в CPS, то вызов / cc вроде бы выпадает "бесплатно". Я думаю, вы могли бы хочу прочитать, например, этот http://www.pipeline.com/~hbaker1/CheneyMTA.html, в котором обсуждается один способ реализации CPS на низком уровне.)