Frank Coelho de Alcantara - 2021
Introduzido, nos anos 1930, por Alonzo Church. Estudo da computação por funções.
Equivalente a Máquina de Turing.
Notação minimalista: expõe apenas o que é necessário para computação com funções.
Duas operações essenciais: criação e aplicação.
Uma abstração: abstração lambda: $$\lambda x.E$$
Representando uma função ($\lambda$) com argumento $x$ e corpo $E$. O $E$ chamado de termo $\lambda$ ou expressão $\lambda$. Ou ainda, de escopo da abstração.
As funções não possuem nomes. $\lambda$ é um signo, uma notação para indicar o início da definição de uma função.
Uma função que tem um parâmetro $x$ e retorna alguma coisa definida pelo corpo $E$.
Abstração lambda ou função anônima unária.
O coração do cálculo lambda e da programação funcional são as funções anônimas.
E as linguagens funcionais, puras ou não: LISP, Scheme, Clojure, Scala, Ocaml, F#, Haskell, ... .
A medida que avançamos na álgebra podemos notar que a palavra cálculo representa um conjunto de regras que determinam como podemos mover símbolos ($x,y,z,...$) em uma página em busca de simplificação ou significado. Isto é válido para integrais, diferenciais, equações diferenciais, transformadas, etc..
O cálculo lambda está relacionado com definir e avaliar funções e é composto de uma linguagem e das regras de manipulação desta linguagem.
$f(x) = a$ escreve-se: $\lambda x.\space a$
$g(x)=x$ escreve-se: $\lambda x. \space x$
$f(x) = x^2+3x+1$ escreve-se: $(\lambda x.x^2+3x+1)$
No último exemplo leremos: a função que, dado o argumento $x$ calcula o valor de $x^2+3x+1$.
Não é necessário mas fica mais claro assim:$(\lambda x.\space (x^2+3x+1))$
| expression | ::= | constante | |
| | | variable | <=identificador | |
| | | expression expression | <=aplicação | |
| | | $\lambda$ variable.expression | <=abstração | |
| | | (expression) | <=agrupamento |
Constante: números ou funções prédefinidas.
Variable: identificadores como $x$ ou $y$.
Considere: $\lambda x.((+\space 1)\space x)$:
| expression | $\Rightarrow$ | $\lambda$ variable.expression |
| $\Rightarrow$ | $\lambda x.$expression | |
| $\Rightarrow$ | $\lambda x.$(expression) | |
| $\Rightarrow$ | $\lambda x.$(expression expression) | |
| $\Rightarrow$ | $\lambda x.$((expression) expression) | |
| $\Rightarrow$ | $\lambda x.$((expression expression) expression) | |
| $\Rightarrow$ | $\lambda x.$((constante constante) expression) | |
| $\Rightarrow$ | $\lambda x.((+\space 1)$ expression) | |
| $\Rightarrow$ | $\lambda x.((+\space 1)$ variable) | |
| $\Rightarrow$ | $\lambda x.((+\space 1)\space x)$ |
Os parênteses são utilizados na aplicação e para eliminar qualquer ambiguidade na interpretação.
Mais claro $(\lambda x.((+\space 1)\space x))$ que $(\lambda x.\space +\space 1\space x)$
Lembre-se, ao colocar, ou retirar, parênteses que você está escrevendo para que outros leiam.
Se outra pessoa não conseguir entender a expressão que você escreveu, em alguns dias, você também não entenderá.
$x$,$y$,$2$,$4$ são expressões lambda válidas que podem ser representados pelas seguintes abstrações:
Também é possível escrever qualquer numero com abstrações lambda veja: Church Encoding.
Com o cálculo Lambda podemos definir:
O cálculo lambda é considerado "a menor linguagem de programação" e permite a criação de qualquer algoritmo. Dá tanto trabalho quanto o Assembly.
A operação básica do cáculo lambda é a aplicação de funções.
Considere: $\lambda x.((+\space 1)\space x)$
Podemos aplicar a esta função o valor 3: $\lambda x.((+\space 1)\space x)\space 3$
Neste caso estamos aplicando o valor 3 à função $\lambda x.((+\space 1)\space x)$
Logo: $$\lambda x.((+\space 1)\space x)\space 3 = (+\space 1\space 3) \Rightarrow 4$$
Só para reforçar, dizemos que aplicamos à função o valor 3. Historicamente chamamos este processo de beta-conversion ou beta-reduction.
Observe que não encontramos um resultado. Encontramos o significado da aplicação. Esta é a forma normal, ou $\beta$-normal.
Chamamos de beta-conversion, beta-reduction ou $\beta$-conversion ao processo de substituir uma variável ligada, no corpo da abstração lambda, pelo argumento passado pela aplicação desta função. O processo inverso, transformar uma expressão já reduzida novamente à abstração é chamado de $\beta$-abstraction.
De forma leiga, podemos dizer que a conversão beta é a aplicação da função ao seu argumento. Tome, por exemplo, a função $f_{(x)}= 3x+1$ quando aplicamos o valor 2 nesta função, teremos: $f_{(2)}= 3\times 2+1 = 7$. Isto é cálculo algébrico. O que fizemos foi aplicar (substituir) à função ao valor 2 substituindo a variável $x$, a variável da função (está ligada).
Para simplificar podemos escrever $\lambda x.((+\space 1)\space x)\space 3$ como $\lambda x.(x+1)\space 3$. Não está sintaticamente correto, mas simplifica;
Com isso temos a seguinte árvore sintática:
aplicação
/ \
λ 3
/ \
x +
/ \
x 1
Considere a função $(\lambda x.x+1)(\lambda y.y+2)\space 3$ neste caso teríamos:
Com isso temos a seguinte árvore sintática:
aplicação => aplicação => aplicação => + => 6
/ \ / \ / \ / \
λ aplicação λ + λ 5 5 1
/ \ / \ / \ / \ / \
x + λ 3 x + 3 2 x +
/ \ / \ / \ / \
x 1 y + x 1 x 1
/ \
y 2
Considere a função $(\lambda x.x+1)(\lambda y.y+2)\space 3$ E tente começar pela primeira função e escreva a árvore sintática:
Com isso temos a seguinte árvore sintática:
aplicação => + => + => + => 6
/ \ / \ / \ / \
λ aplicação aplicação 1 + 1 5 1
/ \ / \ / \ / \
x + λ 3 λ 3 3 2
/ \ / \ / \
x 1 y + y +
/ \ / \
y 2 y 2
Uma variável $x$ qualquer, em uma expressão do cálculo lambda é dita ligada (bound) se esta variável for declarada como tal em uma determinada abstração lambda.
Para $\lambda x. (\times \space 2)\space x$, $x$ é a variável ligada.
Para $\lambda y. (+\space x)\space y$, $y$ é a variável ligada.
Todas a variáveis que eventualmente ocorram na abstração e que não estejam ligadas serão ditas livres. ou globais.
Ou seja: aplicando 2 a $\lambda y.(+\space x)\space y$ teremos $\lambda y.(+\space x)\space 2 \Rightarrow (+\space 2 \space x)$
A mesma variável $x$ pode aparecer em contextos diferentes na mesma abstração lambda. Em algumas instâncias esta variável pode estar ligada e livre em outras. Tome como exemplo: $$(\lambda x. \space+\space(\lambda y.((\lambda x. \times \space x\space y\space )\space 2)) \space x) \space y) $$
Observe que a variável $x$ após o $\times$ está em uma ligação diferente da variável $x$ mais externa.
Observe também que o primeiro $y$ está ligado e que o segundo é livre.
Uma abstração lambda sem variáveis livres são chamadas de combinadores, ou de expressões fechadas.
Combinadores são usados para combinar funções.
O menor combinador possível é a função identidade $I$ $$I \equiv \lambda x.\space x$$
A função identidade, quando avaliada tem o significado da própria variável. $$(\lambda x.\space x) 5 \Rightarrow 5$$
Tomemos a função: $$((\lambda a.a) \lambda b. \lambda c. b)(x)\lambda e.f $$
$$(\lambda b. \lambda c.b) (x)\lambda e.f$$
$$(\lambda c.x) \lambda e.f $$
$$x$$
logo $x$ é a forma $beta$-normal de $((\lambda a.a) \lambda b. \lambda c. b)(x)\lambda e.f $
Tomemos a função: $$(\lambda x. \space+\space(\lambda y.((\lambda x. \times \space x\space y\space )\space 2)) \space x) \space y) $$
Teremos: $$(\lambda x. \space+\space((\lambda y.(\times \space 2\space y\space )) \space x) \space y) $$
$$(\lambda x. \space+\space((\times \space 2\space x\space )) \space y) $$
$$(\lambda x. \space+\space(\times \space 2\space x\space ) \space y) $$
ou seja, a forma $\beta$-normal desta função é equivalente a forma algébrica: $(2x+y)$
Passar por valor é um conceito comum em linguagens de programação imperativas. O equivalente em lambda calculus seria: $$(\lambda x.(\times \space x \space x)(+\space 2\space 3))$$
$$(\lambda x.(\times \space x\space x)\space 5)$$
$$(\times \space 5 \space 5) \Rightarrow 25$$
Ou seja, avaliamos as funções imediatamente passando o resultado para a próxima função.
O nome correto é Lazy Evaluation. $$(\lambda x.(\times \space x \space x)(+\space 2\space 3))$$
$$(\lambda x.(\times \space (+\space 2\space 3)\space (+\space 2\space 3)))$$
$$(\times \space (+\space 2\space 3)\space (+\space 2\space 3))) \Rightarrow 25$$
Ou seja, passamos as funções para outra funções e só avaliamos no final.
Considere:$$((\lambda x. \space x\space x)(\lambda x.\space x\space x))$$
$$((\lambda x.\space x\space x)(\lambda x.\space x\space x))$$
O que leva a uma recursão infinita.
Considere agora: $$((\lambda y. 2)(\lambda x. \space x\space x)(\lambda x.\space x\space x)))$$
Neste caso, passando por valor, continuamos com a indefinição provocada pela recursão. Mas, se passarmos por referência, o resultado é 2 já que não variável $y$ no corpo da função.
Considere:$$(((\lambda f. (\lambda x. f\space (f\space x))) (\lambda y. (\times\space y\space y)))\space 3)$$
Muito difícil de ler... vamos mudar um pouco a notação:
$$\{(\lambda f. (\lambda x. f\space (f\space x))) (\lambda y. (\times\space y\space y))\space \} \space 3 $$
Quase deu... vamos tentar novamente:
$$\{[(\lambda x. (\lambda y. (\times\space y\space y)) \space ((\lambda y. (\times\space y\space y))\space x))] \space \} \space 3 $$
$$\{[(\lambda x. (\lambda y. (\times\space y\space y)) \space (\times\space x\space x)] \space \} \space 3 $$
$$\{[(\lambda x. (\times\space (\times\space x\space x) \space (\times\space x\space x)) \space ]\space \} \space 3 $$
$$\{[(\lambda x. (\times\space (\times\space 3\space 3) \space (\times\space 3\space 3)) \space ]\space \} \space $$
$$ (\times\space 9 \space 9) \Rightarrow 81$$
A técnica conhecida como $\alpha$-Reduction é o formalismo que nos permite mudar o nome de uma variável em uma abstração lambda.
As duas funções acima são equivalentes.
$$(\lambda x. \space +\space x\space 1) \Leftrightarrow_{\alpha} (\lambda y.\space +\space y\space 1)$$
Aplique a técnica $\beta$-Reduction, o máximo possível às seguintes abstrações:
Lembre-se que você sempre pode usar $\alpha$-Reduction.
$(\lambda z.z)(\lambda y.y\space y)(\lambda x.x\space a)$
$((\lambda x.((\lambda y.(x\space y))\space x))(\lambda z.\space w))$
Outra forma de resolver esta função incluiria a aplicação da $\alpha$-reduction.
$(((\lambda x. \lambda y.(x\space y))(\lambda y.y))\space w)$