Согласно Википедии:
В компьютерном программировании функция может быть описана как чистая, если оба эти утверждения о функции выполняются: функция всегда оценивает одно и то же значение результата, учитывая одно и то же значение (я) аргумента. Значение результата функции не может зависеть от какой-либо скрытой информации или состояния, которые могут изменяться по мере выполнения программы или между различными выполнениями программы, а также не может зависеть от какого-либо внешнего ввода от устройств ввода-вывода. Оценка результата не вызывает какого-либо семантически наблюдаемого побочного эффекта или вывода, такого как мутация изменяемых объектов или вывод на устройства ввода-вывода.
Мне интересно, можно ли написать функцию, которая вычисляет, является ли функция чистой или нет. Пример кода в Javascript:
function sum(a,b) {
return a+b;
}
function say(x){
console.log(x);
}
isPure(sum) // True
isPure(say) // False
if (rand(1000000)<2) return WRONG_ANSWER
, многократное исследование функции на предмет согласованного поведения не поможет. Но если у вас есть доступ к определению функции, доказательство тривиально.say
вызовы .console.log
say
Ответы:
Да, это возможно, в зависимости от языка.
В JavaScript вы можете определить, является ли функция чистой по следующим критериям:
Он читает только параметры и локальные данные;
Это пишет только местные жители;
На нелокальных объектах он вызывает только чистые функции;
Все функции, которые он вызывает неявно, являются чистыми, например
toString
; иОн записывает свойства локальных файлов только в том случае, если они не имеют псевдонимов, отличных от локальных.
Псевдоним невозможно определить в JavaScript в общем случае, потому что вы всегда можете посмотреть свойства объекта динамически (
object["property"]
). Если вы никогда этого не делаете, и у вас есть источник всей программы, тогда я думаю, что проблема решаема. Вам также понадобится информация о том, какие нативные функции имеют побочные эффекты, такие какconsole.log
или почти все, что связано с DOM.Термин «чистый» также может использовать некоторые пояснения. Даже в строго статически типизированном, чисто функциональном языке программирования, где все функции прозрачны по ссылкам, функция все равно может не завершиться. Поэтому, когда мы говорим о том
id :: a -> a
, что мы на самом деле говорим, это неСкорее:
Поскольку действительное осуществление
id
ISerror "Not implemented!"
. Как указывает Петерис, эта нетитальность может рассматриваться как некая примесь. Koka - это функциональный язык программирования с синтаксисом, смоделированным на JavaScript, который может определять возможные эффекты, такие как расхождение (нетерминация), ссылочная прозрачность, создание исключений и действия ввода / вывода.источник
toString
является ли он чистым для любого объекта, который вы используете в качестве строки.function a (o) { return o.method(); }
- мы не можем ответить на этот вопрос, потому что это зависит от того, какой параметрo
передан. Кроме того, мы не можем объяснить, что произойдет, если ранее сертифицированная-чистая функция была заменена на не-чистую реализацию, что всегда является потенциальной проблемой с javascript.Нет. Вы можете легко проверить, выполняет ли функция только «чисто безопасные» операции, как описано в ответе Джона Пурди, но этого ИМО недостаточно для ответа на вопрос.
Рассмотрим эту функцию:
Очевидно, что если не
someCheck
является чистым, так и естьpossiblyPure
. Но, еслиsomeCheck
он чистый и возвращаетtrue
все возможные значенияx
, онpossiblyPure
является чистым, поскольку путь к неочищенному коду недоступен!И тут возникает сложная часть: определить,
someCheck
возвращает ли значение true для каждого возможного ввода. Попытка ответить на этот вопрос незамедлительно приводит вас в сферу проблемы остановки и подобных неразрешимых проблем.РЕДАКТИРОВАТЬ: Доказательство того, что это невозможно
Существует некоторая неопределенность, или нет чистая функция должна завершаться на каждом возможном входе. Но в обоих случаях проблему остановки можно использовать, чтобы показать, что проверка чистоты невозможна.
Случай A) Если для завершения каждого возможного входа требуется чистая функция, вам необходимо решить проблему остановки, чтобы определить, является ли функция чистой. Поскольку известно, что это невозможно, по этому определению чистота не может быть вычислена.
Случай B) Если чистой функции разрешено не заканчиваться на некоторых входах, мы можем сконструировать что-то вроде этого: предположим, что
isPure(f)
вычисляет iff
- это строка, определяющая чистую функцию.Теперь
isPure
нужно определить,f
останавливается ли его собственный источник в качестве входных данных. Если оно останавливается,upf
это нечисто; если оно не заканчивается,upf
оно чисто, еслиf
оно чисто.Если бы мы
isPure
работали, как ожидалось (возвращает правильные результаты и завершаются при каждом вводе), мы бы решили проблему остановки (*)! Поскольку известно, что это невозможно,isPure
не может существовать.(*) для функций на чистом JavaScript, что достаточно для его решения и для машины Тьюринга.
источник
На этот вопрос о стековом потоке есть ответ от yfeldblum, который уместен здесь. (И по какой-то причине у меня есть отрицательное мнение, которое я не могу понять. Было бы плохим этикетом повышать голос за то, что ему 3 года?) Он дает доказательство того, что чистая функция сводится к проблеме остановки в комментарии.
Я думаю, что с практической точки зрения для некоторых языков было бы не так сложно, если бы вы позволили функции возвращать да, нет или, может быть. Я смотрел видео о Clojure пару дней назад, и спикер провел подсчет нескольких случаев примесей в кодовой базе, отыскивая около 4 различных строк (например, «ref»). Из-за акцента Clojure на чистоте и отделении нечистых вещей это было тривиально, но это не совсем то, что вы ищете.
Итак, теоретически невозможно, практически возможно, если немного подправить вопрос, и я думаю, насколько это будет сложно, во многом будет зависеть от языка. Упрощенные / более чистые языки с упором на неизменность и хорошее отражение будут проще.
источник
bottom
является допустимым значением первого класса, оно не заслуживает дискриминации таким образом.Отличный вопрос
Лучшее, что вы можете сделать на практике, предполагая, что у вас нет возможности прослушивать действия ввода-вывода для вызова функции столько раз, сколько это возможно. Затем посмотрите, соответствует ли возвращаемое значение.
Но вы не можете сделать это в целом. Можно утверждать, что программы без остановки не являются чистыми, и мы не можем решить проблему остановки.
источник
void
функция будет «чистой», что явно неверно.Не возможно в общем случае. Смотри проблему остановки . Вкратце, невозможно написать программу, которая, учитывая произвольную функцию и ввод, определяет, остановится ли программа или запустится навсегда. Если он работает вечно, это не просто функция, подходящая под определение, которое вы дали.
источник
bottom
значению.