Y-Kombinator Praxisbeispiel

Question

Ich habe ein wenig in letzter Zeit über funktionale Programmierung zu lesen und ich versuche, die Y-Combinator grok. Ich verstehe, dass Sie den Y-Combinator verwenden können, um effektiv Rekursion in einer Sprache zu implementieren, die nicht Rekursion direkt unterstützt. Allerdings verwenden jede Sprache, die ich wahrscheinlich bin schon unterstützt Rekursion so bin ich nicht sicher, wie nützlich es wäre, den Y-Combinator dafür zu verwenden.

Gibt es ein besseres praktisches Beispiel für Y-Combinator Verwendung, die ich vermisst habe? Hat jemand tatsächlich ein in realen Produktionscode verwendet? Oder wird mit dem Y-Combinator wirklich nur eine knifflige akademische Übung (wenn auch ziemlich cool eins).

Answer 1

Ich werde mit anderen Antworten anderer Meinung zu sein: Der Festpunkt (Y) combinator hat haben praktische Anwendungen , aber es dauert einen sehr einfallsreichen Geist, sie zu finden . Wie Bruce McAdam. Hier ist der Auszug aus seinem Papier Das Über Wraps es bis :

  

Die Y Combinator für Fixpunkte Berechnung kann in Standard ML ausgedrückt werden. Es wird häufig als Beispiel für die Macht der Funktionen höherer Ordnung verwendet, ist aber nicht generell als nützliche Programmierung Konstruktion angesehen. Hier sehen wir, wie eine Programmiertechnik, basierend auf der Y Combinator und Wrapper geben können Programmierer ein Maß an Kontrolle über die internen Abläufe von Funktionen nicht anders möglich, ohne zu Umschreiben und Code neu kompilieren. Als Experiment wird die Typ-Inferenz-Algorithmus W unter Verwendung dieser Technik implementiert, so dass Fehlermeldungen mit einem Minimum an Störung für den Algorithmus erzeugt werden. Der Code für dieses Beispielprogramm zeigt den echten Nutzen der Konzepte und die Leichtigkeit, mit der sie angewandt werden kann. Eine Reihe von anderen Implementierungstechniken und Anwendungsmöglichkeiten werden ebenfalls diskutiert, einschließlich der Verwendung von Funktionen höherer Ordnung der Verwendung von Ausnahmen und Fortsetzungen zu simulieren.

Es ist ein großes Papier; alle Interessierten in der funktionalen Programmierung wird wahrscheinlich viel Spaß beim Lesen.

Answer 2

Sie können diese nette Post Check-out des Y Combinator in C # Implementierung: Rekursive Lambda-Ausdrücke , es könnte Ihnen helfen, die Idee besser zu verstehen.

Sie möchten ein paar schöne Artikel auf Wikipedia überprüfen: Festpunkt combinator und < a href = "http://en.wikipedia.org/wiki/Fixed-point_theorem#Fixed_point_theorems_in_discrete_mathematics_and_theoretical_computer_science" rel = "nofollow noreferrer"> Punkt Theoreme Fest

Wie Nathan sagt, viele funktionelle Techniken zur Y Combinator bezogen und sind nützlich, also halten Sie es! Y wirklich nützlich ist, weil es Ihnen besser zu verstehen, den Code läßt, aber ich glaube nicht, das ist ein besonders hilfreich zu beschreiben, wie es hilft.

Answer 3

Sie können denken Sie an die combinator wie die virtuelle Maschine, die Ihre Funktion läuft, die Sie durch eine nicht-rekursive Funktions (= Funktion höherer Ordnung) beschreiben.

Manchmal wäre es schön, diese combinator unter Programmsteuerung zu haben, ähnliche Dinge wie aspektorientierte Programmierung (memoizing, Tracing, ...) zu tun, aber keine Programmiersprache Ich weiß es erlaubt. Wahrscheinlich wäre es zu umständlich den meisten Zeit und / oder zu schwer zu erlernen.

Answer 4

Andere können mich korrigieren, wenn ich falsch liege, aber ich bin ziemlich sicher, dass der Y-Combinator streng akademisch ist. Denken Sie daran: implementieren es Ihre Sprache Funktionen höherer Ordnung unterstützen muss aber nicht Rekursion. Es gibt nur eine Sprache, die ich weiß, wie folgt aus:. Lambda-Kalkül

Also, bis unsere Maschinen von Turing-Maschinen einschalten Lambda-Kalkül zu laufen, wird die Y Combinator streng akademisch sein.

Hinweis: andere funktionelle Techniken zur Y Combinator Zusammenhang sind nützlich, so halten sie an. die Y-Combinator das Verständnis wird Ihnen helfen, Fortsetzungen, lazy evaluation verstehen, etc.

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) x // The Y Combinator
    //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work.
    let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x))
    many1Indents sprite sprites_up

Hier ist ein Beispiel aus dem Compiler für ein kleineres Spiel Bibliothek, die ich in F # mache. Insbesondere in den oben genannten, ich brauche die sprites_up rekursiv sich selbst nennen sonst die Vertiefung Parser nicht richtig funktionieren würde.

Ohne den Y Combinator, konnte ich den Parser nicht richtig gemacht und hätte zurückgreifen müssen, so etwas zu schreiben:

let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) 
let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) 
let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) 
let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) 
let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

Wäre es nicht eine große Lösung gewesen sein, die Y Combinator mich gerettet wirklich da. Es war sicherlich nicht das erste, was allerdings in den Sinn kam.