Машина времени на CPS

[предыдущая серия]

 

Как переводить в CPS-трансформации рекурсивные функции? Да точно так же. Например, у нас есть классический факториал, который мы хотим использовать в условной call-site функции Write:

 

 

int fact(int n) {
  if (n == 0) return 1;
  return n * fact(n - 1);
}

 

Write( fact(5) );

 

В CPS-стиле факториал и его вызов запишется так:

 

void Fact(int n, Action<int> k) {
  if (n == 0) k(1);
  else Fact(n - 1, x => k(n*x));
}

Fact(5, x => Write(x));

 

Исходно CPS-фишка в Scheme называлась call-with-current-continuation, и сегодня массово известна как call/cc.

Интересно, что продолжения, в частности — это монады. Более того, в computer science их можно считать вообще родителями всех монад.

 

Что же мы получаем от CPS-трансформации? Мы полностью исключаем все return. Каждый метод «возвращает» void. Каждый делегат — это Action. Мы полностью отказываемся от стека, потому что мы никогда не возвращаемся «обратно». С помощью CPS даже в C# компактно, буквально одной строчкой, и гораздо более элегантно программируется логика try-catch — в виде метода! Тут же и асинхронная логика, и пресловутый yield, который в C# реализован очень криво, и т. д.

Проблема же с CPS в том, что этот стиль очень непривычен для понимания, особенно программистам, которые привыкли мыслить в логике подпрограмм, циклов, прерываний. Но зато CPS позволяет очень чётко выражать смысл потока управления в программе, скрывая механизмы его реализации (стеки вызовов, адреса возврата, обработчики исключений и т. д.). Именно продолжения фактически проясняют элементарные механизмы управления потоком непосредственно в структуре программы. А всё, что делает акцент на механизмах реализации, только перегружает смысл кода. Ну и кроме того, многие асинхронные пакеты сегодня поддерживают именно CPS-запись.

 

Дело в том, что любой императивный поток управления всегда избыточен. CPS же совершенно прозрачен потому, что все эти потоки по сути лишь причудливые обёртки вокруг условного goto. Условный оператор — это goto, цикл — это goto, return, подпрограммы, прерывания — это всё goto. И поэтому с помощью CPS становится возможным реализовывать весьма тонкие и экзотические структуры управления: например, условия, которые оценивают обе ветки бранча параллельно; короутины; yield return; возобновляемые прерывания (conditions из Лиспа)…

 

Более того, нам ничто не мешает теперь создать машину времени. Мы можем писать программы, которые работают то вперёд, то, если мы захотим, назад!

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

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

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