Continuation passing style

Доброе утро дорогие читатели, позвольте мне сказать, что эта статья будет длинной и сложной, но это все окупится. Я также собираюсь писать статьи в ускоренном темпе, чаще двух раз в неделю.

Я хочу поговорить немного о теме, которую кратко рассмотрел несколько лет назад, а именно о Continuation Passing Style (далее CPS), которую многие люди находят одновременно запутывающей и восхитительной.

Перед тем как продолжить читать дальше эту статью, вы возможно захотите освежить свою память моим кратким введением в CPS в JScript.

http://blogs.msdn.com/b/ericlippert/archive/tags/continuation+passing+style/

Добро пожаловать обратно. Я надеюсь, что это имело смысл. Синтаксис JScript для вложенных анонимных функций довольно прямолинейный и похож на анонимные методы C#., итак, надеюсь, эта статья была понятной даже если вы плохо знаете JScript. В случае, если вы не читали эту статью, позвольте подытожить:

Традиционный стиль программирования с подпрограммами предоставляет программную модель, которая ведет себя так:

  • делаете заметку о том, что вы выполняли и какие значения имеют ваши локальные переменные во временном хранилище, так называемом «стеке»

  • передаете контроль подпрограмме, пока она не вернет управление

  • обращаясь к своим заметкам, продолжаете оттуда, где остановились, теперь зная результат работы подпрограммы, если таковая была.

CPS — это стиль программирования, в котором нет «подпрограмм» по сути и нет «возвращений из подпрограмм». Вместо этого, последняя вещь, которую текущая функция выполняет — вызов следующей функции, передавая результат работы текущей функции. Так как нет функций, которые «возвращают данные из подпрограмм» или делают какую-либо работу после вызова следующей функции, то нет необходимости отслеживать где вы были. Не имеет значения где вы были, потому что вы никогда не вернетесь туда. Чтобы удостовериться, что вещи идут в желаемом порядке, когда вызываете новую функцию, вы обычно передаете «продолжение (continuation)», которое самом по себе функция, выполняющая «все, что идет дальше».

Я показывал вариант, с помощью которого можно добиться этого в JScript. Вы можете сделать так, чтобы каждая функция принимала на вход продолжение. Новые продолжения могли бы быть созданы по мере необходимости из вложенных анонимных функций. В любое время, когда бы вы ни вызывали подпрограмму, вместо этого создаете продолжение, которое представляет еще не сделанную работу и логически передаете это в подпрограмму так, чтобы она сделала это за вас. Чтобы сделать это без использования стека в JScript, вы можете передать это продолжение в некий «оркестровый» код, который будет отслеживать что должно произойти. «Оркестратор» просто находится в цикле, передавая текущее продолжение последним вычисленным результатом. В языках, которые не поддерживают CPS, это максимум, что вы можете сделать без использования стека.

CPS интересен и полезен, потому что у него есть куча замечательных свойств, множество из которых я не объяснил в моей первой серии статей. Я представил CPS исключительно как путь для решения проблем глубокой рекурсии; так как нет подпрограмм, которые что-либо возвращают, то нет необходимости использовать стек вызовов. Но CPS это нечто большее. В частности, одна из вещей, которые он позволяет нам делать — это создавать новые примитивы потока управления в языке, реализуя поток управления как методы. Это может звучать безумно, но взгляните на несколько простых примеров как мы можем создать поток управления из продолжений.

Рассмотрим на примере условного оператора ?:. Он принимает решение о том, что случится дальше и таким образом он является потоком управления. Предположим, у нас есть методы string M(int x), bool B(), int C() и int D(). У нас может быть в программе такой фрагмент:

M(B() ? C() : D())

Теперь предположим, что C# не имеет оператора ?: и вы хотели бы его реализовать как библиотечный метод. Вы не можете просто сделать так:

T Conditional<T>(bool b, T consequence, T alternative)

{

if (b) return consequence; else return alternative;

}

потому что теперь consequence и 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>. Аргументом C и D должен быть Action<int>. Что насчет Conditional? Она все еще должна вычислять свои аргументы «лениво», но вызов этих лямбд в любом случае не может вернуть значения. Наоборот, они тоже должны брать на вход продолжения:

B(b=> Conditional(b, c=> C(c), c=> D(c), t=> M(t, currentContinuation)))

Continuation теперь выглядит так:

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 решает в какой из первых двух делегатов передать третий делегат — продолжение. Предположим, она выбирает alternative. Alternative, D, запускается и передает свой результат в продолжение, которое t=> M(currentContinuation, t). M затем делает что-то с целочисленным t и вызывает текущее продолжение, которое было оригинальным вызовом, и на этом все.

Больше нет возвращений значений. Каждый метод возвращает void. Каждый делегат Action. Последнее, что делает каждый метод, он вызывает другой метод. Стек вызовов нам больше не нужен, потому что нам больше не надо возвращаться назад. Если бы мы могли написать компилятор C#, который оптимизировал код под такой стиль программирования, тогда ни один из этих методов не использовал стек вызовов, кроме их немедленных требований на хранение локальных и временных нужд.

И в какой беспорядок мы превратили простую операцию. Но вы видите что мы сделали там? Я определил CPS версию оператора ?: как библиотечный метод; тот факт, что consequence и alternative выполняются «лениво», получился благодаря преобразованию их в лямбды. Управление потоком теперь достигается передачей правильных продолжений в правильные методы.

И что из этого? Здесь мы не сделали ничего такого, чего не могли бы добиться гораздо легче без продолжений. Вот интересная часть: продолжения — это овеществленное управления потоком. До сих пор мы говорили только о системах, где одиночное продолжение передавалось туда-сюда. Так как продолжения в сущности делегаты, нет причин по которым мы вы не могли бы передавать много продолжений или сохранять их для дальнейшего использования. Делая так, мы можем строить произвольно сложные управления потоками в виде библиотечных методов, отслеживая множественные продолжения и решая какие из них будут продолжать выполняться.