La pregunta subyacente:
¿Qué hace el cálculo lambda por nosotros que no podemos hacer con las propiedades básicas de la función y la notación generalmente aprendidas en el álgebra de la escuela secundaria?
En primer lugar, ¿qué significa abstracto en el contexto del cálculo lambda? Mi comprensión de la palabra resumen es algo que está divorciado de la maquinaria, el resumen conceptual de un concepto.
Sin embargo, las funciones lambda, al eliminar los nombres de las funciones, evitan un cierto nivel de abstracción. Por ejemplo:
f(x) = x + 2
h(x, y) = x + 5 y
Pero incluso sin definir la maquinaria de estas funciones, podemos hablar fácilmente sobre su composición. Por ejemplo:
1. h(x, y) . f(x) . f(x) . h(x, y) or
2. h . f . f . h
Podemos incluir los argumentos si queremos, o podemos abstraernos por completo para dar una visión general de lo que está sucediendo. Y podemos reducirlos rápidamente a una sola función. Echemos un vistazo a la composición 2. Puedo tener capas de detalles de estudiantes con las que puedo escribir dependiendo de mi énfasis:
g = h . f . f . h
g(x, y) = h(x, y) . f(x) . f(x) . h(x, y)
g(x, y) = h . f . f . h = x + 10 y + 4
Realicemos lo anterior con cálculo lambda, o al menos definamos las funciones. No estoy seguro de que esto sea correcto, pero creo que la primera y la segunda expresión aumentan en 2.
(λuv.u(u(uv)))(λwyx.y(wyx))x
Y multiplicar por 5 años.
(λz.y(5z))
En lugar de ser abstracto, esto parece entrar en la maquinaria misma de lo que significa sumar, multiplicar, etc. La abstracción, en mi opinión, significa un nivel más alto en lugar de un nivel más bajo.
Además, estoy luchando por ver por qué el cálculo lambda es incluso una cosa. ¿Cuál es la ventaja de
(λuv.u(u(uv)))(λwyx.y(wyx))x
terminado
h(x) = x + 5 y
o una notación combinada
Hxy.x+5y
o incluso la notación de Haskell
h x y = x + 5 * y
Nuevamente, ¿qué hace el cálculo lambda por nosotros que no podemos hacer con las propiedades de función estilo f (x) y la notación con la que muchos están familiarizados?
Respuestas:
Hay muchas razones por las que el cálculo lambda es tan importante.
Una razón muy importante es que el cálculo lambda nos permite tener un modelo de computación en el que las funciones computables son ciudadanos de primera clase.
No se pueden expresar funciones de orden superior en el lenguaje del álgebra de la escuela intermedia.
Tome como ejemplo la expresión lambda
Esta simple expresión nos muestra que, dentro del cálculo lambda, la composición de funciones es en sí misma una función. En álgebra de secundaria, esto no se expresa fácilmente.
En el cálculo lambda, es muy fácil expresar que una función devolverá una función como resultado.
Aquí hay un pequeño ejemplo. La expresión (donde aquí supongo un cálculo lambda aplicado con suma y constantes enteras)
se reducirá a
Observe también que dentro del cálculo lambda, las funciones son expresiones y no definiciones de la forma . Esto nos libera de la necesidad de nombrar funciones y distinguir entre una categoría sintáctica de expresiones y una categoría sintáctica de definiciones.f(x)=e
Además, cuando se hace imposible (o simplemente notoriamente engorroso) expresar funciones de orden superior, uno también tendrá problemas para asignar tipos a expresiones.
La composición de la función tiene el tipo polimórfico
en el sistema de tipos Hindley-Milner.
Un punto de venta muy fuerte para el cálculo lambda es la noción precisa de cálculo lambda mecanografiado . Los diversos sistemas de tipos para lenguajes de programación funcionales como Haskell y la familia ML se basan en sistemas de tipos para cálculos lambda, y estos sistemas de tipos ofrecen fuertes garantías en forma de teoremas matemáticos:
Si un programa está bien escrito y e se reduce a la e ' residual , entonces e ' también estará bien tipado.mi mi mi′ mi′
Y si está bien escrito, entonces e no exhibirá ciertos errores.mi mi
Las pruebas como correspondencia de programas son particularmente notables. El isomorfismo de Curry-Howard (véase, por ejemplo, https://www.rocq.inria.fr/semdoc/Presentations/20150217_PierreMariePedrot.pdf ) muestra que existe una correspondencia muy precisa entre el cálculo lambda de tipo simple y la lógica proposicional intuitiva: para cada tipo corresponde una fórmula lógica φ T . Una prueba de ϕ T corresponde a un término lambda con tipo T , y una reducción beta de este término corresponde a realizar una eliminación de corte en la prueba.T ϕT ϕT T
Insto a aquellos que sienten que el álgebra de la escuela intermedia es una buena alternativa al cálculo lambda para que desarrollen una explicación del álgebra de la escuela secundaria de tipo polimórfico de orden superior junto con una noción apropiada del isomorfismo de Curry-Howard. Si incluso puede encontrar un asistente de prueba interactivo basado en álgebra de la escuela intermedia que nos permita probar los muchos teoremas que se han formalizado utilizando asistentes de prueba basados en cálculo lambda como Coq e Isabelle, eso sería aún mejor. Entonces comenzaría a usar el álgebra de la escuela secundaria, y así, estoy seguro, lo harían muchos otros conmigo.
fuente
Las funciones en el cálculo lambda son mucho más generales. La definición exacta depende de si su cálculo lambda está escrito o no. En cálculo lambda puro sin tipo, todo es una función. Esto es mucho más general que las funciones reales del cálculo.
Incluso los lenguajes de procedimiento a veces usan ideas del cálculo lambda. La función de clasificación en C acepta como parámetro una función de comparación , que utiliza para comparar elementos. El cálculo de Lambda va mucho más allá: las funciones no solo aceptan funciones como entradas, sino que también pueden generarlas.
El cálculo Lambda es un modelo de cálculo equivalente en potencia a las máquinas de Turing. Es un sistema completo en sí mismo. El cálculo lambda puro no tiene "5" o "+" como términos primitivos: se pueden definir dentro del cálculo, al igual que "5" y "+" no son primitivos de la teoría de conjuntos. (Los lenguajes de programación prácticos implementan números naturales de forma nativa por razones de eficiencia).
Sospecho que una de las razones por las que no está impresionado con el cálculo lambda es que sus ideas han impregnado tanto el discurso de programación que ya no parece innovador.
fuente
El uso de expresiones lambda en lenguajes de programación tiene una ventaja similar; puede escribir lo que hace la función allí donde se necesita, en lugar de tener que definir una función completamente nueva en otro lugar de su programa.
Incluso puedes ver la abstracción lambda implícita en las matemáticas; Por ejemplo, a los estudiantes de cálculo solo se les enseñan derivados derereXX2 rereX X2
Muchas personas encuentran esta notación de doble evaluación confusa y / o inquietante, así como este uso recursivo de la definición puntual de una función. La versión de abstracción lambda
No tiene ese problema.
Finalmente, existe un teorema del sinsentido abstracto que dice "cálculo lambda simplemente tipado" es básicamente lo mismo que "categoría cerrada cartesiana", por lo que si alguna vez desea realizar cálculos en una categoría cerrada cartesiana, probablemente sea una buena idea usar simplemente escribió cálculo lambda para hacerlo.
fuente
Diré por adelantado que no soy un experto en este tema, pero acabo de pasar un poco de tiempo estudiándolo y una de las cosas más fascinantes para mí en cualquier tema es la historia detrás de él. Entonces, para mí, comprender un poco de la historia detrás del cálculo lambda ayuda a explicar por qué es útil.
El breve resumen es que a principios del siglo XX después de que la teoría de conjuntos comenzó a despegar y las matemáticas se volvieron a concebir en función de los conjuntos, algunos matemáticos notaron que si bien una definición de teoría de conjuntos te permite afirmar que existe una determinada estructura, no te dicen cómo para construirlo y calcularlo. Entonces las definiciones de teoría de conjuntos no son constructivas . Los matemáticos comenzaron a preguntarse si había una manera de desarrollar definiciones constructivas que irían más allá de demostrar que algo es y, en cambio, probar cómo es .
Desde Wikipedia :
Luego se demostró que el cálculo lambda y la máquina de Turing podrían representar cualquier función computable y, por lo tanto, son equivalentes.
En teoría, cualquier función o concepto matemático puede codificarse en forma de cálculo lambda y calcularse. Esto significa que el cálculo lambda puede ser una base completamente separada para las matemáticas, aunque obviamente es extremadamente tediosa.
El cálculo de Lambda no es "útil" en el sentido de que no va a escribir código usándolo, pero sí forma la base de la semántica denotacional que se usa para describir programas y sus efectos dinámicos. Esto se usa en las discusiones sobre la corrección del programa y el significado semántico. Obviamente, también influyó mucho en el desarrollo de lenguajes de programación funcionales, que extraen todo su concepto de ejecución del cálculo lambda.
Espero que ayude.
Editar para agregar: Acabo de señalar este documento que muestra la relación entre topología, cálculo lambda y física. Leyendo brevemente me encontré con esta fantástica declaración:
El punto es que el cálculo lambda es un modelo idealizado de cómputo de software y, como tal, no está vinculado a una implementación particular en ningún lenguaje de programación. Modela computación pura .
fuente
fuente
El cálculo Lambda no fue diseñado para ser un lenguaje de programación. De hecho, fue creado en la década de 1930, décadas antes de que incluso tuviéramos computadoras programables. Más bien, fue creado como un modelo formal para estudiar computación, en sí mismo. Si está decepcionado de la facilidad con la que expresa el código o las funciones matemáticas, eso es porque no es para eso.
fuente
El cálculo de Lambda existe para que se puedan crear funciones anónimas (también conocidas como lambda). Si no elimina los nombres de las funciones, el espacio de nombres puede estar abarrotado y uno puede quedarse sin los nombres de las funciones disponibles. Esto es especialmente importante cuando se trata de las llamadas "funciones de orden superior" que devuelven funciones (o punteros de función) por razones obvias.
Esencialmente, las funciones lambda son equivalentes a las variables de ámbito local. La programación funcional sin funciones lambda es análoga a la programación de procedimientos sin ninguna variable local, es decir, una idea terrible.
"por qué el cálculo lambda es incluso una cosa" a los matemáticos les encanta la redundancia. el cálculo lambda rara vez se usa en matemáticas porque, como has descubierto, la notación no es muy útil.
"Si incluso puedes encontrar un asistente de prueba interactivo basado en álgebra de la escuela intermedia que nos permita probar los muchos teoremas que se han formalizado utilizando asistentes de prueba basados en cálculo lambda como Coq e Isabelle, eso sería aún mejor. luego comience a usar el álgebra de la escuela secundaria, y así, estoy seguro, lo harían muchos otros conmigo ". ¿Has oído hablar de metamath? No hay cálculo lambda involucrado allí, puede probar muchos de los teoremas de coq / isabelle
fuente
let
, pero si bienlet
puede codificarse con funciones anónimas, claramente no puede ir a la inversa. La programación funcional no requiere "funciones lambda", por ejemplo, Backus ' FP o Sisal .