LambdaCalculus

Lambda Cálculo e Programação
Funcional
Programação Funcional
Bacharelado em Sistemas de Informação
Maio - 2009

Alonzo Church (1903–1995)
Professor em Princeton, EUA (1929–1967) e UCLA (1967–1990)
Inventou um sistema formal, chamado λ-calculus (Lambda
Cálculo) , e definiu a noção de função computável utilizando este sistema.
O Lambda Cálculo pode ser chamado “a menor linguagem de programação universal” do mundo.
As linguagens de programação funcionais, como Lisp, Miranda,
ML, Haskell são baseadas no Lambda Cálculo.

Lambda Cálculo
O lambda cálculo pode ser visto como uma linguagem de programação abstrata em que funções podem ser combinadas para formar outras funções, de uma forma pura. O lambda cálculo trata funções como cidadãos de primeira classe, isto é, entidades que podem, como um dado qualquer, ser utilizadas como argumentos e retornadas como valores de outras funções.

Sintaxe
Uma expressão simples do lambda cálculo:
(+ 4 5)
Todas as aplicações de funções no lambda cálculo são escritas no formato prefixo.
Avaliando a expressão: (+ 4 5) = 9
A avaliação da expressão procede por redução:
(+ (* 5 6)(* 4 3)) → (+ 30 (* 4 3))
→ (+ 30 12) →

42

Sintaxe
Uma abstração lambda é um tipo de expressão que denota uma função:
(λx. + x 1)
O λ determina que existe uma função, e é imediatamente seguido por uma variável, denominada parâmetro formal da função.
(λ

x .

A função de x que

+

x

1)

incrementa x de 1

Sintaxe
Uma expressão lambda deve ter a forma:
<exp> ::=

<constante>
| <variavel>
| <exp> <exp>
| λ.<variavel> <exp>

Os parênteses podem ser utilizados nas expressões para prevenir ambiguidades.

Exemplos
(λx. x) y
(λx. f x) xy (λx. x) (λx. x)
(λx. x y) z
(λx y. x) t f
(λx y z. z x y) a b (λx y. x)
(λf g. f g) (λx. x) (λx. x) z
(λx y. x y) y
(λx y. x y) (λx. x) (λx. x)
(λx y. x y) ((λx. x) (λx. x))

Análise de Expressões Lambda
A expressão Lambda se estende para a direita

λ f. x y

≡

λ f.(x y)

A aplicação é associativa à esquerda

xyz

≡

(x y) z