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

21

Сторонники FP утверждают, что параллелизм прост, потому что их парадигма избегает изменчивого состояния. Я не понимаю

Представьте, что мы создаем многопользовательское сканирование подземелий (roguelike), используя FP, где мы подчеркиваем чистые функции и неизменные структуры данных. Мы создаем подземелья, состоящие из комнат, коридоров, героев, монстров и добычи. Наш мир фактически является графом объектов и их взаимосвязей. Поскольку вещи меняются, наше представление о мире изменяется, чтобы отразить эти изменения. Наш герой убивает крысу, подбирает короткий меч и т. Д.

Для меня мир (текущая реальность) несет в себе эту идею состояния, и мне не хватает того, как FP преодолевает это. Когда наш герой начинает действовать, функции изменяют состояние мира. Похоже, что каждое решение (ИИ или человек) должно основываться на состоянии мира, как оно есть в настоящем. Где бы мы допустили параллелизм? У нас не может быть нескольких процессов, одновременно изменяющих состояние мира, чтобы один процесс не основывал свои результаты на каком-то просроченном состоянии. Мне кажется, что все управление должно происходить в одном цикле управления, поэтому мы всегда обрабатываем текущее состояние, представленное нашим текущим графом объектов мира.

Ясно, что существуют ситуации, идеально подходящие для параллелизма (т. Е. При обработке изолированных задач, состояния которых не зависят друг от друга).

Я не вижу, насколько параллелизм полезен в моем примере, и это может быть проблемой. Я могу как-то искажать претензию.

Может ли кто-то лучше представить это требование?

Марио Т. Ланца
источник
1
Вы имеете в виду общее состояние; разделяемое состояние всегда будет таким, какое оно есть, и всегда будет нуждаться в некоторой форме синхронизации, наиболее предпочтительной формой среди чистых людей FP является STM, которая позволяет вам рассматривать разделяемую память как локальную память, располагая над ней слой абстракции, который делает доступ к транзакциям настолько гоночным условия обрабатываются автоматически. Другая техника для разделяемой памяти - это передача сообщений, когда вместо общей памяти у вас есть локальная память и знания других акторов, чтобы запросить их локальную память
Джимми Хоффа
1
Итак ... вы спрашиваете, как простой параллелизм общего состояния помогает управлять состоянием в однопоточном приложении? С другой стороны, ваш пример явно поддается концептуальному параллелизму (поток для каждого объекта, управляемого AI), независимо от того, реализован ли он таким образом или нет. Я запутался в том, что вы спрашиваете здесь.
CA McCann
1
Одним словом, Молнии
JK.
2
У каждого объекта будет свой взгляд на мир. Будет возможная последовательность . Вероятно, это также, как вещи работают в нашем «реальном мире» с коллапсом волновой функции .
Герцмейстер
1
Вы можете найти «чисто функциональные ретро-игры» интересными: prog21.dadgum.com/23.html
user802500

Ответы:

15

Я постараюсь намекнуть на ответ. Это не ответ, а только вводная иллюстрация. Ответ @ jk указывает на реальную вещь, молнии.

Представьте, что у вас есть неизменная древовидная структура. Вы хотите изменить один узел, вставив дочерний элемент. В результате вы получите совершенно новое дерево.

Но большая часть нового дерева точно такая же, как старое дерево. Умная реализация будет повторно использовать большинство фрагментов дерева, маршрутизируя указатели вокруг измененного узла:

Из Википедии

Книга Окасаки полна таких примеров.

Поэтому я полагаю, что вы могли разумно изменять небольшие части игрового мира при каждом движении (подбирать монету) и фактически изменять только небольшие части структуры данных вашего мира (ячейка, в которой была подобрана монета). Части, которые принадлежат только прошлым состояниям, будут вовремя убраны мусором.

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

9000
источник
3
+1: за указание на книгу Окасаки. Я не читал это, но это в моем списке дел. Я думаю, что вы изобразили правильное решение. В качестве альтернативы вы можете рассмотреть типы уникальности (Clean, en.wikipedia.org/wiki/Uniqueness_type ): используя этот тип типов, вы можете деструктивно обновлять объекты данных, сохраняя при этом ссылочную прозрачность.
Джорджио
Есть ли польза для отношений, которые будут определены через косвенную ссылку через ключи или идентификаторы? То есть я думал, что меньшее количество реальных прикосновений одной структуры к другой потребует меньше поправок к мировой структуре, когда произойдут изменения. Или эта техника на самом деле не используется в FP?
Марио Т. Ланца
9

Ответ 9000 - это половина ответа, постоянные структуры данных позволяют повторно использовать неизмененные части.

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

Другой момент, связанный с молниями, заключается в том, что молния существует практически для любого типа данных, который вы хотите.

JK.
источник
Боюсь, мне понадобится некоторое время, чтобы покопаться в «молнии», так как я на грани изучения только ФП. У меня нет опыта работы с Haskell.
Марио Т. Ланца
Я постараюсь добавить пример позже сегодня
JK.
4

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

Например, предположим, что вы выполняете решения ИИ независимо друг от друга и в произвольном порядке. Они не сменяются, они все принимают решение одновременно, и тогда мир движется вперед. Код может выглядеть так:

func MakeMonsterDecision curWorldState monster =
    ...
    ...
    return monsterDecision

func NextWorldState curWorldState =
    ...
    let monsterMakeDecisionForCurrentState = MakeMonsterDecision curWorldState
    let monsterDecisions = List.map monsterMakeDecisionForCurrentState activeMonsters
    ...
    return newWorldState

У вас есть функция для вычисления того, что будет делать монстр с данным состоянием мира, и применение его к каждому монстру как часть вычисления следующего состояния мира. Это естественно для функционального языка, и компилятор может выполнять шаг «применить его к каждому монстру» параллельно.

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

Крейг Гидни
источник
Это очень помогает. Я вижу, как в игре было бы очень полезно, чтобы монстры одновременно решали, что они будут делать дальше.
Марио Т. Ланца
4

Прослушивание нескольких переговоров Rich Хики - это один , в частности - облегчено мое замешательство. В одном он указал, что это нормально, что параллельные процессы могут не иметь самого текущего состояния. Мне нужно было это услышать. У меня были проблемы с перевариванием, потому что программы на самом деле были бы в порядке, если бы решения основывались на снимках мира, которые были заменены более новыми. Я продолжал задаваться вопросом, как параллельная FP обошла проблему принятия решений на основе старого состояния.

В банковском приложении мы никогда не хотели бы основывать решение на снимке состояния, которое с тех пор было заменено более новым (произошло снятие).

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

Марио Т. Ланца
источник
0

Сторонники FP утверждают, что параллелизм прост, потому что их парадигма избегает изменчивого состояния. Я не понимаю

Я хотел бы рассказать об этом общем вопросе как о человеке, который является функциональным неофитом, но в течение многих лет испытывал побочные эффекты, и хотел бы смягчить их по разным причинам, включая более простые (или особенно «более безопасные», меньше ошибок ") параллелизм. Когда я смотрю на своих функциональных коллег и то, что они делают, трава кажется немного зеленее и пахнет лучше, по крайней мере, в этом отношении.

Последовательные алгоритмы

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

Более простой параллелизм

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

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

Проблема в том, что вы не можете этого сделать, потому что компараторы, вызываемые вашей функцией сортировки, могутвызывать побочные эффекты, если вы не знаете, как они реализованы (или, по крайней мере, документированы) для всех возможных случаев, что невозможно без дегенерализации функции. Компаратор может сделать что-то отвратительное, например модифицировать глобальную переменную внутри неатомарным способом. 99,9999% компараторов могут этого не делать, но мы все еще не можем многопоточность этой обобщенной функции просто из-за 0,00001% случаев, которые могут вызывать побочные эффекты. В результате вам, возможно, придется предложить как однопоточную, так и многопоточную функцию сортировки и передать ответственность программистам, использующим ее, чтобы решить, какую из них использовать, основываясь на безопасности потоков. И люди могут все еще использовать однопоточную версию и упустить возможности многопоточности, потому что они также могут быть не уверены, является ли компаратор потокобезопасным,

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

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

Побочные эффекты

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

[...] потому что их парадигма избегает изменчивого состояния.

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

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


источник
1
«Изменяемое состояние» всегда означает состояние на уровне приложения, а не на уровне процедуры. Исключение указателей и передача параметров в качестве значений копирования является одним из методов, встроенных в FP. Но любая полезная функция должна видоизменять состояние на некотором уровне - смысл функционального программирования состоит в том, чтобы гарантировать, что изменяемое состояние, которое принадлежит вызывающей стороне, не входит в процедуру, и мутации не выходят из процедуры, кроме как с помощью возвращаемых значений! Но есть несколько программ, которые могут выполнять большую часть работы, не изменяя состояния вообще, и ошибки всегда снова появляются в интерфейсе.
Стив
1
Честно говоря, большинство современных языков допускают использование функционального стиля программирования (с небольшой дисциплиной), и, конечно, есть языки, предназначенные для функциональных шаблонов. Но это менее эффективный в вычислительном отношении паттерн, который широко разрекламирован как решение всех проблем, как это было в 90-х годах. Большинство программ не связаны с интенсивными процессорами вычислений, которые выиграют от распараллеливания, и те из них, которые часто, это из-за сложности рассуждения, проектирования и реализации программы способом, параллельным выполнению.
Стив
1
Большинство программ, которые имеют дело с изменяемым состоянием, делают это, потому что они должны по той или иной причине. И большинство программ не являются неправильными, потому что они используют совместно используемое состояние или обновляют его аномально - обычно это происходит потому, что они получают неожиданный мусор в качестве входных данных (который определяет вывод мусора), или потому, что они неправильно работают на своих входных данных (неправильно в смысле цели быть достигнутым). Функциональные паттерны мало что делают для решения этой проблемы.
Стив
1
@ Стив, я могу, по крайней мере, наполовину согласиться с вами, так как я на этой стороне просто исследую способы сделать вещи более потоко-безопасным способом из языков, таких как C или C ++, и я не думаю, что нам нужно идти полностью взорван чистый функционал, чтобы сделать это. Но я нахожу некоторые концепции в FP полезными, по крайней мере. Я только что закончил тем, что написал ответ о том, как я нахожу PDS здесь полезным, и самое большое преимущество, которое я нахожу в PDS, на самом деле не в безопасности потоков, а в таких вещах, как создание экземпляров, неразрушающее редактирование, безопасность исключений, простые отмены и т. Д .: