Combinators by Paulo Torrens.md

Texto retirado do comentário do Paulo Torrens em uma publicação na APDA.

Combinadores são "funções de alta ordem fechadas". E imagino que por enquanto isso não ajudou muito. Mas é assim:

O cálculo lambda, que ele tá brincando com JavaScript, é algo muito simples, você só pode criar funções com um só argumento, e aplicar elas a outras funções. Por exemplo, o valor TRUE:

var TRUE = function(x) {
  return function(y) {
    return x;
  };
};

E o valor FALSE:

var FALSE = function(x) {
  return function(y) {
    return y;
  };
};

No cálculo lambda, todas as funções são funções de alta ordem (quer dizer, funções que recebem outras funções como argumentos). Na real, tudo que você manipula são funções, não existe mais nada, mas isso é o suficiente pra calcular qualquer coisa, fazer números, vetores, etc.

A lógica combinatória é meio que um subconjunto do cálculo lambda, mas que é igualmente poderoso. Por exemplo, o cálculo SKI define três combinadores apenas, S, K e I. Um combinador é uma função, mas a gente não dá nome pras variáveis (essa é a ideia de combinadores: não precisar nomear variáveis, como "x" e "y" que eu usei ali em cima). Então, no cálculo SKI, tu pode fazer tudo que tu pode no cálculo lambda, mas sem precisar dar nomes pra variáveis, só usando combinadores. A gente pode representar os combinadores em cálculo lambda, pra visualizar o que eles fazem:

S x y z = x z (y z)

Ou, em JavaScript:

var S = function(x) {
  return function(y) {
    return function(z) {
      return x(z)(y(z));
    };
  };
};

Da mesma forma:

K x y = x

Ou, em JavaScript:

var K = function(x) {
  return function(y) {
    return x;
  };
};

E, finalmente:

I x = x

Ou, em JavaScript:

var I = function(x) {
  return x;
};

Vale notar que I não é necessário, porque tu pode definir I usando apenas S e K:

var I = S(K)(K);

O que isso significa: usando apenas as funções S e K acima, aplicadas uma sobre a outra, você pode teoricamente calcular qualquer coisa que qualquer linguagem de programação pode. A gente nota que o I foi definido apenas com combinadores, não precisamos mais criar funções (nem nomear variáveis) pra abstrair.

No caso, a gente pode reescrever TRUE e FALSE:

var TRUE = K;
var FALSE = S(K);

Outro combinador bastante útil é o famoso Y combinator. Ele funciona da seguinte forma:

Y f = f (Y f)

Reparem que ele se aplica a si mesmo. O que isso significa: você cria uma função recursiva baseada numa função que não era recursiva! Ou seja: você pode criar funções recursivas sem nunca dar nomes pra funções/variáveis também.

Você pode definir Y em termos de S e K, mas não vou perder tempo mostrando isso. Você pode fazer de forma ingênua em JavaScript direto:

var Y = function(f) {
  return f(Y(f));
};

Claro que isso ia criar um loop infinito e não iria funcionar... e, além disso, gostaríamos de não precisar de recursão explícita (não queremos usar o Y dentro do Y, afinal, queremos um combinador, que não deve nomear variáveis, certo?), então podemos brincar um pouco com a definição:

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

Eu não vou explicar como derivar pra chegar nesse resultado, mas esse é o combinador Y, sem precisar usar Y de novo ali dentro!

Finalmente... com o Y que defini acima, mais o código do Lucas que ele postou, após corrigir a função add dele que tem um leve erro, podemos escrever a função fibonacci com Church encoding:

const fib = rec => n => If(lessEq(n)(one))(one)(
  x => add(
    rec(sub(n)(one))
  )(
    rec(sub(n)(two))
  )(x)
)

E podemos verificar que, apenas usando função em cima de função, podemos sim fazer cálculos:

console.log(decodeNumber(Y(fib)(eight)));

Agora com licença que eu vou desmaiar.