Lógicas Combinatoriais e
Implementações
Rafael Dueire Lins
Departamento de Informática
Universidade Federal de Pernambuco
Lógica Combinatorial
 Moses
Schönfinkel - 1920
• Eliminação das variáveis da lógica
de primeira ordem
• Combinação de funções constantes
(combinadores) através de
aplicações
 Haskell
B. Curry
• Redescobriu a lógica combinatorial
Lógica Combinatorial
 Evita
o problema da captura
x.(y.yx)) y
 [y/x] x.(y.yx)) = y.yy
 Equivalente
ao -Calculus
• Bracket Abstraction Algorithm
 Expressão em combinadores SK
Bracket Abstraction Algorithm
Schönfinkel - 1924
[x]
=x
[a b]
= [a] [b]
[x.a] = [x] [a]
[x] x = S K K
[x] y = K y, se x  y é var e Cte
[x] (ab) = S ([x] a) ([x] b)
Bracket Abstraction Algorithm
Exemplo:
S = a.b.c.ac (bc)
[a] ([b] ([c] ac (bc)))
= [a] ([b] (S([c] ac) ([c] bc)))
= [a] ([b] (S( S ([c] a) ([c] c))
(S ([c] b) ([c] c)))
= [a] ([b] (S( S (K a) (SKK)
(S (K b) (SKK)))
Bracket Abstraction Algorithm
Exemplo:
Y = f.(y.f(yy))(y.f(yy)))
...
= (S(S(KS)(S(KK)(SKK)))
(K(S(SKK)(SKK))))
(S(S(KS)(S(KK)(SKK)))
(K(S(SKK)(SKK))))
Regras de Redução
K a b => a
S a b c => a c (b c)
I a => a
aplicação: associativa a esquerda
abc = (ab) c
Máquina de Turner
 SASL (St. Andrews Static Language)
 Interpretador
 1a linguagem para ensino
 Utilizou SECD
 Primeiro
a explorar a tradução de
linguagens funcionais para
combinadores
Máquina de Turner

Lógica combinatorial pura
 S, K e I
 Explosão exponencial do código

Grande conjunto de combinadores
 Evita a geração de K
 Novo algoritmo de abstração
 Expansão quadrática do código
Bracket Abstraction Algorithm
Turner - 1979
[x]
=x
[a b]
= [a] [b]
[x.a] = [x] [a]
[x] x
=I
[x] y
= K y,
x  y é var e Cte
[x] (a b) = B a ([x] b),
se a Cte
[x] (a b) = C ([x] a) b,
se b Cte
[x] (a b) = S ([x] a) ([x] b)
Bracket Abstraction Algorithm
Turner - 1979
[x] ((a b) c) = B1 a b ([x] c),
a e b Cte
[x] ((a b) c) = C1 a ([x] b) c,
a e c Cte
[x] ((a b) c) = S1 a ([x]b) ([x]c), a Cte
Combinadores de Turner
Ix

Kcx

Sfgx

Bfgx

Cfgx

S1 c f g x 
B1 c f g x 
C1 c f g x 
Yx

x
c
f x (g x)
f (g x)
fxg
c (f x) (g x)
c f (g x)
c (f x) g
x (Y x)
Máquina de Turner

Máquina de redução de Grafos para
interpretar as expressões de
combinadores

Stack: próximo combinador mais a
esquerda

unwind local após cada redução
Máquina de Turner

Operador de ponto fixo explícito
@
@
y

x
Y x => x (Y x)
y
Estratégia knot-tieing para
manipulação de grafos
@
y
@
y x
De interpretação `a Compilação
 Cardelli
(1983) - FAM
 Linguagens Funcionais estritas
 Johnsson
(1987) - Máquina G
Melhores características da
máquina SECD e a máquina de
Turner
A Máquina G

Johnsson (1987) - Chalmers

Funciona como um interpretador com
geração de grafos preguiçosa

Primeira implementação eficiente
para linguagem funcional preguiçosa

O grafo é gerado apenas quando
necessário
A Máquina G

A forma de controlar o fluxo de
execução e avaliação foi seguida por:
 Spineless G-Machine
 Spineless Tagless G-Machine
 TIM
 GM-C
list 0, where
list n = square n : list (suc n)
 square x = x * x
 suc
x=x+1

:
@
@
list
0
square
@
0
@
list
suc
:
Output: 0
@
0
0
@
@
list
0
suc
0
suc
0
:
@
square
suc
@
suc
:
@
1
@
@ list
0
@
list
1
@
list
suc
Máquinas Categóricas
 Teoria
das Categorias
• Teoria de funções útil para
implementar linguagens funcionais
 Combinadores
Categóricos
• CAM: máquina de pilha
Máquinas Categóricas
 Lins
• Implementações baseadas em
Multi-Combinadores Categóricos
• C foi usado como um macroassembler
¨ Portabilidade
¨ Simplicidade
¨ Eficiência
• Controle de Fluxo - Máquina Abstrata
CMC
 Controle
de fluxo em C
 Funções Especiais
• Funções estritas em todos seus
argumentos que produz tipos
básicos como resultado
• Traduzida diretamente para C
• Vantagens do rápido chaveamento
de contexto das máquinas RISC
• Expressões Aritméticas