Cálculo λ
Fecha de entrega:
- Para propósitos de esta tarea \(0 \in \mathbb{N}\).
- Está altamente recomendado probar sus funciones en un evaluador de
cálculo λ. En la tarea usé la notación del libro de Rebecca Weber,
\((\lambda x | e)\) y con \((\lambda x y | e)\) como abreviación de \((\lambda x | (\lambda
y | e))\), donde \(e\) es alguna expresión. Ese evaluador en cambio
usa la notación ligeramente más estándar \(\lambda x. e\) y no tiene la
abreviación así que hay que poner \(\lambda x . \lambda y . e\). No se preocupen
si su teclado no tiene tecla λ, pueden usar
\en esa página, así que escribirían algo como\x.\y.e.
Numerales de Church
Recuerden que en el cálculo λ representamos el natural \(n\) por medio de \((\lambda f x | f(f(\cdots(f(x))\cdots)))\) con \(n\) aplicaciones de \(f\).
- ¿Qué número representa la función \((\lambda f | (\lambda g | g g) (\lambda h x | h(h x)) f)\)?
- ¿Qué operación aritmética entre los numerales de Church \(m\) y \(n\) representa la función \((\lambda m n f x | f (m (n f) (m f x)))\)?
- La función predecesor está dada por \((\lambda n f x | n (\lambda g h | h(g f)) (\lambda u | x) (\lambda u | u))\). Calcula en detalle los predecesores de los numerales de Church de 0, 1 y 2 y verifica que obtienes 0, 0 y 1 respectivamente.
- Escribe en cálculo λ una versión para numerales de Church de alguna función \(f : \mathbb{N} \to \mathbb{N}\) que cumpla que \(f(n) = n^{2} - 2n + 2\) para \(n \ge 1\). Escoge el valor para \(f(0)\) que te resulte más cómodo.
Verdadero y Falso
Recuerda que codificamos los valores verdadero y falso como sigue:
- \(\V = (\lambda a b | a)\).
- \(\F = (\lambda a b | b)\).
- Escribe en cálculo λ una versión de la función \(\implies\). Recuerda que \(p \implies q\) es \(\V\) a menos que \(p = \V\), \(q = \F\).
- Escribe en cálculo λ una versión de la función booleana \(\may\). La función \(\may\) recibe tres valores booleanos y dice qué valor tiene la mayoría. Por ejemplo \(\may \V \F \V = \V\) y \(\may \F \F \F = \F\).
Prueba que las siguientes dos funciones son equivalentes para \(p\) booleano:
- \((\lambda p a b | p b a)\).
- \((\lambda p | p \F \V)\).
¿A qué función booleana conocida corresponden?
Listas de Scott
En estos problemas exploraremos una manera de codificar listas que es diferente a la que vimos en clase.
Usaremos la siguiente notación:
- La lista vacía es \(\nil\).
- Si \(l\) es una lista podemos formar una lista nueva agregando \(x\) al principio de \(l\), esa nueva lista se denota por \(\cons x \; l\).
La codificación de Scott para listas en el cálculo λ está dada como sigue:
- \(\nil = (\lambda a b | a)\).
- \(\cons = (\lambda x l a b | b x l)\).
- Escribe una función \(\vacia\) en cálculo λ tal que:
- \(\vacia(\nil) = \V\) y
- para cualesquiera \(x\) y \(l\) tengamos que \(\vacia(\cons x \; l) = \F\).
Escribe una función \(\mathsf{longitud}\) en cálculo λ que calcule la longitud de una lista. Vas a tener que usar el combinador \(\Y\) que vimos en clase para definir funciones recursivas: \[\Y = (\lambda f | (\lambda x | f (\lambda v | xxv)) (\lambda x | f (\lambda v | xxv)))\]
Recuerda que \(\Y\) tiene la propiedad de que \(\Y g v = g(\Y g) v\). Lo usamos para convertir una definición recursiva como: \[\fib = (\lambda n | \mathsf{si} (n \le 1) n (\fib(n-1) + \fib(n-2)))\] en una definición que no usa \(\fib\) de lado derecho: \[\fib = \Y(\lambda f n | \mathsf{si} (n \le 1) n (f(n-1) + f(n-2)))\]