Actualización [2011-09-20]: amplié el párrafo sobre η -expansión y extensionalidad. Gracias a Anton Salikhmetov por señalar una buena referencia.
η -conversion( λ x . fx ) = f es un caso especial deβ - conversiónsoloen el caso especial cuandoF es en sí mismo una abstracción, por ejemplo, siF= λ y. yy luego
( λ x . fx ) = ( λ x . ( λ y. yy) x ) =β( λ x . x x ) =αF.
Pero, ¿quépasasi
F es una variable o una aplicación que no se reduce a una abstracción?
En cierto modo, η -rule es como un tipo especial de extensionalidad, pero tenemos que tener un poco de cuidado sobre cómo se afirma. Podemos establecer la extensionalidad como:
- para todos los términos M y N , si M x = N x entonces M = N , oλMETROnorteMETROX = NXMETRO= N
- para todo si ∀ x . f x = g x entonces f = g .F, g∀ x .Fx = gXF= g
El primero es una metadeclaración sobre los términos del cálculo . En ella x aparece como una variable formal, es decir, es parte del cálculo λ . Se puede probar a partir de las reglas β η , véase por ejemplo el Teorema 2.1.29 en "Cálculo de Lambda: su sintaxis y semántica" de Barendregt (1985). Puede entenderse como una declaración sobre todas las funciones definibles , es decir, aquellas que son denotaciones de términos λ .λXλβηλ
La segunda afirmación es cómo los matemáticos suelen entender las afirmaciones matemáticas. La teoría del cálculo describe un cierto tipo de estructuras, llamémoslas " modelos λ ". Un modelo λ podría ser incontable, por lo que no hay garantía de que cada elemento corresponda a un término λ (al igual que hay más números reales que expresiones que describen reales). La extensibilidad luego dice: si tomamos dos cosas f y g en un modelo λ , si f x = g x para todas las x en el modelo, entonces f = gλλλλFsolλFX= gXXF= g. Ahora, incluso si el modelo satisface la regla , no necesita satisfacer la extensionalidad en este sentido. (Se necesita referencia aquí, y creo que debemos tener cuidado de cómo se interpreta la igualdad).η
Hay varias formas en que podemos motivar las conversiones y η . Elegiré aleatoriamente la categoría teórica, disfrazada de cálculo λ , y alguien más puede explicar otras razones.βηλ
Consideremos el cálculo tipificado (porque es menos confuso, pero más o menos el mismo razonamiento funciona para el cálculo λ sin tipo). Una de las leyes básicas que deben bodegas es la ley exponencial C A × B ≅ ( C B ) Una . (Estoy usando las anotaciones A → B y B A de manera intercambiable, seleccionando la que parezca mejor). ¿Qué hacen los isomorfismos i : C A × B → ( C B ) A y j :λλ
CA × B≅( Csi)UN.
A → BsiUNi : CA × B→ ( Csi)UN parece, escrito en
λ- cálculo? Es de suponer que serían
i = λ f : C A × B . λ una : Una . λ b : B . f ⟨ un , b ⟩ y
j = λ g : ( C B ) A . λ p : A × Bj : ( Csi)UN→ CA × Bλi = λ f: CA × B. λ una : Una . λ b : B . F⟨ Un , b ⟩
Un corto cálculo con un par de
beta -reductions (incluyendo la
β -reductions
π 1 ⟨ un , b ⟩ = una y
π 2 ⟨ un , b ⟩ = b para los productos) nos dice que, para cada
g : ( C B ) A tenemos
i ( j g ) =j = λ g: ( Csi)UN. λ p : A × B . sol( π1p ) ( π2p ) .
ββπ1⟨ Un , b ⟩ = unaπ2⟨ Un , b ⟩ = bsol: ( Csi)UN
Desde
i y
j son inversas entre sí, esperamos que
i ( j g ) = g , pero para realmente probar esto tenemos que utilizar
η -Reducción dos veces:
i ( j g ) = ( λ un : A . Λ b : B . g a b ) = η (i ( j g) = Λ un : A . λ b : B . sola b .
yoji ( j g) = gη
Esta es una razón para tenerreducciones
η . Ejercicio: ¿quéregla
η se necesita para mostrar que
j ( i f ) = f ?
i ( j g) = ( Λ un : A . Λ b : B . Ga b ) =η( Λ un : A . Ga ) =ηsol.
ηηj(if)=f
Para responder a esta pregunta, podemos proporcionar la siguiente cita de la monografía correspondiente "Cálculo de Lambda". Su sintaxis y semántica "(Barendregt, 1981):
fuente
Esta es una consecuencia del teorema de Böhm.
fuente
fuente