Уроки абстракции: чему FP может научить ООП

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

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

Одним из наиболее распространенных «лучших практик» в программировании является принцип DRY: не повторяйся. Для реализации этого принципа можно использовать множество методов: инкапсуляция, параметризация, инверсия управления и многое другое. Одним из этих методов является абстракция, и одно из основных различий между функциональным программированием (FP) и объектно-ориентированным программированием (ООП) заключается в способе применения абстракции. Обычной практикой в ООП является ограничение абстракции до строгого полезного минимума для рассматриваемой проблемы. В ООП преждевременное абстрагирование часто считается ошибкой, как и преждевременная оптимизация.

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

В этой статье мы сравним, как ООП и ФП будут обрабатывать абстракцию в конкретной простой задаче: вычислении суммы целых чисел от 1 до произвольного значения n. Проблема настолько проста для решения с помощью императивного программирования, что кажется, что в этом нет ничего интересного. Вот как это можно сделать в Java:

static int sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

Кажется, что нет более простого и эффективного способа сделать это. Однако как для программиста ООП, так и для программиста FP интересная часть проблемы еще впереди, но каждый из этих программистов, вероятно, пойдет совершенно другим путем. Мы также могли заметить (и продемонстрировать!), Что сумма первых n целых чисел равна (n * (n + 1) / 2). Как вы увидите, это было бы наоборот, в сторону наименее возможной абстракции.

Абстрагирование вычислений в объектно-ориентированном программировании

Программисты как FP, так и ООП сразу отметят одну возможную абстракцию, а именно операцию, которая применяется для построения результата. Здесь мы добавляем ценности для построения результата. Что, если бы нас попросили вернуть произведение вместо суммы?

В ООП есть два очевидных способа абстрагирования вычислений: использование шаблона Стратегия или инверсия управления (IoC).

Использование паттерна Стратегия

В Java для абстрагирования вычислений в форме, которую можно передать в другую часть кода, нужно создать объект, содержащий методы, выполняющие вычисление. (Если вам повезет и есть только один метод, лямбда-выражения могут упростить его, но подход остается тем же.) Чтобы это было абстракцией, мы должны превратить абстрактную часть в интерфейс, а конкретную часть - в реализацию интерфейса:

static int compute(int n, Computer computer) {
    int result = computer.identity();
    for (int i = 1; i <= n; i++) {
        result = computer.compute(result, i);
    }
    return result;
}

interface Computer {

    int compute(int a, int b);

    int identity();

}

static class Adder implements Computer {

    @Override
    public int compute(int a, int b) {
        return a + b;
    }

    @Override
    public int identity() {
        return 0;
    }

}

static class Multiplier implements Computer {

    @Override
    public int compute(int a, int b) {
        return a * b;
    }

    @Override
    public int identity() {
        return 1;
    }

}

public static void main(String... args) {
    System.out.println(compute(5, new Adder()));
    System.out.println(compute(5, new Multiplier()));
}

Здесь мы абстрагировали вычисления и теперь можем повторно использовать программу с другой стратегией вычислений, такой как умножение. Обратите внимание, что мы помещаем элемент identity, используемый в качестве начального значения для вычисления, в различные реализации Computer, поскольку он будет отличаться для разных типов вычислений (0 для сложения, 1 для умножения).

Откровенно говоря, это не кажется большим улучшением, и многие программисты не увидят выгоды в отделении вычислений от итерации. Кроме того, этот подход не принимает во внимание, что на самом деле у нас есть две вложенные возможные абстракции: сама операция (сложение или умножение) и концепция identity конкретное число константа, которое связано с операцией. Значение 0 - это identity для сложения, а 1 - для умножения. Другие операции имеют свое значение identity. Пустая строка - это identity для конкатенации строк, а пустой список - это identity для конкатенации списков.

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

Использование инверсии управления (IoC)

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

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

static abstract class Computer {

    public final int compute(int n) {
        int result = identity();
        for (int i = 1; i <= n; i++) {
            result = doCompute(result, i);
        }
        return result;
    }

    abstract int doCompute(int a, int b);

    abstract int identity();

}

static class Adder extends Computer {

    @Override
    public int doCompute(int a, int b) {
        return a + b;
    }

    @Override
    int identity() {
        return 0;
    }
}

static class Multiplier extends Computer {

    @Override
    public int doCompute(int a, int b) {
        return a * b;
    }

    @Override
    int identity() {
        return 1;
    }
}

public static void main(String... args) {
    Computer adder = new Adder();
    System.out.println(adder.compute(5));
    Computer multiplier = new Multiplier();
    System.out.println(multiplier.compute(5));
}

Этот подход, вероятно, является наиболее объектно-ориентированным и может показаться намного чище, чем шаблон стратегии, поскольку он, по-видимому, также абстрагирует итерацию в классе Computer. (Кстати, этому конкретному использованию IoC было дано имя: шаблонный метод) Но на самом деле мы не абстрагировали итерацию! Мы просто инкапсулировали всю программу в классе Computer. Давайте теперь посмотрим, как функциональный программист справится с этой проблемой.

Абстрагирование в функциональном программировании

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

Абстрагирование вычислений

В FP фактическое вычисление будет абстрагироваться очень похоже на то, как мы это делали в шаблоне Стратегия. Создаем интерфейс Computer:

@FunctionalInterface
interface Computer {

    int compute(int a, int b);

}

Но на этот раз Computer - это функциональный интерфейс, а это означает, что у него есть только один абстрактный метод. Вот почему его иногда называют интерфейсом SAM (Single Abstract Method). В Java это называется функциональным интерфейсом, потому что его можно использовать для представления функции.

Поскольку мы используем Java 8, интерфейс Computerне нужен, потому что его можно заменить на IntBinaryOperator:

static int compute(int n, int identity, IntBinaryOperator computer) {
    int result = identity;
    for (int i = 1; i <= n; i++) {
        result = computer.applyAsInt(result, i);
    }
    return result;
}

Если мы используем язык с лямбдами, как в случае Java 8, нам не нужно создавать классы, реализующие IntBinaryOperator:

public static void main(String... args) {
    System.out.println(compute(5, 0, (a, b) -> a + b));
    System.out.println(compute(5, 1, (a, b) -> a * b));
}

Абстрагирование создания коллекции

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

static int[] range(int n) {
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        result[i] = i + 1;
    }
    return result;
}

Абстрагирование итерации

Итерацию, применяющую вычисление, также можно абстрагировать в метод:

static int fold(int[] collection, 
                int identity, 
                IntBinaryOperator computer) {
    int result = identity;
    for(int i : collection) {
        result = computer.applyAsInt(result, i);
    }
    return result;
}

Если мы поместим эти абстракции в библиотеку, наша программа станет такой:

static int compute(int n, int identity, IntBinaryOperator computer) {
    return fold(range(n), identity, computer);
}

public static void main(String... args) {
    System.out.println(compute(5, 0, (a, b) -> a + b));
    System.out.println(compute(5, 1, (a, b) -> a * b));
}

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

• Метод range можно заменить на IntStream :: range, который принимает два параметра, начальное и конечное значение и создает IntStream вместо массива.

• Абстракцию fold можно заменить на reduce.

Полученная программа будет очень простой:

public static void main(String... args) {
    System.out.println(IntStream.rangeClosed(1, 5).reduce(0, (a, b) -> a + b));
    System.out.println(IntStream.rangeClosed(1, 5).reduce(1, (a, b) -> a * b));
}

Вам не кажется, что пример IoC был проще? (Просто шучу.)

Применение абстракции к более сложным задачам

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

Но имейте в виду, что мы еще не довели абстракцию до предела! Мы могли бы абстрагироваться от типа int. В конце концов, мы могли бы применить те же вычисления к другим типам, таким как double, BigDecimal, или даже String или List. Мы также могли бы использовать вычисление, дающее результат другого типа, чем элементы коллекции. Например, мы могли бы применить к списку символов операцию, состоящую в добавлении каждого символа в начальную строку (которая, кстати, может быть или не быть пустой).

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

Первоначальная проблема

Первоначальная задача состоит в том, чтобы вычислить список промежуточных результатов предыдущей задачи. Рассматривая сумму целых чисел от 1 до n, мы теперь хотим создать список промежуточных результатов этого вычисления. Например, если n = 5, мы хотим получить список 1, 3, 6, 10, 15.

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

1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15

Тривиальной реализацией программы вычисления треугольных чисел может быть:

private static List<Integer> triangular(int length) {
    List<Integer> result = new ArrayList<>();
    for(int i = 1; i <= length; i++) { // <1>
        result.add(result.size() == 0
                ? i
                : result.get(result.size() - 1) + i); // <2>
    }
    return result;
}

public static void main(String... args) {
    System.out.println(triangular(5));
}

Мы видим, что в <1> мы создаем список целых чисел от 1 до n включительно. В <2> мы используем result.get (result.size () - 1), чтобы получить последний элемент списка. В качестве первой абстракции мы должны либо переместить эту часть в метод, либо использовать коллекцию, предлагающую эту функциональность.

Абстрагирование обработки коллекций

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

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

private static <T> T last(List<T> list, T defaultValue) {
    return list.size() == 0 ? defaultValue : list.get(list.size() - 1);
}

Имея под рукой эту абстракцию, наша программа становится:

private static List<Integer> triangular(int length) {
    List<Integer> result = new ArrayList<>();
    for(int i = 1; i <= length; i++) {
        result.add(last(result, 0) + i);
    }
    return result;
}

Далее мы абстрагируемся от создания списка последовательных целых чисел. Хотя Java предлагает это (с помощью метода IntSream :: range), мы создадим свои собственные:

private static List<Integer> range(int start, int end) {
    List<Integer> result = new ArrayList<>();
    for(int i = start; i <= end; i++) {
        result.add(i);
    }
    return result;
  }

Мы также абстрагируем операцию fold, как мы это делали в предыдущем примере, но мы позаботимся о более общем случае, когда возвращаемое значение имеет другой тип, чем элементы списка. Напомним, что fold выполняет итерацию по каждому элементу, применение операции к текущему результату и данному элементу, начиная с некоторого начального значения. В предыдущем примере мы назвали это значение «identity». Однако мы не ограничиваемся значением identity. Мы могли выбрать любое значение для начала вычислений. В качестве дополнительной абстракции мы заставим метод работать с любой итеративной коллекцией, а не только со списками:

private static <T, U> U fold(
        Iterable<T> elements, U initial, BiFunction<U, T, U> f) {
    U result = initial;
    for (T t : elements) {
        result = f.apply(result, t);
    }
    return result;
}

Теперь у нас:

private static List<Integer> triangular(int length) {
    return fold(range(1, length), new ArrayList<>(), (a, b) -> {
        a.add(last(a, 0) + b);
        return a;
    });
}

В этой версии new ArrayList <> () является начальным значением, а вычисление состоит из добавления текущего значения к последнему результату и добавления нового результата в список.

Есть две дополнительные мелочи о списках, которые мы могли бы абстрагировать: создание пустого списка и добавление значения в список при возврате результирующего списка.

private static <T> List<T> emptyList() {
    return new ArrayList<>();
}

private static <T> List<T> append(List<T> list, T t) {
    list.add(t);
    return list;
}

Вот версия нашей программы, использующая эти абстракции:

private static List<Integer> triangular(int length) {
    return fold(
        range(1, length),
        emptyList(),
        (a, b) -> append(a, last(a, 0) + b));
}

Абстрагирование вычислений

Как и в предыдущем примере, мы можем абстрагироваться от вычислений, чтобы иметь возможность использовать не только сложение, но, среди прочего, умножение:

private static List<Integer> scan(
        int length, Integer z, BinaryOperator<Integer> op) {
    return fold(
        	range(1, length),
        	emptyList(),
        	(a, b) -> append(a, op.apply(last(a, z), b)));
}

private static List<Integer> triangular(int length) {
    return scan(length, 0, (a, b) -> a + b);
}

private static List<Integer> factorial(int length) {
    return scan(length, 1, (a, b) -> a * b);
}

Обратите внимание, что z используется по соглашению, что означает не 0, а тождественный или нейтральный элемент данной операции, по аналогии с 0, являющимся тождеством сложения.

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

Абстрагирование от типа

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

private static <T> List<T> scan(
        Iterable<T> elements, T z, BinaryOperator<T> op) {
    return fold(
        elements,
        emptyList(),
        (a, b) -> append(a, op.apply(last(a, z), b)));
}

Обратите внимание, что, поскольку тип является дженериком, scan больше не может создавать сами элементы через range, поэтому теперь необходимо:

private static List<Integer> triangular(int length) {
    return scan(range(1, length), 0, (a, b) -> a + b);
}

private static List<Integer> factorial(int length) {
    return scan(range(1, length), 1, (a, b) -> a * b);
}

Использование другого типа для возвращаемого значения

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

private static <T, U> List<U> scanLeft(
        Iterable<T> elements, U z, BiFunction<U, T, U> f) {
    return fold(
        elements,
        emptyList(),
        (a, b) -> append(a, f.apply(last(a, z), b)));
}

private static List<Integer> triangular(int length) {
    return scanLeft(range(1, length), 0, (a, b) -> a + b);
}

private static List<Integer> factorial(int length) {
    return scanLeft(range(1, length), 1, (a, b) -> a * b);
}

Здесь мы просматриваем слева направо (то есть начиная с первого элемента списка) и с помощью BiFunction<U, T, U> . Эта операция является сканированием влево, отсюда и название scanLeft. (Мы могли бы начать справа (хотя и не с Iterable) и использовать BiFunction<T, U, U> , создав другую абстракцию под названием scanRight.)

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

private static List<String> constructString(List<Character> characters) {
    return scanLeft(characters, "", (s, c) -> s + c);
}

System.out.println(constructString(Arrays.asList(
    'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd', '!')));

Эта программа выведет:

[H, He, Hel, Hell, Hello, Hello,, Hello, , Hello, W, Hello, Wo, Hello, Wor, Hello, Worl, Hello, World, Hello, World!]

Конечно, было бы удобно, если бы в интерфейс Collection была добавлена функция scanLeft. Поскольку это не так, мы просто добавим его в нашу функциональную библиотеку.

Остерегайтесь изменяемых списков

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

private static <T> List<List<T>> starts(List<T> list) {
    return scanLeft(list, emptyList(), (lst, elem) -> append(lst, elem));
}

System.out.println(starts(Arrays.asList(1, 2, 3, 4, 5)));

Программа должна вывести:

[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5]]

Но она выведет:

[[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]

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

Проблема заключается в методе append, который принимает в качестве аргумента List и возвращает List с добавленным элементом. Но список, полученный в качестве аргумента, изменяется и возвращается, что означает, что мутация видна вне метода. Чтобы получить правильный результат, мы должны переписать метод как:

private static <T> List<T> append(List<T> list, T t) {
    List<T> result = new ArrayList<>(list);
    result.add(t);
    return result;
}

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

Резюме

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

Итак, является ли преждевременная абстракция злом, как и преждевременная оптимизация? Действительно интересно отметить, что абстракция и оптимизация (для производительности) - две противоположные вещи. Оптимизация часто осуществляется только с учетом специфики решаемой проблемы. С другой стороны, абстракция заключается в поиске наиболее общего представления проблемы.

Учитывая исходную проблему (сумма целых чисел до n), использование формулы (n * (n + 1) / 2) действительно является оптимизацией, принимая во внимание конкретный характер операции, применяемой для сворачивания списка целых чисел, и специфический характер этих целых чисел. Хорошая сторона в том, что это самый быстрый способ вычислить результат. Плохая сторона заключается в том, что если вы измените операцию (например, чтобы вычислить произведение целых чисел до n), это совсем не поможет, и вам придется написать полностью новую программу. Хуже того, в отличие от абстрактного решения, это не будет работать для вычисления суммы любого другого списка целых чисел.

С абстрактным решением вам просто нужно изменить операцию и идентификатор, и вы можете применить его к любому списку целых чисел или даже к любому списку элементов любого типа. Фактически, вы обнаружили особый вид операции, которую можно применить к списку любого типа и функции. Эта операция называется сканированием. Вычисление суммы целых чисел от 1 до n - это сканирование этого списка целых чисел с добавлением. И любой список типа  List<T> можно сканировать с помощью функции типа BiFunction<U, T, U> , чтобы получить результат типа List<U> .

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

Одна из концепций, представленных в этой статье, заключается в том, что некоторые коллекции являются «складными». Если бы у нас было больше места (возможно, в другой статье), было бы интересно проанализировать, как эта концепция связана с Optional.orElse в Java 8. Тогда мы могли бы понять, что эти две концепции на самом деле представляют собой две разные композиции из двух более простых общих концепции. Кстати, мы также обнаружили важное различие между функциональной и нефункциональной парадигмой, известное как ссылочная прозрачность.