Variáveis livres e ligadas no Cálculo Lambda §

---

No cálculo lambda, as variáveis são os blocos básicos que usamos para construir expressões e funções.

Mas nem todas as variáveis têm o mesmo “status”. Algumas estão “amarradas” a uma definição específica, enquanto outras “flutuam” livremente, sem uma ligação clara.

Esses conceitos (variáveis ligadas e variáveis livres) são fundamentais para entender como as expressões funcionam e como as substituições ocorrem.

Definição §

No cálculo lambda, as variáveis podem ser classificadas em dois tipos com base em sua relação com o símbolo :

• Variável ligada: Uma variável é considerada ligada se todas as suas ocorrências no corpo de uma expressão são precedidas por um , que a define como um parâmetro. O (função) “liga” a variável ao seu escopo.
• Variável livre: Uma variável é livre se ela aparece em uma expressão sem estar associada a um que a preceda diretamente na mesma sub-expressão.

Formalmente:

• Em , todas as ocorrências de no corpo são ligadas por .
• Qualquer variável em que não seja precedida por um correspondente é livre.

Todos os nomes no cálculo lambda são locais às suas definições, ou seja, o escopo de uma variável ligada é restrito à expressão onde ela é definida pelo .

O Papel do como “ligador” §

O símbolo atua como um marcador que “captura” uma variável e define seu escopo. Quando escrevemos , estamos dizendo que é um parâmetro da função, e qualquer que apareça em está vinculado a esse .

Isso é semelhante a como parâmetros funcionam em linguagens de programação: o escopo da variável é limitado à função onde ela é declarada.

Variáveis livres e o contexto externo §

Uma variável livre, por outro lado, não tem um que a “prenda” dentro da expressão em que aparece. Ela depende de um contexto externo para ter significado.

Escopo e Sub-expressões §

Em expressões maiores, o mesmo nome pode aparecer em diferentes contextos. Cada cria um novo escopo, e uma variável só é ligada ao mais próximo que a define.

Exemplos §

Exemplo 1: Variável ligada e livre em uma expressão simples §

Considere a expressão:

Aqui, é ligado porque aparece no corpo da função e é precedido por .

Já é livre, pois não há um que o defina nesta expressão. O valor de dependeria de um contexto externo.

Exemplo 2: Múltiplos escopos §

Agora, analise esta expressão mais complexa:

Na sub-expressão :

• é ligado pelo primeiro .

Na sub-expressão :

• é ligado pelo segundo .
• é livre, pois não há um nesta sub-expressão que o ligue. O aqui não está conectado ao da primeira parte, porque os escopos são separados.

Quando avaliamos essa aplicação, o livre em permanece livre, indicando que seu valor viria de fora da expressão.

Referências §

---

Aula 1 - Cálculo Lambda