¿Por qué es más fácil razonar acerca de los lenguajes de programación y los programas que no tienen efectos secundarios?

7

Leí "The Why of Y" de Richard P. Gabriel . Es un artículo fácil de leer sobre el combinador de Y, que es bastante raro. El artículo comienza con la definición recursiva de la función factorial:

(letrec ((f (lambda (n)
              (if (< n 2) 1 (* n (f (- n 1)))))))
  (f 10))

Y explica que letrec se puede definir con un efecto secundario:

(let ((f #f))
  (set! f (lambda (n)
            (if (< n 2) 1 (* n (f (- n 1))))))
  (f 10))

Y el resto del artículo describe que también es posible definir letrec con el combinador Y:

(define (Y f)
  (let ((g (lambda (h)
             (lambda (x)
               ((f (h h)) x)))))
    (g g)))

(let ((f (Y (lambda (fact)
              (lambda (n)
                (if (< n 2) 1 (* n (fact (- n 1)))))))))
  (f 10))

Obviamente, esto es mucho más complicado que la versión con efecto secundario. La razón por la que es beneficioso preferir el combinador de Y sobre el efecto secundario está dada solo por la declaración:

  

Es más fácil razonar acerca de los lenguajes de programación y los programas que no tienen efectos secundarios.

Esto no se explica más. Intento encontrar una explicación.

    
pregunta ceving 13.12.2016 - 18:16

6 respuestas

12

Obviamente, puedes encontrar ejemplos de funciones puras increíblemente difíciles de leer que realizan los mismos cálculos que las funciones con efectos secundarios que son mucho más fáciles de leer. Especialmente cuando usas una transformación mecánica como un combinador en Y para llegar a una solución. Eso no es lo que se entiende por "más fácil de razonar".

La razón por la que es más fácil razonar acerca de las funciones sin efectos secundarios es que solo tiene que preocuparse por las entradas y salidas. Con los efectos secundarios, también debe preocuparse acerca de cuántas veces se llaman las funciones, en qué orden se llaman, qué datos se crean dentro de la función, qué datos se comparten y qué datos se copian. Y toda esa información para cualquier función que pueda llamarse interna a la función a la que está llamando, y recursivamente interna a esas funciones, etc.

Este efecto es mucho más fácil de ver en el código de producción con varias capas que en las funciones de ejemplo de juguete. En la mayoría de los casos, significa que puede confiar mucho más en la firma del tipo de una función. Realmente notará la carga de los efectos secundarios si realiza una programación puramente funcional por un tiempo y luego vuelve a ella.

    
respondido por el Karl Bielefeldt 21.01.2017 - 07:29
10

Una propiedad interesante de los idiomas sin efectos secundarios es que la introducción de paralelismo, concurrencia o asincronía no puede cambiar el significado del programa. Puede hacerlo más rápido. O puede hacerlo más lento. Pero no puede hacerlo mal.

Esto hace que sea trivial paralelizar automáticamente los programas. Tan trivial, de hecho, ¡que por lo general terminas con un paralelismo demasiado ! El equipo de GHC experimentó con la paralelización automática. Encontraron que incluso los programas simples podrían descomponerse en cientos, incluso miles de subprocesos. La sobrecarga de todos esos hilos superará cualquier aceleración potencial en varios órdenes de magnitud.

Entonces, para la paralelización automática de programas funcionales, el problema se convierte en "cómo agrupar pequeñas operaciones atómicas en tamaños útiles de piezas paralelas", a diferencia de los programas impuros, donde el problema es "¿cómo dividir grandes monolíticos?" Operaciones en tamaños útiles de piezas paralelas ". Lo bueno de esto es que lo primero se puede hacer heurísticamente (recuerde: si se equivoca, lo peor que puede suceder es que el programa se ejecute un poco más lento de lo que podría ser), mientras que lo segundo es equivalente a resolver la Detención. Problema (en el caso general), y si te equivocas, tu programa simplemente se bloqueará (¡si tienes suerte!) O devolverá resultados equivocados (en el peor de los casos).

    
respondido por el Jörg W Mittag 14.12.2016 - 00:04
6

Los lenguajes con efectos secundarios emplean análisis de aliasing para ver si hay una ubicación de memoria Es posible que tenga que volver a cargarse después de una llamada de función. Cuán conservador es este análisis depende del lenguaje.

Para C, esto tiene que ser bastante conservador, ya que el lenguaje no es de tipo seguro.

Para Java y C #, estos no tienen que ser tan conservadores debido a su mayor seguridad de tipos.

Ser demasiado conservador evita las optimizaciones de carga.

Tal análisis sería innecesario (o trivial según cómo lo veas) en un lenguaje sin efectos secundarios.

    
respondido por el Erik Eidt 13.12.2016 - 19:51
4

Siempre hay optimizaciones para aprovechar cualquier suposición que proporcione. Las operaciones de reordenamiento vienen a la mente.

Un ejemplo divertido que viene a la mente en realidad aparece en algunos lenguajes ensambladores más antiguos. En particular, MIPS tenía una regla de que la instrucción después de un salto condicional se ejecutó, independientemente de la rama que se tomó. Si no querías esto, pones un NOP después del salto. Esto se hizo debido a la forma en que se estructuró el canal MIPS. Hubo un bloqueo natural de 1 ciclo integrado en la ejecución del salto condicional, ¡así que también podrías hacer algo útil con ese ciclo!

Los compiladores a menudo buscan una operación que debe realizarse en ambas ramas y la deslizan en esa ranura, para obtener un poco más de rendimiento. Sin embargo, si un compilador no puede hacer eso, pero puede mostrar que la operación no tuvo efectos secundarios, el compilador podría pegarlo oportunamente en ese lugar. Por lo tanto, en una ruta, el código ejecutaría una instrucción más rápido. En el otro camino, no hay daño.

    
respondido por el Cort Ammon 13.12.2016 - 22:50
1

"letrec se puede definir con un efecto secundario ..." No veo ningún efecto secundario en su definición. Sí, utiliza set! , que es una forma típica de producir efectos secundarios en el Esquema, pero en este caso no hay ningún efecto secundario , ya que f es puramente local, no puede ser referenciado por cualquier función que no sea localmente. Por lo tanto, no es un efecto secundario como se ve desde cualquier alcance externo. Lo que este código hace hace es eliminar una limitación en el alcance del Esquema que, de manera predeterminada, no permite que una definición lambda se refiera a sí misma.

Algunos otros idiomas tienen declaraciones en las que una expresión utilizada para producir el valor de una constante puede referirse a la constante en sí misma. En tal lenguaje, se puede usar la definición equivalente exacta, pero claramente esto no produce un efecto secundario, ya que solo se usa una constante. Ver, por ejemplo, este programa equivalente de Haskell:

let f = \ n -> if n < 2 
                 then 1 
                 else n*(f (n-1)) 
        in (f 5)

(que se evalúa a 120).

Esto claramente no tiene efectos secundarios (como para que una función en Haskell tenga un efecto secundario, debe devolver su resultado envuelto en una Mónada, pero el tipo que se devuelve aquí es un tipo numérico), pero es estructuralmente idéntico código al código que usted cita.

    
respondido por el Periata Breatta 15.12.2016 - 17:20
0
  

Esto no se explica más. Intento encontrar una explicación.

Es algo que es inherente a muchos de nosotros que hemos depurado bases de código masivas, pero tienes que lidiar con una escala suficientemente grande en el nivel de supervisor durante un tiempo suficiente para apreciarlo. Es como entender la importancia de estar en posición en el póker. Inicialmente, no parece ser una ventaja tan útil durar al final de cada turno hasta que registre el historial de un millón de manos y se dé cuenta de que ganó mucho más dinero en posición que fuera.

Dicho esto, no estoy de acuerdo con la idea de que un cambio en una variable local sea un efecto secundario. Desde mi punto de vista, una función no causa efectos secundarios si no modifica nada fuera de su alcance, que cualquier cosa que toque y manipule no afectará nada debajo de la pila de llamadas o cualquier memoria o recurso que la función no adquirió. .

En general, lo más difícil de razonar en una base de código compleja a gran escala que no tiene el procedimiento de prueba más perfecto que se pueda imaginar es la administración de estado persistente, como todos los cambios a objetos granulares en un mundo de videojuegos a medida que avanza. a través de decenas de miles de funciones, mientras intentaba reducir entre una lista interminable de sospechosos, uno de los cuales causó la violación de un invariante en todo el sistema ("esto nunca debería suceder, ¿quién lo hizo?"). Si nunca se cambia nada fuera de una función, es posible que no pueda causar un mal funcionamiento central.

Por supuesto, esto no es posible hacerlo en todos los casos. Cualquier aplicación que actualice una base de datos almacenada en una máquina diferente está, por naturaleza, diseñada para causar efectos secundarios, así como cualquier aplicación diseñada para cargar y escribir archivos. Pero hay muchas más cosas que podemos hacer sin efectos secundarios en muchas funciones y muchos programas si, por ejemplo, tuviéramos una gran biblioteca de estructuras de datos inmutables y abrazáramos aún más esta mentalidad.

Curiosamente, John Carmack se ha subido al carro de LISP e inmutabilidad a pesar de comenzar en los días de la codificación C más micro sintonizada. Me he encontrado haciendo algo similar, aunque sigo usando mucho C. Esa es la naturaleza de los pragmáticos, creo, que han pasado años depurando y tratando de razonar sobre sistemas complejos a gran escala en su conjunto desde un nivel de supervisor. Incluso los que son sorprendentemente robustos y carecen de una gran cantidad de errores pueden dejarte con la inquietante sensación de que algo malo está acechando a la vuelta de la esquina si se modifica mucho el estado persistente complejo entre el gráfico de llamadas de función más complejo e interconectado. Los millones de líneas de código. Incluso si cada interfaz individual se prueba con una prueba unitaria y todas pasan, también existe la sensación incómoda de lo que podría suceder con los estados centrales con un caso de entrada no anticipado con todas las innumerables llamadas de función interdependientes entre interfaces si la lógica de la aplicación gira en torno al lado en cascada. Efectos a los estados más centrales y persistentes.

En la práctica, a menudo encuentro que la programación funcional hace que sea más difícil comprender una función. Todavía hace girar mi cerebro en giros y nudos, especialmente con lógica recursiva compleja. Pero toda la sobrecarga intelectual asociada con el cálculo de un par de funciones escritas en un lenguaje funcional se ve contrarrestada por la de un sistema complejo con estados persistentes cambiados en decenas de miles de funciones, donde cada función que causa efectos secundarios se suma al total complejidad de razonamiento sobre la corrección de todo el sistema en su conjunto.

Tenga en cuenta que no necesita un lenguaje funcional puro para que las funciones eviten los efectos secundarios. Los estados locales cambiados en una función no cuentan como un efecto secundario, como una variable de contador de bucle for local para una función no cuenta como un efecto secundario. Incluso hoy escribo el código C con el objetivo de evitar los efectos secundarios cuando sea posible y me he ideado una biblioteca de estructuras de datos inmutables y seguras para subprocesos que pueden modificarse parcialmente mientras que el resto de los datos se copian de forma superficial, y me ha ayudado a mucho para razonar acerca de la corrección de mi sistema. Estoy totalmente en desacuerdo con el autor en ese sentido. Al menos en C y C ++ en el software de misión crítica, una función puede estar documentando que no tiene efectos secundarios si no toca nada que pueda afectar al mundo fuera de la función.

    
respondido por el user204677 01.12.2017 - 15:20

Lea otras preguntas en las etiquetas