Считается ли чистая запомненная функция чистой?

47

Допустим, fn(x)это чистая функция, которая делает что-то дорогое, например, возвращает список основных факторов x.

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

Формально говоря, memoizedFn(x)считается чистым?

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

Каллум
источник
24
Может быть, это не чисто для пуристов, но "достаточно чисто" для прагматичных людей ;-)
Док Браун
2
@DocBrown Я согласен, просто интересно, есть ли более формальный термин «достаточно чистый»
каллум
13
Выполнение чистой функции, скорее всего, изменит кэш инструкций процессора, предсказатели ветвлений и т. Д. Но это, вероятно, «достаточно чисто» и для пуристов - или вы можете вообще забыть о чистых функциях.
gnasher729
10
@callum Нет, формального определения «достаточно чисто» не существует. Когда вы спорите о чистоте и семантической эквивалентности двух «ссылочно-прозрачных» вызовов, вы всегда должны точно указать, какую семантику вы собираетесь применять. При некотором низком уровне детализации реализации он всегда будет ломаться и иметь разные эффекты памяти или тайминги. Вот почему вы должны быть прагматичными: какой уровень детализации полезен для рассуждений о вашем коде?
Берги
3
Тогда, ради прагматизма, я бы сказал, что чистота зависит от того, считаете ли вы время вычислений частью вывода. funcx(){sleep(cached_time--); return 0;}каждый раз возвращает одно и то же значение val, но будет работать по-разному
Mars

Ответы:

41

Да. Запомненная версия чистой функции также является чистой функцией.

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

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

Ли Райан
источник
19

Википедия определяет «Чистую функцию» как функцию, которая имеет следующие свойства:

  • Его возвращаемое значение одинаково для тех же аргументов (без изменений с локальными статическими переменными, нелокальными переменными, изменяемыми ссылочными аргументами или входными потоками от устройств ввода-вывода).

  • Его оценка не имеет побочных эффектов (нет мутации локальных статических переменных, нелокальных переменных, изменяемых ссылочных аргументов или потоков ввода-вывода).

По сути, чистая функция возвращает тот же вывод при том же входе и не влияет ни на что, кроме функции. В целях чистоты не имеет значения, как функция вычисляет свое возвращаемое значение, при условии, что она возвращает те же выходные данные при одинаковых входных данных.

Функционально чистые языки, такие как Haskell, обычно используют запоминание для ускорения функции путем кэширования ее ранее вычисленных результатов.

Роберт Харви
источник
16
Я могу что-то пропустить, но как вы собираетесь хранить кеш без побочных эффектов?
вал
1
Сохраняя это внутри функции.
Роберт Харви
4
«отсутствие мутации локальной статической переменной», по-видимому, исключает локальные переменные, сохраняющиеся между вызовами.
вал
3
Это на самом деле не отвечает на вопрос, даже если вы, кажется, подразумеваете, что да, это чисто.
Марс
6
@val Вы правы: это состояние нужно немного ослабить. Чисто-функциональная памятка, на которую он ссылается, не имеет видимой мутации каких-либо статических данных. Что происходит, так это то, что результат вычисляется и запоминается при первом вызове функции и возвращает то же значение при каждом вызове. У многих языков есть для этого идиома: static constлокальная переменная в C ++ (но не в C) или лениво оцененная структура данных в Haskell. Есть еще одно условие: инициализация должна быть поточно-ориентированной.
Дэвислор
7

Да, запоминаемые чистые функции обычно называются чистыми. Это особенно распространено в таких языках, как Haskell, в которых запоминаемые, лениво оцениваемые, неизменяемые результаты являются встроенной функцией.

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

Один пример компьютерного ученого, использующего термин «чисто функциональный» таким образом, - это сообщение в блоге Конала Эллиотта об автоматическом запоминании:

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

Есть много примеров в рецензируемой литературе, и были на протяжении десятилетий. Например, в этой статье 1995 года «Использование автоматической мемоизации в качестве инструмента разработки программного обеспечения в реальных системах искусственного интеллекта» используется очень похожий язык в разделе 5.2 для описания того, что мы сегодня называем чистой функцией:

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

Некоторые императивные языки имеют похожую идиому. Например, static constпеременная в C ++ инициализируется только один раз, прежде чем ее значение используется, и никогда не изменяется.

Davislor
источник
3

Это зависит от того, как вы это делаете.

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

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

В ссылке, предоставленной Робертом Харви , ленивая оценка используется, чтобы избежать побочных эффектов.

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

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

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

Карл Билефельдт
источник
Я не думаю, что какое-либо более чистое решение решает вышеуказанные проблемы: несмотря на то, что вы теряете любые проблемы параллелизма, вы также теряете шанс для двух одновременно запущенных вызовов, таких как collatz(100)и collatz(200)к сотрудничеству. И IIUIC, проблема с кешем, увеличивающимся слишком большим, остается (хотя у Haskell могут быть некоторые хорошие уловки для этого?).
Маартин
Примечание: IOчисто. Все нечистые методы на IOCats и названы unsafe. Async.memoizeтакже чист, поэтому нам не нужно соглашаться на «достаточно чистое» :)
Самуил
2

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

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

Р..
источник
0

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

[Монада состояний] - это в основном функция S => (S, A), где S - это тип, представляющий ваше состояние, а A - результат, который дает функция - Cats State .

В вашем случае состоянием будет запомненное значение или ничего (например, Haskell Maybeили Scala Option[A]). Если запомненное значение присутствует, оно возвращается как A, в противном случае Aвычисляется и возвращается как в переходном состоянии, так и в результате.

Самуил
источник