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

Question

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

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

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

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

Answer 1

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

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

Answer 2

Подумайте о классе 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'.Теперь представьте, что появляется еще одна тема с рекламными вставками «привет».Теперь стоимость другая!Когда вы печатаете третий символ, это пробел от «привет».Итак, вы печатаете:'это там'.

Answer 3

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

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

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

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

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

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

Answer 4

<Ол>

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

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

Answer 5

МВКК (Многоверсионное управление параллелизмом)

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

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

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

Answer 6

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

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