Стрелки как подход к представлению систем на Java +14


Часто встречается описание систем, алгоритмов и процессов в виде структурных схем. Следовательно, актуальна задача представления структурных схем, к примеру, из технической документации или спецификации, на языке программирования.


В статье рассматривается подход к представлению структурных схем с использованием концепции стрелок (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(), выполняющий "действие по умолчанию" (для фильтра Filterfilter(), для Amplifieramplify() и т. д.) и позволяющий вызывать объект как функцию.


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


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.


Несколько упрощенная реализация join
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):

  1. ankh1989
    /#9845120

    Не очевидно. Это всего лишь говорит о том, что у того конкретного эйчара странные критерии поиска сотрудников. О компании это не говорит вообще ничего.

    • sshikov
      /#9845310 / +1

      Новаторский? Этому подходу в Java уже лет так… 10 пожалуй. Кому надо — те давно уже его использовали.

      • yarric
        /#9845504

        Честно говоря не нашел реализации концепции стрелок на Java, да и реализовать их было бы проблематично на более старых версиях.

        • sshikov
          /#9847604

          Проблематично, само собой. Более того, некоторые вещи вообще практически не сделать по разным причинам (спасибо type erasure, в частности). Но тем не менее, реализации были, некоторые вещи примерно 2008 года вполне себе гуглятся без проблем.

        • sshikov
          /#9847608

          Ну вот скажем, “Lazy Error Handling in Java, Part 3: Throwing Away Throws” — это правда не совсем полноценная реализация, а скорее концепт.

        • Sirikid
          /#9847968

          Поэтому их реализовывали, например, на Scala. JVM большая, на всех хватит.

          • yarric
            /#9848732

            Не всегда получается свободно выбирать язык, всё-же Java значительно шире распространён.

        • vitrilo
          /#9849068 / +1

          В Java давно были диаграммы — BPML.
          Netbeans и Eclipce поддерживают редактирование BPML. Это правда enterprise, и BPML выполнял сервер, но некоторые библиотеки свободно генерили читаемую JAVA на выходе.
          Также, очень многие реализовывали диаграммы во время бума workflow engines (Jira и др).
          Но в те времена не был популярным термин функциональное программирование, диаграммы больше описывали DataFlow.

    • yarric
      /#9845502

      Java 8 — вполне себе функциональный язык, даже монады уже есть. Почему бы не реализовать ещё стрелки, хотя бы из интереса.

  2. zloddey
    /#9845294

    Это всё замечательно, конечно, но мой полусонный мозг не может понять — чем описанная конструкция принципиально отличается от Java Streams? Кроме того, что Streams уже есть в самом языке.

    • sshikov
      /#9845376

      Стримы и стрелки — это два разных подхода к композиции программы из кусков. Из стрелок можно например построить обработку ошибок (Either<Result, Exception> это тоже стрелки, если что).


      Т.е. я бы ответил на ваш вопрос так — они всем отличаются. То что вы увидели в примере нечто, показавшееся вам похожим на стримы — чистое совпадение, такой пример автор выбрал.

  3. Ondator
    /#9845484 / +1

    Не очень понял чем стрелка отличается от функции высшего порядка https://en.wikipedia.org/wiki/Higher-order_function. Есть какие-то концептуальные различия?

    • yarric
      /#9845496

      Стрелки — один из функциональных фреймворков, который определяет несколько функций (высшего порядка) для композиции других функций.
      То есть это какбы библиотека, которая предлагает определённый подход к композиции функций.

      • lany
        /#9845796 / +2

        Вот я всё равно не вижу отличия. Можно конкретно посмотреть на существующий интерфейс java.util.function.Function, который очень похож на вашу стрелку. В нём уже есть join (только называется по-другому — andThen).


        А абстрактные пары и прочие туплы — это, конечно, ад. В джаве оно не нужно.

        • sshikov
          /#9847594

          А давайте, расскажите, как вы скажем будете делать Map, у которого ключом является пара значений разных типов? Вместо tuple — отдельный класс поди заведете?

          • lany
            /#9848138

            Естественно! Вы так говорите, будто класс — это что-то плохое.

            • sshikov
              /#9849736

              Может, вы и анонимные классы по-прежнему предпочитаете лямбдам? )

              • lany
                /#9849774

                Нет. При чём тут это? Несуразицу вы сейчас сказали.

                • sshikov
                  /#9849784

                  При том же. Вы предпочитаете написать класс вместо Tuple.of(123, "string")? Даже тогда, когда этот класс не имеет никакого осмысленного имени (а анонимный вы в случае ключа для Map не сделаете), и не имеет никакого смысла вне контекста одной-двух строк кода?


                  Я именно об этом. Tuple — это ровно такой же безымянный, но с типизированными полями при этом, класс, для которого не имеет смысла придумывать названия, как лябмда — это безымянный класс с одним методом.


                  Это удобно. Если вы этого не чувствуете — это ваше дело.

                  • lany
                    /#9849808

                    Угу, а потом вы захотите этот тупл вернуть из метода и передать в другой метод, потом у вас тупл туплов образуется и понеслась. Никто уже не знает, что значит first, а что значит second. Если вам хочется производить write-only code — это, в принципе, тоже ваше дело.

                    • sshikov
                      /#9849840 / +1

                      Ха-ха )))


                      А потом вы захотите эту лямбду вернуть из метода и передать в другой метод, а потом у вас функции высшего порядка образуются, и понеслась.


                      Вы все еще не видите аналогии? Пара (или Tuple в общем случае) — это абстракция, которой тоже нужно уметь пользоваться. Написать с ее помощью всякую чепуху можно точно также, как с помощью любой другой абстракции. Но это совершенно не повод утверждать, что В джаве оно не нужно.


                      Вы никогда не знаете, что внутри у функции Function<Integer, String>, которую вам передали откуда-то, потому что это называется абстракция.


                      Возможно, это плохая абстракция. Но вы можете сделать более хорошую, например Function<Index, Address>. Все в ваших руках. И иногда Tuples для этого очень удобны.

        • yarric
          /#9847626

          andThen — это относится к монадам, а стрелки — более обобщенная концепция, в них ещё first есть.

          • lany
            /#9848140 / +1

            А есть более реалистичный пример, чем вычисление простой математической формулы, требующее в 10 раз больше кода, чем надо (не считая подключения библиотеки)? Когда это может быть оправдано по сравнению с альтернативами уже имеющимися в языке?

            • yarric
              /#9848620

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

            • yarric
              /#9848636

              Кстати решил переписать один из математических примеров в обычном стиле:


              @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
                /#9848956

                Вы неправильно это делаете:


                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
                  /#9849004

                  Блок — это sin_cos (который определён как Action.of(Math::sin).combine(Math::cos)), который можно применять к паре значений.
                  В вашем примере sumSinCos — не лямбда, так что он уже не совсем эквивалентен: нужно ещё описать класс-обёртку. В итоге количество строк такое же.

                  • lany
                    /#9849014 / +1

                    Зачем класс-обёртка? У вас и так уже есть какой-то класс, в нём можно всё написать. Зачем обязательно лямбда? Если где-то принимающая сторона ожидает функциональный интерфейс, воспользуйтесь ссылкой на метод, а если где-то нужно просто вызвать метод, то и вызывайте спокойно. Выглядит так, будто из ничего изобретаются проблемы, а потом они отважно решаются.

                    • yarric
                      /#9849072 / +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
                        /#9849088

                        Во, теперь аргументация звучит убедительнее. Конечно, лямбда попроще будет выглядеть:


                        BiFunction<A, B, C> fn = (instA, instB) -> f3...;

                        И функциональный интерфейс объявлять, конечно, не нужно, всё есть в стандартной библиотеке. Но не суть. Автоматическое распараллеливание — окей, принимается. А что значит "захотим использовать монады"? Приведите пример.

                        • yarric
                          /#9849102

                          Зато придётся описывать интерфейс, если там будет больше аргументов. Что мы пишем BiFunction, что Arrow — какой-то существенной разницы в объёме написанного не видно, честно говоря. Разве что более многословно описывается последовательность вызова функций, но и возможностей больше.


                          Работа с монадами в jArrows пока не реализована из коробки, в статье по ссылкам это называется Kleisli Arrow. С такой стрелкой можно делать композицию функций, которые возвращают монады.

            • sshikov
              /#9849742

              Вы не замечаете тут простую разницу, что при помощи стрелок математические формулы строятся в том числе в runtime? Т.е., по сути, в случае формулы в коде, компилятор за вас построит что-то похожее на стрелки, с выводом типов и т.п.

              • lany
                /#9849782

                Окей, добавив много кода, можно сэмулировать AST-дерево формул прямо из джава сорцов. При этом превращая все формулы в довольно-таки нечитаемое месиво. Но если это действительно нужно, почему бы не подключить символьный математический процессор, который будет в рантайме разбирать ваши формулы (и при необходимости делать с ними преобразования — дифференцировать или интегрировать символьно, например)? При этом формулы можно будет писать по-человечески, не теряя в читабельности. Каждой задаче свой инструмент.

                • sshikov
                  /#9849790 / +1

                  Хм. Вообще-то Kleisli Arrows — это по большому счету и есть средство для написания такого "символьного математического процессора".

                  • lany
                    /#9849814 / +1

                    Напишите статью "как написать символьный математический процессор с помощью Kleisli Arrows". Интересно.

  4. AndreyDmitriev
    /#9846206 / +2

    Похоже вы (точнее, Джон Хьюз) изобрели принцип Data Flow Programming.
    В LabVIEW это работает примерно вот так:

    как говорится, «как слышится, так и пишется».

    Код с синусом и косинусом будет соответственно выглядеть ну как-то вот так, что ли:


    Ну или ещё проще:

    • yarric
      /#9847628

      В своей области LabVIEW хорош, но в мейнстримовом прикладном программировании графический подход почему-то не получил распространения. А к области Java LabVIEW совсем слабо применим.

      • AndreyDmitriev
        /#9847656

        Да, согласен, вы правы, конечно. Просто ну очень уж напомнило. Кто знает, может через много-много (ну очень много) лет графическое функциональное программирование постепенно вытеснит императивное текстовое.

        • taujavarob
          /#9847686

          >Кто знает, может через много-много (ну очень много) лет графическое функциональное программирование постепенно вытеснит императивное текстовое.

          Во многих чатах УЖЕ вытеснило. Смайлик смайлики погоняет…

      • igor_suhorukov
        /#9847886

        Такой подход применим и для java — есть решение. Через пару недель опубликую статью — осталось хороший пример сделать.

        • yarric
          /#9848622

          Я имел ввиду, что на LabView очень редко пишут программы для энтерпрайза, в отличии от Java.

          • igor_suhorukov
            /#9849094

            Конечно, это разные предметные области. Для энтерпрайза в монструозных проетах рисуют архитектуру в виде UML диаграмм. Из визуального программирования для java: BPMN2, ETL и enterprise integration patterns в eclipse редакторе для apache Camel

    • FForth
      /#9848316

      Есть ещё хороший пример — конструктор программ HiAsm