Entendendo, Finalmente, o Combinador Y - Uma Abordagem de uma Perspectiva Amigável a Programadores
Table of Contents
Este post é destinado a estudantes de Computação que estudaram cálculo lambda mas nunca entenderam o Combinador Y, o mais conhecido combinmador de ponto fixo. O cálculo lambda não tem recursão embutida, mas usando combinadores de ponto fixo podemos produzir facilmente funções recursivas, tornando o cálculo lambda capaz de descrever todas as funções computáveis (e outras palavras, equivalente a uma Máquina de Turing universal). Eis nosso amigo Y:
\[ Y = \lambda f \cdot (\lambda x \cdot f (x x)) (\lambda x \cdot f (x x)) \]
Com isso, você pode escrever uma função não-recursiva de uma função, aplicar Y a ela, e obter a funcionalidade recursiva funcionalmente, mesmo que o cálculo lambda não forneça funções recursivas. Não é difícil entender o que isso faz, mas o mistério para mim era sempre como isso funciona.
Em minha experiência, a principal barreira para entender o combinador era lidar com diversas coisas nao-familiares ao mesmo tempo, cada uma delas deixando uma parte diferente do meu cérebro desconfortável: a semântica do cálculo lambda, a sintaxe do cálculo lambda e o problema em mãos.
Então, para focarmos no problema em mãos, vamos dar um jeito no restante.
Semântica do cálculo lambda: cálculo lambda não-tipado resume-se (grosso modo) a uma linguagem bem simples com evaluação preguiçosa. Tudo o que temos são funções, mas mediante encodações espertas podemos representar números e booleanos com cadeias belamente projetadas de funções. Para simplificar as coisas, então, vamos apenas assumir que já temos números, aritmética e if/then/else. A seguir, vamos nos livrar da evaluação preguiçosa e trocá-la pela evaluação antecipada, que é o que costumamos usar em linguagens de programação imperativas típicas. Para fazer isso, vamos usar uma variante do Y, que é chamada de Z:
\[ Z = \lambda f \cdot (\lambda x \cdot f (\lambda y \cdot x x y)) (\lambda x \cdot f (\lambda y \cdot x x y)) \]
Sim, este é um pouco maior (adicionamos as partes com y), mas vai por mim, é mais fácil de entender, e uma vez que tenha entendido, é só uma questão de re-invoicar a evaluação preguiçosa daquelas classes de programação funcional e aplicar a mesma lógica a Y.
A seguir, a sintaxe: o cálculo lambda é feito de termos, abstrações e aplicações, o que no jargão de linguagens de programação são meramente variáveis, declarações de função e chamadas de função. Portanto, podemos simplesmente reescrevê-lo usando alguma notação familiar e livrando-nos das estranhas sintaxe e regras de precedência por ora. Eu nem mesmo vou usar uma linguagem funcional: vamos usar uma forma restrita de Lua, usando apenas características fornecidas pelo cálculo lambda a fim de tornar a sintaxe mais clara
Z = function(f) return (function(x) return f(function (y) return (x(x))(y) end) end)(function(x) return f(function (y) return (x(x))(y) end) end) end
Ok, Ok, isso não está muito legível. Mas já vamos chegar lá. Assumindo que você esteja confortável com funções como valores de primeira classe que podem ser retornados e passados como argumentos, a coisa mais estranha aqui é que no primeiro retorno temos uma função sendo declarada e chamada "em linha", recebendo como parâmetro outra função idêntica a si mesma. Vamos deixar esse fluxo mais claro usando variáveis locais, mas estritamente como "alias". Em outras palavras, isto vai executar sem nenhuma diferença, então não vamos usar nenhuma característica extra que não seja parte do cálculo lambda - note que o nosso uso de variáveis locais aqui será equivalente a uma substituição de macros:
Z = function(f) local f1 = function(x) return f(function (y) return (x(x))(y) end) end local f2 = function(x) return f(function (y) return (x(x))(y) end) end return f1(f2) end
Ok, então esta é a função que queremos entender. Ela ainda não faz sentido, mas podemos ver que Z chama uma função (f1) passando para ela uma função idêntica (f2). Estas funções idênticas retornam o resultado de invocar f (a coisa que queremos tornar recursiva), mas dando como seu argumento outra função que usa algo que chama a si mesmo (x(x)). Um cheiro forte de auto-referência nisso tudo - não é de se espantar, dado que sabemos que a chave para a recursão está aí em algum lugar. Mas vamos parar de brincar de engenharia reversa. Vamos construí-la em vez disso.
Primeiro, vamos relembrar de para que esta função serve, O que queremos ter é funções recursivas, como esta que calcula fatoriais:
fact = function(n) if n == 0 then return 1 else return n * fact(n-1) end end
Mas não dá para ter isso em cálculo lambda. Na realidade, tudo isso está certo,
exceto pela chamada recursiva a fact(). Nós não temos recursão ainda.
O melhor que podemos fazer é escrever uma função que faz um passo da recursão e deixa o próximo passo para ser feito por outrem. Como isso:
stepper = function(next_step, n) if n == 0 then return 1 else return n * next_step(n-1) end end
Porém, eu disse que deveríamos usar apenas características fornecidas pelo cálculo lambda, o que significa que não temos múltiplos argumentos. Felizmente, usando curry, podemos obter o equivalente a múltiplos argumentos. Este é um aspecto do cálculo lambda que eu não vou esconder na sintaxe Lua porque será útil para nosso entendimento. Precisamos fazer um stepper como esse:
stepper = function(next_step) return function(n) if n == 0 then return 1 else return n * next_step(n-1) end end end
A diferença é que agora, em vez de fazer stepper(some_next_step,5) teremos que
fazer stepper(some_next_step)(5).
O que esta construção stepper deixa claro é que agora temos uma "fábrica" de
funções que retorna nossa função-futuramente-recursiva, exceto que ela só
executa um passo e usa outra função que sabe como executar o próximo passo. Você
pode pensar que stepper(next_step) na realidade retorna um "passo", que então é
executado chamando-o com o parâmetro (5).
Mas precisamos de uma função para executar o próximo passo para passar para o
stepper. Como obtê-la? Chamamos a fábrica para obter o próximo passo. Sim, como
stepper(stepper).
De fato, note que se executarmos
stepper(stepper(stepper(stepper(stepper(stepper())))))(5), obteremos o
resultado equivalente a fact(5). (Você pode experimentar no interpretador
Lua!)
É claro, nós não queremos escrever isso dessa forma. O plano, portanto, é obter uma função que combine todas essas chamadas. Está na hora do combinador:
combinator = function(stepper) -- ? end
Esta função deve retornar algo para substituir todos estes steppers aninhados, então queremos que ela retorne uma função que aceita nosso argumento de entrada:
combinator = function(stepper) return function(arg) -- ? end end
E ela precisa executar stepper() no argumento, claro, daí ela computa nossa
função desejada. Mas o que passaremos como próximo passo?
combinator = function(stepper) return function(arg) return stepper( --[[ ? ]] )(arg) end end
Bem, se o que queremos produzir é stepper(stepper(stepper(stepper(... então
talvez o que precisamos é passar stepper() novamente?
combinator = function(stepper) return function(arg) return stepper(stepper)(arg) -- no! end end
Isto está errado porque só vai executar stepper duas vezes (e, claro, nós
sabemos que o combinador não tem essa aparência). Pense na execução de
stepper(stepper). Se passarmos 5 como argumento, obteremos
stepper(stepper)(5). Isso terá 5 como n e stepper como argumento para
next_step. Eventualmente isto invocará next_step(n-1), isto é,
stepper(4). Mas stepper espera uma função como argumento, e não um
número. De fato, se executarmos isto no interpretador Lua, obteremos um erro de
tipo. (Em cálculo lambda não-tipado, não temos uma noção de "erro de tipo", é
claro; o que obtemos é apenas uma expressão lambda que não nos faz sentido algum.)
Precisamos dar ao stepper uma função, então parece que vamos ter que fazer
uma.
combinator = function(stepper) local some_function = function() -- ? end return function(arg) return stepper(some_function)(arg) end end
(Mais uma vez, estou usando uma variável local aqui estritamente como "substituição de macro", apenas a fim de tornar as coisas mais legíveis.)
Para determinar o que colocar em some_function, vamos pensar em para o que ela
seria útil. Ela será passada para stepper, e portanto usada como o
next_step. Isto significa que ela precisa tomar o argumento numérico então?
combinator = function(stepper) local some_function = function(arg) -- ? end return function(arg) return stepper(some_function)(arg) end end
Se estamos recebendo um parâmetro, é justo assumir que teremos que fazer algo
com ele. O que queremos fazer com nossos argumentos de entrada é executar passos
neles, então vamos obter um passo com stepper e fazer isso.
combinator = function(stepper) local some_function = function(arg) return stepper( --[[ ? ]] )(arg) end return function(arg) return stepper(some_function)(arg) end end
Oh-oh, voltamos ao problema do que passar para stepper! Isto significa que
estamos presos num loop? Bem, note que se simplesmente mantivermos fazendo o
mesmo, acabaremos obtendo o equivalente a stepper(stepper(stepper(...))):
combinator = function(stepper) local and_yet_another_step = -- ... !!! local yet_another_step = function(arg) return stepper(and_yet_another_step)(arg) end local another_step = function(arg) return stepper(yet_another_step)(arg) end return function(arg) return stepper(another_step)(arg) end end
Mas não, isto não quer dizer que estamos presos num loop. Quer dizer que estamos chegando perto.
O que estamos deixando passar é que quando consideramos o que passar para o
primeiro stepper, nós simplesmente dizemos que tinha que ser uma função
recebendo um argumento numérico. Mas o que queremos é uma função que retorne o
resultado da computação de stepper, mas também produza a função para o passo
seguinte! O que queremos é outra função no estilo fábrica como quando
transformamos fact em stepper. Em vez de descer um passo, vamos fazer uma
função fábrica que gera outra função que desce um passo. Enquanto estamos nisso,
e este é o ponto chave, removeremos dela a responsabilidade de calcular como
descender para o nível seguinte. Vamos fazer isso assim como quando nos livramos
da recursão - simplesmente assuma que você tem o que precisa como parâmetro:
combinator = function(stepper) local make_step = function(next_step) return function(arg) return stepper(next_step)(arg) end end return function(arg) return stepper(make_step)(arg) end end
Com uma função como make_step, podemos produzir quantos step s quanto
quisermos. Se você tem um traquejo matemático, deve estar pensando agora em
indução; sim, nós construímos uma forma de resolver um passo de nosso problema
assumindo que temos a solução para o seguinte. Este é o espírito.
Então, já chegamos? Isso funciona?
Ainda não. Lembra quando tentamos fazer stepper(stepper)? Isso não funcionou
porque stepper não quer uma fábrica como argumento. Ele quer um passo real
(lembre que em nosso exemplo ela o usará para obter o fatorial de n-1). Em
outras palavras, não queremos passar para ele uma fábrica como
make_step. Queremos que make_step nos faça um passo. Então vamos chamá-lo!
combinator = function(stepper) local make_step = function(next_step) return function(arg) return stepper(next_step)(arg) end end return function(arg) return stepper(make_step( --[[ ? ]] ))(arg) end end
Ok, vamos chamá-la, mas o que entregamos a ela? Vamos olhar para o que o
argumento de make_step costumava ser usado.
Espere um segundo, ele é usado para fazer um passo também! Então vamos simplesmente passar … ele mesmo?
combinator = function(stepper) local make_step = function(next_step) return function(arg) return stepper(next_step(next_step))(arg) end end return function(arg) return stepper(make_step(make_step))(arg) end end
Sim, nós passamos ele mesmo para ele mesmo. E fazemos o mesmo com next_step
também, dado que estamos fazendo exatamente a mesma coisa. Veja, aqui está onde
tudo se ajunta: para ter recursão, precisamos de auto-referência; e em cálculo
lambda, enquanto um termo lambda não pode referenciar a si mesmo em uma
abstração (definição de função), nós temos que um termo lambda, quando atrelado
a uma variável, pode ser aplicado a si mesmo. A função acima é de verdade um
combinador de ponto fixo.
Você pode achar estranho que make_step passa a si mesmo como um parâmetro,
então chama a si mesmo passando a si mesmo como parâmetro… seria esse um loop
infinito? Não necessariamente, porque no meio de casa passo, não executamos
stepper(next_step(next_step)) de cara, imediatamente. Ele vem "embalado"
dentro de um function(arg) ... end. (estes são os lambdas extras que o
combinador Z tem em comparação ao combinador Y.)
Falando disso, este código é o mesmo que a transformação Lua direta do combinador Z que apresentei acima? Vamos recapitular:
Z = function(f) return (function(x) return f(function (y) return (x(x))(y) end) end)(function(x) return f(function (y) return (x(x))(y) end) end) end
Não parece muito, né? Mas vamos dar uma olhada mais de perto em nosso
combinador. Acontece que neste retorno final, em vez de construir esta função
passo explicitamente, podemos simplesmente chamar make_step e obter os mesmos
resultados:
combinator = function(stepper) local make_step = function(next_step) return function(arg) return stepper(next_step(next_step))(arg) end end return make_step(make_step) end
(Em jargão de compiladores, é como se a primeira iteração já tivesse sido desenrolada antes.)
Lembra quando dissemos que as variáveis locais eram meras substituições de
macro? Se expandirmos as duas instâncias de make_step, obtemos isso:
combinator = function(stepper) return (function(next_step) return function(arg) return stepper(next_step(next_step))(arg) end end)(function(next_step) return function(arg) return stepper(next_step(next_step))(arg) end end) end
Agora, a única diferença é que stepper está sendo chamada de dentro de
function(arg) ... end, enquanto na outra está sendo chamada de fora. O
funcionamento é o mesmo, porque o propósito de function(arg) ... end é
"conter" a expansão dos argumentos entre cada chamada de stepper. Precisamos
disso porque Lua não tem evaluação preguiçosa. Para que nossa função se
assemelhe a Z, fazemos isto:
combinator = function(stepper) return (function(next_step) return stepper(function(arg) return (next_step(next_step))(arg) end) end)(function(next_step) return stepper(function(arg) return (next_step(next_step))(arg) end) end) end
Aqui estamos! A mesma exata função, só com nomes de variáveis diferentes.
Finalmente, para testá-la:
local factorial_step = function(f) return function (n) if n == 0 then return 1 else return n * f(n - 1) end end end local factorial = combinator(factorial_step) print(factorial(5))
Aqui obtemos 120, mesmo assim nenhuma função no nosso código chamou a si mesma.
Como podemos ver, não existe nada de mágico sobre o combinador Y: ele produz recursão usando a única forma de auto-referência fornecida pelo cálculo lambda, que é a auto-aplicação de variáveis. Para iniciar o loop, dado que não há forma de atrelar a abstração mais externa (função) a um termo (variável) para que possamos aplicá-la (chamar) a si mesma, ela é simplesmente escrita duas vezes.
Eu tentei explicar isso o mais claro que pude (dadas as suposições que assumi acerca de conhecimento anterior sobre linguagens de programação e cálculo lambda básico). Este foi de fato o fluxo que eu segui quando entendi o combinador. Ele segue claramente uma mentalidade de "programador", o que pode não ser melhor método para todos, mas espero que seja útil para outros como foi útil para mim.
1 META
| Título | Understanding, at last, the Y Combinator - a programmer-friendly perspective |
| Autor | hishamhm |
| Link | https://hisham.hm/2011/04/04/understanding-at-last-the-y-combinator-a-programmer-friendly-perspective/ |
| Arquivo | http://archive.is/rTf0Z |
Created: 2018-12-16 dom 20:13
Nenhum comentário:
Postar um comentário