¿Por qué es determinante si una función es pura difícil?

Ayer estuve en la convención de StackOverflow Dev Days y uno de los oradores estaba hablando de Python. Mostró una función Memoize, y le pregunté si había alguna forma de evitar que se usara en una función no pura. Dijo que no, eso es básicamente imposible, y si alguien pudiera encontrar una manera de hacerlo sería una gran tesis doctoral.

Eso me confundió, porque no parece tan difícil que un compilador / intérprete resuelva de forma recursiva. En pseudocódigo:

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;

Esa es la idea básica. Obviamente, necesitaría algún tipo de verificación para evitar la recursión infinita en funciones que dependen mutuamente, pero eso no es demasiado difícil de configurar.

Las funciones de orden superior que toman punteros de función pueden ser problemáticas, ya que no se pueden verificar de forma estática, pero mi pregunta original presupone que el compilador tiene algún tipo de restricción de lenguaje para designar que solo se puede pasar un puntero de función puro a un determinado parámetro . Si existiera uno, podría utilizarse para satisfacer la condición.

Obviamente, esto sería más fácil en un lenguaje compilado que en uno interpretado, ya que todos estos cálculos numéricos se realizarían antes de que se ejecute el programa, por lo que no ralentizaría nada, pero realmente no veo ningún problema fundamental que lo haga imposible. para evaluar.

¿Alguien con un poco más de conocimiento en esta área sabe lo que me estoy perdiendo?

Respuestas a la pregunta(7)

Su respuesta a la pregunta