Уничтожаем императивность CPS-трансформацией

[первая часть]

 

Сразу отмечу, что в последних версиях C# существует поддержка CPS! Но мы начнём с классических генериков.

 

Вот у нас есть обычная функция, просто возвращающая само значение:

T Foo<T>(T val) { return val; }

 

Например, если есть функция

 

int Inc(int x) { return x+1; }

 

то вызов

 

Inc(Foo(4))

 

вернёт 5, при этом «вызывающая сторона» Inc() обратится к Foo, передаст ей управление, сохранив в стеке состояние, получит результат 4 и далее продолжит работу с прерванного места, после чего завершится сама.

 

Однако мы можем организовать CPS-схему эксплицитно:

 

void Foo<T>(T val, Action<T> k) { k(val); }

 

Параметр k — это делегат встроенного типа Action, метод, который принимает один параметр и не возвращает значения.

 

Мы просто передаём результат вычислений следующей функции-продолжению k(), получаемой через последний параметр. И теперь мы можем записать саму цепочку более красиво, с помощью анонимной лямбда-функции:

 

Foo(4, x => Inc(x));

 

Однако что толку, ведь теперь Foo имеет тип void — а как же нам поймать результат 5 ??

 

Это типичная «непонятка» императивного программиста. Допустим, предыдущий пример в работоспособном виде выглядел так:

 

int n = Inc(Foo(4)); // n == 5

 

Программист пишет эту строчку, сохраняя временное состояние, потом чешет в затылке, думая, куда бы приткнуть переменную n, и решает например показать её на форме в элементе speedValue:

 

speedValue.Text = "SPD:" + n.ToString();

 

Вот это и есть ключевой момент в наших рассуждениях!

 

Рано или поздно, но любая цепочка вычислений в действующей программе завершается в некоторой функции, которая уже ничего не вычисляет (её условно называют вызывающей стороной, call-site).

 

И когда вся программа (или некоторый её смысловой кусочек, наподобие обработчика события) завершается, в конце никакого значения никуда уже не передаётся. Это принципиальный момент, который сразу позволяет разделить прикладную логику цепочек вычислений и чистые (преимущественно) функции, которые мы начинаем комбинировать.

 

В нашем случае определим «финальную» функцию showSpeed, которая ничего не возвращает, а просто записывает в элемент на экране отформатированное значение:

 

void showSpeed(int n) {
  speedValue.Text = "SPD:" + n.ToString();
}

 

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

 

void Inc(int x, Action<int> k) { k(x+1); }

 

Тогда наша CPS-цепочка запишется так:

 

Foo(4, x => Inc(x, y => showSpeed(y)));

 

Весьма наглядный вид, который читается слева направо: сперва берём значение 4, затем обрабатываем его функцией Foo, затем — функцией Inc, и затем передаём завершающей функции showSpeed.

А вот как выглядела бы классическая форма:

 

showSpeed(Inc(Foo(4)));

 

В CPS-записи есть ряд принципиальных моментов, которые мы рассмотрим далее.

Поделиться статьей ...Share on Facebook0Share on Google+0Tweet about this on TwitterShare on LinkedIn0Share on VKPrint this page

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *