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

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

Один ответ сделал ссылку на преимущество неизменных структур данных: каждый поток может иметь свою собственную копию. Теперь для меня это звучит скорее как система управления версиями (использовать аналогию), где вместо того, чтобы блокировать код, который кто-то проверил, чтобы он не мог быть изменен кем-либо еще, каждый может проверить свои собственные копии. Звучит хорошо. Однако в VCS у вас есть концепция "слияния" изменений, в случае, если два человека изменили один и тот же материал. Похоже, что эта проблема может возникнуть в многопоточном сценарии... так как происходит "слияние", когда важно, чтобы потоки отображали самые последние данные?
В этом ответе говорилось о случае, когда операции выполнялись в цикле на объекте, и как вы можете использовать новый объект каждый раз, обновления старого. Однако скажем, что bankAccount обновляется в сценарии без цикла: например, банковская система GUI. Оператор нажимает кнопку "Изменить процентную ставку", которая запускает событие, которое (например, в С#) делает что-то вроде bankAccount.InterestRate = newRateFromUser. Мне кажется, что я здесь плотный, но, надеюсь, мой пример имеет смысл: должен быть какой-то способ обновления объекта, не так ли? Несколько других вещей могут зависеть от новых данных.

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

Ответ 1

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

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

Ответ 2

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

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

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

Это выведет:

строка 1: there

строка 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 изменен, обе переменные указывают на один и тот же объект. Выход будет:

sb 1: hi there

sb 2: hi there

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

Ответ 3

Что касается № 2...

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

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

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

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

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

Ответ 4

Неизменяемые структуры данных не похожи на VCS. Подумайте о неподвижной структуре данных как файле только для чтения. Если его читать только, не имеет значения, кто читает какую часть файла в любой момент времени, все будут читать правильную информацию.
Этот ответ говорит о http://en.wikipedia.org/wiki/Monad_(functional_programming)

Ответ 5

MVCC (MultiVersion Concurrency Control)

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

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

Подробнее см. в этой статье: "Чисто функциональные структуры данных" Криса Окасаки.

Ответ 6

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

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