У меня возникают трудности с поиском ресурсов для написания программ в функциональном стиле. Самая сложная тема, которую я мог найти в Интернете, - это использование структурной типизации для сокращения иерархии классов; большинство просто имеют дело с тем, как использовать карту / сложение / уменьшение / и т.д. для замены императивных циклов.

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

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

Введение к Радости Clojure говорит следующее:

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

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

Программирование в Scala 2nd Edition с. 10 имеет следующее определение:

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

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

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

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

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

Императив:

for (Passenger p : Bus.getPassengers()) {
    p.debit(fare);
}

Функциональный (используя анонимную функцию или «лямбду» в Scala):

myBus = myBus.forEachPassenger(p:Passenger -> { p.debit(fare) })

Более сладкая версия Scala:

myBus = myBus.forEachPassenger(_.debit(fare))

Не первоклассные функции

Если ваш язык не поддерживает первоклассные функции, это может стать очень уродливым. В Java 7 или более ранней версии вы должны предоставить интерфейс «Функциональный объект», например:

// Java 8 has java.util.function.Consumer, but in earlier
// versions you have to roll your own:
public interface Consumer<T> {
    public void accept(T t);
}

Затем класс Bus предоставляет внутренний итератор:

public void forEachPassenger(Consumer<Passenger> c) {
    for (Passenger p : passengers) {
        c.accept(p);
    }
}

Наконец, вы передаете анонимный объект функции в шину:

// Java 8 has syntactic sugar to make this look more like
// the Scala solution, but earlier versions require manually
// instantiating a "Function Object," in this case, a
// Consumer:
Bus.forEachPassenger(new Consumer<Passenger>() {
    @Override
    public void accept(final Passenger p) {
        p.debit(fare);
    }
}

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

public static class MutableIntWrapper {
    private int i;
    private MutableIntWrapper(int in) { i = in; }
    public static MutableIntWrapper ofZero() {
        return new MutableIntWrapper(0);
    }
    public int value() { return i; }
    public void increment() { i++; }
}

final MutableIntWrapper count = MutableIntWrapper.ofZero();
Bus.forEachPassenger(new Consumer<Passenger>() {
    @Override
    public void accept(final Passenger p) {
        p.debit(fare);
        count.increment();
    }
}

System.out.println(count.value());

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

Это уродство было исправлено в Java 8, но обработка проверенных исключений внутри функции первого класса все еще очень уродлива, и Java все еще несет в себе допущение изменчивости во всех своих коллекциях. Что подводит нас к другим целям, часто связанным с FP:

неизменность

Пункт 13 Джоша Блоха «Предпочитают неизменность». Несмотря на общепринятые разговоры об обратном, ООП можно делать с неизменяемыми объектами, и это делает его намного лучше. Например, String в Java является неизменным. StringBuffer, OTOH должен быть изменяемым, чтобы построить неизменяемую строку. Некоторые задачи, такие как работа с буферами, по своей природе требуют изменчивости.

чистота

Каждая функция должна быть, по крайней мере, запоминающейся - если вы даете ей одни и те же входные параметры (и у нее не должно быть никаких входных данных, кроме ее фактических аргументов), она должна выдавать один и тот же вывод каждый раз, не вызывая «побочных эффектов», таких как изменение глобального состояния, выполнение I / O, или бросать исключения.

Говорят, что в функциональном программировании «для выполнения работы обычно требуется какое-то зло». Чистота 100%, как правило, не является целью. Минимизация побочных эффектов есть.

Вывод

Действительно, из всех представленных выше идей неизменность стала самой большой победой с точки зрения практических приложений для упрощения моего кода - будь то ООП или ФП. Передача функций итераторам - вторая по величине победа. Документация по Java 8 Lambdas имеет лучшее объяснение почему. Рекурсия отлично подходит для обработки деревьев. Лень позволяет работать с бесконечными коллекциями.

Если вам нравится JVM, я рекомендую вам взглянуть на Scala и Clojure. Оба являются проницательными интерпретациями функционального программирования. Scala является типобезопасным с несколько C-подобным синтаксисом, хотя в действительности он имеет столько же общего с Haskell синтаксиса, что и с C. Clojure не является типобезопасным и представляет собой Lisp. Недавно я опубликовал сравнение Java, Scala и Clojure в отношении одной конкретной проблемы рефакторинга. Сравнение Логана Кэмпбелла с использованием Game of Life также включает в себя Haskell и типизированный Clojure.

PS

Джимми Хоффа отметил, что мой класс Bus изменчив. Я думаю, что вместо того, чтобы исправить оригинал, это продемонстрирует именно тот вид рефакторинга, о котором идет речь в этом вопросе. Это можно исправить, сделав каждый метод на Bus фабрикой для производства нового Bus, а каждый метод на Passenger - фабрикой для производства нового Passenger. Таким образом, я добавил тип возврата ко всему, что означает, что я скопирую java.util.function.Function в Java 8 вместо интерфейса Consumer:

public interface Function<T,R> {
    public R apply(T t);
    // Note: I'm leaving out Java 8's compose() method here for simplicity
}

Затем на автобусе:

public Bus mapPassengers(Function<Passenger,Passenger> c) {
    // I have to use a mutable collection internally because Java
    // does not have immutable collections that return modified copies
    // of themselves the way the Clojure and Scala collections do.
    List<Passenger> newPassengers = new ArrayList(passengers.size());
    for (Passenger p : passengers) {
        newPassengers.add(c.apply(p));
    }
    return Bus.of(driver, Collections.unmodifiableList(passengers));
}

Наконец, объект анонимной функции возвращает измененное состояние (новая шина с новыми пассажирами). Это предполагает, что p.debit () теперь возвращает нового неизменного Пассажира с меньшим количеством денег, чем оригинал:

Bus b = b.mapPassengers(new Function<Passenger,Passenger>() {
    @Override
    public Passenger apply(final Passenger p) {
        return p.debit(fare);
    }
}

Надеюсь, теперь вы можете принять собственное решение о том, насколько функциональным вы хотите создать свой императивный язык, и решить, будет ли лучше переделать ваш проект с использованием функционального языка. В Scala или Clojure коллекции и другие API-интерфейсы разработаны для упрощения функционального программирования. Оба имеют очень хорошее взаимодействие с Java, поэтому вы можете смешивать и сочетать языки. Фактически, для взаимодействия Java, Scala компилирует свои функции первого класса в анонимные классы, которые почти совместимы с функциональными интерфейсами Java 8. Вы можете прочитать о деталях в Scala в глубине секты. 1.3.2 .

У меня есть личный опыт "выполнения" этого. В конце концов, я не придумал что-то, что было бы чисто функциональным, но я придумал то, чем я доволен. Вот как я это сделал:

• Конвертировать все внешние состояния в параметр функции. Например: если метод объекта изменяется x, сделайте так, чтобы метод передавался xвместо вызова this.x.
• Удалить поведение из объектов.
  1. Сделать данные объекта общедоступными
  2. Преобразуйте все методы в функции, которые вызывает объект.
  3. Имейте клиентский код, который вызывает объект, вызывает новую функцию, передавая данные объекта. EG: конвертировать x.methodThatModifiesTheFooVar()вfooFn(x.foo)
  4. Удалить оригинальный метод из объекта
• Заменить как много итерационных циклов , как вы можете с функций высшего порядка нравится map, reduce, filterи т.д.

Я не мог избавиться от изменчивого состояния. Это было просто слишком нелогично в моем языке (JavaScript). Но, передав все и / или возвращенные состояния, можно проверить каждую функцию. Это отличается от ООП, где настройка состояния может занять слишком много времени или разделение зависимостей часто требует сначала изменения производственного кода.

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

редактировать

Как вы можете видеть здесь , невозможно создать действительно неизменный объект в JavaScript. Если вы прилежны и контролируете, кто вызывает ваш код, вы можете сделать это, всегда создавая новый объект, а не изменяя текущий. Это не стоило мне усилий.

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

Я не думаю, что действительно возможно полностью реорганизовать программу - вам придется изменить дизайн и переопределить правильную парадигму.

Я видел рефакторинг кода, определенный как «дисциплинированный метод реструктуризации существующего тела кода, изменения его внутренней структуры без изменения внешнего поведения».

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

Я думаю, что эта серия статей именно то, что вы хотите:

Чисто функциональные игры

http://prog21.dadgum.com/23.html Часть 1

http://prog21.dadgum.com/24.html Часть 2

http://prog21.dadgum.com/25.html Часть 3

http://prog21.dadgum.com/26.html Часть 4

http://prog21.dadgum.com/37.html Последующие действия

Резюме:

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

Конечно, при написании реальной программы вы будете смешивать и сочетать несколько стилей программирования, используя каждый из них там, где это больше всего помогает. Тем не менее, это хороший учебный опыт, чтобы попытаться написать программу наиболее функциональным / неизменным способом, а также написать ее наиболее спагетти, используя только глобальные переменные :-) (сделайте это как эксперимент, а не в производстве, пожалуйста)

Возможно, вам придется вывернуть весь ваш код наизнанку, так как ООП и ФП имеют два противоположных подхода к организации кода.

ООП организует код вокруг типов (классов): разные классы могут реализовывать одну и ту же операцию (метод с одинаковой сигнатурой). В результате ООП более подходит, когда набор операций не сильно меняется, а новые типы можно добавлять очень часто. Например, рассмотрим библиотеку GUI , в котором каждый виджет имеет фиксированный набор методов ( hide(), show(), paint(), move(), и так далее) , но новые виджеты могут быть добавлены как библиотека расширена. В ООП легко добавить новый тип (для данного интерфейса): вам нужно только добавить новый класс и реализовать все его методы (локальное изменение кода). С другой стороны, добавление новой операции (метода) в интерфейс может потребовать изменения всех классов, реализующих этот интерфейс (даже если наследование может уменьшить объем работы).

FP организует код вокруг операций (функций): каждая функция реализует некоторые операции, которые могут по-разному обрабатывать различные типы. Обычно это достигается путем отправки типа с помощью сопоставления с образцом или каким-либо другим механизмом. Как следствие, FP более подходит, когда набор типов стабилен и новые операции добавляются чаще. Возьмите, например, фиксированный набор форматов изображений (GIF, JPEG и т. Д.) И некоторые алгоритмы, которые вы хотите реализовать. Каждый алгоритм может быть реализован функцией, которая ведет себя по-разному в зависимости от типа изображения. Добавить новый алгоритм легко, потому что вам нужно только реализовать новую функцию (локальное изменение кода). Добавление нового формата (типа) требует изменения всех функций, которые вы реализовали до сих пор для его поддержки (нелокальное изменение).

Итог: ООП и ФП принципиально отличаются в том, как они организуют код, и изменение дизайна ООП в дизайн ФП будет включать изменение всего вашего кода, чтобы отразить это. Это может быть интересное упражнение, хотя. См. Также эти лекционные заметки к книге SICP, на которые ссылается mikemay, в частности слайды с 13.1.5 по 13.1.10.