Paul Graham e Combinatores em Haskell

Paul Graham é um ensaísta, programador e investidor. É graduado em Cornell e possui doutorado por Harvard [1].

Como ensaísta, escreveu diversos artigos sendo o mais famosos deles o “A plan for spam” sobre o uso de um filtro Bayesiano para combater spam.

Como programador, Graham é conhecido por seu trabalho com Lisp, tendo escrito livros sobre esta linguagem e vem desenvolvendo um dialeto chamado Arc. Também desenvolveu a primeira aplicação web chamada Viaweb, posteriormente adquirida pela Yahoo!

Como investidor, fundou em 2005 a empresa Y Combinator que faz investimentos em start-ups. Algumas das empresas financiadas pela Y-Combinator são: Dropbox, Airbnb, reddit e Posterous.

Sobre o nome da empresa, eis uma tradução livre do FAQ deles:

Porque vocês escolheram o nome “Y Combinator?”

O combinador Y é uma das ideias mais legais em ciência da computação e é também uma metáfora para o que nós fazemos. É um programa que roda programas; é uma empresa que ajuda a abrir empresas.

Neste post gostaria de apresentar algumas notas de estudos sobre combinadores em Haskell, descrevendo os principais tipos de combinadores incluindo o tipo Y.


Combinadores em Haskell

Esse post teve origem durante os estudos do Capítulo 9 do Real World Haskell.

Em certo ponto do capítulo o autor menciona o termo de combinadores, não deixando muito claro o que são e para que servem. Fui pesquisar um pouco sobre o assunto e decidi escrever um post.

Um combinador pode ser definido como uma função lambda que não tem variáveis livres. Uma variável livre é uma variável que não foi passada como parâmetro na função lambda. Alguns exemplos de funções lambda em Haskell:

1) A função abaixo é um combinador pois a variável x está no parâmetro

\x -> x

2) No exemplo a seguir y é uma variável livre e portanto não é um combinador.

\x -> x y

3) Aqui ambos x e y foram passadas por parâmetro, então temos um combinador.

\x y -> x y

4) O exemplo abaixo não é um combinador porque f não foi passado como parâmetro

\x y -> f (x y)

5) A seguir temos uma pegadinha. Observe que o operador + é na verdade uma função que recebe dois argumentos, como no exemplo (4). Porém como o operador não foi passado como parâmetro, também não é um combinador.

\x y -> x + y 

Simplificadamente, podemos pensar em um combinador como uma função que recebe funções e retorna outra função resultado da combinação das funções de entrada.

Tipos de combinadores

Nas próximas seções, vamos apresentar alguns dos combinadores mais conhecidos. Esses combinadores têm como nome uma única letra maiúscula. Porém, no livro To Mock a Mocking Bird [2], Raymond Smullyman apelida os diferentes tipos de combinadores com nomes de pássaros. Por isso, cada seção terá o nome do combinador e entre parênteses o apelido dado por Smullyman.

Combinador I (Identity Bird ou Idiot Bird)

Este é o combinador mais simples, a identidade. É uma função que retorna o seu próprio parâmetro. Em Haskell podemos escrever:

i x = x

Essa é justamente a definição da função id da biblioteca Prelude.

Combinador K (Kestrel)

Esse é o combinador constante, ele recebe dois argumentos e ignora o segundo. Em Haskell podemos escrever:

k x y = x

Essa é justamente a definição da função const da biblioteca Prelude.

Combinador S (Starling)

O combinador S é uma função que pode ser definida da seguinte maneira em Haskell:

s x y z = x z (y z)

Podemos escrever o combinador I usando apenas os combinadores S e K como

i = s k k

A demonstração é a seguinte:

Aplicando a função (s k k) sobre um argumento x temos

(s k k) x = s k k x

Substituindo s por sua definição,

(s k k x) = k x (k x)

Agora seja f = (k x) uma função qualquer. Temos que k x f = x por definição, então

k x (k x) = k x f = x = i x

É possível mostrar que qualquer combinador pode ser escrito como função dos combinadores S e K!

Combinador B (Bluebird)

O combinador B pode ser escrito em função de S e K como

b = s (k s) k

Vamos ver a cara dessa função aplicada a alguns argumentos. Seja f1 = (k s). Usando currying vemos que essa é uma função que recebe um argumento e sempre retorna s. Aplicando b sobre um argumento x, temos

b x = s f1 k x = f1 x (k x) = s (k x)

Seja f2 = (k x). Temos que f2 é uma função que recebe um argumento qualquer e sempre retorna x. Assim, temos b x = s f2. Vamos aplicá-la sobre mais dois parâmetros y e z:

(s f2) y z = s f2 y z = f2 z (y z) = x (y z)

Ou seja

b x y z = x (y z)

O que esta função faz é a composição das funções x e y e é justamente a definição do operador (.) do Haskell.

Combinador C (Cardinal)

Esse combinador pode ser escrito em função dos combinadores K, S e B como

c = s (b b s) (k k)

Pode-se mostrar que esse combinador equivale a

c f x y = f y x

Essa é justamente a definição do operador flip do Prelude, que retorna uma função com a ordem dos parâmetros trocada.

Combinador Y (Sage Bird)

Simplificadamente o combinator Y é um combinador que transforma uma função não recursiva em uma função recursiva!

Antes de descrevê-lo, vamos analisar como faríamos isso sem o combinador Y. Para isso, vamos usar como exemplo uma função que calcula o fatorial [8]. Fazendo uso de recursão, podemos escrever:

fat = \n -> if n == 0 then 1 else n * fat (n - 1)
fat 5 -- imprime 120

A expressão lambda acima não é um combinador porque depende de fat, que não foi passado como parâmetro.

Vamos tentar passar a função por parâmetro então

fat' = \f n -> if n == 0 then 1 else n * f (n - 1)

Observe que fat’ não é uma função recursiva. Agora fazemos o seguinte:

fat = fat' fat
fat 5 -- imprime 120

Estamos definindo fat como sendo o resultado de fat' quando passamos fat como parâmetro. Parece mágica, mas em linguagens com avaliação preguiçosa isso vai funcionar. Por quê?

Vamos analisar alguns exemplos. A função fat pode ser desmembrada em

fat = 
  fat' fat = 
      \n -> if n == 0 then 1 else return n * fat (n - 1)

Para n = 0, a função retornará 1 e não se dará ao trabalho de calcular fat(-1).

Vamos agora desmembrar a função duas vezes:

fat = 
  fat' fat = 
      fat' (fat' fat) = if n == 0 then 1 else return n * 
      (if (n - 1) == 0 then 1 ele return (n-1)* fat (n - 2))

Para n = 1, é possível ver que uma avaliação preguiçosa não precisa desmembramentos do que isso.

Ok, conseguimos transformar uma função não recursiva fat' em uma função recursiva. Vamos criar uma função auxiliar para que a função fat' seja passada como parâmetro

aux f = f (aux f)
fat = aux fat'
fat 5 -- imprime 120

A função aux faz o que queremos que o combinador Y faça: recebe uma função não recursiva (por exemplo fat') e retorna uma recursiva (nesse caso fat). Entretanto, aux não é um combinador porque o aux que é chamado recursivamente é uma variável livre.

Vamos apresentar então o combinador Y. Sua definição teórica é dada por

y = \f -> (\x -> f (x x)) (\x -> f (x x))

Ainda não consegui entender essa definição de maneira clara o suficiente para arriscar uma explicação aqui. Minha sugestão é ler [8], onde Mike Vaniel deriva a função acima em Scheme.

De qualquer maneira, se formos implementá-lo em Haskell, teremos um erro de compilação devido a tipo infinito [3]. Para resolver esse problema, [4] apresenta a seguinte solução:

newtype Rec a = In { out :: Rec a -> a }

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

Para evitar problemas com tipo infinito, encapsulamos o segundo termo (\x -> f (x x)) em um novo tipo, o Rec a, através do construtor In. As funções lambda recebem x que é do tipo Rec a e por isso não podemos aplicar x sobre x diretamente. Antes devemos “desencapsular” a função contida nele usando out.

Lembrando, o newtype define uma estrutura semelhante a um tipo de dado algébrico, com a diferença que só se permite um construtor, no caso definido pelo In, e um “getter”, especificado pelo out.

Por exemplo, vamos definir um tipo chamado NovoTipo que encapsula uma função que recebe um tipo genérico e retorna esse mesmo tipo genérico, ou seja, com tipo a -> a.

newtype NovoTipo a = Construtor { getter :: a -> a }

Podemos encapsular uma função que recebe e retorna um inteiro. Por exemplo:

somaUm::Int -> Int
somaUm v = v + 1
let x = Construtor somaUm

Podemos verificar o tipo dessa variável no ghci:

> :type x
x :: NovoTipo Int

O getter extrai a função que foi encapsulada, ou seja, podemos fazer:

> (getter x) 9
10

Outros combinadores

Este site [5] tem uma lista mais extensa de combinadores. Existe um pacote do Haskell chamado data-aviary [6] contendo a implementação de diversos desses combinadores.

Reg Braithwaite discute alguns combinadores na prática usando Ruby no seu blog/projeto homoiconic [7].

Conclusão

Fiquei satisfeito em desviar um pouco da leitura do livro Real World Haskell para aprender mais sobre combinadores. Graças a isso acabei descobrindo coisas interessantes como a origem do nome da empresa do Graham e que algumas funções muito usadas em Haskell são combinadores.

Além disso, embrora o combinador Y não seja tão útil na prática, as ideias por trás dele são muito interessantes (e, na minha opinião, complicadas!).

Referências

[1] Paul Graham – Biografia
[2] How to Mock a Mocking Bird – Smullyman
[3] StackOverflow – Y Combinator in Haskell
[4] [Haskell] How to define Y combinator in Haskell
[5] Combinator Birds
[6] Hackage – The data-aviary package
[7] Github – Homoiconic
[8] Mike’s World-O-Programming – The Y Combinator
[9] Y-Combinator em Javascript

Os comentários estão fechados.

%d bloggers like this: