Estoy tratando de tener una mejor idea de cómo entran los tipos en el cálculo lambda. Es cierto que muchas de las cosas de la teoría de tipos están por encima de mi cabeza. Lisp es un lenguaje tipado dinámicamente, ¿correspondería aproximadamente al cálculo lambda sin tipo? ¿O hay algún tipo de "cálculo lambda de tipo dinámico" que desconozco?¿De qué tipo de cálculo lambda sería un ejemplo Lisp?
Respuesta
Lisp es un lenguaje de tipeo dinámico, ¿correspondería aproximadamente al cálculo lambda sin tipo?
Sí, pero solo más o menos. En el cálculo lambda sin tipo "puro", todo está codificado como funciones. (Puede buscar en Google la popular "codificación Church" y la menos popular "codificación Scott"). Lisp tiene datos no funcionales, como átomos y números, por lo que esto se consideraría como "cálculo lambda sin tipo extendido con constantes".
Otra diferencia importante es en orden de evaluación. Las reglas para reducir los términos lambda-calculus son altamente no deterministas. (Hay un teorema, el teorema de Church-Rosser, que dice vagamente que mientras las cosas terminen, el orden de evaluación no importa). En la práctica, los términos lambda se reducen típicamente usando la reducción más extrema más externa conocida como "orden normal" porque si cualquier estrategia de reducción finaliza, esa sí. Esto es muy diferente de Lisp, que siempre evalúa los argumentos a la forma normal antes de hacer una reducción beta. Esta orden de evaluación se llama "llamada por valor".
En resumen, Lisp corresponde a un cálculo lambda sin tipo, call-by-value extendido con las constantes.
John McCarthy presentó LISP en his April, 1960 paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". El siguiente párrafo es de la página 6:
e. Funciones y Formas. Es habitual en matemáticas, fuera de la lógica matemática, utilizar la palabra "función" de forma imprecisa y aplicarla a los formularios , como y + x. Debido a que luego calcularemos con expresiones para funciones, , necesitamos una distinción entre funciones y formularios y una notación para expresar esta distinción. Esta distinción y una notación para describirlo, desde que nos desviamos trivialmente, viene dada por Church [3].
...
3. A. CHURCH, The Calculi of Lambda-Conversion (Princeton University Press, Princeton, N. J., 1941).
El Wikipedia article on lambda-calculus tiene un historial de publicaciones de la Iglesia. El documento de 1941 al que hace referencia McCarthy parece referirse al mecanografiado lambda-calculus, en contradicción con la introducción del artículo de Wikipedia.
La palabra clave lambda
en Lisp se puede entender que se refiere al cálculo lambda solo a través de la analogía. Una expresión Lisp lambda es un tipo de anonymous function.
Eso es lo que pensé, pero estoy entrenado para pensar que sin tipo! = Tipeado dinámicamente. :-) –
@Heath: sin embargo, la cita dice específicamente que lo que se extrae del documento es la "distinción entre funciones y formas y una notificación para expresar esta distinción", en lugar de implementar el sistema descrito en el documento. – outis
Lisp no es 'un cálculo lambda', no sé lo que es 'un cálculo lambda'.
Si desea identificar los cálculos lambda allí, escriba el sistema, entonces Lisp es el suyo por supuesto. La palabra clave 'lambda' en cualquier ceceo antes de Scheme es ciertamente pretenciosa, y después de Scheme también hay espacio para decir que sí.Solo usar 'func' hubiera sido más humilde. Lisp es un procesador de listas principalmente, no un 'cálculo lambda'
También escribí un artículo bastante extenso sobre esta vez que intenta demostrar por qué A: el término 'programación funcional' no tiene sentido y B: por qué el hablar de ' un cálculo lambda en lugar de 'un sistema de tipo' es lo mismo:
http://blog.nihilarchitect.net/archives/289/on-functional-programming/
Además, tenga en cuenta que en Lisp, todas las funciones son en efecto solo argumento y sólo pueden ser tener listas como sus argumentos.
¡su cuenta ha sido suspendida! Por lo tanto, el enlace está efectivamente muerto –
- 1. ¿Cuál sería un ejemplo de un condicional anafórico en Lisp?
- 2. cálculo lambda
- 3. Lambda Operadores de cálculo precedencia
- 4. ¿Por qué # 'se usa antes de lambda en Common Lisp?
- 5. Renombrando lambda en Common Lisp
- 6. ¿Qué es un lenguaje lambda?
- 7. ¿Sería Lisp extremadamente difícil para un programador nuevo (ish) aprender?
- 8. Incrustar tipos de mayor kínder (¡mónadas!) En el cálculo lambda sin tipo
- 9. Eliminación de un tipo en Common Lisp
- 10. Llamar por valor en el cálculo lambda
- 11. Emacs Lisp: diferencia entre (función (lambda ...)) y (lambda ...)?
- 12. Especificadores de tipo Common Lisp
- 13. ¿Qué es un Lambda?
- 14. Turing la integridad del cálculo lambda?
- 15. consulta en Booleanos en cálculo lambda
- 16. ¿Es lambda un tipo de función de orden superior?
- 17. Función predecesora de cálculo lambda pasos de reducción
- 18. Obtener parámetro lambda tipo
- 19. Cálculo lambda y números de la iglesia confusión
- 20. potencias de cálculo (por ejemplo, 2^11) de forma rápida
- 21. Números de iglesia: cómo codificar cero en cálculo lambda?
- 22. ¿Cuáles son algunos recursos para aprender el cálculo de Lambda?
- 23. ¿Hay un ejemplo simple para explicar las macros de Lisp a un programador "genérico"?
- 24. Lambda para expresiones de tipo en Haskell?
- 25. ¿Qué significa # en LISP
- 26. ¿En qué se compila C# lambda? ¿Un marco de pila, una instancia de tipo anónimo o?
- 27. ¿Qué tiene de bueno Lisp?
- 28. Código ejercicio de las posibilidades únicas de cada borde del cálculo lambda
- 29. Definición de "forma lisp"?
- 30. ¿Qué sucede cuando se asigna un tipo que contiene un lambda?
Si estamos hablando de Lisp, ¿no debería ser (lambda (cálculo)) ;-) –
Mientras no estés hablando de Clojure. Entonces sería '(fn [cálculo])' :-) –
El problema con esta pregunta es que no hay un único y único lenguaje Lisp, hay toda una familia de ellos. ¿A qué Lisp (s) te refieres? – outis