¿Existe una definición canónica de la función "pura"?

9

StackOverflow me señaló aquí, por lo que la pregunta podría ser un poco simple.

Wikipedia define funciones puras como

En la programación de computadoras, una función puede describirse como una función pura si ambas afirmaciones sobre la función tienen:

  1. La función siempre evalúa el mismo valor de resultado dados los mismos valores de argumento. El valor del resultado de la función no puede depender de ninguna información oculta o estado que pueda cambiar a medida que avanza la ejecución del programa o entre diferentes ejecuciones del programa, ni puede depender de ninguna entrada externa de los dispositivos de E / S.
  2. La evaluación del resultado no causa ningún efecto secundario o salida semánticamente observable, como la mutación de objetos mutables o la salida a dispositivos de E / S.

Sin embargo, no parece citar ninguna fuente, por lo que es difícil decir si esta es una definición aceptada o quién la definió de esta manera.

Cuando miro lo que hacen los idiomas cuando incluyen una sintaxis / anotación para funciones "puras", hay varios enfoques diferentes:

  1. En D, la única limitación es la no mutación del estado global. Las funciones "puras" pueden mutar sus argumentos.
  2. En GCC hay dos tipos de "puro": pure(sin efectos secundarios, pero puede leer el estado global) y const(estrictamente puro según la definición de Wikipedia).
  3. En C # , se define como "no realiza ningún cambio de estado visible" (sea lo que sea).
  4. Haskell sigue la definición de Wikipedia.

Entonces mi pregunta es: ¿hay una definición canónica de función pura?
Y si existe, ¿cuál es su fuente?

terminology functional-programming semantics Andrey Shchekin
fuente
Perspectiva histórica relacionada , aunque nadie parece dar ninguna respuesta definitiva o de origen.
Guildenstern
1
Esto no vale una respuesta, pero aquí está mi definición: si x = y (por su definición) entonces fx = fy es verdadero yf no causa un cambio de estado medible externamente (es decir, todo cambio de estado es interno de x, y, y f). Haskell se aprovecha de esto. Implementa una evaluación perezosa mutando thunks y reemplazándolos con funciones que devuelven el resultado inmediatamente. Es decir, si evalúa (fx), en realidad puede cambiar f y x debajo del capó, pero nunca se puede saber.
Jake

Respuestas:

3

Como se señaló en este documento Imperative Functional Programming , (1993) de Peyton-Jones y Wadler (entre el grupo de investigadores que crearon Haskell):

Nos centramos en soluciones puramente funcionales, que descartan los efectos secundarios, por dos razones. En primer lugar, la ausencia de efectos secundarios permite el uso irrestricto del razonamiento equitativo y la transformación del programa ...

La atención se centra en la ausencia de efectos secundarios para permitir las transformaciones del programa (es decir, optimizaciones del compilador).

¿Qué son los efectos secundarios? Este documento a su vez apunta a la integración de la programación funcional e imperativa (1986) de Gifford y Lucassen, que menciona cuatro tipos de clases de efectos : Puro, Función, Observador y Procedimiento. Entonces, el término "función pura" se deriva de este artículo.

  • un PURE es referencialmente transparente: no causa efectos secundarios, su valor no se ve afectado por los efectos secundarios y devuelve el mismo valor cada vez que se evalúa.

Sin embargo, tenga en cuenta que Peyton-Jones y Wadler mencionaron deficiencias en este enfoque. Vale la pena notar, dicen, que es el lenguaje de programación Clean que utiliza tipos lineales para introducir efectos secundarios de manera segura (es decir, seguro para el compilador). Básicamente, distribuye el mundo como una variable en todas las funciones relacionadas con E / S, incluido el punto de entrada principal .

Con eso, es posible tener un lenguaje funcional puro que interactúe con el mundo y tenga efectos secundarios (E / S, el sistema operativo, el sistema de ventanas, etc.), contradiciendo parcialmente su definición de wikipedia. De hecho, se puede decir que Haskell tiene a Clean como uno de sus influenciadores; aunque se aparta de los tipos lineales y utiliza otra construcción de nivel de tipo (mónadas) para garantizar la linealidad, es decir, una referencia única en todo momento.

carlosayam
fuente
"Básicamente, enhebra el mundo como una variable ...". ¿En realidad te refieres a "hilos". ¿Hay una cuenta informal de esto en la web?
babou
Solía ​​"enhebrar" como metáfora. Significa que debe pasar la variable World de una función a otra. Y la tipificación lineal significa que dicha variable World no se usa más de una vez. Implica, por ejemplo, que para abrir un archivo dentro de una función le gustaría hacer (f_handle, world2) = fopen file_name, world(pseudocódigo) y tendrá que usar una próxima llamada world2. En esencia, los programas son vistos como operando en el Universo como un todo. Dicho de otra manera, no hay efectos secundarios cuando estás operando en el Universo :-)
carlosayam
Enhebrar el mundo, como usted dice, parece ser la forma estándar (como recuerdo) de tratar el medio ambiente en semántica denotacional. Entonces, el punto clave debe ser la linealidad. Pero entonces, se supone que la semántica denotativa (DS) es puramente funcional, sin ninguna restricción de linealidad. Supongo que DS es una abstracción matemática y no tiene reparos en hacer malabarismos con muchos mundos. La computación es física y la linealidad permite la evolución mundial, pero solo puede existir un mundo a la vez (lo que probablemente secuencializa la evaluación). ¿Cuál es la semántica de 2 programas limpios que se ejecutan simultáneamente :-)?
babou
¿El documento de Gifford y Lucassen es accesible en la web?
babou
Tengo acceso a través de la Uni.
carlosayam
-1

La definición de Wikipedia es canónica. Los dos requisitos cruciales son:

  • El valor de retorno y el comportamiento de la función es una función determinista de los argumentos que se pasaron explícitamente a la función.

  • Una invocación de la función no tiene efectos secundarios observables.

Estrictamente hablando, D y gcc no deberían usar la palabra "puro" como lo hacen; Es un abuso de la terminología estándar.

DW
fuente