O que é um combinador em Y? [fechadas]

Um combinador Y é um conceito de ciência da computação do lado "funcional" das coisas. A maioria dos programadores não sabe muito sobre combinadores, mesmo que tenha ouvido falar deles.

• O que é um combinador em Y?
• Como os combinadores funcionam?
• Para que servem?
• Eles são úteis em linguagens processuais?

Se você estiver pronto para uma longa leitura, Mike Vanier tem uma ótima explicação . Para encurtar a história, permite implementar a recursão em um idioma que não necessariamente o suporta nativamente.

Um combinador Y é um "funcional" (uma função que opera em outras funções) que permite a recursão, quando você não pode se referir à função por dentro. Na teoria da ciência da computação, ela generaliza a recursão , abstraindo sua implementação e, assim, separando-a do trabalho real da função em questão. O benefício de não precisar de um nome em tempo de compilação para a função recursiva é uma espécie de bônus. =)

Isso é aplicável em idiomas que suportam funções lambda . A natureza baseada na expressão das lambdas geralmente significa que elas não podem se referir a si mesmas pelo nome. E contornar isso por meio da declaração da variável, fazendo referência a ela e atribuindo o lambda a ela, para completar o loop de auto-referência, é frágil. A variável lambda pode ser copiada e a variável original reatribuída, o que interrompe a auto-referência.

Os combinadores Y são complicados de implementar, e costumam usar, em linguagens de tipo estático (que costumam ser linguagens procedurais ), porque geralmente as restrições de digitação exigem que o número de argumentos para a função em questão seja conhecido em tempo de compilação. Isso significa que um combinador y deve ser escrito para qualquer contagem de argumentos que você precise usar.

Abaixo está um exemplo de como o uso e o funcionamento de um Y-Combinator, em C #.

O uso de um combinador Y envolve uma maneira "incomum" de construir uma função recursiva. Primeiro, você deve escrever sua função como um pedaço de código que chama uma função preexistente, e não ela mesma:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

Em seguida, você transforma isso em uma função que recebe uma função para chamar e retorna uma função que faz isso. Isso é chamado de funcional porque leva uma função e executa uma operação que resulta em outra função.

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

Agora você tem uma função que assume uma função e retorna outra função que parece um fatorial, mas, em vez de se chamar, chama o argumento passado para a função externa. Como você faz disso o fatorial? Passe a função interna para si mesma. O Y-Combinator faz isso, sendo uma função com um nome permanente, que pode introduzir a recursão.

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

Em vez da chamada fatorial em si, o que acontece é que o fatorial chama o gerador fatorial (retornado pela chamada recursiva ao Y-Combinator). E, dependendo do valor atual de t, a função retornada pelo gerador chamará o gerador novamente, com t - 1, ou apenas retornará 1, encerrando a recursão.

É complicado e enigmático, mas tudo acontece em tempo de execução, e a chave para o seu trabalho é a "execução adiada" e o rompimento da recursão para abranger duas funções. O F interno é passado como argumento , a ser chamado na próxima iteração, apenas se necessário .

Eu tirei isso de http://www.mail-archive.com/[email protected]/msg02716.html, que é uma explicação que escrevi há vários anos.

Vou usar JavaScript neste exemplo, mas muitos outros idiomas também funcionarão.

Nosso objetivo é ser capaz de escrever uma função recursiva de 1 variável usando apenas funções de 1 variável e sem atribuições, definindo as coisas pelo nome etc. é dado.) Parece impossível, não é? Como exemplo, vamos implementar fatorial.

Bem, o primeiro passo é dizer que poderíamos fazer isso facilmente se trapacearmos um pouco. Usando funções de 2 variáveis ​​e atribuição, podemos pelo menos evitar o uso de atribuição para configurar a recursão.

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

Agora vamos ver se podemos trapacear menos. Bem, primeiro estamos usando a atribuição, mas não precisamos. Podemos apenas escrever X e Y em linha.

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

Mas estamos usando funções de 2 variáveis ​​para obter uma função de 1 variável. Podemos consertar isso? Bem, um cara esperto chamado Haskell Curry tem um truque legal, se você tiver boas funções de ordem superior, precisará apenas de uma variável. A prova é que você pode obter das funções de 2 (ou mais no caso geral) variáveis ​​para 1 variável com uma transformação de texto puramente mecânica como esta:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

onde ... permanece exatamente o mesmo. (Esse truque é chamado de "currying" em homenagem ao seu inventor. A linguagem Haskell também é nomeada para Haskell Curry. Arquivo que é feito sob trivialidades inúteis.) Agora basta aplicar essa transformação em todos os lugares e obteremos a versão final.

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

Sinta-se livre para experimentar. alert () que retornar, amarre-o a um botão, o que for. Esse código calcula fatoriais, recursivamente, sem usar atribuições, declarações ou funções de 2 variáveis. (Mas tentar rastrear como ele funciona provavelmente fará sua cabeça girar. E entregá-la, sem a derivação, apenas um pouco reformatada resultará em um código que certamente irá confundir e confundir.)

Você pode substituir as 4 linhas que definem recursivamente o fatorial por qualquer outra função recursiva desejada.

Gostaria de saber se há alguma utilidade em tentar construir isso a partir do zero. Vamos ver. Aqui está uma função fatorial básica e recursiva:

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

Vamos refatorar e criar uma nova função chamada factque retorna uma função de computação fatorial anônima em vez de executar o próprio cálculo:

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

Isso é um pouco estranho, mas não há nada de errado nisso. Estamos apenas gerando uma nova função fatorial a cada etapa.

A recursão nesse estágio ainda é bastante explícita. A factfunção precisa estar ciente de seu próprio nome. Vamos parametrizar a chamada recursiva:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

Isso é ótimo, mas recurserainda precisa saber o próprio nome. Vamos parametrizar isso também:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

Agora, em vez de chamar recurser(recurser)diretamente, vamos criar uma função wrapper que retorne seu resultado:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

Agora podemos nos livrar recursercompletamente do nome; é apenas um argumento para a função interna de Y, que pode ser substituída pela própria função:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

O único nome externo ainda referenciado é fact, mas agora deve ficar claro que também é facilmente parametrizado, criando a solução completa e genérica:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

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

A maioria das respostas acima descrever o que o Y-Combinator é , mas não o que é para .

Os combinadores de ponto fixo são usados ​​para mostrar que o cálculo lambda está completo . Este é um resultado muito importante na teoria da computação e fornece uma base teórica para a programação funcional .

Estudar combinadores de ponto fixo também me ajudou a entender realmente a programação funcional. Eu nunca encontrei nenhum uso para eles na programação real.

combinador y em JavaScript :

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

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

factorial(5)  // -> 120

Edit : Eu aprendo muito olhando o código, mas este é um pouco difícil de engolir sem algum histórico - desculpe por isso. Com algum conhecimento geral apresentado por outras respostas, você pode começar a separar o que está acontecendo.

A função Y é o "combinador y". Agora dê uma olhada na var factoriallinha onde Y é usado. Observe que você passa uma função para ela que possui um parâmetro (neste exemplo recurse) que também é usado posteriormente na função interna. O nome do parâmetro basicamente se torna o nome da função interna, permitindo que ele execute uma chamada recursiva (uma vez que utiliza recurse()em sua definição.) O combinador y executa a mágica de associar a função interna anônima ao nome do parâmetro da função transmitida para Y.

Para obter uma explicação completa de como Y faz a mágica, confira o artigo vinculado (não por mim).

Para programadores que não encontraram a programação funcional em profundidade e não querem começar agora, mas são levemente curiosos:

O combinador Y é uma fórmula que permite implementar a recursão em uma situação em que as funções não podem ter nomes, mas podem ser passadas como argumentos, usadas como valores de retorno e definidas em outras funções.

Funciona passando a função para si mesma como argumento, para que possa se chamar.

Faz parte do cálculo lambda, que é realmente matemática, mas é efetivamente uma linguagem de programação e é bastante fundamental para a ciência da computação e especialmente para a programação funcional.

O valor prático diário do combinador Y é limitado, pois as linguagens de programação tendem a permitir que você nomeie funções.

Caso você precise identificá-lo em uma fila da polícia, fica assim:

Y = λf. (Λx.f (xx)) (λx.f (xx))

Geralmente, você pode identificá-lo por causa dos repetidos (λx.f (x x)).

Os λsímbolos são a letra grega lambda, que dá nome ao cálculo lambda, e há muitos (λx.t)termos de estilo porque é assim que o cálculo lambda se parece.

Recursão anônima

Um combinador de ponto fixo é uma função de ordem superior fixque, por definição, satisfaz a equivalência

forall f.  fix f  =  f (fix f)

fix frepresenta uma solução xpara a equação de ponto fixo

               x  =  f x

O fatorial de um número natural pode ser comprovado por

fact 0 = 1
fact n = n * fact (n - 1)

Usando fix, provas construtivas arbitrárias sobre funções gerais / μ-recursivas podem ser derivadas sem auto-referencialidade anônima.

fact n = (fix fact') n

Onde

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

de tal modo que

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

Esta prova formal de que

fact 3  =  6

usa metodicamente a equivalência do combinador de ponto fixo para regravações

fix fact'  ->  fact' (fix fact')

Cálculo lambda

O formalismo do cálculo lambda não tipado consiste em uma gramática livre de contexto

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

onde vvaria sobre variáveis, junto com as regras de redução beta e eta

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

A redução beta substitui todas as ocorrências livres da variável xno corpo de abstração ("função") Bpela expressão ("argumento") E. A redução de Eta elimina a abstração redundante. Às vezes é omitido do formalismo. Uma expressão irredutível , à qual não se aplica regra de redução, está na forma normal ou canônica .

λ x y. E

é uma abreviação de

λ x. λ y. E

(multiariedade de abstração),

E F G

é uma abreviação de

(E F) G

(associatividade à esquerda do aplicativo),

λ x. x

e

λ y. y

são equivalentes a alfa .

Abstração e aplicação são as duas únicas "primitivas de linguagem" do cálculo lambda, mas permitem a codificação de dados e operações arbitrariamente complexos.

Os numerais da Igreja são uma codificação dos números naturais semelhantes aos naturais Peano-axiomáticos.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

Uma prova formal de que

1 + 2  =  3

usando a regra de reescrita da redução beta:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

Combinadores

No cálculo lambda, combinadores são abstrações que não contêm variáveis ​​livres. Mais simplesmente I:, o combinador de identidades

λ x. x

isomórfico para a função de identidade

id x = x

Tais combinadores são os operadores primitivos dos cálculos combinadores, como o sistema SKI.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

A redução beta não está fortemente normalizando ; nem todas as expressões redutíveis, "redexes", convergem para a forma normal sob redução beta. Um exemplo simples é a aplicação divergente do ωcombinador ômega

λ x. x x

para si mesmo:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

A redução das subexpressões mais à esquerda (“cabeças”) é priorizada. A ordem aplicativa normaliza os argumentos antes da substituição, a ordem normal não. As duas estratégias são análogas à avaliação ágil, por exemplo, C, e à preguiçosa, como Haskell.

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

diverge sob redução beta de ordem do aplicativo

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

desde em semântica estrita

forall f.  f _|_  =  _|_

mas converge com a redução beta de ordem normal preguiçosa

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

Se uma expressão tiver uma forma normal, a redução beta de ordem normal a encontrará.

Y

A propriedade essencial do Y combinador de ponto fixo

λ f. (λ x. f (x x)) (λ x. f (x x))

É dado por

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  g (g (Y g))
. . .                                      . . .

A equivalência

Y g  =  g (Y g)

é isomórfico para

fix f  =  f (fix f)

O cálculo lambda não tipado pode codificar provas construtivas arbitrárias sobre funções gerais / μ-recursivas.

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(Multiplicação atrasada, confluência)

Para o cálculo lambda não tipificado da Igreja, foi demonstrado que existe uma infinidade recursivamente enumerável de combinadores de ponto fixo Y.

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

A redução beta de ordem normal torna o cálculo lambda não digitado sem extensão um sistema de reescrita completo de Turing.

Em Haskell, o combinador de ponto fixo pode ser implementado com elegância

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

A preguiça de Haskell normaliza para uma finura antes de todas as subexpressões terem sido avaliadas.

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

• David Turner: Tese da Igreja e Programação Funcional
• Igreja de Alonzo: um problema insolúvel da teoria elementar dos números
• Cálculo lambda
• Teorema de Church-Rosser

Outras respostas fornecem respostas bastante concisas para isso, sem um fato importante: você não precisa implementar o combinador de ponto fixo em nenhuma linguagem prática dessa maneira complicada e isso não serve para nenhum propósito prático (exceto "veja, eu sei o que o combinador Y é"). É um conceito teórico importante, mas de pouco valor prático.

Aqui está uma implementação em JavaScript do Y-Combinator e da função fatorial (do artigo de Douglas Crockford, disponível em: http://javascript.crockford.com/little.html ).

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

Um combinador em Y é outro nome para um capacitor de fluxo.

Eu escrevi uma espécie de "guia de idiotas" para o Y-Combinator, tanto em Clojure quanto em Scheme, a fim de me ajudar a lidar com isso. Eles são influenciados pelo material de "The Little Schemer"

No esquema: https://gist.github.com/z5h/238891

ou Clojure: https://gist.github.com/z5h/5102747

Ambos os tutoriais são intercalados com comentários e devem ser recortados e colados no seu editor favorito.

Como iniciante nos combinadores, achei o artigo de Mike Vanier (obrigado Nicholas Mancuso) muito útil. Eu gostaria de escrever um resumo, além de documentar minha compreensão, se isso puder ser útil para alguns outros, eu ficaria muito feliz.

De porcaria a menos porcaria

Usando o fatorial como exemplo, usamos a seguinte almost-factorialfunção para calcular o fatorial do número x:

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

No pseudo-código acima, almost-factorialrecebe função fe número x( almost-factorialé curry, para que possa ser visto como tendo função fe retornando uma função de 1 aridade).

Quando almost-factorialcalcula fatorial para x, delega o cálculo de fatorial para x - 1funcionar fe acumula esse resultado com x(nesse caso, multiplica o resultado de (x - 1) com x).

Pode ser visto como almost-factorialuma versão de baixa qualidade da função fatorial (que só pode calcular o número de caixa x - 1) e retorna uma versão menos ruim de fatorial (que calcula o número de caixa x). Como nesta forma:

almost-factorial crappy-f = less-crappy-f

Se passarmos repetidamente a versão menos cagada do fatorial para almost-factorial, obteremos a função fatorial desejada f. Onde pode ser considerado como:

almost-factorial f = f

Ponto de correção

O fato de que isso almost-factorial f = fsignifica fé o ponto de correção da função almost-factorial.

Essa foi uma maneira realmente interessante de ver as relações das funções acima e foi um momento de aha para mim. (leia a postagem de Mike no ponto de correção, se você não tiver)

Três funções

Para generalizar, temos uma função não recursivafn (como nosso quase fatorial), temos sua função de ponto de correçãofr (como nosso f); então, o que Yfaz é quando você doa Y fn, Yretorna a função de ponto de correção de fn.

Então, em resumo (simplificado assumindo que frleva apenas um parâmetro; xdegenera para x - 1, x - 2... em recursão):

• Nós definimos os cálculos básicos como fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), este é o quase-útil função - embora não possamos usar fndiretamente sobre x, será útil em breve. Este não recursivo fnusa uma função frpara calcular seu resultado
• fn fr = fr, frÉ o ponto de correção de fn, fré o útil funciton, podemos usar frem xconseguir nosso resultado
• Y fn = fr, Yretorna o ponto de correção de uma função, Y transforma nossa função quase útilfn em útil fr

Derivação Y(não incluída)

Vou pular a derivação Ye ir para o entendimento Y. O post de Mike Vainer tem muitos detalhes.

A forma de Y

Yé definido como (no formato de cálculo lambda ):

Y f = λs.(f (s s)) λs.(f (s s))

Se substituirmos a variável sà esquerda das funções, obteremos

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

Então, de fato, o resultado de (Y f)é o ponto de correção de f.

Por que (Y f)funciona?

Dependendo da assinatura de f, (Y f)pode ser uma função de qualquer área, para simplificar, vamos assumir (Y f)apenas um parâmetro, como nossa função fatorial.

def fn fr x = accumulate x (fr (- x 1))

desde então fn fr = fr, continuamos

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

o cálculo recursivo termina quando o mais interno (fn fr 1)é o caso base e fnnão é usado frno cálculo.

Olhando Ynovamente:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

assim

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

Para mim, as partes mágicas dessa configuração são:

• fne frinterdependem um do outro: fr'quebra' fndentro, toda vez que fré usado para calcular x, 'gera' ('elevadores'?) fne delega o cálculo a ele fn(passando por si mesmo fre x); por outro lado, fndepende fre usa frpara calcular o resultado de um problema menor x-1.
• No momento em que fré usado para definir fn(quando fnusado frem suas operações), o real frainda não está definido.
• É isso fnque define a lógica real dos negócios. Com base em fn, Ycria fr- uma função de auxiliar numa forma específica - para facilitar o cálculo para fnem um recursiva maneira.

Isso me ajudou a entender Ydessa maneira no momento, espero que ajude.

BTW, eu também achei muito bom o livro Uma Introdução à Programação Funcional através do Cálculo Lambda , sou apenas parte dele e o fato de não ter conseguido entender o que aconteceu Yno livro me levou a este post.

Aqui estão as respostas para as perguntas originais , compiladas a partir do artigo (que vale TOTALMENTE leitura) mencionado na resposta de Nicholas Mancuso , bem como outras respostas:

O que é um combinador em Y?

Um combinador Y é uma "funcional" (ou uma função de ordem superior - uma função que opera em outras funções) que usa um único argumento, que é uma função que não é recursiva, e retorna uma versão da função que é recursivo.

Um pouco recursivo =), mas com uma definição mais profunda:

Um combinador - é apenas uma expressão lambda sem variáveis ​​livres.
Variável livre - é uma variável que não é uma variável vinculada.
Variável vinculada - variável que está contida no corpo de uma expressão lambda que possui esse nome de variável como um de seus argumentos.

Outra maneira de pensar sobre isso é que combinator é uma expressão lambda, na qual você pode substituir o nome de um combinator por sua definição em todos os lugares em que é encontrado e ter tudo ainda funcionando (você entrará em um loop infinito se o combinator conter referência a si próprio, dentro do corpo lambda).

O combinador Y é um combinador de ponto fixo.

O ponto fixo de uma função é um elemento do domínio da função que é mapeado para ela mesma pela função.
Ou seja, cé um ponto fixo da função f(x)se f(c) = c
Isso significaf(f(...f(c)...)) = fn(c) = c

Como os combinadores funcionam?

Os exemplos abaixo assumem digitação forte + dinâmica :

Combinador Y preguiçoso (ordem normal):
Esta definição se aplica a idiomas com avaliação preguiçosa (também: adiada, chamada por necessidade) - estratégia de avaliação que atrasa a avaliação de uma expressão até que seu valor seja necessário.

Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

O que isso significa é que, para uma determinada função f(que é uma função não recursiva), a função recursiva correspondente pode ser obtida primeiro computando λx.f(x x)e depois aplicando essa expressão lambda a si mesma.

Combinador Y estrito (por ordem de aplicação):
Esta definição se aplica a idiomas com avaliação estrita (também: ansiosa, gananciosa) - estratégia de avaliação na qual uma expressão é avaliada assim que é vinculada a uma variável.

Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

É o mesmo que o preguiçoso em sua natureza, apenas possui um λinvólucro extra para atrasar a avaliação do corpo do lambda. Fiz outra pergunta , um pouco relacionada a esse tópico.

Para que servem?

Roubado emprestado da resposta por Chris Ammerman : o combinador em Y generaliza a recursão, abstraindo sua implementação e, assim, separando-a do trabalho real da função em questão.

Mesmo que o combinador Y tenha algumas aplicações práticas, é principalmente um conceito teórico, cuja compreensão expandirá sua visão geral e provavelmente aumentará suas habilidades analíticas e de desenvolvedor.

Eles são úteis em linguagens processuais?

Como afirma Mike Vanier : é possível definir um combinador Y em muitas linguagens estaticamente tipadas, mas (pelo menos nos exemplos que eu vi) essas definições geralmente requerem algum tipo de hackeamento não óbvio, porque o próprio combinador Y não ' t tem um tipo estático direto. Isso está além do escopo deste artigo, então não vou mencionar mais

E, como mencionado por Chris Ammerman : a maioria das linguagens procedurais possui digitação estática.

Então responda a este - não realmente.

O combinador y implementa recursão anônima. Então, ao invés de

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

você pode fazer

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

é claro, o combinador-y só funciona nos idiomas de chamada por nome. Se você quiser usar isso em qualquer linguagem normal de chamada por valor, precisará do combinador z relacionado (o combinador y divergirá / loop infinito).

Um combinador de ponto fixo (ou operador de ponto fixo) é uma função de ordem superior que calcula um ponto fixo de outras funções. Essa operação é relevante na teoria da linguagem de programação, pois permite a implementação de recursão na forma de uma regra de reescrita, sem suporte explícito do mecanismo de tempo de execução da linguagem. (src Wikipedia)

O operador this pode simplificar sua vida:

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

Então você evita a função extra:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

Finalmente, você liga fac(5).

Acho que a melhor maneira de responder a isso é escolher um idioma, como JavaScript:

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

Agora, reescreva-o para que não use o nome da função dentro da função, mas ainda a chame recursivamente.

O único local em que o nome da função factorialdeve ser visto é no site da chamada.

Dica: você não pode usar nomes de funções, mas pode usar nomes de parâmetros.

Trabalhe o problema. Não procure. Depois de resolvê-lo, você entenderá o problema que o combinador-y resolve.