bkim::Blog

Como eu entendi o Y-combinator

O Y-combinator, ou combinador Y, ou combinador de ponto fixo, é dessas coisas místicas na teoria da computação, como a mônada e continuations, que parecem exigir meditação e um estado elevado de consciência para serem compreendidas e apreciadas. Eu não posso dizer que compreendi inteiramente, mas ao menos aprendi como derivar seguindo alguns passos simples que quero compartilhar.

Esse combinador 1 tem um lugar especial nos corações dos cientistas de computação por permitir construir funções recursivas a partir de funções anônimas. Uma função recursiva é definida em termos de si mesma, logo precisa ter um nome para poder se invocar, como a famosa soma de Fibonacci:

function fibo(x) {
  if (x < 2) {
    return 1;
  }
  // fibo precisa já estar definida neste ponto.
  return fibo(x-2) + fibo(x-1);
}

O combinador Y é uma função que nos permite escrever essa mesma função sem precisar que a linguagem (como Javascript) tenha um suporte especial para recursão, bastando apenas suportar funções anônimas. Mais que isso, o combinador é universal; não precisamos, teoricamente, escrever um combinador diferente para cada nova função que desejamos tornar recursiva. No exemplo abaixo, o combinador é chamado fix; note que ele pode ser utilizado para escrever tanto uma implementação de Fibonacci fibo quanto uma função pre_walk que percorre uma árvore em pré-ordem:

let fibo = fix(function (f) {
  return function (x) {
    if (x < 2) {
      return 1;
    }
    return f(x-2) + f(x-1);
  };
});

let pre_walk = fix(function (f) {
  return function (node) {
    if (node.left != null) {
      f(node.left);
    }
    console.log(node.value);
    if (node.right != null) {
      f(node.right);
    }
  }
});

Reinventando a roda

Sem usar a Wikipédia, como fazer para escrever uma função recursiva a partir de funções anônimas? Uma primeira solução seria simplesmente declarar uma variável que irá conter a função uma vez que esteja definida.

let fibo;
fibo = function(x) {
  if (x < 2) {
    return 1;
  }
  return fibo(x-2) + fibo(x-1);
};

Mas variáveis globais não parecem uma solução muito pura 2… Se passarmos uma referência à própria função como parâmetro, podemos evitar a declaração, embora agora as chamadas internas fiquem mais feias. Vamos chamar essa referência de self.

let fibo_ = function(self, x) {
  if (x < 2) {
    return 1;
  }
  return self(self, x-2) + self(self, x-1);
};

let fibo = function(x) {
  return fibo_(fibo_, x);
};

Essa estratégia chama-se lambda lifting, onde a dependência a uma variável global é substituída por um parâmetro. Note como fica a função pre_walk ao realizarmos o mesmo procedimento:

let pre_walk_ = function(self, node) {
  if (node.left != null) {
    self(self, node.left);
  }
  console.log(node.value);
  if (node.right != null) {
    self(self, node.right);
  }
};

let pre_walk = function(node) {
  return pre_walk_(pre_walk_, node);
};

É da abstração desse procedimento que obteremos o combinador Y! Para isso vamos usar mais duas transformações úteis:

  1. Currying
  2. Conversão de let em lambda

Currying

// Função de muitos argumentos...
let f = function(a, b, c) {
  return a+b+c;
};
f(1, 2, 3); // 6

// ...após o currying.
let f = function(a) {
  return function(b) {
    return function(c) {
      return a+b+c;
    };
  };
};
f(1)(2)(3); // 6

Conversão de let

// Função com variável local...
let inc = function(x) {
  let a = 1;
  return x + a;
};

// ...substituída por invocação...
let inc = function(x) {
  let adder = function(a) {
    return x + a;
  };
  return adder(1);
};

// ...ou inline.
let inc = function(x) {
  return (function(a) {
    return x + a;
  })(1);
};

Derivando a roda

// Função recursiva para calcular as
// potências de 2.
let pow2;
pow2 = function(x) {
  return x == 0
      ? 1
      : 2 * pow2(x-1);
};

// Lambda-lifting
let pow2_ = function(self, x) {
  return x == 0
      ? 1
      : 2 * self(self, x-1);
};
let pow2 = function(x0) {
  return pow2_(pow2_, x0);
};

// Currying
let pow2_ = function(self) {
  return function(x) {
    return x == 0
        ? 1
        : 2 * self(self)(x-1);
  };
};
let pow2 = function(x0) {
  return pow2_(pow2_)(x0);
};

// Declarando pow2_ dentro de pow
let pow2 = function(x0) {
  let pow2_ = function(self) {
    return function (x) {
      return x == 0
          ? 1
          : 2 * self(self)(x-1);
    };
  };
  return pow2_(pow2_)(x0);
};

// Declarando uma função auxiliar f
let pow2 = function(x0) {
  let pow2_ = function(self) {
    let f = function(x) {
      return self(self)(x);
    };
    return function (x) {
      return x == 0
          ? 1
          : 2 * f(x-1);
    };
  };
  return pow2_(pow2_)(x0);
};

// Conversão de let inline (de f)
let pow2 = function(x0) {
  let pow2_ = function(self) {
    return (function (f) {
      return function (x) {
        return x == 0
            ? 1
            : 2 * f(x-1);
      };
    })(function(x) {
      return self(self)(x);
    });
  };
  return pow2_(pow2_)(x0);
};

// Extração da parte específica.
let pow2 = function(x0) {
  let gen_pow2 = function (f) {
    return function (x) {
      return x == 0
          ? 1
          : 2 * f(x-1);
    };
  };
  let pow2_ = function(self) {
    return gen_pow2(function(x) {
      return self(self)(x);
    });
  };
  return pow2_(pow2_)(x0);
};

// Lambda ...un-lifting
let gen_pow2 = function (f) {
  return function (x) {
    return x == 0
        ? 1
        : 2 * f(x-1);
  };
};
let pow2 = (function(gen) {
  return function(x0) {
    let func_ = function(self) {
      return gen(function(x) {
        return self(self)(x);
      });
    };
    return func_(func_)(x0);
  };
})(gen_pow2);

E então chegamos à expressão gloriosa e confusa do fix!

let fix = function (gen) {
  return function (x) {
    let foo = function (self) {
      return gen(function (x) {
        return self(self)(x);
      });
    };
    return foo(foo)(x);
  };
};
let gen_pow2 = function (f) {
  return function (x) {
    return x == 0
        ? 1
        ? 2 * f(x-1);
  };
};
let pow2 = fix(gen_pow2);

E porque chamar assim, o que é o “ponto fixo”? Isso eu completo em breve…


  1. Eu não sei exatamente o que é “combinador”, mas na minha intuição é a de uma função $g(f)$ que recebe apenas uma função $f$ e que retorna uma função, não exatamente com a mesma assinatura de $f$.

  2. Nesse caso, literalmente: esta solução depende de poder mudar o valor de uma variável, o que vai contra a ideia de uma função pura, onde sua saída depende inteiramente dos seus parâmetros.

Published in .