domingo, 24 de agosto de 2014

Combinador de ponto fixo

Glider A beleza da matemática e do cálculo é que algo não precisa ter uma aplicação prática imediata para ser estudado em profundidade. A aplicabilidade pode surgir 150, 200 anos após sua concepção.

Um dos tópicos mais magníficos do cálculo-λ é o combinador de ponto fixo, apesar de ser de interesse mais acadêmico do que diretamente prático.

Ainda assim, seu entendimento engrandece em tamanha proporção o conhecimento do programador, que vale a pela dedicar-lhe algum tempo.

Conceitos básicos

Há alguns pré-requisitos que você precisa conhecer para começar nosso estudo:

Cálculo-λ

Cálculo-λ é uma parte da lógica matemática criada da década de 1930 como parte da investigação dos fundamentos da matemática. No cálculo-λ, todos os elementos são funções de primeira classe, inclusive os números.

Por exemplo, o número 2 é uma função que aplica uma outra função duas vezes, e é representado como λsz.s(sz).

O sinal + (ou S em alguns textos) significa incremento, e é descrito como λwyx.y(wyx). Ou seja, +3 é 3 incrementado, que é igual a 4. 2+3 é a função 2 recebendo como parâmetros + e 3, ou seja, incrementa duas vezes o número 3, +(+3), o que resulta em 5.

A multiplicação é prefixal, não mesoclítica, ou seja, 2x escreve-se como *2x (ou M2x) e sua definição é λab.a(b+)0 ou λxyz.x(yz).

O cálculo-λ é o princípio de onde deriva a programação funcional.

[update 2014-08-25]
A definição de decremento é (caso eu não tenha copiado errado):
DEC = λnfx.n (λgh.h(gf)) (λu.x) I
[/update]

Ponto fixo

Impossível entender combinador de ponto fixo sem saber o que significa ponto fixo. Ponto fixo é o ponto de uma função onde o valor retornado é igual ao valor fornecido.

Por exemplo, dada a função f(x) = 2x-1, o que em notação cálculo-λ fica f = λx.DEC(*2x), o ponto fixo é aquele onde fx = x, ou seja, o resultado é igual ao parâmetro.

Usando aritmética básica:
f(x) = 2x - 1
x = 2x - 1
2x - 1 = x
2x - 1 - x = 0
x - 1 = 0
x = 1

Portanto o ponto fixo de λx.DEC(*2x) é 1.

Repare que a recursão sobre o ponto fixo resulta sempre no mesmo resultado. Se:
x = fx

Podemos substituir x por fx:
x = fx = f(fx) = f(f(fx))) = ...


Variáveis livres e vinculadas

Em cálculo-λ, no corpo de uma função, todas as variáveis que vêm de sua assinatura são vinculadas e as que vêm de fora são livres.

Por exemplo, na função:
λfx.Δxf


As variáveis x e f são vinculadas e a variável Δ é livre.

Combinadores

Combinadores são funções que não possuem variáveis livres. Por exemplo:
λx.xx
λx.y

A primeira linha é um combinador, já a segunda não.

Veja que, a rigor, números e operadores aritméticos são variáveis livres, porém, como são valores constantes e bem definidos, tratam-se de exceções aceitáveis em um combinador.

Construção let

A construção let é uma construção clássica em cálculo-λ e em linguagens funcionais de programação.

Darei um exemplo: seja fx igual a *2x em f4, o resultado é 8 – fx é o dobro e x e o caso é f4. Isso é descrito assim:
let fx = *2x in f4

Podemos construir uma função assim, por exemplo, dado o parâmetro x, sendo fa igual a *2a em fx-1:
λx.let fa = *2a in DEC(fx)

É o mesmo que:
λx.DEC(*2x)

Em Haskell isso pode ser escrito assim:
func x = let f a = 2 * a in f x - 1

Em Racket fica assim:
(describe func
  (λ (x)
    (let ((f (λ (a) (* 2 a)))
      (- (f x) 1))))

A forma genérica da construção let é:
let fx = y in z

E sua abertura é:
(λf.z)(λx.y)


Finalmente: o combinador de ponto fixo

Combinador de ponto fixo é uma função que retorna o ponto fixo da função fornecida como parâmetro. Em cálculo e mesmo em programação isso é muito útil na implementação de funções recursivas.

Função recursiva é aquela que faz chamada a ela mesma, por exemplo, fatorial:
FACT = λn.(ISZERO n) 1 (*n (FACT (DEC n)))

Olhando para o corpo da função, mesmo desconsiderando números e operadores (ISZERO, 1, * e DEC), ainda há a variável livre FACT, que não é definida na assinatura da função.

[update 2014-08-25]
A definição de ISZERO é:
TRUE = λxy.x
FALSE = λxy.y
ISZERO = λn.n(λx.FALSE)TRUE
[/update]

A forma de resolver isso é criar uma função que recebe a si mesma na assinatura:
ALMOST-FACT = λfn.(ISZERO n) 1 (*n (f (DEC n)))

Quando esse combinador recebe como parâmetro o fatorial, ele retorna o próprio fatorial, assim a função fatorial é o ponto fixo dele!

O combinador de ponto fixo é aquele que, ao receber a função como parâmetro, retorna seu ponto fixo – e quando a função recebe o ponto fixo, retorna o próprio ponto fixo, segundo o seguinte comportamento:
yf = f(yf)

Só aqui já seria possível implementar uma função que calcule o ponto fixo. Em Haskell:
fix f = f (fix f)

E em Lazy Racket:
(define fix
  (λ (f)
    (f (fix f))))

Porém seria sem sentido, pois essa mesma função que resolve o problema, é parte do problema, já que ela própria possui variável livre.

Resolver este problema não é difícil: basta pegarmos a definição: dada uma função f, queremos o ponto x onde fx seja igual a x… é uma construção let!

Data uma função que recebe f (λf.), seja x igual a fx (let x = fx) em x (in x):
λf.let x = fx in x

De fato isso já funciona em Haskell:
fix :: (a -> a) -> a
fix f = let x = f x in x


Combinador Y

Para Scheme (Lazy Racket), precisamos destrinchar um pouco mais, abrindo o let.

Precisamos de dois parâmetros na primeira posição, portanto dobraremos o x:
λf.let x = fx in x
λf.let xx = f(xx) in xx
λf.(λx.xx)(λx.f(xx))

Mais um passo e chegamos ao famoso combinador Y de Curry!

Aplicando o parâmetro λx.f(xx) à função λx.xx, temos (λx.f(xx))(λx.f(xx)), exatamente o combinador Y de Curry:
Y = λf.(λx.f(xx))(λx.f(xx))

Em Lazy Racket:
(define Y
  (λ (f)
    ((λ (x) (f (x x))) (λ (x) (f (x x))))))


Linguagens estritas

A maioria das linguagens não suporta lazy evaluation, então é preciso fazer um truque para que a definição do combinador não entre em loop infinito.

O truque é aplicar a função λsv.sv (que é o número 1, equivalente à identidade: I = λx.x). Por exemplo:
g = 1g
g = (λsv.sv) g
g = (λv.gv)

Por exemplo, o combinador Y em Python:
Y = lambda f: (lambda x: x(x))(lambda x: f(x(x)))

Esse código entra em loop infinito! Mas se substituirmos xx por λv.xxv, tudo se resolve:
Y = lambda f: (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args)))


Outros combinadores de ponto fixo

Curry foi o que obteve a solução mais simples para o combinador de ponto fixo, mas não foi o único. Há outras soluções possíveis.

Combinador de Turing:
Θ = (λx.xx)(λab.b(aab))


Combinador de ponto fixo estrito (vimos acima):
Z = λf.(λx.xx)(λx.f(λv.xxv))

Combinador de ponto fixo não padrão:
B = λwyx.w(yx)
∆ = λx.xx
N = B∆(B(B ∆)B)

[]’s