¿Qué es la transparencia referencial?

38

Lo he visto en paradigmas imperativos

f (x) + f (x)

podría no ser lo mismo que:

2 * f (x)

Pero en un paradigma funcional debería ser lo mismo. He tratado de implementar ambos casos en Python y Scheme , pero para mí se ven bastante directos.

¿Cuál sería un ejemplo que pudiera señalar la diferencia con la función dada?

Asgard
fuente
77
Puede, y a menudo lo hace, escribir funciones referencialmente transparentes en python. La diferencia es que el idioma no lo impone.
Karl Bielefeldt
55
en C y por igual: f(x++)+f(x++)podría no ser la misma que 2*f(x++)(? en C es especialmente bonito cuando cosas como que se oculta dentro de macros - hizo que me rompí la nariz en que se apuesta)
mosquito
En mi opinión, el ejemplo de @ gnat es la razón por la cual los lenguajes orientados funcionalmente como R emplean la referencia por paso y evitan explícitamente las funciones que modifican sus argumentos. En R, al menos, en realidad puede ser difícil eludir estas restricciones (al menos, de una manera estable y portátil) sin profundizar en el complicado sistema de entornos y espacios de nombres y rutas de búsqueda del lenguaje.
shadowtalker
44
@ssdecontrol: en realidad, cuando tiene transparencia referencial, el paso por valor y el paso por referencia siempre producen exactamente el mismo resultado, por lo que no importa cuál use el lenguaje. Los lenguajes funcionales se especifican con frecuencia con algo similar al paso por valor para mayor claridad semántica, pero sus implementaciones a menudo usan paso por referencia para el rendimiento (o incluso ambos, dependiendo de cuál sea más rápido para el contexto dado).
Jörg W Mittag
44
@gnat: En particular, f(x++)+f(x++)puede ser absolutamente cualquier cosa, ya que invoca un comportamiento indefinido. Pero eso no está realmente relacionado con la transparencia referencial, lo que no ayudaría para esta convocatoria, está 'indefinido' para funciones referencialmente transparentes como sin(x++)+sin(x++)también en. Podría ser 42, podría formatear su disco duro, podría tener demonios volando de la nariz del usuario ...
Christopher Creutzig

Respuestas:

62

La transparencia referencial, referida a una función, indica que puede determinar el resultado de aplicar esa función solo observando los valores de sus argumentos. Puede escribir funciones referencialmente transparentes en cualquier lenguaje de programación, por ejemplo, Python, Scheme, Pascal, C.

Por otro lado, en la mayoría de los idiomas también puede escribir funciones transparentes no referenciales. Por ejemplo, esta función de Python:

counter = 0

def foo(x):
  global counter

  counter += 1
  return x + counter

no es referencialmente transparente, de hecho llama

foo(x) + foo(x)

y

2 * foo(x)

producirá diferentes valores, para cualquier argumento x. La razón de esto es que la función usa y modifica una variable global, por lo tanto, el resultado de cada invocación depende de este estado cambiante, y no solo del argumento de la función.

Haskell, un lenguaje puramente funcional, separa estrictamente la evaluación de expresiones en la que se aplican funciones puras y que siempre es referencialmente transparente, de la ejecución de la acción (procesamiento de valores especiales), que no es referencialmente transparente, es decir, ejecutar la misma acción puede tener cada vez que Resultado diferente.

Entonces, para cualquier función de Haskell

f :: Int -> Int

y cualquier número entero x, siempre es cierto que

2 * (f x) == (f x) + (f x)

Un ejemplo de una acción es el resultado de la función de biblioteca getLine:

getLine :: IO String

Como resultado de la evaluación de expresiones, esta función (en realidad una constante) produce en primer lugar un valor puro de tipo IO String. Los valores de este tipo son valores como cualquier otro: puede pasarlos, colocarlos en estructuras de datos, componerlos usando funciones especiales, etc. Por ejemplo, puede hacer una lista de acciones de esta manera:

[getLine, getLine] :: [IO String]

Las acciones son especiales, ya que puede indicarle al tiempo de ejecución de Haskell que las ejecute escribiendo:

main = <some action>

En este caso, cuando se inicia su programa Haskell, el tiempo de ejecución recorre la acción vinculada mainy la ejecuta , posiblemente produciendo efectos secundarios. Por lo tanto, la ejecución de la acción no es referencialmente transparente porque ejecutar la misma acción dos veces puede producir resultados diferentes dependiendo de lo que el tiempo de ejecución obtenga como entrada.

Gracias al sistema de tipos de Haskell, una acción nunca se puede usar en un contexto donde se espera otro tipo, y viceversa. Entonces, si desea encontrar la longitud de una cadena, puede usar la lengthfunción:

length "Hello"

devolverá 5. Pero si desea encontrar la longitud de una cadena leída desde el terminal, no puede escribir

length (getLine)

porque obtiene un error de tipo: lengthespera una entrada de la lista de tipos (y una Cadena es, de hecho, una lista) pero getLinees un valor de tipo IO String(una acción). De esta manera, el sistema de tipos asegura que un valor de acción como getLine(cuya ejecución se lleva a cabo fuera del lenguaje central y que puede ser transparente no referencial) no puede ocultarse dentro de un valor de tipo de no acción Int.

EDITAR

Para responder a una pregunta exizt, aquí hay un pequeño programa Haskell que lee una línea desde la consola e imprime su longitud.

main :: IO () -- The main program is an action of type IO ()
main = do
          line <- getLine
          putStrLn (show (length line))

La acción principal consta de dos subacciones que se ejecutan secuencialmente:

  1. getlinede tipo IO String,
  2. el segundo se construye evaluando la función putStrLnde tipo String -> IO ()en su argumento.

Más precisamente, la segunda acción es construida por

  1. vinculante lineal valor leído por la primera acción,
  2. evaluar las funciones puras length(calcular la longitud como un entero) y luego show(convertir el entero en una cadena),
  3. construyendo la acción aplicando la función putStrLnal resultado de show.

En este punto, se puede ejecutar la segunda acción. Si ha escrito "Hola", imprimirá "5".

Tenga en cuenta que si obtiene un valor de una acción usando la <-notación, solo puede usar ese valor dentro de otra acción, por ejemplo, no puede escribir:

main = do
          line <- getLine
          show (length line) -- Error:
                             -- Expected type: IO ()
                             --   Actual type: String

porque show (length line)tiene tipo Stringmientras que la notación do requiere que una acción ( getLinede tipo IO String) sea seguida por otra acción (por ejemplo, putStrLn (show (length line))de tipo IO ()).

EDITAR 2

La definición de Jörg W Mittag de transparencia referencial es más general que la mía (he votado su respuesta). He usado una definición restringida porque el ejemplo en la pregunta se enfoca en el valor de retorno de las funciones y quería ilustrar este aspecto. Sin embargo, RT en general se refiere al significado de todo el programa, incluidos los cambios en el estado global y las interacciones con el entorno (IO) causadas por la evaluación de una expresión. Entonces, para una definición correcta y general, debe referirse a esa respuesta.

Giorgio
fuente
10
¿Puede el votante sugerir cómo puedo mejorar esta respuesta?
Giorgio
Entonces, ¿cómo se puede obtener la longitud de una cadena leída desde la terminal en Haskell?
sbichenko
2
Esto es extremadamente pedante, pero en aras de la integridad, no es el sistema de tipos de Haskell el que garantiza que las acciones y las funciones puras no se mezclen; Es el hecho de que el lenguaje no proporciona ninguna función impura a la que pueda llamar directamente. En realidad, puede implementar el IOtipo de Haskell con bastante facilidad en cualquier idioma con lambdas y genéricos, pero como cualquiera puede llamar printlndirectamente, la implementación IOno garantiza la pureza; sería simplemente una convención.
Doval
Quise decir que (1) todas las funciones son puras (por supuesto, son puras porque el lenguaje no proporciona ninguna impura, aunque hasta donde yo sé hay algunos mecanismos para evitar eso), y (2) funciones puras y Las acciones impuras tienen diferentes tipos, por lo que no se pueden mezclar. Por cierto, ¿qué quieres decir con llamar directamente ?
Giorgio
66
Su punto sobre getLineno ser referencialmente transparente es incorrecto. Está presentando getLinecomo si se evalúa o se reduce a una Cadena, cuya Cadena particular depende de la entrada del usuario. Esto es incorrecto. IO Stringno contiene una cadena más de Maybe Stringlo que lo hace. IO Stringes una receta para tal vez, posiblemente obtener una Cadena y, como expresión, tan pura como cualquier otra en Haskell.
LuxuryMode
25
def f(x): return x()

from random import random
f(random) + f(random) == 2*f(random)
# => False

Sin embargo, eso no es lo que significa Transparencia referencial. RT significa que puede reemplazar cualquier expresión en el programa con el resultado de evaluar esa expresión (o viceversa) sin cambiar el significado del programa.

Tomemos, por ejemplo, el siguiente programa:

def f(): return 2

print(f() + f())
print(2)

Este programa es referencialmente transparente. Puedo reemplazar una o ambas ocurrencias de f()con 2y todavía funcionará igual:

def f(): return 2

print(2 + f())
print(2)

o

def f(): return 2

print(f() + 2)
print(2)

o

def f(): return 2

print(2 + 2)
print(f())

Todos se comportarán igual.

Bueno, en realidad, hice trampa. Debería poder reemplazar la llamada a printcon su valor de retorno (que no tiene ningún valor) sin cambiar el significado del programa. Sin embargo, claramente, si solo elimino las dos printdeclaraciones, el significado del programa cambiará: antes, imprimió algo en la pantalla, después no lo hace. I / O no es referencialmente transparente.

La regla general es: si puede reemplazar cualquier expresión, subexpresión o llamada de subrutina con el valor de retorno de esa expresión, subexpresión o llamada de subrutina en cualquier parte del programa, sin que el programa cambie su significado, entonces tiene referencial transparencia. Y lo que esto significa, prácticamente hablando, es que no puede tener ninguna E / S, no puede tener ningún estado mutable, no puede tener ningún efecto secundario. En cada expresión, el valor de la expresión debe depender únicamente de los valores de las partes constituyentes de la expresión. Y en cada llamada de subrutina, el valor de retorno debe depender únicamente de los argumentos.

Jörg W Mittag
fuente
44
"no puede tener ningún estado mutable": Bueno, puede tenerlo si está oculto y no influye en el comportamiento observable de su código. Piense, por ejemplo, en la memorización.
Giorgio
44
@Giorgio: Esto es quizás subjetivo, pero diría que los resultados almacenados en caché no son realmente "estado mutable" si están ocultos y no tienen efectos observables. La inmutabilidad es siempre una abstracción implementada sobre hardware mutable; con frecuencia es proporcionado por el lenguaje (dando la abstracción de "un valor" incluso si el valor puede moverse entre registros y ubicaciones de memoria durante la ejecución, y puede desaparecer una vez que se sabe que nunca se volverá a usar), pero no es menos válido cuando es proporcionado por una biblioteca o cualquier otra cosa. (Suponiendo que se implemente correctamente, por supuesto.)
ruakh
1
+1 Me gusta mucho el printejemplo. Quizás una forma de ver esto, es que lo que está impreso en la pantalla es parte del "valor de retorno". Si puede reemplazar printcon su función el valor de retorno y la escritura equivalente en el terminal, el ejemplo funciona.
Pierre Arlaud
1
@Giorgio El uso del espacio / tiempo no puede considerarse un efecto secundario a efectos de transparencia referencial. Eso haría 4y 2 + 2no intercambiable, ya que tienen diferentes tiempos de funcionamiento, y el punto central de la transparencia referencial es que se puede sustituir una expresión con lo que se evalúa como. La consideración importante sería la seguridad del hilo.
Doval
1
@overexchange: Transparencia referencial significa que puede reemplazar cada subexpresión con su valor sin cambiar el significado del programa. listOfSequence.append(n)rendimientos None, por lo que debe ser capaz de reemplazar a cada llamada listOfSequence.append(n)con Nonesin cambiar el sentido de su programa. ¿Puedes hacer eso? Si no, entonces no es referencialmente transparente.
Jörg W Mittag
1

Parte de esta respuesta se toma directamente de un tutorial inacabado sobre programación funcional , alojado en mi cuenta de GitHub:

Se dice que una función es referencialmente transparente si, dados los mismos parámetros de entrada, siempre produce la misma salida (valor de retorno). Si se busca una razón de ser para la programación funcional pura, la transparencia referencial es un buen candidato. Cuando se razona con fórmulas en álgebra, aritmética y lógica, esta propiedad, también llamada sustituibilidad de iguales por iguales, es tan fundamental que generalmente se da por sentado ...

Considere un ejemplo simple:

x = 42

En un lenguaje funcional puro, el lado izquierdo y derecho del signo igual son sustituibles entre sí en ambos sentidos. Es decir, a diferencia de un lenguaje como C, la notación anterior realmente afirma una igualdad. Una consecuencia de esto es que podemos razonar sobre el código del programa al igual que las ecuaciones matemáticas.

De la wiki de Haskell :

Los cálculos puros producen el mismo valor cada vez que se invocan. Esta propiedad se llama transparencia referencial y hace posible realizar un razonamiento equitativo en el código ...

Para contrastar esto, el tipo de operación realizada por lenguajes tipo C a veces se denomina asignación destructiva .

El término puro se usa a menudo para describir una propiedad de expresiones, relevante para esta discusión. Para que una función se considere pura,

  • no está permitido exhibir ningún efecto secundario, y
  • debe ser referencialmente transparente.

De acuerdo con la metáfora de la caja negra, que se encuentra en numerosos libros de texto matemáticos, los elementos internos de una función están completamente sellados del mundo exterior. Un efecto secundario es cuando una función o expresión viola este principio, es decir, el procedimiento puede comunicarse de alguna manera con otras unidades del programa (por ejemplo, compartir e intercambiar información).

En resumen, la transparencia referencial es imprescindible para que las funciones se comporten como verdaderas funciones matemáticas también en la semántica de los lenguajes de programación.

yesthisisuser
fuente
esto parece abrirse con una copia palabra por palabra tomada de aquí : "Se dice que una función es referencialmente transparente si, dados los mismos parámetros de entrada, siempre produce la misma salida ..." Stack Exchange tiene reglas para el plagio , son eres consciente de esto? "El plagio es el acto desalmado de copiar fragmentos del trabajo de otra persona, poner su nombre en él y pasar a ser el autor original ..."
mosquito
3
Escribí esa página.
yesthisisuser
Si este es el caso, considere hacer que parezca menos plagio, porque los lectores no tienen forma de saberlo. ¿Sabes cómo hacer esto en SE? 1) Usted hace referencia a la fuente de los originales, como "Como (he escrito) [here](link to source)..." seguido de 2) el formato correcto de las comillas (use comillas, o mejor aún, > símbolo para eso). Tampoco pasaría nada si además de dar una orientación general, las direcciones de responder a la pregunta concreta preguntó acerca de, en este caso sobre f(x)+f(x)/ 2*f(x), ver Cómo Answer - de lo contrario puede parecer que es simplemente la publicidad de su página
mosquito
1
Teóricamente, entendí esta respuesta. Pero, prácticamente siguiendo estas reglas, necesito devolver la lista de secuencias de granizo en este programa . ¿Cómo hago esto?
Intercambio excesivo