¿Qué hace que el cálculo lambda sea relevante para el estudio?

Question

El próximo otoño comenzaré un curso universitario de informática, pero realmente no puedo entender el cálculo λ en el contexto de la programación funcional.Puede que esté malinterpretando esto por completo, pero basándome en esto definición de la Enciclopedia de Filosofía de Stanford, es simplemente otra notación para funciones.

Si se es solo eso, ¿por qué es ventajoso usar el cálculo λ en lugar de las notaciones de funciones regulares para calcular el tiempo de ejecución del algoritmo?

Answer 1

En informática queremos analizar y comprender el código fuente con rigor matemático. Esa es la única forma de demostrar propiedades interesantes (como la terminación) con absoluta certeza. Para eso necesitamos un lenguaje con un significado muy bien definido para cada construcción.

En teoría, este podría ser cualquier lenguaje con un buen semántica formal. Pero para hacer las cosas menos complicadas y menos propensas al error, es mejor usar un lenguaje que sea lo más simple posible pero que aún pueda expresar cualquier programa (es decir, es Turing Complete). Para razonar sobre el código imperativo, hay Máquinas de Turing. Pero para razonar sobre la programación funcional, está el $ lambda $ -calculus.

El $ lambda $ -calculus básico es como un lenguaje de programación funcional, pero con un montón de 'equipaje'. No es importante que este sea un lenguaje agradable para escribir programas, ni que sea un lenguaje eficiente. Solo que es simple y expresivo. Por ejemplo, no necesitamos bucles, porque podemos simularlos con recursión. Y no necesitamos funciones con múltiples parámetros, ya que podemos simularlas con Zurra.

Ahora, en algún momento, es posible que desee probar propiedades sobre construcciones que no forman parte del (sin tipo) $ lambda $ -calculus. Es por eso que los científicos informáticos lo han extendido en diferentes direcciones a lo largo de los años. Por ejemplo, para razonar sobre los sistemas de tipos, hay muchas variaciones de Escrito $ lambda $ -calculi.

Answer 2

Curiosamente, muchos libros hablan sobre cálculo $\lambda$ sin mencionar Ceceo o Esquema, lenguajes de programación modernos basados ​​en él, lo que desafortunadamente deja a los estudiantes con la idea de que es antiguo, abstracto y principalmente teórico.Estudiar Lisp o Scheme puede ser un gran ángulo para ayudar enormemente a comprender el cálculo $\lambda$.

Si se es solo eso, ¿por qué es ventajoso usar el cálculo λ en lugar de las notaciones de funciones regulares para calcular el tiempo de ejecución del algoritmo?

Hay muchas ventajas al usar Lisp o programación funcional y calcular el tiempo de ejecución del algoritmo es solo una posibilidad (aunque sería útil si citara una referencia para eso).dado que ya está en notación funcional, a veces la determinación de las fórmulas para el tiempo de ejecución mediante relaciones de inducción o recurrencia puede tener una relación más fuerte o más obvia con el código original.También se simplifican otros tipos de análisis del algoritmo.

Otra ventaja principal es la simplicidad sintáctica.Los analizadores de otros lenguajes son muy complejos, pero los analizadores Lisp son muy simples.entonces Lisp es un gran lenguaje para estudiar la teoría del análisis sintáctico.

Otro aspecto clave es analizar el software más desde un punto de vista lógico o matemático lente/visión en lugar de una perspectiva "informática".

Como señala la otra respuesta, Lisp tiene que ver con la recursividad en lugar de la iteración y la recursividad está en el corazón de CS.

Se pueden encontrar más recomendaciones para una "vista $\lambda$" y detalles en [1], una referencia semifamosa y gratuita en línea.

[1] Estructura e interpretación de programas informáticos, por Abelson & Sussman