Возвращаясь к стилю передачи продолжений. Часть 2: пассы с логикой управления
В прошлой серии «Невероятных приключений»: «Следуя по этому пути, мы сможем создавать логику управления произвольной сложности в виде библиотечных методов путем сохранения множества продолжений и определения, которое из них будет выполнено следующим» .
Давайте рассмотрим более сложный пример, нежели условный оператор. Давайте рассмотрим упрощенную версию блоков “try-catch”, в котором отсутствует выражение в операторе генерации исключения (throw). throw – это всего лишь нелокальный оператор goto, который передает управление ближайшему внешнему блоку catch. Вот традиционный взгляд на это:
void Q()
{
try
{
B(A());
}
catch
{
C();
}
D();
}
int A()
{
throw;
return 0; // этот код недоступен, но давайте не будет на это обращать внимание
}
void B(int x) { что-нибудь }
void C() { что-нибудь }
void D() { что-нибудь }
Алгоритм работы следующий. Запоминаем местоположение блока catch. Запоминаем наше состояние. Вызываем метод A(). Если он завершается успешно, запоминаем наше состояние и вызываем метод B(), передавая результат выполнения метода A(). Если метод B() завершается успешно, вызываем метод D(). Если метод A() или B() не завершаются успешно, тогда мы ищем сохраненный ранее блок catch. Вызываем метод C() и затем метод D().
В CLR реальный код, реализующий обработку исключений, безумно сложен; он должен взаимодействовать со стеком вызовов, выискивая фильтры, обработчики и т. д. Давайте предположим, что в языке отсутствует поддержка try-catch. Всю эту безумно сложную логику невозможно реализовать в виде библиотечного метода, даже если мы захотим это. Или возможно? Можем ли мы написать методы Try() и Throw() в языке с поддержкой CPS?
Мы можем начать с передачи двух продолжений в каждую функцию, которая может сгенерировать исключение: одно «нормальное» продолжение (“normal” continuation) и одно продолжение в случае возникновения «ошибки» (“error” continuation). Предположим, метод Q может сгенерировать исключение. Мы преобразуем весь код в CPS с «двумя продолжениями». Итак, мы получим:
void A(Action<int> normal, Action error)
{
Throw(()=>normal(0), error);
}
Выглядит разумно. Что делает метод A()? Он вызывает метод Throw и затем возвращает 0, путем передачи нуля в нормальное продолжение метода A. (Как мы вскоре увидим, это не важно, поскольку метод Throw по определению не завершается нормально. Но это всего лишь еще один вызов метода, так что давайте продолжим рассматривать его именно так.)
void B(int x, Action normal, Action error) { что-нибудь }
void C(Action normal, Action error) { что-нибудь }
void D(Action normal, Action error) { что-нибудь }
Как реализовать метод Throw? Это просто! Метод Throw вызывает продолжение, которое вызывается в случае ошибки и не выполняет нормальное продолжение.
void Throw(Action normal, Action error)
{
error();
}
Какая реализация метода Try? А вот это посложнее. Что делает блок try-catch? Он устанавливает новое продолжение, которое вызывается в случае ошибки, для блока try, но не для блока catch. Как нам этого добиться? Позвольте мне опустить детали, мы просто убедимся, что это работает:
void Try(Action<Action, Action> tryBody,
Action<Action, Action> catchBody,
Action outerNormal,
Action outerError)
{
tryBody(outerNormal, ()=>catchBody(outerNormal, outerError));
}
void Q(Action qNormal, Action qError)
{
Try (
/* tryBody */ (bodyNormal, bodyError)=>A(
/* normal for A */ x=>B(x, bodyNormal, bodyError),
/* error for A */ bodyError),
/* catchBody */ C,
/* outerNormal */ ()=>D(qNormal, qError),
/* outerError */ qError );
}
Хорошо, но прежде всего, является ли это CPS? Да. Каждый метод возвращает void, каждый делегат возвращает void, и последнее, что делает каждый метод или лямбда-выражение – это вызов другого метода.
Корректен ли код? Давайте его проанализируем. Мы вызываем метод Try и передаем тело try, тело catch, нормальное продолжение и продолжение для ошибки.
Метод Try вызывает тело try, которое принимает два продолжения. Try передает outerNormal вида ()=>D(qNormal, qError), как нормальное продолжение. И передает ()=>catchBody(outerNormal, outerError) в качестве продолжения в случае возникновения ошибки. Мы знаем, что это означает, и давайте рассмотрим, во что оно разворачивается. Метод C был телом блока catch. Таким образом, продолжение в случае ошибки будет следующим: ()=>C(()=>D(qNormal, qError), qError). (Надеюсь вам понятно).
А что представляло собой тело блока try? Оно было таким: (bodyNormal, bodyError)=>A(x=>B(x, bodyNormal, bodyError), bodyError). Теперь мы знаем, что представляло собой bodyNormal и bodyError, давайте рассмотрим, во что они разворачиваются. После того, как мы развернем их, мы получим следующее:
A(
x=>B( // нормальное продолжение метода A
x, // аргумент метода B
()=>D( // нормальное продлолжение метода B
qNormal, // нормальное продолжение метода D
qError), // продолжение в случае ошибки метода D
()=>C( // продолжение в случае ошибки метода B
()=>D( // нормальное продолжение метоад C
qNormal, // нормальное продолжение метода D
qError), // продолжение в случае ошибки метода D
qError)), // продолжение в случае ошибки метода C
()=>C( // продолжение в случае ошибки метода A
()=>D( // нормальное продолжение метода C
qNormal, // нормальное продолжение метода D
qError), // продолжение в случае ошибки метода D
qError)) // продолжение в случае ошибки метода C
Т.е. вначале будет вызван метод A. Что приведет к немедленному вызову Throw, передавая достаточно сложный кусок кода в качестве нормального продолжения и ()=>C(()=>D(qNormal, qError), qError), для продолжения в случае ошибки.
Метод Throw игнорирует нормальное продолжение и вызывает ()=>C(()=>D(qNormal, qError), qError).
А что будет, если в методе C (или в коде, который вызывается из него) будет сгенерировано исключение? Если в методе C произойдет исключение, управление сразу же перейдет к qError – какой бы обработчик ошибок ни был включен во время вызова Q.. А что если вызов метода C завершится нормально? Нормальным продолжением является ()=>D(qNormal, qError), так что в случае успешного завершения метода C, будет вызван метод D.
Что если в методе D произойдет исключение? Тогда будет вызван qError. В противном случае, в конечном итоге (мы на это надеемся!) будет вызван qNormal.
Давайте сделаем шаг назад. Что если мы уберем вызов метода Throw и, в таком случае метод A не будет генерировать исключение? Что если он передаст 0 в нормальное продолжение? Нормальным продолжением методом A является вызов метода B, таким образом, 0 будет передан методу B. И, как вы можете видеть, если в B произойдет исключение, тогда управление перейдет методу C, а в противном случае – методу D.
Ага. Мы только что реализовали try-catch и throw в виде методов. Более того, мы реализовали их в виде однострочных методов. Очевидно, try-catch-throw не такая уж и сложная штука!
Теперь вы понимаете, что я имел в виду, когда писал, что CPS является реификацией логики управления? Продолжение – это объект, представляющий, что произойдет потом, и ведь логика управления именно этим и является. Любая логика управления может быть представлена в виде CPS.
Любая логика управления – это весьма широкое понятие. Это работает благодаря тому, что любая логика управления представляет собой всего лишь умную оболочку над условным оператором “goto”. Условное выражение – это goto, циклы – это goto, вызовы подпрограмм – это goto, возвращаемые значения – это goto, исключения – это goto, это все goto. При наличии продолжений нам совершенно не важны особенности конкретного типа goto. С помощью CPS вы можете реализовать даже весьма экзотическое управление потоком выполнения. Возобновляемые исключения (resumable exceptions), параллельное выполнение обоих ветвей, yield return, сопрограммы. Черт возьми! Вы можете написать программы, которые вначале будут выполняться в одном направлении, а потом в обратном, если вам это действительно нужно. Если нечто является разновидностью догики управления, тогда вы сможете сделать это с помощью CPS.
В следующий раз: размышления о сопрограммах.