Estoy comenzando mi primer año (en la universidad) en Ciencias de la Computación el próximo año y escribo principalmente en C (si eso es importante). He intentado buscar, pero la mayor parte de lo que encuentro supone conocimiento del cálculo lambda. ¿Por qué el cálculo lambda se considera mucho más útil que el cálculo de una sola variable en la programación? ¿Existe una relación entre las expresiones lambda y los programas funcionales? ¿Fue el trabajo de Alonzo Church sobre el cálculo lambda lo que influyó en el desarrollo de los lenguajes de programación?
Todos los que están fuera de la escuela siguen hablando de ello y no tengo idea de qué hablarán, aunque estoy ansioso por aprenderlo y ver cómo se relaciona directamente con mi programación y mi comprensión de los lenguajes de programación.
fuente
Respuestas:
El cálculo Lambda es interesante, elegante y facilita mucho la comprensión de los lenguajes de programación funcionales. Sin embargo, no encontrará el LC en un curso típico de licenciatura de CS, por lo que no tiene que aprenderlo en este momento: recomendaría experimentar primero con lenguajes funcionales antes de volver a visitar el cálculo Lambda. Creo que OCaml es un buen punto de partida en la programación funcional para un programador en C, y que Scheme es un buen punto de partida para sumergirse en el cálculo Lambda.
El cálculo Lambda no está asociado con el cálculo (que debería llamarse análisis en su lugar). En general, un cálculo es un "sistema formal", es decir, un conjunto de reglas para hacer algo. Mientras que el cálculo diferencial proporciona reglas con respecto al cambio de valores, las reglas del cálculo Lambda describen la computación misma. A partir de este conjunto de reglas muy básicas, podemos construir cálculos arbitrarios, representaciones de datos como booleanos, enteros o listas, e incluso controlar construcciones de flujo como condicionales o bucles. El LC es equivalente a las máquinas de Turing, pero cualquiera de los modelos tiene diferentes puntos fuertes.
El cálculo Lambda tuvo un inmenso impacto en los lenguajes de programación. El segundo lenguaje de alto nivel que se implementó fue Lisp, que puede entenderse como una codificación directa del LC en un lenguaje de programación. Esta "programación funcional" tiene un efecto inmenso en la evolución de los lenguajes de programación. Las características tales como funciones anónimas, punteros de función, cierres (funciones anidadas), recolección de basura, alcance variable, metaprogramación, avances en sistemas de tipos, inferencia de tipos, lenguajes interpretados, lenguajes dinámicamente escritos, programación orientada a objetos se deben en gran parte. a la rama de programación funcional de lenguajes de programación. Hay una broma de que cualquier nuevo lenguaje de programación (no académico) solo agrega características que Lisp ya ha tenido durante décadas.
Más allá de eso, el cálculo Lambda y otros cálculos relacionados son herramientas indispensables en la teoría del lenguaje de programación y en ciertas técnicas de construcción de compiladores.
Cualquier lenguaje que tenga funciones anónimas que se comporten como cierres y puedan transmitirse libremente de inmediato contiene una codificación del cálculo lambda. Las funciones anónimas corresponden a expresiones lambda, excepto que en las funciones LC siempre tienen exactamente un argumento. Sin embargo, cualquier lenguaje completo de Turing es equivalente al LC, por lo que el LC siempre se puede implementar sobre dichos lenguajes. Esto tiende a suceder en sistemas de coincidencia de reglas o formatos de configuración demasiado inteligentes, dando lugar a la "décima regla de Greenspun" (en broma, principalmente): " Cualquier programa C o Fortran suficientemente complicado contiene un ad hoc, especificado informalmente, lleno de errores , implementación lenta de la mitad de Common Lisp. "
fuente
x = fn (a, b, c) => a + b + c(tipoint * int * int -> int, invocaciónfn (1, 2, 3)) se puede transformar enx = fn a => fn b => fn c => a + b + c(tipoint -> int -> int -> int, invocación((x 1) 2) 3- parens opcional en ML). Ahora, en lugar de proporcionar los tres argumentos, solo podemos proporcionar dos:plus3 = x 1 2que tiene tipoint -> int. Esta es una aplicación parcial / curry.El cálculo Lambda no tiene nada que ver con el cálculo diferencial / integral. El cálculo en el sentido más genérico de la palabra solo significa un sistema de cálculo.
A un nivel muy alto, el cálculo lambda es un modelo de computación de la misma manera que una máquina de Turing es un modelo de computación. La razón por la cual los investigadores del lenguaje de programación estudian el cálculo lambda es porque, como modelo, tiene fuertes conexiones con métodos formales en matemáticas como la lógica y la teoría de categorías. Por lo tanto, los métodos de esos dominios se pueden aplicar al estudio de varios aspectos y extensiones del cálculo lambda que a su vez ayuda a diseñar mejores lenguajes de programación con ciertas propiedades.
La influencia más directa del cálculo lambda en los lenguajes de programación generalmente aparece en forma de funciones y cierres de primera clase. C no es compatible con los cierres, por lo que deberá explorar el concepto en un lenguaje de más alto nivel como Lisp, Python, Ruby, JavaScript, etc. Históricamente, Lisp se considera la primera implementación concreta del cálculo lambda como lenguaje de programación .
fuente