Effacer, dérivation intuitive du combinateur point fixe (Y Combinator)?

cs.stackexchange https://cs.stackexchange.com/questions/9604

Question

Le combinateur de point fixe FIX (aka le combinateur Y) dans le (sans type) calcul de lambda ($ \ lambda $) est défini comme suit:

FIX $ \ triangleq \ lambda f. (\ Lambda x. F ~ (\ lambda y. X ~ x ~ y)) ~ (\ lambda x. F ~ (\ lambda y. X ~ x ~ y)) $

Je comprends son but et je peux suivre l'exécution de son application parfaitement bien; Je voudrais comprendre comment obtenir FIX des premiers principes .

Voici autant que je reçois lorsque je tente de tirer moi-même:

  1. FIX est une fonction: FIX $ \ triangleq \ lambda_ \ ldots $
  2. FIX prend une autre fonction, $ f $, pour le rendre récursif: FIX $ \ triangleq \ lambda f ._ \ ldots $
  3. Le premier argument de la fonction $ f $ est le « nom » de la fonction, utilisée lorsqu'une demande récurrente est destinée. Par conséquent, toutes les apparences du premier argument de $ f $ devrait être remplacé par une fonction, et cette fonction devrait attendre le reste des arguments de $ f $ (supposons que $ f $ prend un argument): FIX $ \ triangleq \ lambda f ._ \ ldots f ~ (\ lambda y. _ \ ldots y) $

C'est là, je ne sais pas comment « faire un pas » dans mon raisonnement. Les petits points de suspension indiquent où mon FIX manque quelque chose (bien que je ne suis en mesure de savoir que en le comparant à la FIX « réel »).

J'ai déjà lu Types et Langages de programmation , qui ne tente pas de tirer directement, et demande plutôt le lecteur à le Petit Schemer pour une dérivation. J'ai lu que, aussi, et sa « dérivation » était pas utile. De plus, il est moins d'une dérivation directe et plus d'une utilisation d'un exemple très précis et un ad-hoc tente d'écrire une fonction récursive appropriée dans $ \ lambda $.

Était-ce utile?

La solution

Je n'ai pas lu ça nulle part, mais c'est comment je crois que $ Y $ aurait été dérivée:

Ayons une fonction récursive $ f $, peut-être un factoriel ou autre chose comme ça. Officieusement, nous définissons $ f $ en terme pseudo-lambda où $ f $ se produit dans sa propre définition:

$$ f = \ ldots f \ ldots f \ ldots $$

Tout d'abord, nous nous rendons compte que l'appel récursive peut être pris comme un paramètre:

$$ f = \ underbrace {(\ lambda r. (\ Ldots r \ ldots r \ ldots))} _ {M} f $$

Maintenant, on pourrait définir $ f $ si nous avions seulement un moyen comment passer comme argument à lui-même. Ce n'est pas possible, bien sûr, parce que nous n'avons pas $ f $ à portée de main. Ce que nous avons à portée de main est $ M $. Depuis $ M $ contient tout ce dont nous avons besoin pour définir $ f $, nous pouvons essayer de passer $ M $ comme argument au lieu de $ f $ et essayer de reconstruire $ f $ de plus tard à l'intérieur. Nos premiers regards de tentative comme ceci:

$$ f = \ underbrace {(\ lambda r. (\ Ldots r \ ldots r \ ldots))} _ {M} \ underbrace {(\ lambda r. (\ Ldots r \ ldots r \ ldots)) } _ {M} $$

Cependant, ce n'est pas tout à fait correct. Avant, $ f $ mais j'ai remplacé pour $ r $ à l'intérieur $ M $. Mais maintenant, nous passons $ M $ au lieu. Nous devons corriger en quelque sorte tous les endroits où nous utilisons $ r $ pour que reconstruisent $ f $ de $ M $. En fait, ce pas difficile du tout: Maintenant que nous savons que $ f = M M $, partout où nous utilisons $ r $ il suffit de remplacer par $ (r) $

.

$$ f = \ underbrace {(\ lambda r. (\ Ldots (rr) \ ldots (rr) \ ldots))} _ {M '} \ underbrace {(\ lambda r. (\ Ldots (rr) \ ldots (rr) \ ldots)}) _ {M '} $$

Cette solution est bonne, mais nous avons dû changer l'intérieur $ M $. Ce n'est pas très pratique. Nous pouvons le faire avec plus d'élégance, sans avoir à modifier M $ $ en introduisant un autre $ \ lambda $ qui envoie à M $ $ son argument appliqué à lui-même: En exprimant M '$ en $ \ lambda xM (xx) $, nous obtenons

$$ f = (\ lambda x. \ Underbrace {(\ lambda r. (\ Ldots r \ ldots r \ ldots))} _ {M} (xx)) (\ lambda x. \ Underbrace {(\ lambda r. (\ ldots r \ ldots r \ ldots))} _ {M} (xx)) $$

Ainsi, lorsque $ M $ est substitué à $ x $, $ MM $ est substitué à $ r $, ce qui est par définition égale à $ f $. Cela nous donne une définition non récurrente de $ f $, exprimée en terme de lambda valide!

La transition vers $ Y $ est maintenant facile. Nous pouvons prendre un terme lambda arbitraire au lieu de $ M $ et effectuer cette procédure sur elle. Nous pouvons donc factoriser M $ $ et définir

$$ Y = \ lambda m. (\ Lambda x. M (xx)) (\ lambda x.m (xx)) $$

En effet, $ Y M $ réduit à $ f $ comme nous l'avons définie.

Note: Je suis tirais $ Y $ tel qu'il est défini dans la littérature. Le combinateur que vous avez décrit est une variante de $ Y $ pour langues , parfois aussi appelé $ Z $. Voir cet article de Wikipedia .

Autres conseils

Comme Yuval a souligné qu'il n'y a pas un seul opérateur de point fixe. Il y a beaucoup d'entre eux. En d'autres termes, l'équation pour point fixe théorème ne pas une seule réponse. Donc, vous ne pouvez pas tirer l'opérateur d'eux.

Il est comme demander comment les gens tirent $ (x, y) = (0,0) $ comme une solution pour $ x = y $. Ils ne le font pas! L'équation n'a pas de solution unique.

Juste au cas où que ce que vous voulez savoir comment le premier théorème du point fixe a été découvert. Permettez-moi de dire que je me suis demandé aussi sur la façon dont ils sont venus avec les théorèmes fixe points / récursion quand je les ai vus. Il semble si ingénieux. En particulier, sous la forme de la théorie de la calculabilité. Contrairement à ce que Yuval dit que ce n'est pas le cas que les gens ont joué autour jusqu'à ce qu'ils ont trouvé quelque chose. Voici ce que j'ai trouvé:

Pour autant que je me rappelle, le théorème est à l'origine en raison de S.C. Kleene. Kleene est venu avec le théorème de point fixe d'origine en récupérant la preuve de l'incompatibilité d'origine lambda-calcul de l'Eglise. d'origine lambda-calcul de l'Église souffrait d'un paradoxe de type Russel. Le calcul lambda modifié a évité le problème. Kleene a étudié la preuve d'incohérence probablement de voir comment si le calcul lambda modifié souffrirait d'un problème similaire et transféra la preuve d'incohérence dans un théorème utile dans le calcul du lambda modifié. Grâce à son travail en ce qui concerne l'équivalence du calcul lambada avec d'autres modèles de calcul (machines de Turing, fonctions récursives, etc.) il a été transféré à d'autres modèles de calcul.

Comment tirer l'opérateur que vous pourriez demander? Voici comment je le garde à l'esprit. théorème de point fixe est sur la suppression de l'auto-référence.

Tout le monde connaît le paradoxe du menteur:

Je suis tanière.

Ou sous la forme plus linguistique:

Cette phrase est fausse.

Maintenant, la plupart des gens pensent que le problème avec cette phrase est à l'auto-référence. Ce n'est pas! L'auto-référence peut être éliminé (le problème est avec la vérité, une langue ne peut pas parler de la vérité de ses propres phrases en général, voir le indéfinissable de Tarski du théorème vérité ). La forme dans laquelle on élimine l'auto-référence est la suivante:

Si vous écrivez la citation suivante deux fois, la deuxième fois à l'intérieur de citations, la peine est fausse: « Si vous écrivez deux fois citation suivante, la deuxième fois à l'intérieur de citations, la peine est fausse: »

Pas d'auto-référence, nous avons des instructions sur la façon de construire une phrase puis faire quelque chose avec elle. Et la phrase qui obtient construite est égale aux instructions. Notez que dans $ \ lambda $ -calcul nous ne citations pas besoin parce qu'il n'y a pas de distinction entre les données et les instructions.

Maintenant, si nous analysons ce que nous avons $ MM $ où Mx $ est les instructions pour construire xx $ $ et de faire quelque chose.

$ Mx = f (xx) $

$ M $ est $ \ lambda x. f (xx) $ et nous avons

$ MM = (\ lambda x. F (xx)) (\ lambda x. F (xx)) $

Ceci est un $ fixe f $. Si vous voulez faire un opérateur on ajoute juste $ \ lambda f $ et nous obtenons $ Y $:

$ Y = \ lambda f. (MM) = \ lambda f. ((\ Lambda x. F (xx)) (\ lambda x. F (xx))) $

Je viens donc de garder à l'esprit le paradoxe sans autoréférence et qui me permet de comprendre ce que $ Y $ est sur le point.

Vous devez donc définir un point fixe Combinator 

fix f = f (fix f)
      = f (f (fix f))
      = f (f (f ... ))

mais sans récursion explicite. Commençons par le plus simple Combinator irréductible 

omega = (\x. x x) (\x. x x)
      = (\x. x x) (\x. x x)
      = ...

Le x dans la première lambda est substitué de façon répétée par la seconde lambda. alpha-conversion simple rend ce processus plus clair: 

omega =  (\x. x x) (\x. x x)
      =α (\x. x x) (\y. y y)
      =β (\y. y y) (\y. y y)
      =α (\y. y y) (\z. z z)
      =β (\z. z z) (\z. z z)

i.e.. la variable dans la première lambda disparaît toujours. Donc, si l'on ajoute un f à la première lambda 

(\x. f (x x)) (\y. y y)

le f va bob up 

f ((\y. y y) (\y. y y))

Nous avons obtenu notre retour de omega. Il doit être clair maintenant que si l'on ajoute un f au deuxième lambda, le f apparaîtra dans la première lambda, puis il bob jusqu'à: 

Y f = (\x. x x)     (\x. f (x x))
      (\x. f (x x)) (\x. f (x x)) -- the classical definition of Y

Depuis 

(\x. s t) z = s ((\x. t) z), if `x' doesn't occur free in `s'

on peut réécrire l'expression 

f ((\x. x x) (\x. f (x x))

qui est juste 

f (Y f)

et nous avons obtenu notre Y f = f (Y f) équation. Ainsi, le combinateur Y est essentiellement

  1. le double de la f
  2. la première f montait
  3. répétition

Vous avez peut-être vu l'exemple classique d'une équation sans une forme normale:

$$ (\ lambda x, xx) (\ lambda x, xx) \ triangleright (\ lambda x, xx) (\ lambda x, xx) $$

Une équation similaire est suggérée par ce que pour la récursion générale:

$$ \ begin {array} {} rr & (\ Lambda x.R (xx)) (\ lambda x.R (xx)) ~ \\ \ Triangleright & R (~ (\ lambda x.R (xx)) (\ lambda x.R (xx)) ~) \\ \ Triangleright & R (R (~ (\ lambda x.R (xx)) (\ lambda x.R (xx)) ~)) \\ \ & Triangleright \ points \ End {array} \ balise {A} $$

(A) est une manière d'écrire des équations récursives générales de calcul de lambda (au-delà récursive primitive). Alors, comment vous résoudre l'équation $ Yf = f (YF) $? Branchez $ f $ dans pour $ R $ dans l'équation ci-dessus pour obtenir:

$$ Yf = (\ lambda x.f (xx)) (\ lambda x.f (xx)) $$ $$ Y = \ lambda f. (\ Lambda x.f (xx)) (\ lambda x.f (xx)) $$

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top