comprensión transparencia referencial

Question

En general, tengo un dolor de cabeza porque algo está mal con mi razonamiento:

1. Para 1 juego de argumentos, la función referencial transparente siempre devolverá 1 conjunto de valores de salida.

2. eso significa que dicha función podría representarse como una tabla de verdad (una tabla donde se especifica 1 conjunto de parámetros de salida para 1 conjunto de argumentos).

3. que hace que la lógica detrás de este tipo de funciones es combinatoria (en contraposición a secuencial)

4. que significa que con lenguaje funcional puro (que tiene sólo funciones RT) es posible describir única lógica combinacional.

La última afirmación se deriva de este razonamiento, pero obviamente es falsa; eso significa que hay un error en el razonamiento. [pregunta: ¿dónde está el error en este razonamiento?]

UPD2. Ustedes, muchachos, dicen muchas cosas interesantes, pero no responden mi pregunta. Lo definí más explícitamente ahora. Perdón por arruinar la definición de la pregunta!

Answer 1

El error en su razonamiento es el siguiente:
"eso significa que dicha función podría representarse como una tabla de verdad".

Usted concluye que desde un lenguaje funcional es propiedad de la transparencia referencial. Hasta ahora la conclusión sonaría plausible, pero Usted supervisa que una función puede aceptar colecciones como entrada y procesarlas en contraste con las entradas fijas de una puerta lógica.

¡Por lo tanto, una función no es igual a una puerta lógica, sino más bien un plan de construcción de una puerta lógica de este tipo, en función de la entrada real (en tiempo de ejecución determinada)!

Para comentar su comentario: Los lenguajes funcionales pueden, aunque sean sin estado, implementar una máquina de estado construyendo los estados desde cero cada vez que se accede a ellos.

Answer 2

Por lo que yo entiendo, la transparencia referencial solo significa: una función determinada siempre arrojará el mismo resultado cuando se invoque con los mismos argumentos. Entonces, las funciones matemáticas que aprendió en la escuela son referencialmente transparentes.

Un idioma que podría consultar para aprender cómo se hacen las cosas en un lenguaje puramente funcional sería Haskell. Hay formas de usar "posibilidades de almacenamiento actualizable" como el Reader Monad, y el State Monad por ejemplo. Si está interesado en estructuras de datos puramente funcionales, Okasaki podría ser una buena lectura.

Y sí, tienes razón: el orden de evaluación en un lenguaje puramente funcional como haskell no importa en idiomas no funcionales, porque si no hay efectos secundarios, no hay razón para hacer algo antes/después algo más, a menos que la entrada de uno dependa de la salida del otro, o medios como mónadas entren en juego.

No sé realmente sobre la pregunta de la tabla de verdad.

Answer 3

Edit: Aunque aparentemente me perdí la diana en la pregunta real, creo que mi respuesta es bastante buena, así que lo estoy guardando :-) (ver abajo).

Supongo que una forma más concisa de expresar la pregunta podría ser: ¿puede un lenguaje puramente funcional calcular algo que es imperativo?

En primer lugar, supongamos que tomó un lenguaje imperativo como C y lo hizo para que no pueda alterar las variables después de definirlas. Por ejemplo:

int i; 

for (i = 0; // okay, that's one assignment 
    i < 10; // just looking, that's all 
    i++) // BUZZZ! Sorry, can't do that! 

Bueno, ahí va su lazo for. ¿Podemos mantener nuestro loop while?

while (i < 10) 

Claro, pero no es muy útil. i no se puede cambiar, por lo que se ejecutará para siempre o no se ejecutará en absoluto.

¿Qué tal la recursividad? Sí, usted tiene que mantener la recursividad, y sigue siendo un montón de utilidad:

int sum(int *items, unsigned int count) 
{ 
    if (count) { 
     // count the first item and sum the rest 
     return *items + sum(items + 1, count - 1); 
    } else { 
     // no items 
     return 0; 
    } 
} 

Ahora, con funciones, que no alteran el estado, pero las variables puede, además, variar. Una vez que una variable pasa a nuestra función, está bloqueada. Sin embargo, podemos llamar a la función nuevamente (recursividad), y es como obtener un nuevo conjunto de variables (las antiguas siguen siendo las mismas). Aunque hay varias instancias de items y count, sum((int[]){1,2,3}, 3) siempre evaluará a 6, por lo que puede reemplazar esa expresión con 6 si lo desea.

¿Todavía podemos hacer lo que queramos? No estoy 100% seguro, pero creo que la respuesta es "sí". Sin dudas, puedes si tienes cierres.

---

Lo tienes todo. La idea es que una vez que se define una variable, no se puede redefinir. Una expresión referencialmente transparente, dadas las mismas variables, siempre produce el mismo valor de resultado.

Recomiendo buscar en Haskell, un lenguaje puramente funcional. Haskell no tiene un operador de "asignación", estrictamente hablando. Por ejemplo:

my_sum numbers = ??? where 
    i  = 0 
    total = 0 

Aquí, no puede escribir un "bucle for" que incrementa i y el total a medida que avanza. Todo no esta perdido. Sólo tiene que utilizar la recursividad para seguir recibiendo nueva i s y total s:

my_sum numbers = f 0 0 where 
    f i total = 
     if i < length numbers 
      then f i' total' 
      else total 
     where 
      i' = i+1 
      total' = total + (numbers !! i) 

(Tenga en cuenta que esta es una manera estúpida para sumar una lista en Haskell, pero demuestra un método de hacer frente a una sola tarea.)

Ahora, considere el código de aspecto altamente imperativo:

main = do 
    a <- readLn 
    b <- readLn 
    print (a + b) 

es el azúcar sintáctica realidad para:

La idea es que, en lugar de que main sea una función que consta de una lista de sentencias, main es una acción IO que ejecuta Haskell, y las acciones se definen y encadenan junto con operaciones de vinculación. Además, una acción que no hace nada, que produce un valor arbitrario, se puede definir con la función return.

Tenga en cuenta que vincular y devolver no son específicos de las acciones. Se pueden usar con cualquier tipo que se llame a sí mismo una Mónada para hacer todo tipo de cosas funky.

Para aclarar, considere readLn. readLn es una acción que, si se ejecuta, leerá una línea de entrada estándar y arrojará su valor analizado.Para hacer algo con ese valor, no se puede almacenar en una variable, ya que violaría transparencia referencial:

a = readLn 

Si esto se permite, el valor de un dependería del mundo y sería diferente cada vez llamamos readLn, lo que significa readLn no sería referencialmente transparente.

En su lugar, se unen la acción readLn a una función que se ocupa de la acción, produciendo una nueva acción, así:

readLn >>= (\x -> print (x + 1)) 

El resultado de esta expresión es un valor de acción. Si Haskell se baja del sofá y realiza esta acción, leerá un número entero, lo incrementará e imprimirá. Al vincular el resultado de una acción a una función que hace algo con el resultado, obtenemos transparencia referencial mientras jugamos en el mundo del estado.

Answer 4

Aquí es mi puñalada en responder a la pregunta:

Cualquier sistema puede ser descrito como una función combinatoria, grande o pequeña.

No hay nada de malo en el razonamiento de que las funciones puras solo pueden tratar con la lógica combinatoria; es cierto, solo que los lenguajes funcionales ocultan eso de usted en mayor o menor medida.

Incluso podría describir, por ejemplo, el funcionamiento de un motor de juego como una tabla de verdad o una función combinatoria.

Puede tener una función determinista que adopta "el estado actual de todo el juego" como la RAM ocupada por el motor del juego y la entrada del teclado, y devuelve "el estado del juego un cuadro más tarde". El valor de retorno estaría determinado por las combinaciones de los bits en la entrada.

Por supuesto, en cualquier función significativa y sensata, la entrada se procesa en bloques de enteros, decimales y booleanos, pero las combinaciones de los bits en esos valores siguen determinando la salida de su función.

Tenga en cuenta también que la lógica digital básica se puede describir en las tablas de verdad. La única razón por la que no se hace para algo más que, por ejemplo, la aritmética en enteros de 4 bits, es porque el tamaño de la tabla de verdad crece exponencialmente.

Answer 5

Question: where is error in this reasoning?

Una función referencialmente transparente podría requerir un tabla de verdad infinita para representar su comportamiento. Tendrá dificultades para diseñar un circuito infinito en lógica combinatoria.

Otro error: el comportamiento de la lógica secuencial se puede representar puramente funcional como una función de estados a estados. El hecho de que en la implementación estos estados ocurran secuencialmente en el tiempo no impide que uno defina una función puramente referencialmente transparente que describe cómo el estado evoluciona con el tiempo.