Я пытаюсь найти способ вызова /cc. Лучшее, что я нашел, это фрагмент Haskell:
callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k
Хотя это не так просто, как я хочу из-за Cont и runCont. Я также нашел описания того, что он делает, хотя никогда не так ясно, как фактический код.
Итак, как это реализовано в простейшей форме? Я отмечаю это с помощью Scheme и Haskell, поскольку это два языка, которые я предпочитаю.
"Реализация 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) и выработать то, как вы получаете результаты, которые вы делаете, чтобы почувствовать поток управления.
Рекомендуем продолжить чтение на продолжениях:
call/cc тривиально реализовать. Жесткая часть - это настройка среды, где это возможно.
Мы должны сначала определить среду выполнения стиля передачи (CPS). В этой среде ваши функции (или функции-подобные вещи) прямо не возвращают значения; вместо этого им передается функция, которая представляет "следующий шаг" в вычислении - "продолжение" - и они передают их результат там. В Haskell это выглядит так:
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
Как вы можете видеть, действие monad Cont действительно является функцией, которая принимает продолжение (a -> r), передает результат a в продолжение и возвращает окончательный результат r, который он просто проходит через его вызывающий объект (т.е. a Cont действие монады должно взывать хвост в продолжение). runCont просто выводит его из оболочки newtype - вы также можете думать об этом как о вызове действия с каким-то конкретным продолжением, как в runCont someAction someContinuation.
Затем мы можем превратить это в монаду:
instance Monad (Cont r) where
return x = Cont $ \cc -> cc x
(Cont f) (>>=) g = Cont $ \cc -> f (\r -> runCont (g r) cc)
Как вы можете видеть, return просто получает продолжение cc и передает его значение в продолжение. (>>=) немного сложнее, он должен вызывать f с продолжением, которое затем вызывает g, возвращает действие и затем передает внешнее продолжение этому новому действию.
Таким образом, учитывая эту структуру, переход к продолжению прост. Мы просто хотим дважды вызвать функцию с ее продолжением. Трудная часть заключается в том, что мы должны переписать это продолжение в новом монадическом действии, которое вытесняет существующее продолжение. Поэтому пусть немного сломается:
-- Invoke a raw continuation with a given argument, throwing away our normal
-- continuation
gotoContinuation :: (a -> r) -> a -> Cont r x
gotoContinuation continuation argument = Cont $ \_ -> continuation argument
-- Duplicate the current continuation; wrap one up in an easy-to-use action, and
-- the other stays the normal continuation for f
callCC f = Cont $ \cc -> runCont (f (gotoContinuation cc)) cc
Простой, нет?
В других языках, таких как Scheme, принцип тот же, хотя он может быть реализован как примитив компилятора; причина, по которой мы можем это сделать в Haskell, состоит в том, что продолжение продолжения было чем-то, что мы определили в Haskell, а не на более низком уровне времени выполнения. Но принцип тот же - вам нужно сначала CPS, а затем call/cc является тривиальным приложением этой модели выполнения.
Вы слышали сторону Хаскелла уравнения; Я дам вам Racket/Scheme, и какой бы ни был вам полезен, вы можете работать с ним.
Мой ответ будет намного короче, потому что я думаю, что лучший источник, который я могу дать вам для реализации call/cc в простом оценщике ракетки, принадлежит Shriram Krishnamurthi PLAI, в частности раздел 20. Я думал о включении соответствующей части интерпретатора - на странице 205, но после попытки переформатировать его несколько раз я решил, что это будет иметь больше смысла в его надлежащее место на странице.
Опять же, я не пытаюсь объяснить идею вызова /cc здесь, просто укажу вам на рабочую реализацию. Дайте мне знать, если у вас есть другие вопросы.
Рискуя быть внеязыком, я думаю, что в Smalltalk продолжения могут быть реализованы и понятны проще всего. Причина в том, что в Smalltalk исполняемый стек формируется из обычных объектов, к которым можно получить доступ и манипулировать, как и любой другой объект.
Для реализации простого объекта продолжения необходимы следующие два метода. В первом методе мы инициализируем продолжение путем итерации по родительским (отправителям) кадрам (контекстам) и копированию их состояния (счетчик программ, временные параметры, аргументы):
Continuation>>initializeFromContext: aContext
context := aContext.
stream := WriteStream on: (Array new: 200).
[ context notNil ] whileTrue: [
stream nextPut: context.
1 to: context class instSize do: [ :index |
stream nextPut: (context instVarAt: index) ].
1 to: context size do: [ :index |
stream nextPut: (context at: index) ].
context := context sender ].
values := stream contents
Второй способ - возобновить выполнение: сначала мы разматываем текущий стек (опять же это просто простой цикл над стеком выполнения), затем мы восстанавливаем захваченные кадры стека, привязываем их к текущему фрейму стека thisContext и возобновите выполнение с аргументом anObject:
Continuation>>value: anObject
self terminate: thisContext.
stream := values readStream.
[ stream atEnd ] whileFalse: [
context := stream next.
1 to: context class instSize do: [ :index |
context instVarAt: index put: stream next ].
1 to: context size do: [ :index |
context at: index put: stream next ] ]
thisContext swapSender: values first.
^ anObject
С помощью этих двух методов мы можем легко построить callCC:
Continuation class>>callCC: aBlock
^ aBlock value: (self new initializeFromContext: thisContext sender)
Красота такого подхода заключается в том, что напечатанный код показывает все, что необходимо для реализации полных продолжений (и аналогично других видов продолжений). В системе (VM) нет скрытого поведения. Можно использовать отладчик для перехода через каждую часть и наблюдать за тем, как управляется стек выполнения.
Вышеприведенный код приведен из Seaside веб-рамки. Чтобы играть с кодом, вы можете использовать готовый дистрибутив и перейти к классам WAContinuation и WAContinuationTest.
Хорошо, я дам гораздо более короткий, основанный на Схеме ответ, так как это тоже помечено как "схема".
Чтобы понять, почему ваша попытка реализовать call/cc должна завершиться неудачно, вы должны понять, что стиль продолжения прохождения. Как только вы это понимаете, это довольно просто:
call/cc не может быть реализована в прямом стиле.Однако, чтобы дать немного больше информации, стиль продолжения передачи - это дисциплина управления потоком, в которой вы отказываетесь от использования стека вызовов в пользу соглашения о вызове, где каждый вызов процедуры передает "дополнительный" аргумент: закрытие, которое вызвало процедура должна вызываться, когда она "сделана" (передавая "возвращаемое значение" в качестве аргумента). Эти дополнительные замыкания аргументов называются продолжениями.
Любая программа может быть механически переведена в стиль продолжения, с помощью чего-то названного, достаточно подходящего, преобразования CPS. Многие системы Scheme фактически работают так: программа анализируется, к ней применяется преобразование CPS, а затем синтаксическое дерево CPS абстрактно интерпретируется или переводится в объектный код.
Вот как вы бы реализовали call/cc в стиле продолжения передачи (используя continuation в качестве имени дополнительного аргумента для продолжения):
(define (call/cc-cps proc continuation)
(proc continuation continuation))
Как вы должны видеть, (a) вы не можете реализовать это в прямом стиле (напротив CPS) и (b) он тривиально в CPS. call/cc - это просто процедура, которая принимает другую процедуру как свой аргумент и (обязательное) продолжение, и вызывает эту процедуру с продолжением как в качестве аргумента, так и в ее продолжении.