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

Question

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 una recursión infinita en funciones que dependen mutuamente, pero no es tan 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 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 ejecutara el programa y, por lo tanto, no ralentizarían nada, pero realmente no veo ningún problema fundamental que pudiera hacer que sea imposible de evaluar.

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

Answer 1

Es particularmente difícil en Python. Dado que anObject.aFunc se puede cambiar arbitrariamente en tiempo de ejecución, no puede determinar en el momento de la compilación qué función anObject.aFunc () llamará o incluso si será una función. .

Answer 2

También debe anotar cada llamada al sistema, cada FFI, ...

Y, además, la 'fuga' más pequeña tiende a filtrarse en todo el código base.

No es un problema teóricamente intratable, pero en la práctica es muy difícil de hacer de manera que todo el sistema no se sienta quebradizo.

Aparte de eso, no creo que esto sea una buena tesis doctoral; Haskell efectivamente ya tiene (una versión de) esto, con la mónada IO.

Y estoy seguro de que muchas personas continúan mirando esto 'en la práctica'. (especulación salvaje) En 20 años podemos tener esto.

Answer 3

Además de las otras excelentes respuestas aquí: su pseudocódigo solo analiza si una función modifica las variables. Pero eso no es realmente lo que " puro " medio. " Puro " Por lo general, significa algo más cercano a " referencialmente transparente. " En otras palabras, la salida depende completamente de la entrada. Entonces, algo tan simple como leer la hora actual y hacer que eso sea un factor en el resultado (leer de la entrada o leer el estado de la máquina, o ...) hace que la función no sea pura sin modificar ninguna variable.

Además, puedes escribir un " puro " Función que modificó las variables.

Answer 4

Esto es lo primero que me vino a la mente cuando leí tu pregunta.

  

Jerarquías de clase

Determinar si una variable se modifica incluye el acto de investigar cada método que se llama en la variable para determinar si está mutando. Esto es ... algo sencillo para un tipo sellado con un método no virtual.

Pero considera los métodos virtuales. Debe encontrar cada tipo derivado único y verificar que cada anulación de ese método no mute el estado. Determinar esto simplemente no es posible en ningún lenguaje / marco que permita la generación dinámica de código o simplemente es dinámico (si es posible, es extremadamente difícil). La razón por la que se debe a que el conjunto de tipos derivados no es fijo porque se puede generar uno nuevo en tiempo de ejecución.

Tome C # como ejemplo. No hay nada que me impida generar una clase derivada en tiempo de ejecución que anule ese método virtual y modifique el estado. Una estática verificada no podría detectar este tipo de modificación y, por lo tanto, no pudo validar si el método era puro o no.

Answer 5

Creo que el principal problema sería hacerlo de manera eficiente.

D-language tiene funciones puras, pero usted mismo debe especificarlas, de modo que el compilador sepa que debe verificarlas. Creo que si los especificas manualmente sería más fácil hacerlo.

Answer 6

Decidir si una función dada es pura, en general, es reducible para decidir si un programa dado se detendrá, y es bien sabido que el problema de detención es el tipo de problema que no se puede resolver de manera eficiente.

Answer 7

Tenga en cuenta que la complejidad también depende del idioma. Para los lenguajes más dinámicos, es posible redefinir cualquier cosa en cualquier momento. Por ejemplo, en Tcl

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

Cada pieza de eso podría ser modificada en cualquier momento. Por ejemplo:

• el " si " El comando se puede reescribir para usar y actualizar variables globales.
• el " retorno " comando, en la misma línea, podría hacer lo mismo
• podría ser un seguimiento de ejecución en el comando if que, cuando " if " se utiliza, el comando de retorno se redefine en función de las entradas del comando if

Es cierto que Tcl es un caso extremo; Uno de los lenguajes más dinámicos que hay. Dicho esto, resalta el problema de que puede ser difícil determinar la pureza de una función incluso una vez que la haya ingresado.