Почему сложно определить, является ли функция чистой?

StackOverflow https://stackoverflow.com/questions/1609303

Вопрос

Вчера я был на конференции StackOverflow Dev Days, и один из докладчиков рассказывал о Python.Он показал функцию запоминания, и я спросил, есть ли какой-нибудь способ предотвратить ее использование в нечистой функции.Он сказал, что нет, это в принципе невозможно, и если бы кто-то смог придумать, как это сделать, из этого получилась бы отличная докторская диссертация.

Это в некотором роде сбило меня с толку, потому что компилятору / интерпретатору не кажется таким уж сложным решать рекурсивно.В псевдокоде:

function isPure(functionMetadata): boolean;
begin
   result = true;
   for each variable in functionMetadata.variablesModified
      result = result and variable.isLocalToThisFunction;
   for each dependency in functionMetadata.functionsCalled
      result = result and isPure(dependency);
end;

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

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

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

Кто-нибудь, обладающий немного большими знаниями в этой области, знает, чего мне не хватает?

Это было полезно?

Решение

Это особенно сложно в Python. Поскольку anObject.aFunc может быть произвольно изменен во время выполнения, вы не можете определить во время компиляции, какая функция будет вызывать anObject.aFunc () или даже если она вообще будет функцией .

Другие советы

Вам также нужно аннотировать каждый системный вызов, каждый FFI, ...

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

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

Кроме того, я не думаю, что это хорошая кандидатская диссертация; У Haskell уже есть (версия) это с монадой ввода / вывода.

И я уверен, что многие люди продолжают смотреть на это «на практике». (дикое предположение) Через 20 лет мы можем иметь это.

В дополнение к другим отличным ответам здесь: Ваш псевдокод смотрит только на то, изменяет ли функция переменные. Но это не совсем то, что «чисто» средства. & Quot; Чистый & Quot; обычно означает что-то более близкое к «ссылочно-прозрачному». Другими словами, вывод полностью зависит от ввода. Таким образом, простое считывание текущего времени и внесение этого фактора в результат (или чтение из входных данных, или чтение состояния машины, или ...) делает функцию не чистой без изменения каких-либо переменных.

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

Вот первое, что пришло мне в голову, когда я прочитал ваш вопрос.

  

Иерархии классов

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

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

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

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

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

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

Обратите внимание, что сложность также зависит от языка.Для более динамичных языков можно переопределить что угодно в любое время.Например, в Tcl

proc myproc {a b} {
    if { $a > $b } {
        return $a
    } else {
        return $b
    }
}

Каждый отдельный элемент этого может быть изменен в любое время.Например:

  • команду "if" можно было бы переписать для использования и обновления глобальных переменных
  • команда "return" в том же духе могла бы сделать то же самое
  • это может быть трассировка выполнения команды if, которая при использовании "if" переопределяет команду возврата на основе входных данных команды if

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top