Transparencia referencial

En informática, la transparencia referencial y la opacidad referencial son propiedades de partes de 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: su valor 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 llama 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. Una característica definitoria de la programación funcional es que solo permite funciones referencialmente transparentes. Otros lenguajes de programación pueden proporcionar medios para garantizar selectivamente la transparencia referencial. Algunos lenguajes de programación funcionales exigen 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 probar la corrección, simplificar un algoritmo, ayudar a modificar el código sin romperlo u optimizar el código mediante la memorización, la eliminación de subexpresiones comunes, la evaluación diferida o la paralelización.

Historia

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

Un modo de contención φ es referencialmente transparente si, cuando una ocurrencia de un término singular t es puramente referential en un término o frase י(t), es puramente referential también en el término que contiene o frase φ(actual(t)).

El término apareció en su uso contemporáneo de la informática, en la discusión de las variables en los lenguajes de programación, en el conjunto seminal de notas de conferencias de Christopher Strachey Conceptos fundamentales en lenguajes de programación (1967). Las notas de la lección hacían referencia a Word and Object 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 Source podría identificar un archivo de disco en particular, el teclado, etc. Incluso con valores idénticos de Source, los valores de retorno sucesivos serán diferentes. Por lo tanto, la función GetInput() no es ni 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. Luego, esto 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 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 * 5 puede ser reemplazado 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 x en particular.

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

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

En lenguajes sin efectos secundarios, como Haskell, podemos sustituir iguales por iguales: es decir, si x == y entonces f(x) == f(y). Esta es una propiedad también conocida como idénticos indistinguibles. Tales propiedades no tienen por qué ser válidas en general para 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 probados por el sistema, sin incluir la equivalencia definida por el usuario para los tipos. Por ejemplo, si B f(A x) y el tipo A ha anulado la noción de igualdad, p. haciendo todos los términos iguales, entonces es posible tener x == y y aun así 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 tipificado de forma 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 ninguna garantía 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 se pueden realizar automáticamente mejores transformaciones para mejorar el código. Por ejemplo, al programar en C, habrá una penalización de rendimiento por incluir una llamada a una función costosa dentro de un ciclo, incluso si la llamada a la función se puede mover fuera del ciclo sin cambiar los resultados del programa. El programador se vería obligado a realizar un movimiento de código manual 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 la transparencia referencial es que hacen que la expresión de operaciones que naturalmente se ajustan a un estilo de programación imperativo de secuencia de pasos sea más incómoda y menos concisa. Dichos lenguajes a menudo incorporan mecanismos para facilitar estas tareas al tiempo que conservan la calidad puramente funcional del lenguaje, como las gramáticas de cláusulas definidas y las mónadas.

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) {} retorno x + 1;}int #()int x) {} g++; retorno x + g;}

La función rt es referencialmente transparente, lo que significa que si x == y entonces rt(x) == rt(y). Por ejemplo, rt(6) = 7. Sin embargo, no podemos decir tal cosa para ro porque usa una variable global que modifica.

La opacidad referencial de ro dificulta el razonamiento sobre programas. Por ejemplo, supongamos que deseamos razonar sobre la siguiente afirmación:

int i = #()x) + #()Sí.) * ()#()x) - #()x));

Uno puede verse tentado a simplificar esta declaración a:

int i = #()x) + #()Sí.) * 0;int i = #()x) + 0;int i = #()x);

Sin embargo, esto no funcionará para ro porque cada aparición de ro(x) se evalúa como un valor diferente. Recuerda que el valor de retorno de ro se 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 se cumplen.

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

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

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

Esto requiere más pasos y requiere un grado de comprensión 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 podíamos esperar al realizar pruebas y la posibilidad de ver oportunidades de optimización.