¿Cuáles son algunos conceptos en el cálculo lambda que es bueno saber antes de aprender programación funcional?

Ninguna. El cálculo de Lambda es un tema que se puede ajustar en una página de texto. Es como preguntar “¿cuáles son algunos conceptos de sumar números naturales que es bueno saber antes de aprender idiomas imperativos?” Hay un par de conceptos, como “la función es un valor que puede pasar a otra función, y puede construir mucho”. “, pero estas cosas las aprenderás de todos modos con cualquier lenguaje funcional, por lo que no necesitas sumergirte profundamente en el cálculo lambda antes de eso, no hay mucha profundidad para una inmersión.

Hay cosas interesantes como el combinador Y y los combinadores S, K, I, pero realmente no los necesitas antes de aprender FP. Y probablemente los encontrará allí de todos modos (los métodos de aplicación aplicadores para “(-> a)“ son básicamente combinadores S y K).

Tanto el cálculo Lambda como el álgebra combinatoria son computacionalmente completos y [por el bien de los matemáticos que trabajan con ellos] sintácticamente mínimos. Entonces, estos sistemas algebraicos nos pueden decir algo sobre los elementos esenciales de la informática. LISP no utiliza asignaciones ni procedimientos ni constantes, pero sí utiliza variables y son las únicas primitivas. Esto nos dice que la mayoría de la maquinaria que se ve en los lenguajes de programación es innecesaria, la mayoría de las estructuras de programación se proporcionan solo por conveniencia y eficiencia. Si disculpamos las primitivas de LISP [CAR, CDR, CONS, …], cualquier cálculo puede programarse sin SET, DEFUN o PROG. Por otro lado, las primitivas del álgebra combinatoria son constantes; y así demuestra que las variables no son necesarias [si tenemos un conjunto completo de constantes].

Una presentación concisa del cálculo Lambda para los lectores de mi texto, “LISP Lore and Logic: An Algebraic View of LISP Programming, Foundations, and Applications”, se ofrece en el capítulo 7 [aproximadamente 13 páginas]. El texto está disponible gratis en Internet. También recomiendo “Estructura e interpretación de programas de computadora” por Abelson y Sussman.

Enseñé LISP en UT Austin, Bell Labs y USF por más de 30 años. A menudo siguió un curso de teoría de la recursión [del texto de Hartley Rogers]. Trabajando desde una comprensión de la teoría matemática computacional, pude cubrir algunos de los poderes más fantásticos vistos en LISP [por ejemplo, el combinador Y, programas que se reescriben a sí mismos mientras parecen hacer algo mundano, el problema de detención]. Esta era mi forma de tratar de estar a la altura de la legendaria “Hora mágica” del profesor John McCarthy en el MIT.

Una vez que se le preguntó al profesor McCarthy “si un intérprete y compilador de LISP se puede escribir en C, entonces, ¿cómo puede ser que LISP sea más poderoso que C?”, Respondió que el Teorema de punto fijo [casi increíble] de Kleene para funciones computables obviamente se encuentra en LISP. Proporcionó un ejemplo muy sintáctico en

((LAMBDA (X) (LISTA X (LISTA (COTIZACIÓN COTIZACIÓN) X)))
(COTIZACIÓN (LAMBDA (X) (LISTA X (LISTA (COTIZACIÓN COTIZACIÓN) X)))

que se evalúa a sí mismo! Otros ejemplos fueron lo que el estudiante estaba pidiendo, pero los expertos apreciarían este.