Вычислить, если функция является чистой

11

Согласно Википедии:

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

Мне интересно, можно ли написать функцию, которая вычисляет, является ли функция чистой или нет. Пример кода в Javascript:

function sum(a,b) {
    return a+b;
}

function say(x){
    console.log(x);
}

isPure(sum) // True
isPure(say) // False
Oni
источник
7
Это может быть кандидат на обмен стека информатики . Это больше относится к области теории («возможно»), чем к практике и дизайну ... Это немного за пределами моего понимания.
... и хотя это «возможно» и «теория», вполне вероятно, что на него найдется реальный ответ (подходящий для вопросов и ответов), который может даже включать доказательство… которое снова возвращает его в мир компьютерных наук. ,
Я думаю, что вы можете определить, является ли функция чистой, посмотрев на тип функций, которые вызываются в ее определении. Я имею в виду, вы можете определить чистоту по индукции в структуре функций.
Джорджио
7
Невозможно обойтись без взломов, зависящих от платформы. Если функция является черным ящиком, ни один эксперимент не может доказать ее чистоту. Например, если есть что-то подобное if (rand(1000000)<2) return WRONG_ANSWER, многократное исследование функции на предмет согласованного поведения не поможет. Но если у вас есть доступ к определению функции, доказательство тривиально.
SK-logic
1
@ user470365 Из определения чистой функции - «Оценка результата не вызывает какого-либо семантически наблюдаемого побочного эффекта или вывода, такого как мутация изменяемых объектов или вывод на устройства ввода-вывода». - Все, что пишет в IO, нечисто по определению. В этом примере также нечистыми являются sayвызовы . console.logsay

Ответы:

17

Да, это возможно, в зависимости от языка.

В JavaScript вы можете определить, является ли функция чистой по следующим критериям:

  • Он читает только параметры и локальные данные;

  • Это пишет только местные жители;

  • На нелокальных объектах он вызывает только чистые функции;

  • Все функции, которые он вызывает неявно, являются чистыми, например toString; и

  • Он записывает свойства локальных файлов только в том случае, если они не имеют псевдонимов, отличных от локальных.

Псевдоним невозможно определить в JavaScript в общем случае, потому что вы всегда можете посмотреть свойства объекта динамически ( object["property"]). Если вы никогда этого не делаете, и у вас есть источник всей программы, тогда я думаю, что проблема решаема. Вам также понадобится информация о том, какие нативные функции имеют побочные эффекты, такие как console.logили почти все, что связано с DOM.

Термин «чистый» также может использовать некоторые пояснения. Даже в строго статически типизированном, чисто функциональном языке программирования, где все функции прозрачны по ссылкам, функция все равно может не завершиться. Поэтому, когда мы говорим о том id :: a -> a, что мы на самом деле говорим, это не

Учитывая некоторое значение типа a, функция idсоздает значение типа a.

Скорее:

Учитывая некоторое значение типа aфункция idделает не производит значение , которое не типа a.

Поскольку действительное осуществление idIS error "Not implemented!". Как указывает Петерис, эта нетитальность может рассматриваться как некая примесь. Koka - это функциональный язык программирования с синтаксисом, смоделированным на JavaScript, который может определять возможные эффекты, такие как расхождение (нетерминация), ссылочная прозрачность, создание исключений и действия ввода / вывода.

Джон Перди
источник
+1 - С учетом ответа Петерис получил так много откликов .....
mattnz
Я полагаю, вам нужно добавить «Он вызывает только чистые функции» в список критериев.
Грег Хьюгилл
1
@GregHewgill: хороший улов. Я обновил ответ соответственно. Можно вызывать мутационные функции у местных жителей, если они не оказывают побочного действия. «Чистый» слишком перегружен термином…
Джон Пурди,
Вы также должны проверить, toStringявляется ли он чистым для любого объекта, который вы используете в качестве строки.
Волков Олег Васильевич
Я не думаю, что этот ответ является правильным, потому что есть только подмножество обстоятельств, где вы можете сделать эти определения. Подумайте: чиста ли эта функция? function a (o) { return o.method(); }- мы не можем ответить на этот вопрос, потому что это зависит от того, какой параметр oпередан. Кроме того, мы не можем объяснить, что произойдет, если ранее сертифицированная-чистая функция была заменена на не-чистую реализацию, что всегда является потенциальной проблемой с javascript.
Жюль
11

Нет. Вы можете легко проверить, выполняет ли функция только «чисто безопасные» операции, как описано в ответе Джона Пурди, но этого ИМО недостаточно для ответа на вопрос.

Рассмотрим эту функцию:

function possiblyPure(x) {
    if (someCheck(x)) {
        return x+1; // pure code path
    }
    else {
        console.log("I'm so unpure..."); // unpure code path
    }
}

Очевидно, что если не someCheckявляется чистым, так и есть possiblyPure. Но, если someCheckон чистый и возвращает trueвсе возможные значения x, он possiblyPureявляется чистым, поскольку путь к неочищенному коду недоступен!

И тут возникает сложная часть: определить, someCheckвозвращает ли значение true для каждого возможного ввода. Попытка ответить на этот вопрос незамедлительно приводит вас в сферу проблемы остановки и подобных неразрешимых проблем.

РЕДАКТИРОВАТЬ: Доказательство того, что это невозможно

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

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

Случай B) Если чистой функции разрешено не заканчиваться на некоторых входах, мы можем сконструировать что-то вроде этого: предположим, что isPure(f)вычисляет if f- это строка, определяющая чистую функцию.

function halts(f) {
   var fescaped = f.replace(/\"/g, '\\"');
   var upf = 'function() { '+f+'("'+fescaped+'\); console.log("unpure"); }';
   return isPure(upf);
}

Теперь isPureнужно определить, fостанавливается ли его собственный источник в качестве входных данных. Если оно останавливается, upfэто нечисто; если оно не заканчивается, upfоно чисто, если fоно чисто.

Если бы мы isPureработали, как ожидалось (возвращает правильные результаты и завершаются при каждом вводе), мы бы решили проблему остановки (*)! Поскольку известно, что это невозможно, isPureне может существовать.

(*) для функций на чистом JavaScript, что достаточно для его решения и для машины Тьюринга.

user281377
источник
3
Правда. Всегда можно провести консервативный анализ - проверить, является ли функция определенно чистой, но невозможно проверить, если она определенно не является чистой.
SK-logic
Многие случаи тривиально разрешимы - те чистые функции, описанные Джоном Пурди, или нечистые функции, которые безусловно делают что-то грязное; но в целом можно построить случаи, которые неразрешимы.
user281377 22.11.12
1

На этот вопрос о стековом потоке есть ответ от yfeldblum, который уместен здесь. (И по какой-то причине у меня есть отрицательное мнение, которое я не могу понять. Было бы плохим этикетом повышать голос за то, что ему 3 года?) Он дает доказательство того, что чистая функция сводится к проблеме остановки в комментарии.

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

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

Майкл Шоу
источник
Я считаю, что это было понижено, потому что это неправильно. bottomявляется допустимым значением первого класса, оно не заслуживает дискриминации таким образом.
SK-logic
0

Отличный вопрос

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

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

Петерис
источник
1
-1: было бы не просто написать функцию, которая проходит этот тест и не является чистой.
Mattnz
3
По этой логике любая voidфункция будет «чистой», что явно неверно.
Грег Хьюгилл
1
@ Грег: По сути, void foo (void) также должен быть чистым.
Mattnz
0

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

dbkk
источник
5
Запуск навсегда, похоже, не освобождает функцию от соответствия его критериям чистой функции.
whatsisname
+1: неявно требуется, чтобы функция заканчивалась на «Функция всегда оценивает одно и то же значение результата, которое дают ....»
mattnz
2
Постоянно работающий вечно без изменения какого-либо состояния совершенно "чист". Но, конечно, это проблема терминологии здесь.
SK-logic
@mattnz, такая функция всегда будет соответствовать bottomзначению.
SK-logic
1
Я могу видеть, где возникает проблема терминологии. В некоторых интерпретациях «чистая» функция - это функция, которая является детерминированной, а также никогда не передает какое-либо состояние или значение извне во время своего выполнения. В других интерпретациях остановка добавляется к требованиям. С первой интерпретацией легко определить, является ли функция чистой: машина, которая выполняет определенный язык, должна быть в состоянии определить, осуществляет ли программа на этом языке какую-либо связь с внешним миром.
Рувон