Combinador Y, composição da função

7

Estou tentando entender os combinadores Y. Poderia explicar por que os seguintes itens são equivalentes

(Y (f ∘ g))   
(f (Y (g ∘ f)))

(Y é uma combinação de pontos fixos)

David
fonte

Respostas:

6

Depende da noção de equivalência que você está usando.

Suponha que comparemos esses termos de acordo com sua semântica denotacional, nos domínios -CPO. Denote com a semântica dos termos . Assim, são funções contínuas de Scott. Então, temos que a semântica de é, de acordo com o teorema do ponto fixo de KleeneωF,Gf,gF,GY(fg)

(1 1)=[[Y(fg)]]={,F(G()),F(G(F(G()))),}
que indica o limite superior / mínimo superior.

Da mesma forma, temos

(2)=[[f(Y(gf)]]=F({,G(F()),G(F(G(F()))),})

Por continuidade, obtemos

(2)={F(),F(G(F())),F(G(F(G(F())))),}

Pode-se então provar que observando que qualquer elemento de qualquer cadeia está delimitado acima por algum elemento da outra cadeia. De fato, temos estabelecendo isso . Além disso, que , concluindo a prova.(1 1)=(2)

F(),F(G())F(G(F())),
(1 1)(2)
F()F(G()),F(G(F()))F(G(F(G()))),
(2)(1 1)

Muito menos formalmente, o termo expressa a aplicação infinita e, da mesma forma, expressa É bastante natural, portanto, que a aplicação de um único em cima do segundo resulte no primeiro. A prova teórica do domínio acima fornece uma justificativa formal disso.Y(fg)

f(g(f(g())))
Y(gf)
g(f(g(f())))
f
chi
fonte