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

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

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

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

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

Оо, я хочу увидеть язык программирования, где данные хранятся как VCS, и вы объединяете изменения, а не просто обновляете их. Может быть в стиле фанк.
jmucchiello 11.12.2008 23:30:07
6 ОТВЕТОВ
РЕШЕНИЕ

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

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

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

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

3
11.12.2008 21:54:53
Но скажем, данные обновляются по параллельному сценарию; например, файл только для чтения может быть перезаписан новым файлом только для чтения. Тогда у вас все еще есть проблема с кем-то, возможно, читающим старый файл? (Это то, что я не получаю)
J Cooper 11.12.2008 22:00:10
Это часть концепции, если вы не можете обновить ее, ничто не устареет. Неизменный означает, что вы не можете изменить это.
Pyrolistical 11.12.2008 22:09:28
Но что, если оно нуждается в обновлении? :( Очевидно, я слишком глуп, чтобы рассуждать об этом, мне нужно будет найти какой-то код, который происходит в действии. Спасибо за ответ
J Cooper 11.12.2008 22:35:08

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

7
11.12.2008 23:14:19
То, что вы говорите, верно, но я не вижу актуальности для вопросов ОП.
aefxx 8.01.2016 13:53:26

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

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

1
11.12.2008 23:21:27

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

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

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

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

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

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

4
12.12.2008 00:45:31

MVCC ( MultiVersion Concurrency Control )

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

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

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

3
19.02.2010 13:02:46