
Introdução ao -calculus
Prof. Gustavo Motta
Departamento de Informática/UFPB
00
(c) 2007 Gustavo Motta
1
-calculus
Sumário
 Histórico
 Variáveis e funções na matemática e nas
linguagens de programação
 Domínios, tipos e funções de alta ordem
 Funções polimórficas e Currying
00
(c) 2007 Gustavo Motta
2
-calculus
Histórico
 Alonzo Church -1930s

Teoria unificada de funções
abrangendo todos os tipos de
funções da matemática


Definição, aplicação e recursão
Resposta negativa ao
Entscheidungsproblem -1936

Definiu o que é uma função
computável

Influência na ciência computação

00
Linguagens funcionais
(c) 2007 Gustavo Motta
Alonzo Church (1903–1995)3
-calculus
Introdução – Variáveis
e funções na
matemática e nas linguagens de programação
 Variável na matemática

Toda ocorrência refere-se a um mesmo valor
x  2x  3
2
 Variável nas linguagens de programação

Qual é o seu sentido?
x  x 1
00
(c) 2007 Gustavo Motta
4
-calculus
Introdução – Variáveis
e funções na
matemática e nas linguagens de programação
 Modos de uso de variáveis em textos matemáticos

Ocorrência livre de variáveis
x  2x  3
2


x representa um valor fixo implicitamente definido por
uma equação ou outra relação
Ocorrência amarrada (bounded) de variáveis
1
x
e
 dx
x( x 2  5x  6  0)
0
00
(c) 2007 Gustavo Motta
5
-calculus
Introdução – Variáveis
e funções na
matemática e nas linguagens de programação
 O problema

Distinguir variáveis livres e amarradas
x  3x  3x  1
3

2
A variável x é livre ou amarrada?
 Sendo a expressão uma função, então x é considerada
amarrada, mesmo que implicitamente

A notação lambda força a diferenciação entre
variáveis livres e amarradas com o uso do símbolo ‘’
x.( f ) x
x.x
00
(c) 2007 Gustavo Motta
6
-calculus
Introdução – Variáveis
e funções na
matemática e nas linguagens de programação
 Funções na matemática

Enfoque intensional (conotativo)

Procedimento computacional para computar o valor
da função para um dado argumento

Caráter dinâmico, conceito original

Similar nas linguagens de programação
 Função unicamente definida por um procedimento

Pressupõe uma descrição finita de uma função em
termos de um procedimento para computação
00
(c) 2007 Gustavo Motta
7
-calculus
Introdução – Variáveis
e funções na
matemática e nas linguagens de programação
 Funções na matemática

Enfoque extensional (denotativo)
 Postula
a existência
um valor da equal
função para um
Definição 1.1
Duas funções
sãodeextensionally
se e somentedado
se elas
têm o mesmo
valor para
todo
argumento
sem especificar
como
computá-los
argumento.
 Caráter estático, baseado na teoria de conjuntos
f  g  x  f ( x)  g ( x)
 Funções como conjuntos de pares ordenados

Diferentes funções conotativas (procedimentos)
podem computar a mesma função denotativa
 Não é decidível, em geral, se duas funções definidas
procedimentalmente são extensionally equal
00
(c) 2007 Gustavo Motta
8
-calculus
Introdução – Domínios, tipos
e funções de alta ordem
 Sejam D (domínio) e R (co-domínio) dois conjuntos

Uma função é definida por um conjunto de pares
ordenados
[(x, y) | x  D, y  R]
onde o segundo componente é unicamente
determinado pelo primeiro

00
Caso a função tenha exatamente um par (x, y) para
cada x  D, então ela é chamada função total, caso
contrário é chamada função parcial
(c) 2007 Gustavo Motta
9
-calculus
Introdução – Domínios, tipos
e funções de alta ordem

Uma função com domínio D e co-domínio R
também é chamada de mapeamento de D para
R e seu conjunto pares é denominado de grafo

Existem muitas funções diferentes de D para R
cada uma tendo o tipo [D  R], D ≠ , R ≠ 

Para D e R finitos, o número de funções totais
possíveis para o tipo [D  R] é R

D
O conjunto de todas as funções com tipo
[D  R] é chamado espaço de função R D
00
(c) 2007 Gustavo Motta
10
-calculus
Introdução – Domínios, tipos
e funções de alta ordem

Se R tem pelo menos dois elementos
RD  D

O conjunto de todas as funções com tipo [  ]
é não enumerável

O conjunto de funções computáveis é enumerável

Tem um procedimento computacional, i. e., uma
máquina de Turing associada
 Máquinas de Turing podem ser enumeradas
 Expressão  formada por strings finitos num alfabeto finito

00
A grande maioria das funções com tipo [  ] é
não computável
(c) 2007 Gustavo Motta
11
-calculus
Introdução – Domínios, tipos
e funções de alta ordem

Existe uma propriedade definível extensionally que
permita distinguir o grafo das funções computáveis
do grafo das funções não computáveis?

Os grafos das funções computáveis devem ser
“contínuos” num sentido abstrato
 Base para construção de um modelo matemático para o
-calculus sem tipos

O propósito original do -calculus foi prover um
framework para o estudo das propriedades formais de
funções arbitrárias
 Objetivo ambicioso, não alcançado
 Usada para estudo das funções computáveis
00
(c) 2007 Gustavo Motta
12
-calculus
Introdução – Domínios, tipos
e funções de alta ordem

Não se pode ter uma expressão  para cada
função com tipo [  ]


-calculus com tipos consideram o domínio e o
co-domínio das funções relevantes no
tratamento formal


00
O conjunto de “contínuas” coincide com o conjunto
de funções que podem ser precisamente descritas
por expressões , i. e., funções computáveis
Toda variável tem um tipo associado
Tipos são conjuntos de valores com operações
associadas
(c) 2007 Gustavo Motta
13
-calculus
Introdução – Domínios, tipos
e funções de alta ordem

integer, boolean, real, char, array, class

O espaço de função R D é um conjunto

Usado para construção de tipos funções
Pode ser usado como domínio e co-domínio de
3
2
2
O par ( outras
f ( x) 
x

3
x

3
x

1
,
f
(
x
)

3
x
 6 x  3)
funções
faz parte doD conjunto
de pares desta função, então,
D
] é um tipo
para funções de alta ordem
R  Ré aplicada,
quando a [função
tem-se
(ou funcionais), funções que recebem funções como
d ( f ( x)  x3  3x 2  3x 1)  f ( x)  3x 2  6 x  3
argumento e devolvem funções como resultado

 A função que calcula a derivada simbólica é uma função
de segunda ordem
00
(c) 2007 Gustavo Motta
14
-calculus
Introdução – Funções polimórficas e currying
 O problema

Uma função para calcular o número de elementos
de uma lista não deveria depender do tipo dos
elementos da lista
 A solução – funções polimórficas

Uma função é dita polimórfica se o tipo de pelo
menos um de seus argumentos puder variar de
chamada para chamada
00
(c) 2007 Gustavo Motta
15
-calculus
Introdução – Funções polimórficas e currying
Object
clone
equals
…
 Exemplo
...
void serialize(Object obj) {
...
Point
x, y
distance
move
draw
}
...
Date
y, m, d
…
Circle c = new Circle(...);
Date d = new Date(...);
... serialize(c); ...
... serialize(d); ...
00
Circle
r
draw
diameter
(c) 2007 Gustavo Motta
Rectangle
w, h
draw
width
height
16
-calculus
Introdução – Funções polimórficas e currying
 O tipo de uma função relaciona-se com a aridade

A função de adição de naturais tem o seguinte tipo

[    ]

Quando estendida para um número de argumentos
add (a, b) = a + b
arbitrário é chamada de poliádica
 Por exemplo, a função  é poliádica e o seu domínio é
   (  )  (    )  …
00
(c) 2007 Gustavo Motta
17
-calculus
Introdução – Funções polimórficas e Currying
 Linguagens de programação convencionais não
suportam funções poliádicas

Soluções

Funções com um único parâmetro, que é uma
seqüência de valores – arrays ou listas

Adotar a solução de Currying (Haskell B. Curry)
 Técnica de transformar uma função que toma múltiplos
argumentos numa função que toma um argumento por vez
 O -calculus sem tipos adota funções Curryed
00
(c) 2007 Gustavo Motta
18
-calculus
Introdução – Funções polimórficas e Currying
 Exemplo de Currying


00
Função tradicional

[    ]

add(10)  erro
add (a, b) = a + b
Função Curryed

[  [  ]]

add (10)  add (b) = 10 + b
add (a) (b) = a + b
[  ]
(c) 2007 Gustavo Motta
19
-calculus
Bibliografia

00
Revesz, G. E. Lambda-Calculus, Combinators, and
Functional Programming. Cambridge University
Press, 1988.
(c) 2007 Gustavo Motta
20