Возвращаясь к стилю передачи продолжения. Часть 1
Здравствуйте, читатели невероятных приключений. Позвольте мне начать тему, которая будет действительно долгой и действительно сложной, но полностью окупится в конце. Также я собираюсь публиковать сообщения в ускоренном режиме, более двух в неделю. Позже станет ясно, почему я так поступаю, добавлю для интриги. Помните, неопределенность является показателем качества блога.
Я хотел бы немного поговорить о предмете, который впервые был затронут мною несколько лет тому назад, а именно, о стиле передачи продолжения (Continuation Passing Style – здесь и далее CPS), тема, которую многие (включая меня) считают одновременно очаровательной и сбивающей с толку.
Прежде чем переходить к чтению этой серии сообщений вы возможно захотите вспомнить мое краткое введение в CPS на JScript.
https://blogs.msdn.com/b/ericlippert/archive/tags/continuation+passing+style/
Вернемся к теме. Я надеюсь это понятно. Синтаксис JScript вложенных анонимных функций является довольно простым и похож на синтаксис анонимных методов С#, так что будем надеяться, что все будет понятно, даже если вы не можете свободно читать JScript. Если же вы не сумеете проделать весь путь, позвольте мне подытожить:
Традиционный стиль программирования с подпрограммами опирается на модель программирования, которая выглядит следующим образом:
- запишите во временную память («стек») то, что вы делаете, и какие значения имеют локальные переменные
- передайте управление подпрограмме и дождитесь возврата управления из нее
- сверьтесь со своими записями, возобновите выполнение с момента остановки, зная результаты выполнения подпрограммы, если таковые были.
В стиле программирования CPS понятия «подпрограмма» и «возвращение», по сути, отсутствуют. Вместо этого последним действием текущей функции является вызов следующей функции с передачей ей результатов выполнения текущей. Поскольку никакая функция не «возвращает» и не продолжает работу после вызова следующей функции, нет необходимости сохранять информацию о том, где вы были. Неважно, где вы были, потому что вы никогда уже не вернетесь туда снова. Чтобы обеспечить необходимый порядок выполнения, при вызове новой функции вы обычно передаете «продолжение» (continuation), которое само по себе является функцией, выполняющей «все, что будет дальше»
Я показал, как это исследовать в JScript. Каждая функция должна иметь продолжение. Новые продолжения могут при необходимости создаваться из вложенных анонимных функций. Всякий раз вместо вызова процедуры вы строите продолжение, представляющее работу, которую предстоит выполнить, и логически передаете его подпрограмме, так что она сможет выполнить работу за вас. Для того чтобы делать это без использования стека в JScript, можно передавать продолжения коду «оркестровки», который отслеживает то, что должно произойти дальше. Дирижер просто находится в цикле, распределяя текущее продолжение с полученными последними результатами. В языках без естественной поддержки CPS это самое лучшее, чего можно достичь, если вы хотите получить полное CPS-программирование без использования стека.
CPS интересен и полезен тем, что имеет множество любопытных свойств, о многих из которых я не упомянул в своей первой серии статей. Тогда я представил CPS только как способ решения задач глубокой рекурсии; т.к. нет вызовов подпрограмм, возвращающих что-либо, то нет необходимости в вызовах стека. Но CPS не ограничивается только этим. В частности, одной из вещей, которую позволяет делать CPS, является построение новых примитивов управляющей логики в языке путем ее реализации в виде методов. Это может звучать бредово, но давайте рассмотрим очень простой пример, как построить логику управления из продолжений.
Рассмотрим условный оператор « ? : ». Он принимает решение о том, что произойдет дальше и поэтому является формой управляющей логики. Предположим, что у нас имеются методы string M(int x), bool B(), int C() и int D(). И где-то в программе мы можем встретить такой фрагмент:
M( B() ? C() : D())
Теперь предположим, что в С# нет оператора ? : и вы хотели бы реализовать его как вызов библиотечного метода. Вы не можете написать просто:
T Conditional<T>(bool b, T consequence, T alternative)
{
if (b) return consequence; else return alternative;
}
потому что вычисления и прямой и альтернативной ветви проходят заранее, а не отложенно. Но можно сделать так:
T Conditional<T>(bool b, Func<T> consequence, Func<T> alternative)
{
if (b) return consequence(); else return alternative();
}
и вызвать
M(Conditional(B(), ()=>C(), ()=>D()))
Теперь у нас есть реализация нашего условного оператора в виде библиотечного метода.
Предположим, что мы хотим реализовать этот условный оператор в стиле CPS, потому что… Потому что мы не ищем легких путей, я полагаю. В CPS у нас есть продолжение; что-то должно произойти после вызова M. Давайте назовем это «текущим продолжением», чем бы оно ни являлось. Не важно, откуда оно появилось, предположим, что оно у нас есть.
Нам нужно переписать метод B так чтобы он принимал продолжение, которое принимает булево выражение. «Продолжение, принимающее булево выражение» звучит ужасно, так же как Action<bool>, поэтому предположим, что мы можем переписать bool B() в форме void B(Action<bool>).
Что такое продолжение B, «что произойдет потом»? Рассмотрим процесс поэтапно.
B(b=>M(Conditional(b, ()=>C(), ()=>D)))
У нас есть B в стиле CPS, но лямбда-выражение, передаваемое в B, не соответствует CPS по двум причинам: вызов Conditional и вызов M. Чтобы соответствовать CPS, оно должно вызывать что-то, как свое последнее действие. Повторим анализ, выполненный для B. M необходимо принять int и Action<string>. С и D необходимо принять Action<int>. А что с условием? Оно по-прежнему должно отложенно вычислять свои аргументы, но вызов лямбда-выражений не может возвращать значения в обоих случаях; вместо этого они должны также принимать продолжения:
B(b=>Conditional(b, c=>C(c), c=>D(c), t=>M(t, currentContinuation)))
Conditional теперь выглядит следующим образом:
void Conditional<T> (bool condition, Action<Action<T>> consequence, Action<Action<T>> alternative, Action<T> continuation)
{
if (condition) consequence(continuation) ; else alternative(continuation);
}
Суммируем: B выполняется и передает булев результат лямбда-выражению. Лямбда-выражение передает b и три других лямбда-выражения Conditional. Conditional определяет, который из первых двух делегатов будет передан третьему делегату – продолжению. Предположим, что это альтернативный. Альтернатива D выполняется и передает результаты продолжению – t=>M(currentContinuation, t). Затем M выполняется с целым t и вызывает текущее продолжение, каким бы оно ни было, и мы закончили.
Больше нет возвращаемых значений. Каждый метод имеет тип void. Каждый делегат имеет тип Action. Последним действием каждого метода является вызов другого метода. Мы не нуждаемся в обращениях к стеку вызовов, потому что нам не нужно возвращаться назад.
Если мы могли бы написать компилятор C#, оптимизирующий код для этого стиля программирования, то ни один из этих методов не будет потреблять стек вызовов за границами их непосредственных потребностей в хранении локальных и временных переменных.
И, боже мой, в какой беспорядок мы превратили эту простую операцию. Но вы видите, что именно мы сделали? Я определил CPS-версию оператора ?: как библиотечный метод; тот факт, что основной и альтернативный варианты оцениваются отложенно, достигается путем переписывания их в виде лямбда-выражений. Затем поток управления завершается передачей правильного продолжения правильному методу.
Ну и что? Мы не сделали здесь ничего, что нельзя было бы гораздо легче сделать без продолжения. Но интересный момент: продолжения являются реификацией (reification) логики выполнения. До сих пор мы рассматривали лишь системы, передающие только одно продолжение. Так как продолжения эффективно реализуются с помощью делегатов, то нет причин, почему бы не передавать множество продолжений, или не накапливать их для последующего использования. Следуя по этому пути, мы сможем создавать логику управления произвольной сложности в виде библиотечных методов путем сохранения множества продолжений и определения, которое из них будет выполнено следующим.
В следующий раз: некоторые размышления о более сложной логике управления.