- Этот пост сопровождает это видео и не будет иметь большого смысла без него
В прошлом месяце я выступил с докладом на конференции Curry On , новой конференции совместно с академической конференцией по языку программирования ECOOP. Curry On предназначен для преодоления разрыва между академическими кругами. Мои академические интересы не включают языки программирования, которые я рассматриваю как субдисциплину информатики, которая постоянно завышала и недоставала больше, чем любая другая (за исключением, возможно, ИИ). Меня больше интересуют алгоритмы, чем абстракции, и исследование языка программирования в основном касается последних. Тем не менее, как разработчик, я должен использовать абстракции, предоставляемые языками программирования, которые я выбрал для использования, и с некоторой тревогой я заметил поток определенных абстракций из академических языков в основной поток, который в некоторых случаях делает плохо подходят и в основном вызывают боль. В качестве примера, я бы хотел, чтобы вы подумали о том, что сейчас гораздо больше людей используют монады в Java, чем в Haskell.
В своем выступлении я подчеркнул, что основной абстракцией императивного программирования является блокирующий поток. Как только вы уберете его, вы потеряете большинство других императивных абстракций, таких как поток управления и обработка исключений (что требует их повторной реализации в библиотеках), и большинство преимуществ императивных языков, таких как посмертная отладка, профилирование и автоматическое обратное давление. Это также затрудняет написание и чтение кода. Я утверждаю, что асинхронное программирование — анафема для императивных языков, независимо от того, используете ли вы монады, чтобы облегчить их боль. Несоответствие между асинхронностью и императивом является фундаментальным. В то же время мы можем достичь абстракции, такой же мощной, как монады — если не больше — которая естественным образом подходит для императивных языков, прекрасно сочетаясь с их структурой и способностями.
Если вы еще этого не сделали, сейчас самое время посмотреть выступление:
В своем выступлении я утверждал, что так же, как монады являются супер-абстракцией чисто функционального программирования, продолжения являются супер-абстракцией императивного программирования, так и представил абстракцию, которую я назвал «продолженными областями», которая представляет собой нечто большее, чем продолжение с разделителями. специальный соус (я понятия не имею, обсуждалась ли эта концепция где-то в другом месте; если бы она была таковой, я бы хотела знать ее собственное имя [см. дополнение в конце статьи)).
Поскольку я подумала об этой идее незадолго до выступления, я была не готова к представлению продолжений с определенной областью, и, поскольку с тех пор я еще более подробно рассмотрела эту тему, я бы хотела продолжить обсуждение этой идеи. Я сделал три претензии:
- Продолжения с заданной областью естественно соответствуют императивному коду
- Продолжения с заданной областью так же сильны, как монады
- Продолжения в области видимости сочиняются лучше, чем монады
Я думаю, что я остановился на пункте № 1, поскольку продолженные области позволяют вам поддерживать поток императивного управления, а они сохраняют стековый контекст, который необходим для посмертной отладки и профилирования. Я был гораздо более расплывчатым, когда дело дошло до # 2, интуитивно отмечая связь между монадами и продолжениями и приводя некоторые примеры, но не приводя доказательств, и один из слушателей справедливо вызвал меня для этого.
Первый раунд: Цепочка — Продолжение с разделителями против монад
После беседы я поговорил с Джулианом Арни, который показал мне пост в блоге «Мать всех монад» Дэна Пипони . Соответствующее обсуждение в Reddit ) привело меня к этому доказательству Анджея Филинского 1 от 1994 года, согласно которому продолжения с разделителями (называемые частичными или составными продолжениями в статье Филинского) могут представлять любую монадическую композицию. Он говорит:
Мы показываем, что любая монада, чьи операции единицы и расширения могут быть выражены как чисто функциональные термины, может быть встроена в язык вызова по значению с «составными продолжениями»…
… Несколько примечательно, что монады не оказали сопоставимого влияния на «нечистое» функциональное программирование. Возможно, главная причина в том, что … монадическая структура уже встроена в семантическое ядро активных функциональных языков с эффектами и не нуждается в явном выражении. «Нечистые» конструкции, как лингвистические (например, обновляемое состояние, исключения или первоклассные продолжения), так и внешние по отношению к языку (ввод-вывод, интерфейс ОС и т. Д.), Подчиняются монадической дисциплине. Единственный аспект, который может показаться отсутствующим, — это способность программистов использовать свои собственные монадические абстракции, специфичные для приложения, такие как недетерминизм или синтаксические анализаторы, с той же легкостью и естественностью, что и встроенные эффекты.
… Далее мы покажем, что… язык… с продолжениями первого класса уже «монадически завершен» в том смысле, что любая программа, выражаемая в несколько искаженном монадическом стиле, также может быть написана в прямом стиле.
У меня нет необходимого фона, чтобы следовать работе Филински, но, если я не ошибаюсь, трудность доказательства связана с тем фактом, что преобразование из монадической формы в продолжения (то, что он называет «прямым стилем») не простое математическое отображение монадических функций или монадического композитора (что Хаскель называет связыванием ), но требует более глубокого преобразования их представления исходного кода. Я, однако, представлю конкретную реализацию разделенных продолжений таким образом, чтобы, надеюсь, объяснить интуицию, лежащую в основе сходства с moand-продолжением.
Продолжение с разделителями захватывает часть стека вызовов. Это позволяет нам приостановить вычисление, а затем возобновить его. Давайте посмотрим на API продолжения с разделителями в Java:
|
1
2
3
4
5
6
7
8
|
public class Continuation<T> implements Runnable, Serializable, Cloneable { public Continuation(Callable<T> target) { ... } public T run() { ... } public boolean isDone() { ... } public T getResult() { ... } public static Continuation<?> suspend(Consumer<Continuation<?>> ccc) { ... }} |
Метод suspend (который работает как shift Схемы) приостанавливает текущее продолжение (при условии, что мы работаем внутри него) и вызывает (необязательно) предоставляемый обратный вызов ccc (имя ccc является аббревиатурой для Called with Current Continuation , который является игрой на call-cc схемы call-cc ). Функция run (которая соответствует reset схемы) выполняет продолжение до тех пор, пока оно не приостановится или не прекратит работу. Так, например:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
|
class Foo { static int foo() { bar(); bar(); return 3; } static void bar() { System.out.println("Pausing..."); Continuation.suspend(null); } public static void main(String[] args) { Continuation<Integer> c = new Continuation(Foo::foo); c.run(); // prints "Pausing..." c.run(); // prints "Pausing..." c.run(); System.out.println(c.getResult()); // prints "3" }} |
Поскольку suspend возвращает продолжение и передает его в функцию обратного вызова, мы можем расширить класс Continuation и добавить некоторые внутренние поля, чтобы получить ValuedContinuation :
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
public class ValuedContinuation<T, Out, In> extends Continuation<T> { private Out pauseOut; private In pauseIn; private RuntimeException pauseInException; public run(In in); public run(RuntimeException e); public Out getPauseValue() { ... } public static <Out, In> In pause(Out value) {...} public static <In> In pause(Consumer<ValuedContinuation<?, ?, In>> ccc) {...} public static <V, In> In pause(V x, BiConsumer<V, ValuedContinuation<?, ?, In>> ccc) {...}} |
ValuedContinutation позволяет нам передавать значения и из продолжения. Если мы вызовем pause(3) , значение 3 будет возвращено getPauseValue , а если мы возобновим продолжение с помощью run(5) , значение 5 будет возвращено pause . run(new RuntimeException()) заставит pause вызвать это исключение. Например:
|
01
02
03
04
05
06
07
08
09
10
11
|
ValuedContinuation<Void, Integer, Integer> c = new ValuedContinuation<>(() -> { int x = pause(5); x = pause(x + 10); x = pause(x * 100); return null; });while(!c.isDone()) { c.run(3); System.out.println(c.getPauseValue()); // prints: 5, 13, 300} |
Теперь мы в состоянии понять интуицию, лежащую в основе утверждения, что продолжения могут выражать любую монаду: наш монадический композитор (или bind ) будет обратным вызовом, ccc , переданным для pause ; код, следующий за каждой pause является следующей монадической функцией в монадической последовательности, а вызов c.run(x) применяет следующую монадическую функцию в цепочке.
Разница в том, что монадические функции возвращаются обратно к включающему композитору (bind), тогда как здесь мы вызываем композитор (наш ccc ) внутри нашего продолжения. Как я утверждаю в выступлении, преимущество продолжений в императивных языках состоит в том, что они хорошо взаимодействуют со всеми императивными понятиями, такими как поток императивного управления и исключения, и сохраняют контекст стека, который важен для отладки и профилирования.
Прежде чем двигаться дальше, давайте рассмотрим пример, который использует обратный вызов ccc . Это пример «будущей монады» в форме продолжения. Предположим, у нас есть асинхронный сервис:
|
1
2
3
4
5
6
7
8
|
interface AsyncHandler<T> { void success(T result); void failure(RuntimeException error);}interface AsyncService<T> { void submit(AsyncHandler<T> callback); } |
Затем мы можем определить этот метод:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
static <T> Consumer<ValuedContinuation<?, ?, T>> await(AsyncService<T> service) { return c -> { service.submit(new AsyncHandler<T>() { public void success(T result) { c.run(result); } public void failure(RuntimeException error) { c.run(error); } }); };} |
который мы будем использовать в коде, работающем внутри продолжения следующим образом:
|
1
|
String y = pause(await(service)); |
Вышеизложенное приостанавливает продолжение до тех пор, пока не завершится запрос на обслуживание, а затем возобновляет его с результатом.
Второй раунд: сочинение — продолжение по определению против монадных трансформаторов
В своем выступлении я также утверждал, что монады трудно составлять 2 , даже на чисто функциональных языках, которые отлично подходят для монад. Составление монад (т.е. написание монадического кода, который использует исключения и IO и создает последовательность) требует использования монадных преобразователей, которые довольно трудно понять, поскольку они используют функции очень высокого порядка для формирования дразнящей мозг цепочки лямбда-косвенности.
Чтобы создать легко компонуемые продолжения, в своем выступлении я представил продолжения с определенными областями , которые представляют собой вариант продолжения с разделителями. Продолжения с заданной областью являются вложенными продолжениями, где на любом уровне код может приостановить любое из входящих в него продолжений. Идея очень похожа на вложенные блоки try / catch , где, в зависимости от типа исключения, выполнение переходит к блоку catch в соответствующей области вложенности.
Чтобы проверить, насколько хорошо идея работает на практике, я реализовал прототип продолжения с заданной областью в Java и Clojure. Вы можете найти код, используя продолжение в заданной области, в cont веток Quasar и Pulsar, соответственно, здесь и здесь .
Для реализации продолжений я использовал инструментарий Quasar, который был довольно простым (хотя продолжения с определенными областями могут когда-нибудь пробиться в восходящий Quasar, это произойдет не скоро, так как сначала нам нужно сделать инструменты полностью прозрачными и практичными, что, как мы надеемся, делать когда выйдет Java 9). Сложная часть заключалась в поддержке клонирования вложенных продолжений (необходимых для недетерминированного продолжения, представленного ниже) в среде, где ссылки на продолжения могут существовать не только в стеке, но и в куче. Я попробовал три разных подхода, и я не слишком доволен ни одним из них.
Для продолжений с определенной областью нам нужно немного ValuedContinuation класс Continuation (и аналогично ValuedContinuation ):
|
1
2
3
4
5
6
7
8
|
public class Continuation<S extends Suspend, T> implements Runnable, Serializable, Cloneable { public Continuation(Class<S> scope, Callable<T> target) { ... } // <-- scope public T run() { ... } public boolean isDone() { ... } public T getResult() { ... } public static Continuation<?> suspend(S scope, Consumer<Continuation<?>> ccc) { ... } // <-- scope} |
Области являются глобальными именами. В Java я выбрал представление области так же, как представлены области исключений: в качестве имени класса (в текущей реализации области — это классы, расширяющие Suspend который является типом исключения).
Продолжения в области определены и используются так:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class ACont<T> extends ValuedContinuation<AScope, T> { public Continuation(Callable<T> target) { super(AScope.class); // ... } public static AScope A = new AScope();}// similarly BCont, and then:static void foo() { Continuation<Void> c = new ACont(() -> { // ... Continuation<Void> c = new BCont(() -> { // ... suspend(B, ...); // suspends the enclosing BCont // ... suspend(A, ...); // suspends the enclosing ACont // ... }); // ... }); // ...} |
В Clojure области являются глобальными символами, а продолжения областей могут быть определены так:
|
01
02
03
04
05
06
07
08
09
10
11
|
(let ; .... (let ; .... (pause B ...) ; ... (pause A ...) ; ... ))])))] ; ...) |
Идея продолжений с заданной областью состоит в том, что приостановка любой включающей области продолжения сопоставима с монадическими функциями, возвращающимися к любому включающему композитору (bind). Но в случае продолжений с заданной областью нам не нужно монадировать преобразователи для преобразования ни композитора, ни цепных монадических функций.
Чтобы понять, как такие композиции будут выглядеть в реальном коде, я реализовал два типа продолжения: CoIterable — который, подобно генераторам Python, генерирует Iterable с продолжением и соответствует монаде списка Хаскелла — и Ambiguity — который реализует недетерминированные вычисления с возвращение назад окружения а-ля Схемы и соответствует монаде Хаскелла.
В изоляции CoIterable используется следующим образом:
|
1
2
3
4
5
6
|
Iterable<Integer> range(int from, int to) { return new CoIterable<>(() -> { for (int i = from; i < to; i++) produce(i); });} |
Примеры операторов CoIterable таких как flatmap , map и filter см. Здесь , и обратите внимание, что дополнительные возможности гибкости дают нам более монады. Так как монадические функции возвращаются обратно к композитору, операции filter и map должны быть реализованы в терминах одного компоновщика с плоским отображением, в то время как с продолжениями у нас есть свобода выбора собственного правила композиции из продолжения и мы можем реализовать filter и map независимо от flatMap для лучшей производительности.
А вот пример Ambiguity используемой изолированно:
|
1
2
3
4
5
6
7
8
9
|
Ambiguity<Integer> amb = solve(() -> { int a = amb(1, 2, 3); // a is either 1, 2, or 3 int b = amb(2, 3, 4); // b is either 2, 3, or 4 assertThat(b < a); // ... but we know that b < a return b; });amb.run(); // returns 2 as that's the only possible solution for b |
А теперь давайте посмотрим, как эти два компонента сочетаются без проблем:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
|
Ambiguity<Integer> amb = solve(() -> { Iterable<Integer> a = iterable(() -> { produce(amb(2, 1)); // pauses on Ambiguity and CoIterable produce(amb(3, 10)); }); int sum = 0; for (int x : a) { // using imperative loops on purpose; functional would work, too sum += x; assertThat(x % 2 == 0); // we assert that all elements are even } return sum;});amb.run(); // returns 12 |
Обратите внимание, что продолжение продолжается как на Ambiguity так и на CoIterable областях. Он создает список, первый элемент которого равен 2 или 1 , а второй элемент равен 3 или 10 , что дает четыре возможных списка: (2, 3) , (2, 10) , (1, 3) и (1, 10) Позже мы утверждаем, что все элементы должны быть четными, что означает, что единственным допустимым списком для a является (2, 10) , а единственным возможным значением для sum является 12.
В качестве последнего примера (больше примеров можно найти в тестах здесь и здесь ; примеры Clojure можно найти здесь ) давайте еще больше усложним ситуацию с другим уровнем вложенности:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
|
Fiber<Integer> f = new Fiber<>(() -> { Ambiguity<Integer> amb = solve(() -> { Iterable<Integer> a = iterable(() -> { produce(amb(2, 1)); sleep(20); // pauses on the Fiber scope produce(amb(3, 10)); }); int sum = 0; for (int x : a) { sum += x; Fiber.sleep(20); assertThat(x % 2 == 0); } return sum; }); return amb.run();}).start();f.get(); // returns 12 |
Теперь мы вложили все это в волокно — легковесную реализацию потоков Quasar, которая представляет собой нечто большее, чем продолжение, запланированное планировщиком Java ForkJoin . Теперь, вложенный код внутри паузы в трех различных областях, не нарушая потоки и без преобразователей любого рода.
Но как насчет безопасности типов?
Haskell имеет очень богатую систему типов, которую монады используют с большим эффектом. Посмотрев на сигнатуру (монадической) функции, вы можете сразу сказать, в каком типе монады она может «жить», и вы не можете использовать ее нигде, кроме этой монады. Оказывается, продолжения с определенной областью можно набирать так же безопасно, не теряя ни одного из желаемых свойств. Для этого нам нужна (простая) система типов, которая позволяет нам объявлять:
|
1
|
void foo() suspends A, B |
Это означает, что foo может приостановить продолжения как в области A и в области B , и, следовательно, может вызываться только в коде, который находится в обеих областях. Класс Continuation будет тогда определен как (в псевдо-Java):
|
1
2
3
4
5
6
|
public class Continuation<S extends Suspend, T> implements Runnable, Serializable, Cloneable { public Continuation(Class<S> scope, [Callable<T> suspends S|Others] target) { ... } public T run() suspends Others { ... } public static Continuation<?> suspend(S scope, Consumer<Continuation<?>> ccc) suspends S} |
Таким образом, продолжение может запускать любой целевой код, который, возможно, приостанавливается в параметризованной области S и, возможно, в других областях, а метод run проглатывает область S но все же приостанавливает другие области.
Как оказалось, у нас уже есть такая система типов — почти : проверенные исключения Java. Если бы мы создали область действия Suspend , от которой спускаются все области, мы могли бы использовать throws Java точно так же, как и suspend в псевдо-Java выше. Причина, по которой я этого не сделал, состоит в том, что система типов Java не позволяет вам захватывать несколько проверенных типов исключений, как я делал с Others выше, что означало бы, что нам потребуются явные случаи для явных областей действия (функции, которые приостанавливают одну область действия, две области и т. д.), которые могут сделать вещи громоздкими.
Затем мы могли бы также улучшить безопасность типов ValuedContinuation , параметризовав область видимости, чтобы у нас было:
|
1
|
void foo() suspends CoIterableScope<Integer> |
Что позволило бы вызывать только foo внутри CoIterable который производит последовательность из Integer s (а не, скажем, String s). К сожалению, мы также не можем сделать это, поскольку Java в настоящее время не допускает универсальных типов исключений.
Продолжение следует?
Я надеюсь, что при более глубоком обсуждении продолжений с заданной областью я смог объяснить идею лучше, чем махание рукой, которое использовал в своем выступлении, и я рад, что нашел доказательство Филински (которое, вероятно, хорошо известно в кругах PL ).
Я надеюсь, что мой доклад убедил вас, что монадам нет места в императивных языках (за исключением параллельных вычислений, может быть), и если нет, я бы хотел услышать, почему нет. Я также считаю, что продолжения с заданной областью сочинения лучше, чем монады, даже на языках PFP (а также то, что монады, в общем, не очень хороший способ моделирования эффектов, но это совсем другое обсуждение).
Наконец, хотя я твердо убежден, что императивные языки должны иметь некоторую форму легких потоков (волокна АКА, потоки пользовательского режима АКА, своего рода зеленые потоки АКА) и потоки (любого рода) — это не что иное, как продолжения, запланированные соответствующим планировщиком. Я не обязательно думаю, что императивные языки должны непосредственно представлять объемные продолжения как абстракцию. В конце концов, существуют абстракции для увеличения повторного использования кода, помощи в обслуживании кода и помощи в проверке: короче говоря, они существуют для снижения затрат на разработку и — по крайней мере с точки зрения неисследований — это единственный показатель, по которому они используются. судили 3 . Я думаю, что продолжения — это элегантный императивный аналог элегантных монад PFP, но я еще не уверен в их полезности на практике.
Если вы хотите узнать больше о продолжениях, это история их развития, которая отдает должное всем нужным людям.
Приложение 1
С тех пор, как я впервые опубликовал этот пост в блоге, мне удалось найти ссылку на продолжение с областью действия в статье Филипа Уодлера 1993 года « Монады и составные продолжения» , где он называет продолжения с областью действия просто как «составные продолжения с несколькими уровнями». Поскольку Вадлер показал, что продолжения с разделителями можно выразить через монады, а Филинский (год спустя) показал, что монады можно выразить как продолжения с разделителями, очевидно, что оба они являются дуальными. Тем не менее, само собой разумеется, что, даже будучи дуалами, каждый из них больше подходит для определенного стиля программирования, и нет никаких сомнений в том, что продолжения больше подходят для нечистых языков с вызовом по значению (императивных и функционально-императивных). Вадлер завершает свою статью, говоря:
Одна из целей составных продолжений с несколькими уровнями состояла в том, чтобы иметь возможность разделять различные эффекты на разные уровни. Данви и Филински утверждают, что таким образом относительно легко объединить различные эффекты. Монады также предназначены для учета эффектов таким образом, чтобы облегчить их комбинацию. Однако не существует единого правила для объединения любых двух монад. Эта статья использовала монады, чтобы пролить свет на составные продолжения. Проливают ли композиционные продолжения проблему объединения монад?
Приложение 2
В онлайн-дискуссии читатель прокомментировал, что я неправильно понял монады, говоря о том, как они выглядят, а не как они есть. Я думаю, что это не более чем разница в интерпретации, поэтому я хотел бы уточнить:
Поскольку было доказано (я думаю), что любой эффект может быть смоделирован монадами, вы можете сказать, что все эффекты являются монадическими, но, как и математик в известной шутке, это абсолютно верно, но абсолютно бесполезно (в зависимости от вашей точки зрения). -вид, наверное).
С математической точки зрения, когда две вещи изоморфны, они являются «одинаковыми». Но с точки зрения программирования, они могут быть очень разными, поскольку абстракции — это психологические взаимодействия с умом программиста, и две изоморфные математические концепции могут психологически взаимодействовать с программистом совершенно по-разному. Поэтому, если мне не нужно «думать в монадах» при работе с абстракцией, то абстракция не является монадой, даже если между ними существует изоморфизм.
Согласно математической интерпретации, быть «против монад» так же бессмысленно, как и против числа 1. Хотя в моей интерпретации представление числа 1 арабскими цифрами, церковными цифрами или теориями множеств очень психологически отличается и следовательно, в языках программирования они существенно различаются, поскольку языки программирования — это, прежде всего, человеческие языки. В языке программирования абстракции определяются (и измеряются) как математическими, так и психологическими (или экономическими) свойствами.
Я «алгоритмист», а не «абстракционист» (и, к сожалению, я думаю, что эти две перспективы CS часто расходятся), поэтому я измеряю полезность абстракции только в изменении стоимости, которое она вносит в написание и поддержку мои алгоритмы, так что для меня монады — это скорее шаблон проектирования, а не математический объект, выраженный в какой-то конкретной записи.
- Затем я обнаружил этот пост, в котором говорится, что доказательство Филински не распространяется на монады, использующие ленивую оценку (по имени).
- Например, попробуйте составить потоки Java с помощью
CompletableFutures. Это не легко. - Смотрите это обсуждение HN по этому вопросу.
| Ссылка: | От императива к чисто функциональному и обратно: продолжения монады и области действия от нашего партнера JCG Рона Пресслера в блоге Parallel Universe . |