Livre e vinculado no cálculo Lambda

Aqui está algo da "Sintaxe e semântica das linguagens de programação" de Slonneger:

Uma variável pode ocorrer tanto vinculada como livre na mesma expressão lambda: por exemplo, em λx.yλy.yx, a primeira ocorrência de y é livre e as outras duas são ligadas.

Presumo que a variável livre seja y logo após o λx. e os ys limitados são λy.y que eu posso entender intuitivamente. Então ((λx.yλy.yx) a) b) reduziria a (yλy.ya) b) então a bba? Alguém pode explicar como isso aconteceu? No final, é a expressão b duas vezes. Alguém pode talvez fornecer mais exemplos de variáveis vinculadas e livres?

lambda-calculus
fonte

Eu acho que Slonneger não usou um bom exemplo lá, porque pode ser facilmente interpretado como , que geralmente é a abreviação de . Eu daria um exemplo diferente: em , a última ocorrência de

λ x . y

$\lambda x.y$

λ x y

$\lambda xy$

λ x . λ y

$\lambda x.\lambda y$

(λ x . λ y . x y x) x

$(\lambda x.\lambda y. xyx)x$

x

$x$ é gratuito e os outros estão vinculados.

Jay

Respostas:

Adicionei colchetes para desambiguar

λ x . (y (λ y . (y x)))

$\lambda x.(\color{red}y (\color{green}{\lambda y}.(\color{blue}yx)))$ o vermelho

y

$y$ é livre e o azul é limitado pela abstração verde. Eu não acho que faz sentido dizer que o verde

y

$y$ está ligado, mas junto com o lambda é um aglutinante.

Podemos beta reduzir o termo uma vez

\begin{matrix} λ x . (y (λ y . (y x))) a b \\ \to_{β} & (y (λ y . (y a))) b \end{matrix}

$\begin{array}? && \lambda x.(y (\lambda y.(yx)))ab \\ &\to_\beta& (y (\lambda y.(ya)))b \end{array}$

mas não mais, pois não há redexes restantes restantes.

fonte