Transparencia referencial - Referential transparency

Este artículo trata sobre la transparencia referencial en la teoría del lenguaje de programación. Para su uso en lingüística y filosofía, consulte Contexto opaco .

La transparencia referencial y la opacidad referencial son propiedades de partes de los programas informáticos . Una expresión se llama referencialmente transparente si se puede reemplazar con su valor correspondiente (y viceversa) sin cambiar el comportamiento del programa. Esto requiere que la expresión sea pura , es decir, el valor de la expresión debe ser el mismo para las mismas entradas y su evaluación no debe tener efectos secundarios . Una expresión que no es referencialmente transparente se denomina referencialmente opaca.

En matemáticas, todas las aplicaciones de funciones son referencialmente transparentes , por la definición de lo que constituye una función matemática . Sin embargo, este no es siempre el caso en la programación, donde los términos procedimiento y método se utilizan para evitar connotaciones engañosas. En la programación funcional solo se consideran funciones referencialmente transparentes. Algunos lenguajes de programación proporcionan medios para garantizar la transparencia referencial. Algunos lenguajes de programación funcional imponen transparencia referencial para todas las funciones.

La importancia de la transparencia referencial es que permite al programador y al compilador razonar sobre el comportamiento del programa como un sistema de reescritura . Esto puede ayudar a demostrar la corrección , simplificar un algoritmo , ayudar a modificar el código sin romperlo u optimizar el código mediante memorización , eliminación de subexpresiones comunes , evaluación diferida o paralelización .

Historia

El concepto parece haberse originado en los Principia Mathematica (1910-13) de Alfred North Whitehead y Bertrand Russell . Fue adoptado en filosofía analítica por Willard Van Orman Quine . En §30 de Word and Object (1960) Quine da esta definición:

Un modo de contención φ es referencialmente transparente si, siempre que una ocurrencia de un término singular t es puramente referencial en un término o oración ψ (t), es puramente referencial también en el término o oración que lo contiene φ (ψ (t)).

El término apareció en su uso contemporáneo de la ciencia de la computación, en la discusión de variables en lenguajes de programación , en el conjunto seminal de notas de clase de Christopher Strachey , Conceptos fundamentales en lenguajes de programación (1967). Las notas de la clase hacen referencia a la palabra y el objeto de Quine en la bibliografía.

Ejemplos y contraejemplos

Si todas las funciones involucradas en la expresión son funciones puras , entonces la expresión es referencialmente transparente.

Considere una función que devuelve la entrada de alguna fuente. En pseudocódigo, una llamada a esta función podría ser GetInput(Source)donde Sourcepodría identificar un archivo de disco en particular, el teclado , etc. Incluso con valores idénticos de Source, los valores devueltos sucesivos serán diferentes. Por tanto, la función GetInput()no es determinista ni referencialmente transparente.

Un ejemplo más sutil es el de una función que tiene una variable libre , es decir, depende de alguna entrada que no se pasa explícitamente como parámetro. Esto luego se resuelve de acuerdo con las reglas de vinculación de nombres a una variable no local , como una variable global , una variable en el entorno de ejecución actual (para vinculación dinámica ) o una variable en un cierre (para vinculación estática). Dado que esta variable se puede modificar sin cambiar los valores pasados ​​como parámetro, los resultados de las llamadas posteriores a la función pueden diferir incluso si los parámetros son idénticos. Sin embargo, en la programación funcional pura , la asignación destructiva no está permitida y, por lo tanto, si la variable libre está vinculada estáticamente a un valor, la función sigue siendo referencialmente transparente, ya que ni la variable no local ni su valor pueden cambiar debido a la vinculación estática. e inmutabilidad , respectivamente.

Las operaciones aritméticas son referencialmente transparentes: 5 * 5pueden ser reemplazadas por 25, por ejemplo. De hecho, todas las funciones en el sentido matemático son referencialmente transparentes: sin(x)es transparente, ya que siempre dará el mismo resultado para cada particular x.

Las reasignaciones no son transparentes. Por ejemplo, la expresión Cx = x + 1 cambia el valor asignado a la variable x. Suponiendo que xinicialmente tiene valor 10, dos evaluaciones consecutivas de la expresión producen, respectivamente, 11y 12. Claramente, reemplazar x = x + 1con 11o 12da un programa con un significado diferente, por lo que la expresión no es referencialmente transparente. Sin embargo, llamar a una función como es transparente, ya que no cambiará implícitamente la entrada y, por lo tanto, no tiene tales efectos secundarios . int plusone(int x) { return x + 1; } x

today()no es transparente, como si lo evaluara y lo reemplazara por su valor (digamos, "Jan 1, 2001"), no obtendrá el mismo resultado que obtendrá si lo ejecuta mañana. Esto se debe a que depende de un estado (la fecha).

En idiomas sin efectos secundarios, como Haskell , podemos sustituir iguales por iguales: es decir, si x == yentonces f(x) == f(y). Esta es una propiedad también conocida como idénticos indistinguibles . Estas propiedades no tienen por qué ser válidas en general para los lenguajes con efectos secundarios. Aun así, es importante limitar tales afirmaciones a la llamada igualdad de juicio, es decir, la igualdad de los términos tal como los prueba el sistema, sin incluir la equivalencia de tipos definida por el usuario. Por ejemplo, si B f(A x)y el tipo Aha anulado la noción de igualdad, por ejemplo, haciendo que todos los términos sean iguales, entonces es posible tener x == yy aún encontrar f(x) != f(y). Esto se debe a que sistemas como Haskell no verifican que las funciones definidas en tipos con relaciones de equivalencia definidas por el usuario estén bien definidas con respecto a esa equivalencia. Así, la transparencia referencial se limita a tipos sin relaciones de equivalencia. La extensión de la transparencia referencial a las relaciones de equivalencia definidas por el usuario se puede hacer, por ejemplo, con un tipo de identidad Martin-Lof, pero requiere un sistema de tipificación dependiente como en Agda , Coq o Idris .

Contraste con la programación imperativa

Si la sustitución de una expresión por su valor es válida solo en un cierto punto de la ejecución del programa, entonces la expresión no es referencialmente transparente. La definición y el orden de estos puntos de secuencia son la base teórica de la programación imperativa y parte de la semántica de un lenguaje de programación imperativo.

Sin embargo, debido a que una expresión referencialmente transparente puede evaluarse en cualquier momento, no es necesario definir puntos de secuencia ni garantía alguna del orden de evaluación. La programación realizada sin estas consideraciones se denomina programación puramente funcional .

Una ventaja de escribir código en un estilo referencialmente transparente es que, dado un compilador inteligente, el análisis de código estático es más fácil y es posible realizar mejores transformaciones que mejoran el código automáticamente. Por ejemplo, al programar en C, habrá una penalización de rendimiento por incluir una llamada a una función costosa dentro de un bucle, incluso si la llamada a la función se puede mover fuera del bucle sin cambiar los resultados del programa. El programador se vería obligado a realizar el movimiento manual del código de la llamada, posiblemente a expensas de la legibilidad del código fuente. Sin embargo, si el compilador puede determinar que la llamada a la función es referencialmente transparente, puede realizar esta transformación automáticamente.

La principal desventaja de los lenguajes que imponen transparencia referencial es que hacen que la expresión de operaciones que se ajustan naturalmente a un estilo de programación imperativo de secuencia de pasos sea más incómoda y menos concisa. Estos lenguajes a menudo incorporan mecanismos para facilitar estas tareas al tiempo que conservan la calidad puramente funcional del lenguaje, como las gramáticas y las mónadas de cláusulas definidas .

Otro ejemplo

Como ejemplo, usemos dos funciones, una que es referencialmente transparente y la otra que es referencialmente opaca: 

int g = 0;

int rt(int x) {
  return x + 1;
}

int ro(int x) {
  g++;
  return x + g;
}

La función rtes referencialmente transparente, lo que significa que si x == yentonces rt(x) == rt(y). Por ejemplo, rt(6) = 7. Sin embargo, no podemos decir nada de eso roporque usa una variable global que modifica.

La opacidad referencial de rodificulta el razonamiento sobre los programas. Por ejemplo, digamos que deseamos razonar sobre la siguiente afirmación: 

int i = ro(x) + ro(y) * (ro(x) - ro(x));

Uno puede tener la tentación de simplificar esta afirmación para: 

int i = ro(x) + ro(y) * 0;
int i = ro(x) + 0;
int i = ro(x);

Sin embargo, esto no funcionará roporque cada aparición de se ro(x)evalúa con un valor diferente. Recuerde que el valor de retorno de rose basa en un valor global que no se pasa y que se modifica en cada llamada a ro. Esto significa que las identidades matemáticas como x - x = 0 ya no son válidas.

Tales identidades matemáticas se mantendrán para funciones referencialmente transparentes como rt.

Sin embargo, se puede utilizar un análisis más sofisticado para simplificar la declaración a: 

int tmp = g; int i = x + tmp + 1 + (y + tmp + 2) * (x + tmp + 3 - (x + tmp + 4)); g = g + 4;
int tmp = g; int i = x + tmp + 1 + (y + tmp + 2) * (x + tmp + 3 - x - tmp - 4)); g = g + 4;
int tmp = g; int i = x + tmp + 1 + (y + tmp + 2) * (-1); g = g + 4;
int tmp = g; int i = x + tmp + 1 - y - tmp - 2; g = g + 4;
int i = x - y - 1; g = g + 4;

Esto requiere más pasos y requiere un grado de conocimiento del código que no es factible para la optimización del compilador.

Por lo tanto, la transparencia referencial nos permite razonar sobre nuestro código, lo que conducirá a programas más robustos, la posibilidad de encontrar errores que no podríamos esperar encontrar mediante las pruebas y la posibilidad de ver oportunidades de optimización .

Ver también

Referencias

enlaces externos