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

Question

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

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

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;

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

Кроме того, вы можете написать «чистую» функцию, которая изменяет переменные.

Answer 4

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

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

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

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

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

Answer 5

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

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

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

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

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

Answer 6

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

Answer 7

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

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