¿Cuál es la relación entre el cálculo lambda y los lenguajes de programación? [cerrado]

13

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.

RonaldMunodawafa
fuente
2
Esta pregunta se responderá mejor en cs.stackexchange.com .
davidk01
@ChrisF. Quizás esta pregunta se ajuste mejor a uno de los sitios de informática. Si no, traté de reducirlo, y me pregunto si se puede volver a abrir en su forma actual.
Tom Au
Mathematica tiene un cálculo lambda horneado al notar que nadie lo mencionó.
William

Respuestas:

26

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. "

amon
fuente
Esta es una mejor respuesta que la que había seleccionado antes. Tu respuesta realmente da en el blanco. ¡Esto es exactamente lo que estaba buscando!
RonaldMunodawafa
"... excepto que en las funciones LC siempre tiene exactamente un argumento": ¿Esta característica se llama curry o al menos está relacionada con ella?
Giorgio
@Giorgio Currying es diferente, pero está relacionado. LC no tiene funciones de múltiples argumentos, pero esas simplemente pueden codificarse como funciones anidadas que toman un argumento cada una. Ejemplo usando notación ML: x = fn (a, b, c) => a + b + c(tipo int * int * int -> int, invocación fn (1, 2, 3)) se puede transformar en x = fn a => fn b => fn c => a + b + c(tipo int -> 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 tipo int -> int. Esta es una aplicación parcial / curry.
amon
Pensé que curry significaba que todas las funciones tomaran solo un argumento (como en LC).
Giorgio
8

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 .

davidk01
fuente
1
Es posible que desee mencionar idiomas específicos que están bastante cerca del cálculo lambda, por ejemplo, Lisp.
Giorgio
1
Todavía estoy aprendiendo Scheme usando SICP y espero aprender más sobre esta área. Gracias por su elaborada respuesta y sugerencia.
RonaldMunodawafa