Функции, которые выглядят чисто для вызывающих, но внутренне используют мутацию

Question

Я только что получил свою копию Expert F # 2.0 и наткнулся на это утверждение, которое меня несколько удивило:

Например, при необходимости вы можете использовать побочные эффекты длячастные структуры данных, выделенные в начале алгоритма и затем отбрасывающие эти структуры данных перед возвратом результата;тогда общий результат фактически является функцией без побочных эффектов.Одним из примеров отделения от библиотеки F # является реализация библиотеки List.map, которая использует мутацию внутри;записи происходят во внутренней, отдельной структуре данных, к которой другой код не может получить доступ.

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

Другими словами, если бы производительность была отложена, было бы предпочтительнее реализовать List.map в чистом виде?

(Очевидно, это касается, в частности, F #,Мне тоже интересно общая философия)

Answer 1

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

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

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

(Если вы хотите углубиться, локальные эффекты, такие как в реализации List.map в F #, не только не мешают распараллеливанию, но на самом деле выигрывают с точки зрения того, что более Эффективная реализация выделяет меньше, и, следовательно, меньше нагрузки на общий ресурс GC.)

Answer 2

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

Важным моментом является то, что когда вы используете Control.Monad.ST, чтобы сделатьПодобные вещи в Haskell, сама система типов обеспечивает инкапсуляцию.В Scala (и, вероятно, F #) подход более «просто доверьтесь нам, что мы не делаем ничего хитрого здесь с этим ListBuffer в вашем map».

Answer 3

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

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

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

Answer 4

Такой же подход можно найти в использовании в Clojure. Неизменяемые структуры данных в Clojure - list, map и vector - имеют свои «временные» аналоги, которые могут изменяться. Ссылка Clojure о переходных процессах призывает использовать их только в коде, который не виден «любому другому коду».

В коде клиента предусмотрена защита от переходных процессов:

• Обычная функция, которая работает с неизменяемыми структурами данных, не работает с переходными процессами. Вызов их вызовет исключение.

• Переходные процессы связаны с потоком, в котором они созданы. Изменение их из любого другого потока вызовет исключение.

Код clojure.core сам по себе использует множество переходных процессов за кулисами.

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

Таким образом, строго контролируемое использование изменяемого состояния в функциональных языках кажется нормальным.

Answer 5

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

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

Answer 6

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

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

Answer 7

Я бы ответил на вопрос: «Вы пишете функцию или используете функцию?»

Есть 2 аспекта для функций, пользователей и разработчиков.

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

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

Многие люди разрабатывают функцию, которую они затем используют, поэтому применяются оба эти аспекта.

В чем преимущества неизменяемости по сравнению с изменяемыми структурами - это другой вопрос.