Y-combinator: Das ewige Vergessen

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Y-combinator: Das ewige Vergessen

    Ich hatte es mal verstanden. Und zwar aufgrund eines Beitrages, der auf SO verlinkt war. Leider finde ich den nicht mehr. Und leider bekomme ich es aus dem aktuellen Gedächtnis nicht mehr hin. (Wenngleich ich das Gefühl habe, kurz davor zu stehen.)

    Also, wie ging das noch einmal mit der Fixpunktfunktion in Objective-C?
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?
  • Soweit mich meine Erinnerung nicht vollständig verlässt, ist der Y-Combinator ein Fixpunkt eines Closures. Aber ganz praktisch: Blöcke rekursiv aufrufen. (Und ja, den Workaround hausmacher Art kenne ich. Aber mich stört es, dass ich die eigentliche Lösung vergessen habe und dann nicht einmal den Artikel mehr finde.)
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?
  • Für's Protokoll und nach Lektüre von Teilen und angestrengtem Nachdenken:

    Man schreibt eine Funktion (oder einen Block), die einen Block nimmt. Die Funktion führt den Block aus, wobei dieser Block als Parameter sich selbst erhält. Damit kann er sich aufrufen.

    Das Problem besteht dann darin, dass man einen rekursiven Typen hat, weil der übergebene Block ja eine Parameterliste hat, die einen Block enthält, welcher einen Block bekommt, der einen … Das geht in C nicht. (Geht es eigentlich in Swift?)

    Das ist aber egal, weil man einfach id nimmt.
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?
  • Ja das geht auch in Swift.

    Beispiel:

    Quellcode

    1. typealias Foo = (Int) -> Int
    2. var foo: Foo?
    3. foo = { n in
    4. if n == 0 {
    5. return 0
    6. }
    7. else if n == 1 {
    8. return 1
    9. }
    10. else {
    11. return foo!(n - 1) + foo!(n - 2)
    12. }
    13. }
    14. let foos = (0..<10).map{ foo!($0) }
    15. print(foos) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    Alles anzeigen

    Der Haken dabei ist, daß a) die Variable, die die Closure hält, als Optional definiert sein muß und b) bevor dieser Variablen die konkrete (rekursive) Closure zugewiesen wird, sie vorab einmal als nil bestimmt ist, damit man eben im Body der Closure wieder darauf zugreifen kann. Etwas unschön ist es, daß der Aufruf dann als EUO (!) erfolgt.

    Könntest Du den Code mal nach Objective-C transponieren? Mit Blocks in Objective-C stand ich immer auf Kriegsfuß... :whistling:
    Das iPhone sagt: "Zum Antworten streichen". Wie? Echt Jetzt? Muß ich erst die Wohnung streichen!?
  • Das ist kein Y-Ccombinator, sondern auch die in Objective-C verbreitete Hausmacherlösung, einen Y-Combinator zu vermeiden.
    en.wikipedia.org/wiki/Fixed-point_combinator

    In Objective-C definierst du einfach die Variable als __block, so dass sie beschreibbar ist. Dann weißt du den Cosure zu. Ist also derselbe Ansatz. Davon ist er ja in Swift gestohlen worden. Aber es ist eben kein Y-Combinator, was sich schon leicht daran zeigt, dass man eine Variable benötigt.


    Meine Frage bezog sich aber ohnehin auf rekursive Typen.
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?
  • Na gut, dann eben obiges Beispiel als Y-Kombinator in Swift:

    Quellcode

    1. func Y<T, U>(_ f: @escaping (@escaping (T) -> U) -> (T) -> U) -> (T) -> U {
    2. return { x in return f(Y(f))(x) }
    3. }
    4. let foos: [Int] = (0..<10).map { x in
    5. Y { f in
    6. { n in
    7. switch n {
    8. case 0, 1:
    9. return n
    10. default:
    11. return f(n - 1) + f(n - 2)
    12. }
    13. }
    14. } (x)
    15. }
    16. print(foos) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    Alles anzeigen
    Wer's lesend sofort versteht, kriegt von mir einen Keks. :D

    Mich würde es wirklich interessieren, wie das jetzt _konkret_ in Objective-C aussehen würde. ?(
    Das iPhone sagt: "Zum Antworten streichen". Wie? Echt Jetzt? Muß ich erst die Wohnung streichen!?
  • torquato schrieb:

    Na gut, dann eben obiges Beispiel als Y-Kombinator in Swift:

    Quellcode

    1. func Y<T, U>(_ f: @escaping (@escaping (T) -> U) -> (T) -> U) -> (T) -> U {
    2. return { x in return f(Y(f))(x) }
    3. }
    4. let foos: [Int] = (0..<10).map { x in
    5. Y { f in
    6. { n in
    7. switch n {
    8. case 0, 1:
    9. return n
    10. default:
    11. return f(n - 1) + f(n - 2)
    12. }
    13. }
    14. } (x)
    15. }
    16. print(foos) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    Alles anzeigen
    Wer's lesend sofort versteht, kriegt von mir einen Keks. :D

    Mich würde es wirklich interessieren, wie das jetzt _konkret_ in Objective-C aussehen würde. ?(
    Du hattest zuletzt danach gefragt, wie die Hausmacherlösung in Objective-C aussieht. Die findest du ja im Internet 1000fach. Ihc glaube aber, du willst jetzt wissen, wie ein Y-combinator aussieht?

    github.com/jballanc/objc-ycomb/blob/master/y.h

    Wobei das jetzt eine generische Lösung ist.
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?
  • hns schrieb:

    Wobei ich mich sofort frage: wozu.
    "Aber mich stört es, dass ich die eigentliche Lösung vergessen habe und dann nicht einmal den Artikel mehr finde."

    Weil Objective-C wie auch Swift ja Blockvariablen kennt, ist es natürlich überflüssig. Aber ich ärgerte mich halt, dass ich nicht mehr wusste, we es eigentlich richtig geht
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?
  • So, habe selbst noch einmal eine (halb)generische) Lösung geschrieben:

    Quellcode

    1. typedef int (^R)(int, id);
    2. int (^y)(int a, id r) = ^( int a, id r){ return ((R)r)(a, r); };

    Danach dürfte auch jeder das sofort anwenden können. Zum Beispiel Fakultät:

    Quellcode

    1. int result = y( 5,
    2. ^(int a, id r)
    3. {
    4. if( a < 2 )
    5. return a;
    6. else
    7. return a * ((R)r)(a-1,r);
    8. });

    Da sieht man eben den Vorteil von generischen Lösungen: Einer, der schlau ist, denkt einmal darüber nach und viele müssen es dann nicht mehr.

    Interessehalber: Gibt es eine generische Lösung in Swift?
    Und noch offen: Gibt es rekursive Typen in Swift?

    Also, um das noch einmal mit Objective-C zu vergleichen: Natürlich gibt es so etwas eingeschränkt aus C. Ein klassisches Beispiel:

    Quellcode

    1. struct s { int v, struct s *next }

    Das geht, weil hier nur ein Zeiger definiert wird und der Compiler dessen Größe unabhängig von der Struktur kennt. Ist aber eigentlich ein Sonderfall.

    Bei mir gibt es folgendes Problem: Nehmen wir mal etwa den Funktionskopf von y:

    Quellcode

    1. int (^y)(int a, id r)

    Der Trick liegt ja darin, dass ich y den Block r gebe, der dann von y wieder an r übergeben wird. Wie man ja sieht, wenn man das ganze Typjedöns weglässt, steht in y:

    Quellcode

    1. r(a, r)

    Die richtige Typisierung von r wäre daher

    Quellcode

    1. int (^r)(int a, int (^r)( int a, int (^r)( int (^r), int a …


    Man kann es halt nicht hinschreiben …
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Amin Negm-Awad ()

  • Ah, mit einer offenen Parameterliste könnte es vielleicht gehen. Darüber muss ich beizeiten noch einmal nachdenken.

    Oder noch eine Idee: Das Problem liegt ja in der typstrenge von Blocks. Wenn man das Ganze in ein Objekt wrappen könnte, hätte man dynamisches Dispatching und die ganze Geschichte würde alleine funktionieren.
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Amin Negm-Awad ()

  • Amin Negm-Awad schrieb:

    Interessehalber: Gibt es eine generische Lösung in Swift?

    Steht doch oben. Der Kombinator, den ich geschrieben habe, ist generisch oder mach ich da ein Denkfehler?

    Amin Negm-Awad schrieb:

    Und noch offen: Gibt es rekursive Typen in Swift?

    Ja. Mit structs geht das leider nicht, aber bei enums. Dafür gibt es das Keyword indirect.

    Quellcode

    1. indirect enum Foo {
    2. case bar, baz(Foo)
    3. }

    Mit enums kann man in Swift überhaupt eine ganze Menge spannender Sachen machen, wofür sie ursprünglich gar nicht gedacht waren. Vgl. z.B. Erica Sadun über No-case Enums.
    Das iPhone sagt: "Zum Antworten streichen". Wie? Echt Jetzt? Muß ich erst die Wohnung streichen!?
  • Ach, habe ich überlesen. Sorry.

    Na, ja, enums als Typ ist ja auch eine sehr formale Betrachtung. Das Beispiel bei Sadun ist allerdings eines, das belegt, dass man eben zu Hacks greifen muss, wenn die Sprache nicht ordentlich formuliert ist.
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?