Функциональное программирование - неизменность

12

Я пытаюсь понять, как работать с неизменяемыми данными в FP (особенно в F #, но с другими FP тоже все в порядке) и сломать старую привычку полного состояния мышления (стиль ООП). Часть выбранного ответа на вопрос здесь повторила свой поиск любых написать окна вокруг проблем, которые решаются с помощью сохраняющего состояния представлений в объектно - ориентированном программировании с неизменными единицами в FP (Для Ex: очередь с производителями и потребителями). Любые мысли или ссылки приветствуются? Заранее спасибо.

Изменить : чтобы прояснить вопрос немного, как неизменные структуры (например, очередь) будут совместно использоваться несколькими потоками (например, производитель и потребитель) в FP

venkram
источник
Один из способов решения проблем параллелизма - каждый раз делать копии очереди (довольно дорого, но работает).
Работа
infoq.com/presentations/Functional-Data-Structures-in-Scala Вы можете найти это выступление проницательным.
Deadalnix

Ответы:

19

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

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

q := Queue.new();
while (true) {
    if (Queue.is_empty(q)) {
        Queue.add(q, producer());
    } else {
        consumer(Queue.take(q));
    }
}

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

q := Queue.empty;
while (true) {
    if (q = Queue.empty) {
        q := Queue.add(q, producer());
    } else {
        (tail, element) := Queue.take(q);
        consumer(element);
        q := tail;
    }
}

Поскольку очередь теперь неизменна, сам объект не изменяется. В этом псевдокоде qсама переменная; назначения q := Queue.add(…)и q := tailсделать его указывать на другой объект. Интерфейс функций очереди изменился: каждый из них должен возвращать новый объект очереди, полученный в результате операции.

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

main_loop(q, other_state) {
    if (q = Queue.empty) {
        let (new_state, element) = producer(other_state);
        main_loop(Queue.add(q, element), new_state);
    } else {
        let (tail, element) = Queue.take(q);
        let new_state = consumer(other_state, element);
        main_loop(tail, new_state);
    }
}
main_loop(Queue.empty, initial_state)

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

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

Продолжая пример, поскольку существует одна очередь, она управляется одним конкретным узлом. Потребители отправляют этому узлу сообщение для получения элемента. Производители отправляют этому узлу сообщение для добавления элемента.

main_loop(q) =
    consumer->consume(q->take()) || q->add(producer->produce());
    main_loop(q)

Единственный «промышленно развитый» язык, который получает право параллелизма3 - это Erlang . Изучение Эрланга - это определенно путь к просветлению о параллельном программировании.

Теперь все переходят на языки без побочных эффектов!

Term этот термин имеет несколько значений; здесь я думаю, что вы используете это для обозначения программирования без побочных эффектов, и это значение я тоже использую.
² Программирование с неявным состоянием является обязательным программированием ; ориентация объекта является полностью ортогональной проблемой.
³ Воспалительно, я знаю, но я это имею в виду. Потоки с общей памятью - это язык ассемблера параллельного программирования. Передача сообщений намного легче понять, и отсутствие побочных эффектов действительно сияет, как только вы вводите параллелизм.
И это от кого-то, кто не фанат Эрланга, но по другим причинам.

Жиль "ТАК - прекрати быть злым"
источник
2
+1 Гораздо более полный ответ, хотя я полагаю, можно было бы сказать, что Erlang не является чистым языком FP.
Рейн Хенрикс
1
@ Рейн Хенрикс: Действительно. Фактически, из всех существующих в настоящее время основных языков, Erlang - тот, который наиболее точно реализует объектно-ориентирование.
Йорг Миттаг
2
@ Йорг Согласен. Хотя, опять же, можно утверждать, что чистые FP и OO ортогональны.
Рейн Хенрикс
Таким образом, для реализации неизменяемой очереди в параллельном программном обеспечении сообщения должны отправляться и приниматься между узлами. Где хранятся ожидающие сообщения?
Mouviciel
@mouviciel Элементы очереди хранятся в очереди входящих сообщений узла. Это средство очереди сообщений является основной функцией распределенной инфраструктуры. Альтернативный дизайн инфраструктуры, который хорошо работает для локального параллелизма, но не для распределенных систем, заключается в блокировке отправителя до тех пор, пока получатель не будет готов. Я понимаю, что это не все объясняет, для того, чтобы полностью это объяснить, понадобится одна-две главы о параллельном программировании.
Жиль "ТАК - перестань быть злым"
4

Поведение с сохранением состояния в языке FP реализуется как преобразование из предыдущего состояния в новое состояние. Например, enqueue будет преобразованием из очереди и значения в новую очередь со значением в очереди. Удаление из очереди будет преобразованием из очереди в значение и в новую очередь со удаленным значением. Такие конструкции, как монады, были разработаны, чтобы абстрагировать это преобразование состояния (и другие результаты вычислений) полезными способами.

Рейн Хенрикс
источник
3
Если это новая очередь для каждой операции добавления / удаления, как две (или более) асинхронные операции (потоки) совместно используют очередь? Это образец для абстрагирования нового очереди?
Венкрам
Параллелизм - это совершенно другой вопрос. Я не могу дать достаточный ответ в комментарии.
Рейн Хенрикс
2
@ Рейн Хенрикс: «не могу дать достаточный ответ в комментарии». Обычно это означает, что вы должны обновить ответ для решения проблем, связанных с комментариями.
S.Lott
Параллельность также может быть монадической, см. Haskells Control.Concurrency.STM.
альтернатива
1
@ S.Lott в этом случае означает, что ОП должен задать новый вопрос. Параллелизм - это ОТ этого вопроса, который касается неизменных структур данных.
Рейн Хенрикс
2

... проблемы, которые решаются с помощью представлений с состоянием в ООП с неизменяемыми в FP (например: очередь с Producers & Consumer)

Ваш вопрос - это то, что называется «проблемой XY». В частности, концепция, которую вы цитируете (очередь с производителями и потребителями), на самом деле является решением, а не «проблемой», как вы описываете. Это создает трудности, потому что вы просите чисто функциональную реализацию чего-то нечистого по своей природе. Итак, мой ответ начинается с вопроса: какую проблему вы пытаетесь решить?

Существует несколько способов для нескольких производителей отправить свои результаты одному общему потребителю. Возможно, наиболее очевидное решение в F # - сделать потребителя агентом (ака MailboxProcessor) и предоставить производителям Postсвои результаты агенту-потребителю. При этом используется внутренняя очередь, и она не является чистой (отправка сообщений в F # является неконтролируемым побочным эффектом, примесью).

Однако вполне вероятно, что основная проблема - это нечто большее, чем шаблон рассеяния из параллельного программирования. Чтобы решить эту проблему, вы можете создать массив входных значений, а затем Array.Parallel.mapповерх них и собрать результаты с помощью последовательного интерфейса Array.reduce. В качестве альтернативы вы можете использовать функции из PSeqмодуля для параллельной обработки элементов последовательностей.

Я также должен подчеркнуть, что в государственном мышлении нет ничего плохого. Чистота имеет свои преимущества, но она, безусловно, не является панацеей, и вам следует осознать и ее недостатки. Действительно, именно поэтому F # не является чисто функциональным языком: поэтому вы можете использовать примеси, когда они предпочтительнее.

Джон Харроп
источник
1

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

Я настоятельно рекомендую вам прочитать отличную статью о состоянии и идентичности в Clojure , она объясняет детали гораздо лучше, чем я мог.

Адам Быртек
источник