
Introdução ao -calculus
Prof. Gustavo Motta
Departamento de Informática/UFPB
03
(c) 2007 Gustavo Motta
1
-calculus
Sumário
 Expressões- sem variáveis livres
 Combinadores aritméticos, constantes & Cia.
03
(c) 2007 Gustavo Motta
2
-calculus
Expressões- sem variáveis livres
 Expressões- com variáveis livres são dependentes
do contexto


Sentido (ou valor) depende de suas variáveis livres
Usar uma expressão- num certo contexto significa
usá-la como subexpressão em outra expressão

x.(y)x usada no contexto ((x.y.hole)E)F
resulta em ((x.y.x.(y)x)E)F  x.(F)x
 Note que a ocorrência livre de y foi capturada pelo
contexto onde a subexpressão foi empregada

03
Um contexto é uma expressão- com um ou mais
holes (lacunas)
(c) 2007 Gustavo Motta
3
-calculus
Expressões- sem variáveis livres

Note a diferença entre usar uma expressão- E
num contexto C e a substituição de hole por E,
com hole sendo variável livre em C

((hole.C)E  [E / hole]C
 Nesse caso, as varáveis livres não são capturadas
 Variáveis livres  variáveis globais


03
Variáveis livres numa expressão- correspondem a
variáveis globais usadas num bloco aninhado ou
no corpo de um procedimento numa linguagem
de programação convencional
Variáveis amarradas correspondem a parâmetros
formais ou a variáveis locais
(c) 2007 Gustavo Motta
4
-calculus
Expressões- sem variáveis livres
 Expressões- sem variáveis livres são independentes
do contexto

Comportam-se da mesma forma em qualquer
contexto


Similares a símbolos constantes
A expressão- x.x representa a transformação de
identidade em qualquer contexto
 Combinadores

03
Definição - Expressões- sem variáveis livres são
chamadas de expressões- fechadas ou de
combinadores
(c) 2007 Gustavo Motta
5
-calculus
Expressões- sem variáveis livres
 Usados para “combinar” funções na formação de
novas funções
 Exemplos

Combinador identidade - I

I é considerado um símbolo constante (ou palavra
reservada) e não uma variável

Representa uma classe de expressões- -congruentes

Definido como
I  x.x
03
(c) 2007 Gustavo Motta
6
-calculus
Expressões- sem variáveis livres
 Exemplos
 Combinador composição - compose

Define a composição de duas funções f e g
compose  f.g.x.(f)(g)x
 Tratamento de símbolos para combinadores


(1) Abreviação para expressões-
(2) Considerá-los atômicos e introduzir regras de
redução específicas
(I)E  E
(((compose)F)G)E  (F)(G)E
03
(c) 2007 Gustavo Motta
7
-calculus
Expressões- sem variáveis livres
 Exemplos

Combinadores booleanos
true  x.y.x
false  x.y.y

Regras de redução
((true)P)Q  P
((false)P)Q  Q

03
Seleciona uma de duas alternativas
(c) 2007 Gustavo Motta
8
-calculus
Expressões- sem variáveis livres

Combinadores booleanos

A expressão condicional
If C then P else Q

toma a forma
((C)P)Q


na notação , com P e Q denotando expressões-
arbitrárias e C sendo redutível a x.y.x ou a x.y.y
Representada pelo combinador
c.p.q.((c)p)q
 Lembrem-se que o lambda-calculus é livre de tipos
03
(c) 2007 Gustavo Motta
9
-calculus
Combinadores aritméticos,
constantes & Cia.
 Observações

Valores verdade e operadores booleanos padrão
podem ser representados por combinadores
específicos


Comportam-se da mesma maneira em diferentes
contextos
Em princípio, não há diferença entre um valor constante
como true ou false e uma função bem definida
como and
 De fato, toda função bem definida pode ser considerada
uma entidade constante
 Mesmo os valores verdade são representados por funções
03

Quase tudo pode ser representado dessa maneira
(c) 2007 Gustavo Motta
10
-calculus
Combinadores aritméticos,
constantes & Cia.
 Representação dos números naturais

Numerais de Church
0  f.x.x
1  f.x.(f)x
2  f.x.(f)(f)x
3  f.x.(f)(f)(f)x

03
Em geral, o combinador representando o n-ésimo
número realiza n iterações do primeiro argumento
sobre o segundo
(c) 2007 Gustavo Motta
11
-calculus
Combinadores aritméticos,
constantes & Cia.
 Representação dos números naturais

Operadores aritméticos
succ  n.f.x.(f)((n)f)x
(n.f.x.(f)((n)f)x)f.x.(f)x
f.x.(f)((f.x.(f)x)f)x
f.x.(f)(x.(f)x)x
f.x.(f)(f)x  2

03
Notem que o nome das variáveis bounded não é
importante
(c) 2007 Gustavo Motta
12
-calculus
Combinadores aritméticos,
constantes & Cia.
 Representação dos números naturais

Operadores aritméticos
+  m.n.f.x.((m)f)((n)f)x
((m.n.f.x.((m)f)((n)f)x)f.x.(f)(f)x)f.x.(f)(f)(f)x
(n.f.x.((f.x.(f)(f)x)f)((n)f)x)f.x.(f)(f)(f)x
f.x.((f.x.(f)(f)x)f)((f.x.(f)(f)(f)x)f)x
f.x.(x.(f)(f)x)(x.(f)(f)(f)x)x
f.x.(x.(f)(f)x)(f)(f)(f)x
f.x.(f)(f)(f)(f)(f)x
03
5
(c) 2007 Gustavo Motta
13
-calculus
Combinadores aritméticos,
constantes & Cia.
 Representação dos números naturais

Operadores aritméticos
*  m.n.f.(m)(n)f

Teste de zero
zero  n.((n)(true)false)true
(n.((n)(true)false)true)f.x.(f)x
((f.x.(f)x)(true)false)true
(x.((true)false)x)true
((true)false)true  false
03
(c) 2007 Gustavo Motta
14
-calculus
Combinadores aritméticos,
constantes & Cia.
 Representação dos números naturais

Operadores aritméticos

A representação da operação predecessor, que resulta
em n – 1 para n > 0 e 0 para n = 0 é engenhosa
 Representar pares do tipo [n, n – 1] na notação-, onde
um par qualquer [a, b] é dado por
z.((z)a)b
tendo as seguintes propriedades
(z.((z)a)b)true  a
(z.((z)a)b)false  b
03
(c) 2007 Gustavo Motta
15
-calculus
Combinadores aritméticos,
constantes & Cia.
 Representação dos números naturais

Operadores aritméticos
 Define-se então a função next, para obter [n + 1, n] a partir de
[n, n – 1], que corresponde à seguinte expressão-
next  p.z.((z)(succ)(p)true)(p)true
Aplicando esse operador a partir do par z.((z)0)0, temos
((n)p.z.((z)(succ)(p)true)(p)true)z.((z)0)0
Agora, para se ter a função predecessor, basta selecionar o
segundo elemento do par ordenado resultante
pred  n.(((n)p.z.((z)(succ)(p)true)(p)true)z.((z)0)0)false
03
(c) 2007 Gustavo Motta
16
-calculus
Bibliografia

03
Revesz, G. E. Lambda-Calculus, Combinators, and
Functional Programming. Cambridge University
Press, 1988.
(c) 2007 Gustavo Motta
17