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

Question

Я недавно задал вопрос о функциональном программировании и получил (хорошо!) Ответы, которые вызвали больше вопросов (как иногда бывает с обучением). Вот пара примеров:

1. В одном ответе упоминается преимущество неизменных структур данных: каждый поток может иметь свою собственную копию. Теперь, для меня это звучит скорее как система контроля версий (по аналогии), где вместо блокировки кода, который кто-то извлек, чтобы никто не мог его изменить, каждый может проверить свои копии. Звучит хорошо. Тем не менее, в VCS у вас есть концепция «слияния» изменений, в случае, если два человека изменили один и тот же материал. Кажется, что эта проблема, безусловно, может возникнуть в многопоточном сценарии ... так как же происходит слияние, когда важно, чтобы потоки видели самые последние данные?

2. В этом ответе говорилось о случае, когда операции выполнялись в цикле над объектом, и о том, как вы можете использовать новый объект каждый раз вместо обновления старого. Однако, скажем, bankAccount обновляется в нецикличном сценарии - например, в банковской системе с графическим интерфейсом. Оператор нажимает кнопку «Изменить процентную ставку», которая запускает событие, которое будет (в C # например) делать что-то вроде bankAccount.InterestRate = newRateFromUser. Я чувствую, что я здесь плотный, но, надеюсь, мой пример имеет смысл: должен быть какой-то способ, которым объект обновляется, верно? Несколько новых вещей могут зависеть от новых данных.

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

Answer 1

Подумайте о классе String в .Net (который является неизменным объектом). Если вы вызываете метод для строки, вы получаете новую копию:

String s1 = "there";
String s2 = s1.Insert(0, "hello ");

Console.Writeline("string 1: " + s1);
Console.Writeline("string 2: " + s2);

Будет выведено:

строка 1: там

строка 2: привет там

Сравните это поведение со StringBuilder, который имеет в основном ту же сигнатуру метода:

StringBuilder sb  = new StringBuilder("there");
StringBuilder sb2 = sb.Insert(0, "hi ");

Console.WriteLine("sb 1: " + sb.ToString());
Console.WriteLine("sb 2: " + sb2.ToString());

Поскольку StringBuilder является изменяемым, обе переменные указывают на один и тот же объект. Выход будет:

сб 1: привет там

сб 2: привет там

Итак, вы абсолютно не можете изменить строку после того, как создали ее. s1 всегда будет «там» до конца времени (или до тех пор, пока его мусор не будет собран). Это важно в потоке, потому что вы всегда можете пройтись по каждому символу и напечатать его значение, зная, что он всегда будет печатать «там». Если вы начали печатать StringBuilder после того, как он был создан, вы можете напечатать первые два символа там и получить 'th'. А теперь представьте, что другая нить идет вместе со вставками объявлений "привет". Значение теперь другое! Когда вы печатаете третий символ, это пробел от «привет». Таким образом, вы печатаете: 'th там'.

Answer 2

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

Часть 2. Чистые функциональные языки без сохранения состояния не решают эту проблему. Даже с чистой программой на Haskell может быть связано состояние. Разница в том, что код с состоянием имеет другой тип возврата. Функция, которая манипулирует состоянием, выражается в виде последовательности операций, которые работают с объектом, представляющим это состояние. В абсурдном примере рассмотрим файловую систему компьютера. Каждый раз, когда программа изменяет содержимое файла (даже одним байтом), она создает новую «версию» всей файловой системы. И, соответственно, новая версия всей вселенной. Но давайте сосредоточимся на файловой системе сейчас. Любая другая часть программы, которая проверяет файловую систему, может теперь быть затронута этим измененным байтом. Итак, Хаскелл говорит, что функции, работающие в файловой системе, должны эффективно передавать объект, представляющий версию файловой системы. Тогда, поскольку с этим было бы утомительно обращаться вручную, оно выворачивает требование наизнанку и говорит, что если функция хочет иметь возможность ввода-вывода, она должна вернуть своего рода контейнерный объект. Внутри контейнера находится значение, которое функция хочет вернуть. Но контейнер служит доказательством того, что функция также имеет побочные эффекты или может видеть побочные эффекты. Это означает, что система типов Haskell способна различать функции с побочными эффектами и «чистые» функции. Таким образом, он помогает хранить и управлять состоянием кода, фактически не устраняя его.

Answer 3

Относительно # 2 ...

Некоторые другие вещи могут зависеть от новые данные.

Это то, что пуристы называют "эффектом". Понятие множественных ссылок на объекты на один и тот же изменяемый объект - это сущность изменчивого состояния и суть проблемы. В ООП у вас может быть объект «a» типа BankAccount, и если вы читаете a.Balance или еще много чего в разное раз , вы можете увидеть разные значения. Напротив, в чистом FP, если «a» имеет тип BankAccount, то он неизменный и имеет одно и то же значение независимо от времени.

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

В результате, единственный возможный способ вызвать «a.Balance» или что-то в этом роде - это использовать код, который благодаря статическим типам гарантирует, что некоторая «мировая история, которая нас дошла до сих пор», была правильно подключена к точка вызова, и какая бы мировая история ни была входной, влияет на то, какой результат мы получим от a.Balance.

Чтение о State Monad может быть полезно, чтобы получить представление о том, как вы просто моделируете «разделяемое изменяемое состояние».

Answer 4

MVCC ( MultiVersion Concurrency Control )

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

Короче говоря : вместо передачи данных по ссылке непосредственно клиентам, вы добавляете еще один уровень по косвенности и передаете ссылку на ссылку на данные. ( Ну, на самом деле вы хотели бы иметь по крайней мере еще один уровень косвенности. Но давайте предположим, что структура данных очень проста, как «массив». )
Поскольку данные являются неизменяемыми, каждый раз, когда данные должны быть изменены, вы создаете копию измененной части (, в случае массива вы должны создать другой массив! ), плюс вы создаете другую ссылку на все " измененные данные.
Таким образом, для всех клиентов, которые использовали первую версию массива, они используют ссылку на первую версию. Каждый клиент, пытающийся получить доступ ко 2-й версии, использует вторую ссылку.
Структура данных «массив» не очень интересна для этого метода, потому что вы не можете разделить данные и вынуждены копировать все. Но для более сложных структур данных, таких как деревья, некоторые части структуры данных могут быть «общими», поэтому вы не обязаны каждый раз копировать все.

Для получения дополнительной информации, пожалуйста, взгляните на этот документ: "Чисто функциональные структуры данных" , Крис Окасаки.

Answer 5

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

2. Этот ответ говорит о http://en.wikipedia.org/wiki/Monad_(functional_programming)

Answer 6

«Неизменяемый» означает именно это: оно не меняется.

Функциональные программы выполняют обновления, передавая новые вещи. Существующее значение никогда не меняется: вы просто создаете новое значение и передаете его вместо этого. Очень часто новое значение делит состояние со старым; Хорошими примерами этой техники являются списки, состоящие из клеток cons, и zipper .