Часто встречается описание систем, алгоритмов и процессов в виде структурных схем. Следовательно, актуальна задача представления структурных схем, к примеру, из технической документации или спецификации, на языке программирования.
В статье рассматривается подход к представлению структурных схем с использованием концепции стрелок (arrows), описанных Джоном Хьюзом и нашедших применение в Haskell в FRP-фреймворках Yampa и Netwire, а также в XML-фреймворке Haskell XML Toolbox.
Особенностью структурных схем является наглядное представление последовательностей операций (блоков) без акцентирования внимания на самих обрабатываемых данных (переменных) и их состояниях. Для примера рассмотрим радиоприёмник прямого усиления
Как же реализовать такой способ описания систем и вычислений в рамках существующих мейнстримовых языков программирования?
Традиционное описание такой схемы на C-подобном языке программирования выглядело бы примерно так
// Создаём блоки обработки
Antenna antenna = new Antenna(Ether.getInstance());
Filter filter1 = new Filter(5000); // параметр - частота настройки
Filter filter2 = new Filter(5000);
Filter filter3 = new Filter(5000);
Detector detector = new Detector("AM"); // тип модуляции - амплитудная
Amplifier amp = new Amplifier(5); // коэффициент усиления
Speaker speaker = new Speaker(10); // громкость
Signal inputSignal = antenna.receive();
# Описываем связи между блоками
Signal filter1Res = filter1.filter(inputSignal);
Signal filter2Res = filter2.filter(filter1Res);
Signal filter3Res = filter3.filter(filter2Res);
Signal detected = detector.detect(filter3Res);
Signal amplified = amp.amplify(detected);
speaker.speak(amplified);Видно, что в программу добавились переменные, которых нет в структурной схеме, и которые, следовательно, не добавляют никакой информации о работе радиоприёмника, а нужны лишь для хранения промежуточных результатов обработки входного сигнала.
Такая программа, описывающая лишь простое поэтапное прохождение сигнала через блоки обработки, выглядит довольно громоздко. Более лаконичным подходом будет описание схемы с использованием нового метода join, подключающего блоки друг к другу:
Receiver receiver = Receiver.join(filter1).join(filter2).join(filter3)
.join(detector).join(amp).join(speaker);
receiver.apply(antenna.receive());Метод join() описывает последовательное соединение блоков, то есть a.join(b) означает, что результат обработки блоком a будет передан на вход блока b. При этом лишь требуется, чтобы соединяемые классы Filter, Amplifier, Detector, Speaker дополнительно реализовывали метод apply(), выполняющий "действие по умолчанию" (для фильтра Filter — filter(), для Amplifier — amplify() и т. д.) и позволяющий вызывать объект как функцию.
При функциональном подходе эти классы были бы функциями, возвращающими функции, так что нам не пришлось бы даже создавать экземпляры классов и вся программа выглядела бы примерно так:
Receiver receiver = Receiver.join(filter(5000)).join(filter(5000)).join(filter(5000))
.join(detector("AM")).join(amplifier(5)).join(speaker(10));
receiver.apply(antenna.receive());Стрелки как способ описания вычислений
Особенностью функционального подхода является использование комбинаторов (например монад), которые являются функциями, объединяющими другие функции в составные вычисления.
Стрелки (arrows) также являются комбинатором и позволяют обобщенно описывать составные вычисления. В этой статье используется реализация стрелок jArrows, написанная на Java 8.
Что такое стрелка
Стрелка Arrow<In, Out> a от функции Out f(In x) представляет вычисление, которое выполняется функцией f. Как вы уже могли догадаться In — тип входного значения стрелки (принимаемого функцией f), Out — тип выходного значения (возвращаемого функцией f). Преимуществом представления вычислений в виде стрелок является возможность явного комбинирования вычислений различными способами.
Например вычисление y = x * 5.0, на Java представленное функцией
double multBy5_0(int in) {
return in*5.0;
}можно представить в виде стрелки
Arrow<Integer, Double> arrMultBy5_0 = Action.of(multBy5_0);Далее упакованное в стрелку вычисление можно комбинировать с другими вычислениями-стрелками. Класс Action является одной из реализаций интерфейса Arrow. Другой реализацией этого интерфейса является ParallelAction, поддерживающий многопоточные вычисления.
Композиция стрелок
Стрелку arrMultBy5_0 можно последовательно соединить с другой стрелкой — например, прибавляющей к входному значению 10.5, а затем — со следующей стрелкой, представляющей результат в виде строки. Получится цепочка из стрелок
Arrow<Integer, String> mult5Plus10toStr = arrMultBy5_0.join(in -> in+10.5)
.join(in -> String.valueOf(in));
mult5Plus10toStr.apply(10); // "60.5" Получившееся вычисление, представленное составной стрелкой mult5Plus10toStr, можно представить в виде структурной схемы:
Вход этой стрелки имеет тип Integer (входной тип первого вычисления в цепочке), а выход имеет тип String (выходной тип последнего вычисления в цепочке).
Метод someArrow.join(g) соединяет в цепочку вычисление, представленное стрелкой someArrow с вычислением, представленным g, при этом g может быть другой стрелкой, лямбда-функцией, методом, или чем-то ещё, что реализует интерфейс Applicable с методом apply(x), который можно применить к входному значению x.
class Action<In, Out> implements Arrow<In, Out>, Applicable<In, Out> {
Applicable<In, Out> func;
public Arrow<In, OutB> join(Applicable<Out, OutB> b) {
return Action.of(i -> b.apply(this.func.apply(i)));
}
}Здесь In — тип входных данных стрелки a, OutB — тип выходных данных b, и он же — тип выходных данных получившейся новой составной стрелки a_b = a.join(b), Out — тип выходных данных стрелки a, он же — тип входных данных стрелки b.
Функция func хранится в экземпляре стрелки, инициализируется при её создании и выполняет само вычисление. Аргумент b поддерживает интерфейс Applicable и может быть другой стрелкой или функцией, поэтому мы просто применяем b к результату применения a.func(i) к входным данным i стрелки a_b. Сам входные данные будут переданы при вызове apply составной стрелки a_b, так что a_b.apply(x) вернёт результат вычисления b.func(a.func(x)).
Другие способы композиции стрелок
Кроме последовательного соединения методом join стрелки можно соединять параллельно методами combine, cloneInput и split. Пример использования метода combine для описания вычисления sin(x)^2+cos(x)^2
Arrow<Pair<Double, Double>, Pair<Double, Double>>
sin_cos = Action.of(Math::sin).combine(Math::cos);
Arrow<Double, Double> sqr = Action.of(i -> i*i);
Arrow<Pair<Double, Double>, Double> sum_SinCos = sin_cos.join(sqr.combine(sqr))
.join(p -> p.left + p.right);
sum_SinCos.apply(Pair.of(0.7, 0.2)); // 1.38
Получившаяся "широкая" стрелка sin_cos принимает на вход пару значений типа Pair<Double, Double>, первое значение pair.left пары попадает на вход первой стрелки (функция sin), второе pair.right — на вход второй стрелки (функция cos), их результаты тоже объединяются в пару. Следующая составная стрелка sqr.combine(sqr) принимает на вход значение типа Pair<Double, Double>и возводит оба значения пары в квадрат. Последняя стрелка суммирует результат.
Метод someArrow.cloneInput(f) создаёт стрелку, параллельно соединяя someArrow и f и применяя их к входу, её выход представляется в виде пары, объединяющей результаты вычилений этих стрелок. Входные типы someArrow и f должны совпадать.
Arrow<Integer, Pair<Integer, Double>> sqrAndSqrt = Action.of((Integer i) -> i*i)
.cloneInput(Math::sqrt);
sqrAndSqrt.apply(5); // Pair(25, 2.236)
Параллельное соединение в данном случае означает, что результаты двух вычислений, соединённых параллельно, не зависят друг от друга — в отличии от последовательного соединения методом join, когда результат одного вычисления передаётся на вход другого. Многопоточные параллельные соединения реализуется классом ParallelAction.
Метод someArrow.split(f, g) — дополнительный метод, эквивалентный someArrow.join(f.cloneInput(g)). Результат вычисления someArrow параллельно передаётся на вход f и g, выходом такой стрелки будет пара с результатами вычислений f и g.
Обход вычислений
Иногда нужно передать часть входного значения стрелки далее по цепочке вместе с результатом вычисления. Это реализуется методом someArrow.first() и дополняющим его someArrow.second(), преобразующим стрелку someArrow так, что получившаяся стрелка принимает на вход пару значений и применяет вычисление лишь к одному из элементов этой пары
Arrow<Integer, Double> arr = Action.of(i -> Math.sqrt(i*i*i));
Pair input = Pair.of(10, 10);
arr.<Integer>first().apply(Pair.of(10, 10))); // Pair(31.623, 10)
arr.<Integer>second().apply(Pair.of(10, 10))); // Pair(10, 31.623)
Эти методы аналогичны методам someArrow.bypass2nd() и someArrow.bypass1st() соответственно.
Полнота описания
Согласно Хьюзу, описание любого вычисления возможно с использованием лишь трёх функций:
- 1) Конструктора, строящего стрелку из функции (в данной реализации Action.of)
- 2) Функции, последовательно соединяющей две стрелки (Arrow::join)
- 2) Функции, применяющей вычисление к части входа (Arrow::first)
Реализация jArrows также расширена дополнительными методами, упрощающими описание систем.
Выводы
Высокоуровневое описание процессов в виде блок-схем практически не используется в императивном подходе в программировании. В тоже время такое описание хорошо укладывается в функциональный реактивный подход, получающий всё большее распространение.
Как показано в статье Хьюза, стрелки, по-сути являющиеся реализацией описания систем в виде блок-схем в рамках функционального программирования, являются более обобщенным описанием, чем монады, которые уже получили распространение в мейнстриме, в частности в виде их реализации Optional в Java 8. В данной статье описаны основные принципы данного подхода, в дальнейшем представляет интерес адаптация существующих и разработка новых паттернов для применения стрелок в мейнстримовой разработке программного обеспечения.
Комментарии (43)
zloddey
06.10.2016 20:35Это всё замечательно, конечно, но мой полусонный мозг не может понять — чем описанная конструкция принципиально отличается от Java Streams? Кроме того, что Streams уже есть в самом языке.
sshikov
06.10.2016 21:30Стримы и стрелки — это два разных подхода к композиции программы из кусков. Из стрелок можно например построить обработку ошибок (Either<Result, Exception> это тоже стрелки, если что).
Т.е. я бы ответил на ваш вопрос так — они всем отличаются. То что вы увидели в примере нечто, показавшееся вам похожим на стримы — чистое совпадение, такой пример автор выбрал.
Ondator
06.10.2016 22:56+1Не очень понял чем стрелка отличается от функции высшего порядка https://en.wikipedia.org/wiki/Higher-order_function. Есть какие-то концептуальные различия?
yarric
06.10.2016 23:00Стрелки — один из функциональных фреймворков, который определяет несколько функций (высшего порядка) для композиции других функций.
То есть это какбы библиотека, которая предлагает определённый подход к композиции функций.
lany
07.10.2016 03:16+2Вот я всё равно не вижу отличия. Можно конкретно посмотреть на существующий интерфейс
java.util.function.Function, который очень похож на вашу стрелку. В нём уже естьjoin(только называется по-другому —andThen).
А абстрактные пары и прочие туплы — это, конечно, ад. В джаве оно не нужно.
sshikov
07.10.2016 19:08А давайте, расскажите, как вы скажем будете делать Map, у которого ключом является пара значений разных типов? Вместо tuple — отдельный класс поди заведете?
lany
08.10.2016 04:44Естественно! Вы так говорите, будто класс — это что-то плохое.
sshikov
10.10.2016 09:56Может, вы и анонимные классы по-прежнему предпочитаете лямбдам? )
lany
10.10.2016 10:14Нет. При чём тут это? Несуразицу вы сейчас сказали.
sshikov
10.10.2016 10:18При том же. Вы предпочитаете написать класс вместо Tuple.of(123, "string")? Даже тогда, когда этот класс не имеет никакого осмысленного имени (а анонимный вы в случае ключа для Map не сделаете), и не имеет никакого смысла вне контекста одной-двух строк кода?
Я именно об этом. Tuple — это ровно такой же безымянный, но с типизированными полями при этом, класс, для которого не имеет смысла придумывать названия, как лябмда — это безымянный класс с одним методом.
Это удобно. Если вы этого не чувствуете — это ваше дело.
lany
10.10.2016 10:31Угу, а потом вы захотите этот тупл вернуть из метода и передать в другой метод, потом у вас тупл туплов образуется и понеслась. Никто уже не знает, что значит first, а что значит second. Если вам хочется производить write-only code — это, в принципе, тоже ваше дело.
sshikov
10.10.2016 10:49+1Ха-ха )))
А потом вы захотите эту лямбду вернуть из метода и передать в другой метод, а потом у вас функции высшего порядка образуются, и понеслась.
Вы все еще не видите аналогии? Пара (или Tuple в общем случае) — это абстракция, которой тоже нужно уметь пользоваться. Написать с ее помощью всякую чепуху можно точно также, как с помощью любой другой абстракции. Но это совершенно не повод утверждать, что В джаве оно не нужно.
Вы никогда не знаете, что внутри у функции Function<Integer, String>, которую вам передали откуда-то, потому что это называется абстракция.
Возможно, это плохая абстракция. Но вы можете сделать более хорошую, например Function<Index, Address>. Все в ваших руках. И иногда Tuples для этого очень удобны.
yarric
07.10.2016 19:23andThen — это относится к монадам, а стрелки — более обобщенная концепция, в них ещё first есть.
lany
08.10.2016 04:50+1А есть более реалистичный пример, чем вычисление простой математической формулы, требующее в 10 раз больше кода, чем надо (не считая подключения библиотеки)? Когда это может быть оправдано по сравнению с альтернативами уже имеющимися в языке?
yarric
08.10.2016 20:10Например верификация пользователя. По-сути, любой процесс, который можно описать блок-схемой, хорошо ложится на эту модель, математические примеры приведены просто чтобы не писать много кода для описания реальных объектов.
yarric
08.10.2016 20:27Кстати решил переписать один из математических примеров в обычном стиле:
@FunctionalInterface interface Function2 <A, B, R> { public R apply (A a, B b); } ... Function2 <Double, Double, Double> sum_SinCos = (a, b) -> { double sin_res = Math.sin(a); double cos_res = Math.cos(b); return sin_res*sin_res + cos_res*cos_res; };
Не сказал бы, что он в 10 раз короче, тем более тут мы лишились возможности повторного использования блоков.
lany
09.10.2016 05:20Вы неправильно это делаете:
static double sumSinCos(double a, double b) { double sin_res = Math.sin(a); double cos_res = Math.cos(b); return sin_res*sin_res + cos_res*cos_res; }
Если блоком вы считаете вызов метода
Math.sin, то почему мы лишились возможности вызватьMath.sinв других местах?yarric
09.10.2016 09:59Блок — это
sin_cos(который определён какAction.of(Math::sin).combine(Math::cos)), который можно применять к паре значений.
В вашем примереsumSinCos— не лямбда, так что он уже не совсем эквивалентен: нужно ещё описать класс-обёртку. В итоге количество строк такое же.lany
09.10.2016 10:32+1Зачем класс-обёртка? У вас и так уже есть какой-то класс, в нём можно всё написать. Зачем обязательно лямбда? Если где-то принимающая сторона ожидает функциональный интерфейс, воспользуйтесь ссылкой на метод, а если где-то нужно просто вызвать метод, то и вызывайте спокойно. Выглядит так, будто из ничего изобретаются проблемы, а потом они отважно решаются.
yarric
09.10.2016 12:18+1А как, отвлекаясь от простых математических функций из примера, из статического метода сделать closure? Статический метод — это уже не эквивалент лямбды и примера со стрелкой.
Проблемы, решаемые данным подходом, показаны в начале статьи: явное описание dataflow в приложении. Если Ваc смущает, что простые математические функции можно вызвать проще, то можно написать более абстрактный пример:
Arrow<Pair<A, B>, С> someArrow = Action.of(f1).combine(f2) .join(arr2.combine(arr2)) .join(f3); someArrow.apply(Pair.of(instA, instB));
Тут
f1, f2, arr2, f2— какие-то существующие длинные функции, как это обычно и бывает. В безточечной записи с обычными вызовами это будет выглядеть примерно так (описание интерфейса лямбды опустим):
Function someLambda = (A instA, B instB) -> { return f3(arr2(f1(instA)), arr2(f2(instB))); } someLambda.apply(instA, instB);
Для простых функций оно выглядит почти одинаково, но что, если мы захотим использовать монады или сделать параллельный
combine, например? Со стрелкой мы просто используем ParallelAction вместо Action, а вот лямбду придётся переписывать с futures со всеми вытекающими.lany
09.10.2016 12:38Во, теперь аргументация звучит убедительнее. Конечно, лямбда попроще будет выглядеть:
BiFunction<A, B, C> fn = (instA, instB) -> f3...;
И функциональный интерфейс объявлять, конечно, не нужно, всё есть в стандартной библиотеке. Но не суть. Автоматическое распараллеливание — окей, принимается. А что значит "захотим использовать монады"? Приведите пример.
yarric
09.10.2016 13:06Зато придётся описывать интерфейс, если там будет больше аргументов. Что мы пишем
BiFunction, чтоArrow— какой-то существенной разницы в объёме написанного не видно, честно говоря. Разве что более многословно описывается последовательность вызова функций, но и возможностей больше.
Работа с монадами в
jArrowsпока не реализована из коробки, в статье по ссылкам это называется Kleisli Arrow. С такой стрелкой можно делать композицию функций, которые возвращают монады.
sshikov
10.10.2016 10:01Вы не замечаете тут простую разницу, что при помощи стрелок математические формулы строятся в том числе в runtime? Т.е., по сути, в случае формулы в коде, компилятор за вас построит что-то похожее на стрелки, с выводом типов и т.п.
lany
10.10.2016 10:17Окей, добавив много кода, можно сэмулировать AST-дерево формул прямо из джава сорцов. При этом превращая все формулы в довольно-таки нечитаемое месиво. Но если это действительно нужно, почему бы не подключить символьный математический процессор, который будет в рантайме разбирать ваши формулы (и при необходимости делать с ними преобразования — дифференцировать или интегрировать символьно, например)? При этом формулы можно будет писать по-человечески, не теряя в читабельности. Каждой задаче свой инструмент.
AndreyDmitriev
07.10.2016 11:25+2Похоже вы (точнее, Джон Хьюз) изобрели принцип Data Flow Programming.
В LabVIEW это работает примерно вот так:
как говорится, «как слышится, так и пишется».
Код с синусом и косинусом будет соответственно выглядеть ну как-то вот так, что ли:
Ну или ещё проще:
yarric
07.10.2016 19:27В своей области LabVIEW хорош, но в мейнстримовом прикладном программировании графический подход почему-то не получил распространения. А к области Java LabVIEW совсем слабо применим.
AndreyDmitriev
07.10.2016 19:40Да, согласен, вы правы, конечно. Просто ну очень уж напомнило. Кто знает, может через много-много (ну очень много) лет графическое функциональное программирование постепенно вытеснит императивное текстовое.
taujavarob
07.10.2016 20:05>Кто знает, может через много-много (ну очень много) лет графическое функциональное программирование постепенно вытеснит императивное текстовое.
Во многих чатах УЖЕ вытеснило. Смайлик смайлики погоняет…
igor_suhorukov
07.10.2016 22:41Такой подход применим и для java — есть решение. Через пару недель опубликую статью — осталось хороший пример сделать.
yarric
08.10.2016 20:13Я имел ввиду, что на LabView очень редко пишут программы для энтерпрайза, в отличии от Java.
igor_suhorukov
09.10.2016 12:49Конечно, это разные предметные области. Для энтерпрайза в монструозных проетах рисуют архитектуру в виде UML диаграмм. Из визуального программирования для java: BPMN2, ETL и enterprise integration patterns в eclipse редакторе для apache Camel
ankh1989
Не очевидно. Это всего лишь говорит о том, что у того конкретного эйчара странные критерии поиска сотрудников. О компании это не говорит вообще ничего.
sshikov
Новаторский? Этому подходу в Java уже лет так… 10 пожалуй. Кому надо — те давно уже его использовали.
yarric
Честно говоря не нашел реализации концепции стрелок на Java, да и реализовать их было бы проблематично на более старых версиях.
sshikov
Проблематично, само собой. Более того, некоторые вещи вообще практически не сделать по разным причинам (спасибо type erasure, в частности). Но тем не менее, реализации были, некоторые вещи примерно 2008 года вполне себе гуглятся без проблем.
sshikov
Ну вот скажем, “Lazy Error Handling in Java, Part 3: Throwing Away Throws” — это правда не совсем полноценная реализация, а скорее концепт.
Sirikid
Поэтому их реализовывали, например, на Scala. JVM большая, на всех хватит.
yarric
Не всегда получается свободно выбирать язык, всё-же Java значительно шире распространён.
vitrilo
В Java давно были диаграммы — BPML.
Netbeans и Eclipce поддерживают редактирование BPML. Это правда enterprise, и BPML выполнял сервер, но некоторые библиотеки свободно генерили читаемую JAVA на выходе.
Также, очень многие реализовывали диаграммы во время бума workflow engines (Jira и др).
Но в те времена не был популярным термин функциональное программирование, диаграммы больше описывали DataFlow.
yarric
Java 8 — вполне себе функциональный язык, даже монады уже есть. Почему бы не реализовать ещё стрелки, хотя бы из интереса.