Atualização [20/09/2011]: ampliei o parágrafo sobre -expansion e extensionality. Agradecemos a Anton Salikhmetov por apontar uma boa referência.η
η -conversion é um caso especial de - conversão apenas no caso especial quando é uma abstração, por exemplo, se entãoMas e se for uma variável ou um aplicativo que não se reduz a uma abstração?(λx.fx)=fβff=λy.yy
(λx.fx)=(λx.(λy.yy)x)=β(λx.xx)=αf.
f
De certa forma, -rule é como um tipo especial de extensionalidade, mas precisamos ter um pouco de cuidado sobre como isso é afirmado. Podemos afirmar a extensionalidade como:η
- para todos -Termos e , se então , ouM N M x = N x M = NλMNMx=NxM=N
- para todos os se então .∀ x . f x = g x f = gf,g∀ x . fx = gxf= g
O primeiro é uma meta-declaração sobre os termos do -calculus. Nele aparece como uma variável formal, isto é, faz parte do -calculus. Isso pode ser provado a partir de -rules, veja, por exemplo, o Teorema 2.1.29 em "Lambda Calculus: its Syntax and Semantics" de Barendregt (1985). Pode ser entendido como uma declaração sobre todas as funções definíveis , isto é, aquelas que são denotações de -terms.x λ β η λλxλβηλ
A segunda afirmação é como os matemáticos geralmente entendem afirmações matemáticas. A teoria do -calculus descreve um certo tipo de estruturas, vamos chamá-los de " -models ". Um -model pode ser incontável, portanto não há garantia de que cada elemento corresponda a um -term (assim como existem mais números reais do que expressões que descrevem reais). Extensionalidade então diz: se tomarmos quaisquer duas coisas e em um -model, se para todo no modelo, então . Agora, mesmo que o modelo satisfaça aλ λ λ f g λ f x = g x x f = g ηλλλλfgλfx = gxxf= gη regra, ele não precisa satisfazer a extensionalidade nesse sentido. (Referência necessária aqui, e acho que precisamos ter cuidado com a interpretação da igualdade.)
Existem várias maneiras pelas quais podemos motivar conversões - e . Escolherei aleatoriamente a teoria da categoria, disfarçada como -calculus, e alguém mais pode explicar outras razões.η λβηλ
Vamos considerar o -calculus digitado (porque é menos confuso, mas mais ou menos o mesmo raciocínio funciona para o -calculus não digitado). Uma das leis básicas que deve ser mantida é a lei exponencial(Estou usando as notações e intercambiável, escolhendo o que parecer melhor.) O que os isomorfismos e parecem escritos em -calculus? Presumivelmente, eles seriam eX C Uma × B ≅ ( C B ) Uma . Um → B B A i : C Uma × B → ( C B ) Um j : ( C B ) Um → C Uma × B λ i = λ f : C A x B . λ um : A . λ b :λλ
CA × B≅( CB)UMA.
A → BBUMAi : CA × B→ ( CB)UMAj : ( CB)UMA→ CA × BλJ = λ g : ( C B ) Uma . λ p : Um × B . g ( π 1 p ) ( π 2 p ) . p p π 1 ⟨ um , b ⟩ = um π 2 ⟨ um , b ⟩ = b g : (i = λ f: CA × B. λ um : A . λ b : B . f⟨ Um , b ⟩
j = λ g: ( CB)UMA.λp:A×B.g(π1p)(π2p).
Um breve cálculo com um par de -reductions (incluindo o -reductions e para produtos) nos que, diz para cada temos
Como e são inversos um do outro, esperamos que , mas para provar isso de fato, precisamos usar reduction duas vezes:
ββπ1⟨a,b⟩=aπ2⟨a,b⟩=b i ( j g ) = λ um : Uma . λ b : B . g a b . i j i ( j g ) = g η i ( j g ) = ( λ um : Um . λ b : B . g um b ) = η ( λ um :g:(CB)Ai(jg)=λa:A.λb:B.gab.
iji(jg)=gηi(jg)=(λa:A.λb:B.gab)=η(λa:A.ga)=ηg.
Portanto, esse é um motivo para ter reduções. Exercício: que é necessário -rule para mostrar que ?
η j ( i f ) = fηηj(if)=f
Para responder a essa pergunta, podemos fornecer a seguinte citação da monografia correspondente “Cálculo Lambda. Sua sintaxe e semântica “(Barendregt, 1981):
fonte
Apenas para acrescentar à muito boa resposta de Andrej: a teoria das regras de redução sem tipo -calculus com e satisfaz algumas propriedades muito boas:β ηλ β η
É consistente no sentido de que existem dois termos, por exemplo, e que não são equivalentes. Isso é uma conseqüência do teorema da confluência para a redução .λ x y . y β η β ηλxy.x λxy.y βη βη
É uma teoria consistente máxima , no seguinte sentido: se é uma relação de equivalência em termos tais que:ι
É fechado por congruência: etc.u =ι v⇒t u =ι t v
É equivale 2 não equivalente termosβη que são formas normais : não existe e na forma normal de tal modo que e
.t u t=ιu t≠βηu
Então a teoria é inconsistente : para cada termo , na forma normal, .t u t=βηιu
Isso é uma consequência do teorema de Böhm.
fonte
fonte