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

Estuve en la convención StackOverflow Dev Days ayer, y uno de los oradores estaba hablando de Python. Mostró una función Memoize, y le pregunté si había alguna manera de evitar que se utilizara en una función no pura. Dijo que no, eso es básicamente imposible, y que si alguien pudiera encontrar la forma de hacerlo, sería una gran tesis doctoral.¿Por qué es determinante si una función es puramente difícil?

Eso me confundió, porque no parece tan difícil para un compilador/intérprete resolver 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 control para evitar la recursión infinita en funciones mutuamente dependientes, pero eso no es demasiado difícil de configurar.

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

Obviamente esto sería más fácil en un lenguaje compilado que en uno interpretado, ya que todo este proceso de numeración se haría antes de que se ejecute el programa y no desacelerará nada, pero realmente no veo ningún problema fundamental que haría imposible evaluar.

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

Fuente

2009-10-22 Mason Wheeler

Sería cualquier variable * accedida * que debe ser local, no solo modificada. Una función cuyo resultado depende del valor actual de un global, incluso si no modifica ese global, claramente no es puro. – caf

La pregunta obvia: ¿el registro afecta la pureza? Diría que, por el contrario, en realidad MODIFICAR un valor global (si esto no puede arrojarse), no afecta el resultado de su método y, por lo tanto, permite la memorización incluso si claramente no es puro. –

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

Fuente

2009-10-22 19:13:48

¡Ay! Está bien, puedo ver cómo eso lo haría más difícil. –

Hay más - eval, setattr(), __gettattr() __ haciendo cosas raras, etc. Las características como esta hacen que los lenguajes sean difíciles de analizar estáticamente. –

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

Clase Jerarquías

La determinación de si se modifica una variable incluye el acto de excavación a través de cada método único que se llama en la variable para determinar si se trata de mutar. Esto es ... un tanto directo para un tipo sellado con un método no virtual.

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

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

Fuente

2009-10-22 19:07:55 JaredPar

Oh, buen punto. El polimorfismo definitivamente complicaría las cosas. Aunque eso podría solucionarse poniendo una "restricción pura" en la función virtual base. –

también hay que anotar cada llamada al sistema, todos los FFI, ...

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

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

Como nota aparte, no creo que esto haga una buena tesis de doctorado; Haskell efectivamente ya tiene (una versión de) esto, con la mónada IO.

Y estoy seguro de que mucha gente sigue mirando esto 'en la práctica'. (Especulación salvaje) En 20 años podemos tener esto.

Fuente

2009-10-22 19:09:10 Brian

Computer AI está a solo 4-6 años de distancia y seguro que será capaz de resolver este problema :) – JaredPar

En Haskell todas las funciones son puras. 'IO' no cambia eso. Bueno, tal vez excepto aquellos que hacen 'inseguroPerformIO'. –

Anotar toda la clase de sistema es que .NET está haciendo para sus contratos de código.En caso de duda, asume que el método no es puro. –

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 significa "puro". "Puro" típicamente significa algo más cercano a "referencialmente transparente". En otras palabras, la salida depende por completo de la entrada. Entonces, algo tan simple como leer la hora actual y convertirlo en un factor en el resultado (o leer desde 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, podría escribir una función "pura" que modifique las variables.

Fuente

2009-10-22 19:28:52

+1 Ser libre de efectos secundarios no significa usar solo valores inmutables. –

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

D-language tiene funciones puras, pero tiene que especificarlas usted mismo, por lo que el compilador sabrá comprobarlas. Creo que si los especifica manualmente, sería más fácil hacerlo.

Fuente

2009-10-22 21:58:41 Egon

Decidir si una función determinada es pura, en general, es reducible a la decisión de si un determinado programa 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.

Fuente

2009-10-22 22:04:17 yfeldblum

Sé sobre el problema de detención, pero ¿por qué dices que es equivalente? –

Supongamos que escribo un programa P que simula la ejecución de alguna función de entrada F (es decir, P es un intérprete). Supongamos que P se escribe de manera que se detiene al completar la evaluación de F e inmediatamente después de ejecutar cualquier paso impuro de F (con una salida que indique por qué se detuvo). Como algunos F pueden tener la forma 'f a = f a' - sintaxis Haskell para una función con un argumento que simplemente se llama a sí mismo con el mismo argumento recursivamente ad infinitum - hay algo de F para el cual P ejecutando F no se detendrá. Por lo tanto, la pregunta del OP es reducible al problema de detención. – yfeldblum

Tenga en cuenta que en Haskell, si nos deshacemos de las lagunas del lenguaje permitiendo cierto código impuro dentro de un código puro, el compilador puede determinar fácilmente qué código es puro y qué código no es seguro simplemente mirando los tipos. Haskell representa impureza en el nivel de tipo. – yfeldblum

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 una de las piezas se puede modificar en cualquier momento. Por ejemplo:

el "si" de comandos podría reescribirse de usar y actualizar las variables globales
la orden de "retorno", a lo largo de las mismas líneas, podría hacer lo mismo
la podría haber una ejecución trace en el comando if que, cuando se usa "if", 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 idiomas 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.

Fuente

2009-10-23 03:49:21 RHSeeger

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

Respuesta

Cuestiones relacionadas