O que é um Y-Combinator? [fechadas]

StackOverflow https://stackoverflow.com/questions/93526

Pergunta

A Y-Combinator é um conceito de ciência da computação do lado “funcional” das coisas. A maioria dos programadores não sei muita coisa sobre combinadores, se eles sequer ouvido falar sobre eles.

  • O que é um Y-Combinator?
  • Como fazer combinators trabalho?
  • O que são bons para?
  • Eles são úteis em linguagens procedurais?
Foi útil?

Solução

Se você está pronto para uma longa leitura, Mike Vanier tem um grande explicação. Longa história curta, que lhe permite implementar recursão em uma língua que não suporta necessariamente nativamente.

Outras dicas

A Y-Combinator é um "funcional" (uma função que opera em outras funções) que permite a recursividade, quando você não pode se referir à função de dentro de si. Em teoria, ciência da computação, ele generaliza recursão , abstraindo a sua execução, e, assim, separando-o do trabalho real da função em questão. A vantagem de não necessitar de um nome em tempo de compilação para a função recursiva é uma espécie de bônus. =)

Isto é aplicável em idiomas que suporte funções lambda . natureza baseada a expressão de lambdas normalmente significa que eles não podem se referem a si mesmos pelo nome. E trabalhar em torno deste por meio de declarar a variável, referindo-se a ele, em seguida, atribuindo o lambda para ele, para completar o ciclo de auto-referência, é frágil. A variável lambda pode ser copiado, e a variável original re-atribuído, que quebra a auto-referência.

Y-combinadores são difíceis de implementar, e muitas vezes a utilização, em estática digitado idiomas (que linguagens procedurais são muitas vezes), porque as restrições normalmente digitação exigem que o número de argumentos para a função em questão a ser conhecido no momento da compilação. Isto significa que uma y-combinator devem ser escritos por qualquer contagem argumento de que é preciso usar.

Segue-se um exemplo de como o uso e de trabalho de um Y-combinador, em C #.

Usando um Y-Combinator envolve uma maneira "incomum" de construir uma função recursiva. Primeiro você deve escrever suas funções como um pedaço de código que chama uma função pré-existente, ao invés de si mesmo: 

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

Então você transformar isso em uma função que leva uma função para chamadas, e retorna uma função que faz isso. Isso é chamado de funcional, porque leva uma função, e realiza uma operação com ele 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 leva uma função, e retorna outra função que tipo de olhares como um factorial, mas em vez de chamar a si mesmo, ele chama o argumento passado para a função externa. Como você faz isso o fatorial? Passar a função interior para si. O Y-Combinator faz isso, por ser uma função com um nome permanente, que pode introduzir a recursividade. 

// 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.
}

Ao contrário do que a própria vocação fatorial, o que acontece é que as chamadas fatoriais o gerador fatorial (retornado pela chamada recursiva para Y-Combinator). E, dependendo do valor atual de t a função retornou do gerador será ou ligue para o gerador de novo, com t -. 1, ou apenas retornar 1, que encerra o recursão

É complicado e enigmático, mas todos os shakes fora em tempo de execução, e a chave para o seu trabalho é "execução diferida", ea quebra da recursividade a extensão duas funções. O F interior é passado como um argumento , a ser chamado na próxima iteração, somente se necessário .

Eu já levantou esta de http: //www.mail-archive .com / Boston-pm @ mail.pm.org / msg02716.html que é uma explicação que eu escrevi há vários anos.

Vou usar JavaScript neste exemplo, mas muitas outras línguas irá funcionar tão bem.

Nosso objetivo é ser capaz de escrever uma função recursiva de 1 variável usando apenas as funções de 1 variáveis ??e não há atribuições, definindo as coisas pelo nome, etc. (Por que este é o nosso objetivo é uma outra questão, vamos tomar isso como o desafio que nos é dada.) Parece impossível, não é? Como um exemplo, vamos implementar fatorial.

Bem etapa 1 é dizer que nós poderíamos fazer isso facilmente se enganado um pouco. Usando funções de 2 e variáveis atribuição de pelo menos podemos evitar ter que usar atribuição para definir a recursividade. 

// 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 enganar menos. Bem em primeiro lugar estamos usando atribuição, mas não precisa. 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 nós estamos usando funções de 2 variáveis ??para obter uma função de 1 variável. Nós podemos consertar isso? Bem, um cara inteligente pelo nome de Haskell Curry tem um truque, se você tem boa ordem superior funções, então você só precisa de funções de uma variável. o Prova disso é que você pode obter de funções de 2 (ou mais no caso geral) variáveis ??para uma variável com um puramente transformação de texto 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. (Este truque é chamado "Currying" após o seu inventor. A linguagem Haskell é também nomeado para Haskell Curry. Arquivo que sob trivia inútil.) Agora é só aplicar esta transformação em todos os lugares e temos nossa 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 experimentá-lo. alert () que o retorno, amarrá-lo a um botão, o que for. Esse código calcula fatoriais, de forma recursiva, sem usar atribuição, declarações, ou funções de 2 variáveis. (Mas tentando rastrear como ele funciona é susceptível de fazer girar a cabeça. E entregá-lo, sem a derivação, apenas ligeiramente reformatada irá resultar em código que é certo para confundir e confundir.)

Você pode substituir as 4 linhas que recursivamente definir fatorial com qualquer outra função recursiva que você quer.

Gostaria de saber se há qualquer uso na tentativa de construir este a partir do zero. Vamos ver. Aqui está, uma função factorial recursiva básica: 

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

Vamos refactor e criar uma nova função chamada fact que retorna uma função de computação factorial anônimo em vez de executar o cálculo em si: 

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 com ele. Nós apenas estamos gerando uma nova função fatorial em cada etapa.

A recursão nesta fase ainda é bastante explícito. A função fact 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 recurser ainda precisa conhecer o seu 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 retorna seu resultado: 

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

var factorial = Y();

Agora podemos livrar-se do nome recurser completamente; é apenas um argumento para a função interna de Y, que pode ser substituído com a 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 nome somente externo ainda referenciada é fact, mas deve estar claro agora que que é facilmente parametrizado, também, criar a completo, genérico, solução: 

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 .

combinadores de ponto fixo são usados ??para mostrar que lambda calculus é turing completa . Este é um resultado muito importante na teoria da computação e fornece uma base teórica para funcional programação.

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

y-combinator 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

Editar : Eu aprendo muito de olhar para o código, mas este é um pouco difícil de engolir, sem algum fundo - 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 "y-combinator". Agora, dê uma olhada na linha var factorial onde Y é usado. Observe que você passar uma função a ele que tem um parâmetro (neste exemplo, recurse) que também é usado mais tarde na função interna. O nome do parâmetro, basicamente, torna-se o nome da função interna que lhe permite efectuar uma chamada recursiva (uma vez que utiliza recurse() nele de definição.) O y-combinator executa a mágica de se associar a função interna de outra forma anônima com o nome do parâmetro da função passada para Y.

Para a explicação completa de como Y faz a mágica, check-out do ligada artigo (não por mim btw).

Para os programadores que não têm encontrado programação funcional em profundidade, e não se importam de começar agora, mas são levemente curioso:

O Combinator Y é uma fórmula que permite implementar recursão em uma situação em que as funções não podem ter nomes, mas pode ser passado ao redor como argumentos, utilizados como valores de retorno, e definido dentro de outras funções.

Ele funciona passando a função para si como um argumento, para que ele possa chamar-se.

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

O dia-a-dia valor prático da combinator Y é limitado, uma vez que as linguagens de programação tendem a deixar o nome funções.

Em caso de necessidade de identificá-lo em uma linha de polícia, ele se parece com isso:

Y = ?f. (?x.f (x x)) (?x.f (x x))

Você geralmente pode detectá-lo por causa da (λx.f (x x)) repetido.

Os símbolos λ são o lambda letra grega, que dá ao lambda calculus seu nome, e há um monte de termos de estilo (λx.t) porque é isso que o lambda calculus aparência semelhante.

Outras respostas fornecer resposta concisa bonita para isso, sem um fato importante: Você não precisa implementar combinator ponto fixo em qualquer linguagem prática desta forma complicada e isso não serve a nenhum propósito prático (exceto "Olha, eu sei o que Y-combinador é "). É importante conceito teórico, mas de pouco valor prático.

Aqui está uma implementação JavaScript do Y-Combinator e a 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);

A Y-combinador é um outro nome para um condensador de fluxo.

Eu escrevi uma espécie de "guia de idiotas" ao Y-Combinator tanto em Clojure e Scheme, a fim de ajudar a mim mesmo vir a enfrentar isso. Eles são influenciados por materiais em "The Little Schemer"

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

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

Ambos os tutoriais são código intercaladas com comentários e deve ser cortado & colável em seu editor favorito.

Anonymous recursão

De ponto fixo

Um combinador é uma fix função de ordem superior que satisfaz por definição a equivalência 

forall f.  fix f  =  f (fix f)

fix f representa um x solução para o ponto fixo equação 

               x  =  f x

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

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

Usando fix, provas construtivas arbitrárias mais gerais funções / µ-recursiva pode ser derivada sem nonymous autorreferencialidade. 

fact n = (fix fact') n

onde 

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

tal 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

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

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

Lambda calculus

O untyped lambda cálculo formalismo consiste em uma gramática livre de contexto 

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

onde gamas v mais variáveis, juntamente com o beta e redução eta regras 

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

substitutos de redução Beta todas as ocorrências livres do x variável na abstração ( “função”) B corpo pela expressão ( “argumento”) E. redução Eta elimina abstração redundante. Às vezes é omitido do formalismo. Um irredutível expressão, à qual nenhuma regra redução é aplicável, está em normais ou forma canônica . 

λ x y. E

é um atalho para 

λ x. λ y. E

(multiarity abstração), 

E F G

é um atalho para 

(E F) G

(aplicação deixou-associatividade), 

λ x. x

e 

λ y. y

alfa-equivalente .

Abstraction e aplicação são os dois únicos “primitivos de linguagem” do cálculo lambda, mas eles permitem que codificação de dados e operações arbitrariamente complexas.

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

   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
    . . .

A prova formal de que 

1 + 2  =  3

usando a regra de reescrita de redução de 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

Em cálculo lambda, combinators são abstrações que não contêm variáveis ??livres. A maioria simplesmente: I, o combinator identidade 

λ x. x

isomorphic para a função identidade 

id x = x

Esses combinators são os operadores primitivos de combinator cálculos como o sistema SKI. 

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

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

λ x. x x

para si: 

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

Redução de mais à esquerda subexpressions ( “cabeças”) é priorizado. ordem Applicative normaliza argumentos antes da substituição, ordem normal não. As duas estratégias são análogos a avaliação ansiosa, v.g. C, e a avaliação lenta, por exemplo Haskell. 

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

diverge sob redução de beta-fim aplicativo ansioso 

=  (λ 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))
. . .
=  _|_

já que em estrita semântica 

forall f.  f _|_  =  _|_

mas converge sob redução de beta-ordem normal preguiçoso 

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

Se uma expressão tem uma forma normal, redução de beta-ordem normal vai encontrá-lo.

Y

A propriedade essencial da Y ponto fixo combinator 

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

é dada 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)

é isomorfo a 

fix f  =  f (fix f)

O cálculo lambda sem tipo pode codificar arbitrárias provas construtivas sobre gerais funções / µ-recursiva. 

 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 atrasado, confluência)

Para Churchian cálculo lambda não tipado, não foi demonstrado que existe uma infinidade recursivamente enumerável de combinadores de ponto fixo além 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))
  . . .

redução normal de ordem beta faz com que o lambda não tipado unextended cálculo um sistema de reescrita Turing completo.

Em Haskell, o combinador de ponto fixo pode ser elegantemente implementado 

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

normaliza preguiça de Haskell para a finitude antes de todas subexpressions foram avaliadas. 

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

Os implementos y-Combinator recursão anônima. Assim em vez 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, a y-combinator só funciona em línguas chamada por nome. Se você quiser usar isso em qualquer linguagem normal chamada por valor, então você vai precisar do z-combinator relacionada (y-combinator irão divergir / infinito-loop).

Como um novato para combinadores, achei Mike Vanier (graças Nicholas Mancuso) para ser realmente útil. Eu gostaria de escrever um resumo, além de documentar meu entendimento, se poderia ser de ajuda para alguns outros que eu ficaria muito feliz.

From Cagado e Menos Cagado

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

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

No pseudo-código acima, toma em almost-factorial f função e número x (almost-factorial é Curry, de modo que pode ser visto como tendo em função f e retornando uma função 1-aridade).

Quando almost-factorial calcula fatorial para x, delega o cálculo de fatorial para x - 1 a função f e acumula-se esse resultado com x (neste caso, que multiplica o resultado de (x - 1) com x).

Ele pode ser visto como almost-factorial leva em um porcaria versão da função fatorial (que só pode calcular até número x - 1) e retorna um menos porcaria versão do fatorial ( que calcula até número x). Como neste formato: 

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

Se nós repetidamente passar o menos porcaria versão do fatorial para almost-factorial, que acabará por chegar a nossa função desejada f fatorial. Onde ele pode ser considerado como: 

almost-factorial f = f

Fix-point

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

Esta foi uma forma muito interessante de ver as relações das funções acima e foi um momento aha para mim. (Leia o post de Mike na correção de ponto se você não tiver)

funções Três

Para generalizar, temos um não-recursiva função fn (como o nosso quase-factorial), temos a sua correção de ponto função fr (como o nosso f), então o que Y faz é quando você dá Y fn, Y retorna a função de ponto de correção de fn.

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

  • Nós definimos os cálculos do núcleo como fn : def fn fr x = ...accumulate x with result from (fr (- x 1)), este é o quase útil função - embora não podemos usar fn diretamente sobre x, que será útil em breve. Este fn não recursivo usa uma função fr para calcular o seu resultado
  • fn fr = fr, fr é o ponto-fix de fn, fr é o útil funciton, podemos usar fr em x para obter o nosso resultar
  • Y fn = fr, Y retorna o ponto-fix de uma função, Y transforma o nosso quase útil função fn em útil fr

Derivando Y (não incluído)

Vou pular a derivação de Y e ir para Y entendimento. O post de Mike Vainer tem um monte de detalhes.

A forma de Y

Y é definido como (em lambda cálculo format): 

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

Se substituirmos a variável s na esquerda das funções, temos 

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, the resultar de (Y f) é o ponto-fix de f.

Por que o trabalho (Y f)?

Dependendo da assinatura do f, (Y f) pode ser uma função de qualquer arity, para simplificar, vamos supor (Y f) leva apenas um parâmetro, como a nossa função fatorial. 

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

desde 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)))

os termina cálculo recursivo quando o mais interna (fn fr 1) é o caso base e fn não usa fr no cálculo.

Olhando para Y novamente: 

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 peças mágicas desta configuração são:

  • fn e depender mutuamente fr uns sobre os outros: (? 'Elevadores') dentro fr fn 'wraps', cada fr tempo é usado para x calcular, é desova 'um fn e delegados o cálculo para que fn (passando em si fr e x); por outro lado, fn depende fr e usos fr ao resultado calcular de um x-1 problema menor.
  • No fr tempo é usado para definir fn (quando usos fn fr em suas operações), o fr reais ainda não está definido.
  • É de fn que define a lógica de negócio real. Baseado em fn, Y cria fr - uma função auxiliar de uma forma específica -. Para facilitar o cálculo para fn em um recursiva maneira

Ele me ajudou a compreender Y desta forma no momento, esperamos que ajuda.

BTW, eu também encontrei o livro Uma Introdução à Programação Funcional Através Lambda Calculus muito bom, eu sou apenas parte através dele eo fato de que eu não podia colocar minha cabeça em torno Y no livro me levou a este post.

Aqui estão as respostas para o perguntas originais , compilados a partir de o artigo (que é totalmente vale a pena ler) mencionado na resposta por Nicholas Mancuso , bem como outras respostas:

O que é um Y-Combinator?

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

= Algo recursivo), mas mais aprofundada definição:

A combinator - é apenas uma expressão lambda sem variáveis ??livres.
variável livre - é uma variável que não é uma variável ligada.
variável ligada -. variável que está contido dentro do corpo de uma expressão lambda que tem esse nome de variável como um de seus argumentos

Outra maneira de pensar sobre isso é que combinator é tal expressão lambda, em que você é capaz de substituir o nome de um elemento de combinação com a sua definição em todos os lugares é encontrado e têm tudo ainda trabalho (você vai entrar em um loop infinito se combinator conteria referência a si mesmo, dentro do corpo lambda).

Y-combinador é um elemento de combinação de ponto fixo.

ponto de uma função fixa é um elemento do domínio da função que está mapeado para si pela função.
Ou seja, c é um ponto fixo da função f(x) se f(c) = c
Isto significa f(f(...f(c)...)) = fn(c) = c

Como fazer combinators trabalho?

Exemplos abaixo assumem forte + dinâmica digitando:

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

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

O que isto significa é que, para um dado f função (que é uma função não-recursiva), a função recursiva correspondente pode ser obtido primeiro por λx.f(x x) de computação, e, em seguida, aplicar essa expressão lambda para si.

estrita (aplicativa-fim) Y-combinator:
Esta definição aplica-se a línguas com estrita (também: ansioso, ganancioso) avaliação - estratégia de avaliação em que a expressão é avaliada, logo que ele está vinculado 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)))

É mesmo como um preguiçoso em sua natureza, ele só tem um wrappers λ extra para atrasar a avaliação do corpo do lambda. Pedi outra pergunta , um pouco relacionado com este tema.

O que são bons para?

Stolen por Chris Ammerman : Y -combinator generaliza recursão, abstraindo a sua execução, e, assim, separando-o do trabalho real da função em questão.

Mesmo assim, Y-Combinator tem algumas aplicações práticas, é principalmente um conceito teórico, o entendimento de que irá expandir sua visão geral e, provavelmente, aumentar suas habilidades analíticas e de desenvolvedores.

Eles são úteis em linguagens procedurais?

Como afirma Mike Vanier : , é possível definir um Combinator Y em muitas linguagens de tipagem estática, mas (pelo menos nos exemplos que eu vi) tais definições geralmente requerem algum tipo hackery não-óbvia, porque tele Y Combinator em si não tem um tipo estático simples. Que está além do escopo deste artigo, por isso não vou mencioná-lo ainda mais

E, como mencionado por Chris Ammerman : línguas mais processuais tem estática digitação.

Assim resposta para esta pergunta -. Não é realmente

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

A este operador pode simplificar sua vida: 

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

Em seguida, você evita a função extra: 

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

Finalmente, você chama fac(5).

Eu 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, reescrevê-lo para que ele não usa o nome da função dentro da função, mas ainda chama isso de forma recursiva.

O único lugar do factorial nome da função deve ser visto é no site da chamada.

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

Trabalhar o problema. Não procurá-lo. Uma vez que você resolvê-lo, você vai entender o problema que os resolve y-Combinator.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top