Derivando o combinador Y

Antes que
eu comece: esteja ciente que eu estou escrevendo este artigo para forçar a mim mesmo a
entender algo através da escrita. Se você tirar algo disso, considere um bônus.
Eu vou derivar o Y() em JavaScript, e darei uma versão em Ruby.

Depois de titubear neste artigo em Raganwald ano passado (um site muito interessante, falando
nisso), eu fiquei inicialmente intrigado e então totalmente frustrado por não
conseguir entender o que o combinador Y era. É de uso prático limitado para
mim, mas me chateia quando meu cérebro não consegue entender algo. Esta é uma
tentativa de aliviar minha frustração. Você pode achar este artigo da Wikipedia e o de Richard Gabriel, The Why of Y (PDF, exemplos em Scheme). Eu juntei tudo isso de outros artigos de
Raganwald e o que achei no Google.

Eu acredito que estamos familiarizados com a ideia de uma função como algo que tem
algum valor de entrada e retorna algum valor de saída.  Digamos, a função para elevar números ao quadrado:

• f(x) = x²

Ou em JavaScript:

var square = function(x) {
  return x * x;
};

Os pontos
fixos são meus valores de entrada para os quais f(x) i são iguais a
x. Portanto, os pontos fixos de f(x) = x² são
0 e 1.

Agora, em matemática e em qualquer linguagem que suporta funções de primeira
classe (isto é, funções que podem ser passadas como dados), temos coisas
chamadas funções de ordem maior. Essas são funções que pegam outra função como
entrada, ou retornam uma função como saída, ou ambos. O ponto fixo ou função de
ordem maior f é outra função p de modo que f(p) = p.
(pode ser mais útil pensar em termos de funções de fato serem executadas). A
afirmação anterior é equivalente à afirmação de que f(p)(x) =
p(x) para todos os valores de x.). Y (o combinador Y) é
uma função especial que retorna os pontos fixos de funções de ordem maior, que
significa:

• f(Y(f))
  = Y(f)

Y é comumente usado para permitir recursões anônimas sem assumir que
suas linguagem de hospedagem o suporta. Digamos que quero uma função que
calcule a fatorial de um número:

var factorial = function(x) {
  return x == 0 ? 1 : x * factorial(x-1);
};

Antes
de irmos além: o JavaScript suporta a recursão anônima. A forma correta da
função acima é:

var factorial = function(x) {
  return x == 0 ? 1 : x * arguments.callee(x-1);
};

arguments.callee dá a todas as funções uma referência interna para elas
mesmas. Este artigo é sobre o que fazer se tal recurso não estiver disponível
em sua linguagem.

Não existe um grande problema com a função acima (aquela sem arguments.callee): ela se apóia no nome que eu dei à função externamente. Se eu
fizer isso:

var bar = factorial;
factorial = "something";
bar(5)  // -> does not work

Minha
função fatorial para de funcionar, porque, dentro dela, o factorial não mais o
que é esperado. Agora, vamos fazer uma função que aja como uma
fábrica para funções fatoriais:

var f = function(q) {
  return function(x) {
    return x == 0 ? 1 : x * q(x-1);
  };
};

Essa
função f irá retornar uma função fatorial. Para fazer a recursão, ela chama uma
função local (definida somente dentro de f, não globalmente), chamada q.
Precisamos passar essa função f para fazer a recursão funcionar corretamente,
mas de que função precisamos? A função q precisa ser uma função fatorial para que a função interna trabalhe apropriadamente, mas estamos de volta onde começamos: não podemos escrever uma função fatorial
segura, porque não podemos usar uma recursão anônima. Mas note o que aconteceu:
se passarmos a função fatorial para f, ela irá retornar a função fatorial. A
função fatorial é assim um ponto fixo de f, e pode ser determinada usando o combinador Y. Então como chegamos lá?

Para começarmos, vamos transformar a função recursiva para factorial ao passá-la
como um parâmetro:

var factorial = function(h, x) {
  return x == 0 ? 1 : x * h(h, x-1);
};

factorial(factorial, 5)  // -> 120

Agora
vamos passar uma função para dizer a factorial como fazer a recursão sem se
referir à nenhuma variável global. Mas essa interface não é realmente
satisfatória – eu quero ser capaz de chamar a functionName(valor). Então vamos
criar uma função que retorna outra função (isso é chamado currying a
nossa função factorial):

var factorial = function(h) {
  return function(x) {
    return x == 0 ? 1 : x * h(h)(x-1);
  };
};

factorial(factorial)(5)  // -> 120

Está
tudo bem agora, mas ainda temos muitas duplicações e sujeira de código, e temos  h(h)(x) na
definição da função em vez de no (x) acima. Portanto, criamos outra
função aninhada que cria uma única referência a h(h):

var factorial = function(h) {
  return function(x) {
    var f = function(q, x) {
      return x == 0 ? 1 : x * q(x-1);
    };
    return f(h(h), x);
  };
};

factorial(factorial)(5)  // -> 120

Isso
está quase parecido com a nossa função f de antes. Nós apenas vamos
“limpar” a função de dentro para completar a transformação:

var factorial = function(h) {
  return function(x) {
    var f = function(q) {
      return function(x) {
        return x == 0 ? 1 : x * q(x-1);
      };
    };
    return f(h(h))(x);
  };
};

factorial(factorial)(5)  // -> 120

Agora
que a função interna f não contém nenhuma referência a variáveis fora
dela, podemos retirá-la, e ela irá funcionar da mesma maneira:

var f = function(q) {
  return function(x) {
    return x == 0 ? 1 : x * q(x-1);
  };
};

var factorial = function(h) {
  return function(x) {
    return f(h(h))(x);
  };
};

factorial(factorial)(5)  // -> 120

Agora
temos nossa f original da qual queremos o ponto fixo. O ponto fixo é a função
fatorial dada pela factorial (factorial), para que possamos escrever nossa função
Y() para retorná-la:

var Y = function(f) {
  var g = function(h) {
    return function(x) {
      return f(h(h))(x);
    };
  };
  return g(g);
};

Isso
é mais comumente escrito como:

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

Y()
agora irá retornar o ponto fixo de qualquer função de ordem maior, que é
exatamente o que queríamos:

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

E mais – a recursão anônima com nenhuma dependência ou variáveis globais
ou suporte da linguagem hospedeira. Se você quiser fazer isso em Ruby, (não
estou certo se isso tem um análogo para arguments.callee), que se parece com
isto:

def y(&f)
  lambda { |g| g[g] } [
    lambda do |h|
      lambda { |*args| f[h[h]][*args] }
    end
  ]
end

factorial = y do |recurse|
  lambda do |x|
    x.zero? ? 1 : x * recurse[x-1]
  end
end

O que é frustrante sobre Y é que, uma vez que você o derivou, é
totalmente impossível dizer o que ele faz somente ao olhar para ele. Se você
chegou até aqui, parabéns.

?

Texto original disponível em http://blog.jcoglan.com/2008/01/10/deriving-the-y-combinator/