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

Вчера я был на съезде 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;

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

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

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

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

Ответы на вопрос(7)

Ваш ответ на вопрос