Магистр ДонНТУ Чуприн Владислав Игоревич

Чуприн Владислав Игоревич

Факультет компьютерных наук и технологий

Кафедра прикладной математики и информатики

Специальность «Инженерия программного обеспечения»

Повышение эффективности реализации модели распределённых вычислений MapReduce в рамках программного каркаса Hadoop

Научный руководитель: д.т.н., доц. Дмитриева Ольга Анатольевна

Основные концепции функционального программирования

Мотивация

К моменту написания статьи я не так давно заинтересовался одним из многочисленных ныне языков под JVM — Scala [1]. Причин тому много, основная — всё нарастающее со временем чувство неудобства при работе с Cи-подобными языками. Так как, наибольшее время на момент написания я проработал с Java, буду сравнивать с ней. Язык я начал учить еще 4 года назад на курсах от Sun Microsystems. Опыта разработки enterprise приложений к моменту написания этой статьи у меня чуть больше года.

Ну что сказать, по началу мне Java нравилась практически во всем. Особенно после 1,5 лет программирования на PHP. Но, к моменту изучения Scala ощущение было неоднозначное. Так как раздел о функциональном программировании, скажу только о плохих сторонах. Ну невозможно получать удовольствие от написания однотипного кода. Например, взять колбеки - 2 класса для того чтобы выполнить простой метод по событию - явно чересчур. А как насчет итераторов, разве это не лишнее - каждый раз создавать циклы для обхода, даже с помощью конструкции foreach при наличии декларативного синтаксиса с передачей обработчика в качестве параметра? По видимому, надоедало это не только мне, иначе бы JDK 8 не вышла такой, какой она вышла.

В общем, именно так я пришел к мысли что неплохо было бы для общего развития запастись подходами из области функционального программирования. То, что удалось уже выучить приведено ниже. Стоит отметить, что примеры будут на Java с целью акцентировать внимание непосредственно на концепциях, а не на языке программирования, и донесения их более широкому кругу читателей.

Введение

Первым языком, который использовал парадигмы функционального программирования был Lisp [2], разработанный в конце 1950-х годов и являющийся вторым старейшим языком программирования высокого уровня после Fortran. ML [3] семейство языков программирования появились в 1970, в том числе Caml, OCaml (гибрид объектно-функциональный язык), и F# от Microsoft. Возможно, самый известный функциональный язык, который является наиболее близким к понятию функциональной «чистоты» является Haskell [4], который был создан в начале 1990-х. Другие недавние функциональные языки - Clojure [5] и Scala. Оба разработаны для JVM платформы, в настоящее время портированы на .NET окружение. Сегодня, также, многие другие языки используют концепции функционального программирования.

Во всех ли языках программирования существует понятие функции? Если да, то почему не все языки программирования считаются функциональными? Функциональные языки разделяют несколько основных концепций.

Отсутствие изменяемого состояния

Первый принцип - использование неизменных значений. Вы можете вспомнить известное со школы уравнение Пифагора, которое описывает соотношение сторон в треугольнике:

х2 + у2 = z2

Если заданы значения для переменных х и у, скажем х = 3 и у = 4, можно вычислить значение для z (5 в данном случае). Ключевая идея здесь в том, что значения никогда не изменяются. Было бы быть сумасшествием, написать 3++, но вы могли бы повторно решить уравнение назначив сначала новые значения для тех же переменных.

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

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

Второе преимущество неизменяемого состояния относится к корректности программ в других отношениях. Код с изменяемым состоянием сложнее к пониманию и тестированию, особенно если модификации не локализованы в одном месте.

Рассмотрим следующий пример, в котором изменяемый список используется для хранения заказов клиента:

public class Customer {
    // No setter method
    private final List  orders;

    public List  getOrders() {
        return orders;
    }

    public Customer(...) {...}
}

Это оправданно, что клиенты Customer захотят просмотреть список Orders. К сожалению, в результате изменений списка через метод доступа getOrders, мы потеряли контроль над ним! Клиент может изменить список без нашего ведома. Мы не предоставляем мутатор для заказов и класс запрещен к наследованию, однако эти меры защиты не срабатывают. Сам список еще может быть изменен.

Мы могли бы обойти эту проблему, имея getOrders, который возвращает копию списка, или добавив специальные методы доступа в Customer, которые обеспечат контролируемый доступ к заказам. Тем не менее, копирование списка стоит дорого, особенно для больших списков. Добавление нерегламентированных методов доступа увеличивает сложность объекта, время тестирования и усилия, необходимые другим программистам, чтобы понять и использовать класс.

Однако, если список заказов неизменен и элементы списка являются неизменными, эти опасения не актуальны. Клиенты могут вызвать методы чтения но они не могут изменить заказы, поэтому мы сохраняем контроль над состоянием объекта.

Что произойдет, когда список заказов требуется изменить, но он стал огромным? Должны ли мы сделать его изменяемым, чтобы избежать накладных расходов на создание копии большого объекта? К счастью, у нас есть эффективный способ для копирования больших структур данных; мы повторно используем части, которые не изменяются! Когда мы добавляем новый заказ в наш список заказов, мы можем повторно использовать остальную часть списка.

Некоторая изменчивость является неизбежной. Все программы должны выполнять ввод/вывод данных. В противном случае, они не смогут сделать ничего, кроме как разогреть процессор. Однако функциональное программирование побуждает нас мыслить стратегически о том, когда и где изменчивость необходима. Если мы инкапсулируем изменения в четко определенных областях и будем держать остальной код без них, мы повысим надежность и модульность нашего кода.

Функции первого класса

В Java мы привыкли к передаче объектов и примитивных значений методам, возвращению их из методов, и присвоения их переменным. Это означает, что объекты и примитивы значения первого класса. Обратите внимание, что сами классы не являются значениями первого класса, хотя рефлексия предоставляет информацию о классах.

Функции не значения первого класса в Java. Поясним разницу между методами и функциями.

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

В объктно-ориентированных языках вы не можете передать метод в качестве аргумента другому методу, возвращать метод из метода, или присвоить метод в качестве значения переменной.

Однако большинство анонимных вложенных классов являются эффективными "обертками" для функций. Например, многие методы в Java принимают экземпляр реализующий интерфейс, который содержит один метод. Вот типичный пример, указание ActionListener для AWT / Swing приложений:

package functions;

import java.awt.*;
import java.awt.event.*;

class HelloButtonApp2 {

    private final Button button = new Button();

    public HelloButtonApp2() {
        button.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                System.out.println("Hello There: event received: " + e);
            }
        });
    }
}

Если мы хотим создать кнопку, чтобы сделать что-то, мы должны указать объект ActionListener, который имеет один метод: actionPerformed. Мы использовали анонимный вложенный класс для реализации интерфейса и метод.

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

В мире Java API, должны быть созданы сотни разовых, специальных интерфейсов, таких как ActionListener. Это значительно увеличивает когнитивную нагрузку на разработчика, когда требуется знать все из них. Вы проводите много времени за чтением Javadocs или обращаетесь к IDE чтобы она напомнила вам. Нам говорили, что абстракция это хорошо, так? Ну, давайте введем абстракции для всех этих "объектов-функций"!

Во-первых, нужен интерфейс, который определяет "функцию", которая принимает один аргумент типа параметра А и возвращает void: 

package functions;

public interface FunctionlVoid  {
    void apply(A a);

}

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

Теперь давайте представим, что есть "функциональная" версия Abstract Window Toolkit (AWT), java.fawt.Component, с методом addActionListener, который принимает объект FunctionVoid вместо ActionListener:

package functions;

import java.fawt.*;
import java.fawt.event.*;

class FunctionalHelloButtonApp {
    private final Button button = new Button();

    public FunctionalHelloButtonApp() {
        button.addActionListener(new Function1Void () { // 1 public void apply(ActionEvent e) {    // 2
            System.out.println("Hello There: event received: "+e);
        });
    }
}

Вы можете возразить, что наличие пользовательского типа в качестве аргумента addActionListener не позволяет передать неподходящий объект. Вам также могут утверждать, что отдельное имя интерфейса и пользовательского метода упрощает изучение API.

Давая абстракции специальные названия не представляется возможным предотвратить неправильную реализацию пользователем. Параметр типа для FunctionVoid<ActionEvent> по прежнему останется в контракте addActionListener. Это еще немного документации для пользователя.

Лямбда-выражения

Разве не было бы замечательно, если бы мы могли просто написать анонимную функцию просто со списком аргументов и телом?

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

public FunctionalHelloButtonApp() { 
    button.addActionListener(#{ ActionEvent e -> System.out.println("Hello There: event received: "+e) });
}

Выражение # {...} является синтаксисом лямбда-выражений. Слева от "стрелки" (->) список аргументов и тело функции справа. Обратите внимание, сколько спагетти-кода этот синтаксис удаляет!

Термин лямбда - это еще одно название для анонимной функции.

Замыкания

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

Функций высших порядков

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

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

Функции свободные от побочных эффектов

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

В математике, функции никогда не имеют побочных эффектов, то есть они свободны от побочных эффектов. Например, независимо от того, сколько раз запустить sin(х), всегда его результат будет одинаковым. Никакое внешнее состояние не будет изменено. Обратите внимание, что реальная реализация может кэшировать ранее вычисленные значения, для повышения эффективности, что потребует изменения состояния кэша.

Возможность заменить вызов функции для определенного набора параметров его возвращаемым значением называется ссылочной прозрачностью. Это приводит к фундаментальному следствию для функций без побочных эффектов - функция и соответствующие возвращаемые значения являются синонимами. Вы можете заменить результат вызова любой такой функции значением. С другой стороны, можно представить любое значение с вызовом функции!

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

Рекурсия

Напомним, что функциональное программирование в чистом виде не позволяет изменять значения. Это означает, что мы не можем использовать изменяемые счетчики цикла для перебора коллекции!

Однако, существуют другие подходы итерации в рамках операций над функциональными коллекциями.

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

Рассмотрим следующий пример, когда модульный тест определяет простой тип дерева, со значением в каждом узле, и левым и правым поддеревьями. Тип Tree определяет рекурсивный метод toString, который обходит дерево и сохраняет строку из каждого узла. После определения, модульный тест создает экземпляр дерева и проверяет ожидаемую работу ToString:

package functions;

import static org.junit.Assert.*;

import org.junit.Test;

public class RecursionTest {

    static class Tree {
        // public fields for simplicity
        public final Tree left; // left subtree
        public final Tree right; // right subtree
        public final int value; // value at this node

        public Tree(Tree left, int value, Tree right) {
            this.left = left;
            this.value = value;
            this.right = right;
        }

        public final String toString() {
            String leftStr = left == null ? "n" : left.toString();
            String rightStr = right == null ? "n" : right.toString();
            return "(" + leftStr + "-" + value + "-" + rightStr + ")";
        }
    }

    @Test
    public void walkATree() {
        Tree root = new Tree(new Tree(
            new Tree(null, 3, null), 2, new Tree(new Tree(null, 5, null), 4, null)),
            1,
            new Tree(new Tree(null, 7, null), 6, new Tree(null, 8, null))
        );
        String expected = "(((n-3-n)-2-((n-5-n)-4-n))-i-((n-7-n)-6-(n-8-n)))";
        assertEquals(expected, root.toString());
    }
}

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

Выводы

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

Все же хотелось бы предаться снобизму, характерному для сообщества Scala программистов. Использование функционального языка со всем его многообразием концепций оправданно только в командах с высоким уровнем подготовки. К сожалению, в команде с тимлидом двумя джуниорами и тремя индусами воспользоваться функциональным языком вряд ли выйдет. В остальных случаях все зависит от потребностей конкретного приложения. В случае, когда требуется высокий уровень распределенности, отсутствие разделяемого состояния покажется как нельзя кстати. Именно в связи с этим функциональный подход хорошо прижился в распределенном каркасе Hadoop с его функциями Map и Reduce, которые, к слову, появились еще в LISP и есть в подавляющем большинстве функциональных языков программирования.

Литература

  1. Scala (programming language) [Электронный ресурс]. – Режим доступа: http://en.wikipedia.org/wiki/Scala_(programming_language)
  2. Lisp (programming language) [Электронный ресурс]. – Режим доступа: http://en.wikipedia.org/wiki/Lisp_(programming_language)
  3. ML (programming language) [Электронный ресурс]. – Режим доступа: http://en.wikipedia.org/wiki/ML_(programming_language)
  4. Haskell (programming language) [Электронный ресурс]. – Режим доступа: http://en.wikipedia.org/wiki/Haskell_(programming_language)
  5. Clojure [Электронный ресурс]. – Режим доступа: http://en.wikipedia.org/wiki/Clojure_(programming_language)

Работы магистров предыдущих лет

  1. Функциональное программирование [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/2011/fknt/pranskevichus/ind/index.htm
  2. Парадигмы программирования [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/2002/fvti/drugobitskiy/library/paradigm.html
  3. Конвертор императивных программ в функциональный эквивалент [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/2011/fimm/pharaon/library/article4.htm
  4. Параллельное программирование в функциональном стиле [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/2006/fvti/davlethanov/library/files/art1.htm

Полезные источники

  1. "Функциональное программирование" (Харрисон/Филд)
  2. "Введение в функциональное программирование" (Харрисон)
  3. "Программирование на Clojure" (Чаз Эмерик, Брайен Карпер, Кристоф Гранд)
  4. "Функциональное программирование на языке Haskell" (Роман Душкин)
  5. "Программирование в Erlang" (Франческо Чезарини, Симон Томпсон)
  6. "Функциональное программирование. SCALA для нетерпеливых" (Кей Хорстман)