Apa itu Y-combinator? [Tutup]

Y-combinator adalah konsep ilmu komputer dari sisi "fungsional". Kebanyakan programmer tidak tahu sama sekali tentang kombinator, jika mereka pernah mendengarnya.

• Apa itu Y-combinator?
• Bagaimana cara kerja kombinator?
• Apa yang baik untuk mereka?
• Apakah mereka berguna dalam bahasa prosedural?

Jika Anda siap membaca lama, Mike Vanier memiliki penjelasan yang bagus . Singkatnya, ini memungkinkan Anda untuk menerapkan rekursi dalam bahasa yang belum tentu mendukungnya secara asli.

Y-combinator adalah "fungsional" (fungsi yang beroperasi pada fungsi lain) yang memungkinkan rekursi, ketika Anda tidak dapat merujuk ke fungsi dari dalam dirinya sendiri. Dalam teori ilmu komputer, ia menggeneralisasikan rekursi , mengabstraksikan implementasinya, dan dengan demikian memisahkannya dari kerja aktual dari fungsi yang dimaksud. Manfaat tidak memerlukan nama waktu kompilasi untuk fungsi rekursif adalah semacam bonus. =)

Ini berlaku dalam bahasa yang mendukung fungsi lambda . The ekspresi alam berbasis lambdas biasanya berarti bahwa mereka tidak bisa menyebut diri mereka dengan nama. Dan mengatasinya dengan mendeklarasikan variabel, merujuknya, lalu menugaskan lambda padanya, untuk menyelesaikan loop referensi-diri, rapuh. Variabel lambda dapat disalin, dan variabel asli ditugaskan kembali, yang mematahkan referensi-diri.

Y-combinator sulit untuk diimplementasikan, dan sering digunakan, dalam bahasa yang diketik statis (yang sering menggunakan bahasa prosedural ), karena biasanya pembatasan pengetikan membutuhkan jumlah argumen agar fungsi yang bersangkutan diketahui pada waktu kompilasi. Ini berarti bahwa kombinator-y harus ditulis untuk setiap argumen yang perlu digunakan.

Di bawah ini adalah contoh bagaimana penggunaan dan kerja Y-Combinator, dalam C #.

Menggunakan Y-combinator melibatkan cara "tidak biasa" untuk membangun fungsi rekursif. Pertama, Anda harus menulis fungsi Anda sebagai bagian dari kode yang memanggil fungsi yang sudah ada sebelumnya, daripada fungsi itu sendiri:

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

Kemudian Anda mengubahnya menjadi fungsi yang membutuhkan fungsi untuk memanggil, dan mengembalikan fungsi yang melakukannya. Ini disebut fungsional, karena dibutuhkan satu fungsi, dan melakukan operasi dengannya yang menghasilkan fungsi lain.

// 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);

Sekarang Anda memiliki fungsi yang mengambil fungsi, dan mengembalikan fungsi lain yang terlihat seperti faktorial, tetapi alih-alih menyebut dirinya sendiri, ia memanggil argumen yang dilewatkan ke fungsi luar. Bagaimana Anda menjadikan ini faktorial? Lewati fungsi batin itu sendiri. Y-Combinator melakukan itu, dengan menjadi fungsi dengan nama permanen, yang dapat memperkenalkan rekursi.

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

Daripada memanggil faktorial itu sendiri, yang terjadi adalah bahwa faktorial memanggil generator faktorial (dikembalikan oleh panggilan rekursif ke Y-Combinator). Dan tergantung pada nilai t saat ini, fungsi yang dikembalikan dari generator akan memanggil generator lagi, dengan t - 1, atau hanya mengembalikan 1, mengakhiri rekursi.

Ini rumit dan samar, tetapi semuanya bergetar pada saat run-time, dan kunci untuk kerjanya adalah "eksekusi yang ditunda", dan pemecahan rekursi untuk menjangkau dua fungsi. Batin F dilewatkan sebagai argumen , untuk dipanggil dalam iterasi berikutnya, hanya jika perlu .

Saya telah mengangkat ini dari http://www.mail-archive.com/[email protected]/msg02716.html yang merupakan penjelasan yang saya tulis beberapa tahun yang lalu.

Saya akan menggunakan JavaScript dalam contoh ini, tetapi banyak bahasa lain juga akan berfungsi.

Tujuan kami adalah untuk dapat menulis fungsi rekursif dari 1 variabel menggunakan hanya fungsi 1 variabel dan tidak ada tugas, mendefinisikan sesuatu berdasarkan nama, dll. (Mengapa ini adalah tujuan kami adalah pertanyaan lain, mari kita anggap ini sebagai tantangan yang kami diberikan.) Sepertinya tidak mungkin, ya? Sebagai contoh, mari kita terapkan faktorial.

Nah langkah 1 adalah mengatakan bahwa kita bisa melakukan ini dengan mudah jika kita sedikit curang. Menggunakan fungsi 2 variabel dan tugas, kita setidaknya bisa menghindari harus menggunakan tugas untuk mengatur rekursi.

// 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
);

Sekarang mari kita lihat apakah kita bisa menipu lebih sedikit. Yah pertama-tama kita menggunakan tugas, tetapi kita tidak perlu. Kita cukup menulis X dan Y sebaris.

// 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
);

Tapi kami menggunakan fungsi 2 variabel untuk mendapatkan fungsi 1 variabel. Bisakah kita memperbaikinya? Nah pria yang cerdas dengan nama Haskell Curry memiliki trik yang rapi, jika Anda memiliki fungsi urutan yang lebih tinggi maka Anda hanya perlu fungsi 1 variabel. Buktinya adalah bahwa Anda dapat memperoleh dari fungsi 2 (atau lebih dalam kasus umum) variabel menjadi 1 variabel dengan transformasi teks murni mekanis seperti ini:

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

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

di mana ... tetap persis sama. (Trik ini disebut "currying" setelah penemunya. Bahasa Haskell juga bernama untuk Haskell Curry. File yang di bawah trivia tidak berguna.) Sekarang hanya menerapkan transformasi ini di mana-mana dan kami mendapatkan versi final kami.

// 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
);

Jangan ragu untuk mencobanya. waspada () yang kembali, ikat ke tombol, apa pun. Kode itu menghitung faktorial, secara rekursif, tanpa menggunakan penugasan, deklarasi, atau fungsi 2 variabel. (Tetapi mencoba melacak cara kerjanya kemungkinan membuat kepala Anda berputar. Dan menyerahkannya, tanpa derivasi, hanya sedikit diformat ulang akan menghasilkan kode yang pasti membingungkan dan membingungkan.)

Anda dapat mengganti 4 baris yang secara rekursif mendefinisikan faktorial dengan fungsi rekursif lain yang Anda inginkan.

Saya ingin tahu apakah ada gunanya mencoba membangun ini dari bawah ke atas. Ayo lihat. Berikut ini adalah fungsi faktorial rekursif dasar:

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

Mari kita refactor dan membuat fungsi baru factyang mengembalikan fungsi komputasi faktorial anonim alih-alih melakukan perhitungan itu sendiri:

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

var factorial = fact();

Itu agak aneh, tetapi tidak ada yang salah dengan itu. Kami hanya membuat fungsi faktorial baru di setiap langkah.

Rekursi pada tahap ini masih cukup eksplisit. The factFungsi perlu menyadari dari nama sendiri. Mari kita parameterkan panggilan rekursif:

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

Itu hebat, tetapi recursermasih perlu tahu namanya sendiri. Mari kita parameterkan juga:

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

var factorial = recurser(recurser);

Sekarang, alih-alih menelepon recurser(recurser)secara langsung, mari kita buat fungsi pembungkus yang mengembalikan hasilnya:

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

var factorial = Y();

Kita sekarang bisa menyingkirkan recursernama itu sama sekali; itu hanya argumen untuk fungsi dalam Y, yang dapat diganti dengan fungsi itu sendiri:

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

var factorial = Y();

Satu-satunya nama eksternal masih dirujuk adalah fact, tetapi harus jelas sekarang bahwa itu dengan mudah parameter, juga menciptakan solusi lengkap, generik,:

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);
    };
});

Sebagian besar jawaban atas menggambarkan apa yang Y-Combinator adalah tetapi tidak apa itu untuk .

Combinator titik tetap digunakan untuk menunjukkan bahwa kalkulus lambda sudah selesai . Ini adalah hasil yang sangat penting dalam teori komputasi dan memberikan landasan teoritis untuk pemrograman fungsional .

Mempelajari kombinator titik tetap juga membantu saya benar-benar memahami pemrograman fungsional. Saya tidak pernah menemukan gunanya bagi mereka dalam pemrograman yang sebenarnya.

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

Sunting : Saya belajar banyak dari melihat kode, tetapi yang ini agak sulit untuk ditelan tanpa latar belakang - maaf tentang itu. Dengan pengetahuan umum yang disajikan oleh jawaban lain, Anda dapat mulai memilah apa yang terjadi.

Fungsi Y adalah "y-combinator". Sekarang lihat var factorialgaris di mana Y digunakan. Perhatikan bahwa Anda meneruskan fungsi ke sana yang memiliki parameter (dalam contoh ini, recurse) yang juga digunakan nanti di fungsi dalam. Nama parameter pada dasarnya menjadi nama fungsi dalam yang memungkinkannya untuk melakukan panggilan rekursif (karena digunakan recurse()dalam definisi itu.) Y-kombinator melakukan keajaiban dalam mengaitkan fungsi dalam yang anonim dengan nama parameter fungsi yang diteruskan ke Y.

Untuk penjelasan lengkap tentang bagaimana Y melakukan sihir, lihat artikel yang terhubung (bukan oleh saya btw.)

Untuk programmer yang belum menemukan pemrograman fungsional secara mendalam, dan tidak peduli untuk memulainya sekarang, tetapi sedikit ingin tahu:

Kombinator Y adalah rumus yang memungkinkan Anda menerapkan rekursi dalam situasi di mana fungsi tidak dapat memiliki nama tetapi dapat diedarkan sebagai argumen, digunakan sebagai nilai pengembalian, dan didefinisikan dalam fungsi lainnya.

Ia bekerja dengan melewatkan fungsi itu sendiri sebagai argumen, sehingga bisa memanggil dirinya sendiri.

Ini adalah bagian dari kalkulus lambda, yang benar-benar matematika tetapi secara efektif merupakan bahasa pemrograman, dan sangat mendasar bagi ilmu komputer dan terutama untuk pemrograman fungsional.

Nilai praktis sehari-hari dari penggabung Y terbatas, karena bahasa pemrograman cenderung memberi Anda fungsi.

Jika Anda perlu mengidentifikasinya di barisan polisi, sepertinya ini:

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

Anda biasanya dapat menemukannya karena diulang (λx.f (x x)).

The λsimbol huruf Yunani lambda, yang memberikan lambda kalkulus namanya, dan ada banyak (λx.t)hal gaya karena itulah yang lambda kalkulus terlihat seperti.

Rekursi anonim

Combinator titik tetap adalah fungsi tingkat tinggi fixyang menurut definisi memenuhi kesetaraan

forall f.  fix f  =  f (fix f)

fix fmerupakan solusi xuntuk persamaan titik tetap

               x  =  f x

Faktorial dari bilangan alami dapat dibuktikan dengan

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

Menggunakan fix, bukti konstruktif sewenang-wenang atas fungsi-fungsi umum / μ-rekursif dapat diturunkan tanpa referensialitas diri yang tidak simultan.

fact n = (fix fact') n

dimana

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

seperti yang

   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

Ini bukti resmi itu

fact 3  =  6

secara metodis menggunakan kesetaraan combinator titik tetap untuk penulisan ulang

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

Kalkulus Lambda

The untyped lambda kalkulus formalisme terdiri dalam tata bahasa bebas konteks

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

di mana vrentang variabel, bersama dengan aturan pengurangan beta dan eta

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

Pengurangan beta menggantikan semua kemunculan variabel bebas xdalam tubuh abstraksi ("fungsi") Bdengan ekspresi ("argumen") E. Reduksi Eta menghilangkan abstraksi yang berlebihan. Kadang-kadang dihilangkan dari formalisme. Sebuah tereduksi ekspresi, yang tidak ada aturan pengurangan berlaku, dalam yang normal atau bentuk kanonik .

λ x y. E

adalah singkatan

λ x. λ y. E

(aneka ragam abstraksi),

E F G

adalah singkatan

(E F) G

(aplikasi-asosiasi kiri),

λ x. x

dan

λ y. y

adalah alpha-setara .

Abstraksi dan aplikasi adalah dua-satunya "bahasa primitif" dari kalkulus lambda, tetapi mereka memungkinkan pengkodean data kompleks kompleks dan operasi.

Angka-angka Gereja adalah pengkodean bilangan alami yang mirip dengan alami-aksiomatik Peano.

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

Bukti formal itu

1 + 2  =  3

menggunakan aturan penulisan ulang reduksi 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

Combinators

Dalam kalkulus lambda, kombinator adalah abstraksi yang tidak mengandung variabel bebas. Paling sederhana I:, penggabung identitas

λ x. x

isomorfik dengan fungsi identitas

id x = x

Combinator seperti itu adalah operator primitif dari calculin combinator seperti sistem SKI.

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

Pengurangan beta tidak sangat normal ; tidak semua ekspresi yang dapat direduksi, “redexes”, konvergen ke bentuk normal di bawah reduksi beta. Contoh sederhana adalah aplikasi divergen ωkombinator omega

λ x. x x

untuk dirinya sendiri:

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

Pengurangan subekspresi paling kiri ("kepala") diprioritaskan. Pesanan aplikatif menormalkan argumen sebelum substitusi, pesanan normal tidak. Kedua strategi ini analog dengan evaluasi yang bersemangat, misalnya C, dan evaluasi malas, misalnya Haskell.

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

menyimpang di bawah pengurangan beta aplikasi-order bersemangat

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

karena dalam semantik yang ketat

forall f.  f _|_  =  _|_

tetapi konvergen di bawah reduksi beta normal-order malas

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

Jika ekspresi memiliki bentuk normal, reduksi orde normal beta akan menemukannya.

Y

Properti penting dari Y combinator titik tetap

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

diberikan oleh

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

Kesetaraan

Y g  =  g (Y g)

isomorfik untuk

fix f  =  f (fix f)

Kalkulus lambda yang tidak diketik dapat menyandikan bukti konstruktif sewenang-wenang atas fungsi umum / μ-rekursif.

 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

(Multiplikasi tertunda, pertemuan)

Untuk kalkulus lambda Gereja yang tidak diketik, telah terbukti ada tak terhingga jumlah tak terhitung dari kombinator titik tetap 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))
  . . .

Pengurangan beta orde normal membuat kalkulus lambda tanpa tulisan yang tidak dibatasi menjadi sistem penulisan ulang Turing-complete.

Di Haskell, kombinator titik tetap dapat diterapkan secara elegan

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

Kemalasan Haskell menjadi normal sebelum semua subekspresi dievaluasi.

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

• David Turner: Tesis dan Pemrograman Fungsional Gereja
• Gereja Alonzo: Masalah yang Tidak Dapat Dipecahkan dari Teori Angka Dasar
• Kalkulus Lambda
• Teorema Gereja – Rosser

Jawaban lain memberikan jawaban yang cukup ringkas untuk ini, tanpa satu fakta penting: Anda tidak perlu menerapkan kombinator titik tetap dalam bahasa praktis apa pun dengan cara berbelit-belit ini dan melakukan hal itu tidak memiliki tujuan praktis (kecuali "lihat, saya tahu apa kombinator Y adalah"). Ini adalah konsep teoretis yang penting, tetapi memiliki sedikit nilai praktis.

Berikut ini adalah implementasi JavaScript dari Y-Combinator dan fungsi faktorial (dari artikel Douglas Crockford, tersedia di: 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);

Y-Combinator adalah nama lain untuk kapasitor fluks.

Saya telah menulis semacam "panduan idiot" kepada Y-Combinator di Clojure dan Skema untuk membantu saya memahami hal itu. Mereka dipengaruhi oleh materi dalam "The Little Schemer"

Dalam Skema: https://gist.github.com/z5h/238891

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

Kedua tutorial adalah kode yang diselingi dengan komentar dan harus dipotong & dapat ditempel ke editor favorit Anda.

Sebagai pemula untuk kombinator, saya menemukan artikel Mike Vanier (terima kasih Nicholas Mancuso) sangat membantu. Saya ingin menulis ringkasan, selain mendokumentasikan pemahaman saya, jika bisa membantu beberapa orang lain saya akan sangat senang.

Dari Crappy ke Less Crappy

Menggunakan faktorial sebagai contoh, kami menggunakan almost-factorialfungsi berikut untuk menghitung faktorial angka x:

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

Dalam pseudo-code di atas, almost-factorialtake in function fand number x( almost-factorialis curried, sehingga dapat dilihat sebagai fungsi take fdan mengembalikan fungsi 1-arity).

Ketika almost-factorialmenghitung faktorial x, ia mendelegasikan perhitungan faktorial untuk x - 1berfungsi fdan mengakumulasikan hasil itu dengan x(dalam hal ini, mengalikan hasil dari (x - 1) dengan x).

Hal ini dapat dilihat sebagai almost-factorialmengambil dalam versi jelek dari fungsi faktorial (yang hanya dapat menghitung sampai angka x - 1) dan mengembalikan versi faktorial yang kurang jelek (yang menghitung sampai angka x). Seperti dalam formulir ini:

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

Jika kita berulang kali melewatkan versi faktorial yang kurang jelekalmost-factorial , kita akhirnya akan mendapatkan fungsi faktorial yang kita inginkan f. Di mana itu dapat dianggap sebagai:

almost-factorial f = f

Titik perbaikan

Fakta yang almost-factorial f = fberarti fadalah titik perbaikan fungsi almost-factorial.

Ini adalah cara yang sangat menarik untuk melihat hubungan fungsi-fungsi di atas dan itu adalah momen aha bagi saya. (harap baca posting Mike tentang titik perbaikan jika Anda belum)

Tiga fungsi

Untuk menggeneralisasi, kami memiliki non-rekursif fungsi fn(seperti kami hampir-faktorial), kita memiliki nya fix-titik fungsi fr(seperti f kami), lalu apa Yyang dilakukannya adalah ketika Anda memberikan Y fn, Ymengembalikan fungsi fix-titik fn.

Jadi dalam ringkasan (disederhanakan dengan asumsi frhanya membutuhkan satu parameter; xberdegenerasi ke x - 1, x - 2... dalam rekursi):

• Kita mendefinisikan perhitungan inti sebagai fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), ini adalah hampir-berguna fungsi - meskipun kita tidak dapat menggunakanfnsecara langsung dix, itu akan berguna segera. Non-rekursif inifnmenggunakan fungsifruntuk menghitung hasilnya
• fn fr = fr, fradalah titik perbaikan dari fn, fradalah berguna funciton, kita dapat menggunakanfrpadaxuntuk mendapatkan hasil kami
• Y fn = fr, Ymengembalikan titik perbaikan suatu fungsi, mengubah fungsi Y kami yang hampir berguna fungsi fnmenjadi berguna fr

Berasal Y(tidak termasuk)

Saya akan melewatkan derivasi Ydan pergi ke pemahaman Y. Posting Mike Vainer memiliki banyak detail.

Bentuk dari Y

Ydidefinisikan sebagai (dalam kalkulus lambda format ):

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

Jika kita mengganti variabel sdi sebelah kiri fungsi, kita dapatkan

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

Jadi memang, hasil dari (Y f) adalah titik perbaikan dari f.

Kenapa (Y f) berhasil?

Bergantung pada tanda tangan f, (Y f)dapat menjadi fungsi dari arity apa pun, untuk menyederhanakan, mari kita asumsikan (Y f)hanya mengambil satu parameter, seperti fungsi faktorial kami.

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

sejak itu fn fr = fr, kami melanjutkan

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

perhitungan rekursif berakhir ketika yang paling dalam (fn fr 1)adalah kasus dasar dan fntidak digunakan frdalam perhitungan.

Melihat Ylagi:

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

Begitu

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

Bagi saya, bagian magis dari pengaturan ini adalah:

• fndan frsaling tergantung satu sama lain: fr'membungkus' fndi dalam, setiap kali frdigunakan untuk menghitung x, itu 'memunculkan' ('mengangkat'?) fndan mendelegasikan perhitungan itu fn(lewat sendiri frdan x); di sisi lain, fntergantung frdan digunakan fruntuk menghitung hasil dari masalah yang lebih kecil x-1.
• Pada saat frdigunakan untuk mendefinisikan fn(saat fndigunakan frdalam operasinya), yang sebenarnya frbelum didefinisikan.
• Itu fnyang mendefinisikan logika bisnis nyata. Berdasarkan fn, Ymenciptakan fr- fungsi pembantu dalam bentuk tertentu - untuk memfasilitasi perhitungan fnsecara rekursif .

Itu membantu saya memahami Y cara ini saat ini, semoga membantu.

BTW, saya juga menemukan buku Pengantar Pemrograman Fungsional Melalui Lambda Calculus sangat baik, saya hanya bagian dari itu dan fakta bahwa saya tidak bisa mendapatkan kepala saya di Ydalam buku membawa saya ke posting ini.

Berikut adalah jawaban untuk pertanyaan asli , yang disusun dari artikel (yang bernilai layak dibaca) yang disebutkan dalam jawaban oleh Nicholas Mancuso , serta jawaban lain:

Apa itu Y-combinator?

Y-combinator adalah "fungsional" (atau fungsi tingkat tinggi - fungsi yang beroperasi pada fungsi lain) yang mengambil argumen tunggal, yang merupakan fungsi yang tidak rekursif, dan mengembalikan versi fungsi yang rekursif.

Agak rekursif =), tetapi definisi yang lebih mendalam:

Combinator - hanyalah ekspresi lambda tanpa variabel bebas.
Variabel bebas - adalah variabel yang bukan variabel terikat.
Bound variable - variabel yang terkandung di dalam tubuh ekspresi lambda yang memiliki nama variabel sebagai salah satu argumennya.

Cara lain untuk berpikir tentang ini adalah bahwa kombinator adalah ekspresi lambda, di mana Anda dapat mengganti nama kombinator dengan definisi di mana-mana ia ditemukan dan memiliki semuanya masih berfungsi (Anda akan masuk ke loop tak terbatas jika kombinator akan mengandung referensi untuk dirinya sendiri, di dalam tubuh lambda).

Y-combinator adalah combinator titik tetap.

Titik tetap dari suatu fungsi adalah elemen dari domain fungsi yang dipetakan ke dirinya sendiri oleh fungsi.
Artinya, cadalah titik tetap dari fungsi f(x)jika f(c) = c
Ini berartif(f(...f(c)...)) = fn(c) = c

Bagaimana cara kerja kombinator?

Contoh di bawah ini menganggap pengetikan kuat + dinamis :

La-combinator Y (normal-order):
Definisi ini berlaku untuk bahasa dengan evaluasi lazy (juga: ditunda, sesuai kebutuhan) - strategi evaluasi yang menunda evaluasi ekspresi hingga nilainya diperlukan.

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

Ini artinya, untuk fungsi yang diberikan f(yang merupakan fungsi non-rekursif), fungsi rekursif yang sesuai dapat diperoleh terlebih dahulu dengan menghitung λx.f(x x), dan kemudian menerapkan ekspresi lambda ini ke dirinya sendiri.

Ketat (aplikatif-order) Y-combinator:
Definisi ini berlaku untuk bahasa dengan evaluasi ketat (juga: bersemangat, serakah) - strategi evaluasi di mana ekspresi dievaluasi segera setelah terikat pada variabel.

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

Sama seperti malas di alamnya, ia hanya memiliki λpembungkus tambahan untuk menunda evaluasi tubuh lambda. Saya telah mengajukan pertanyaan lain , yang agak terkait dengan topik ini.

Apa yang baik untuk mereka?

Dicuri dipinjam dari jawaban oleh Chris Ammerman : Y-combinator menggeneralisasi rekursi, mengabstraksikan implementasinya, dan dengan demikian memisahkannya dari kerja sebenarnya dari fungsi yang dimaksud.

Meskipun, Y-combinator memiliki beberapa aplikasi praktis, itu terutama konsep teoretis, pemahaman yang akan memperluas visi Anda secara keseluruhan dan, kemungkinan, akan meningkatkan keterampilan analitis dan pengembang Anda.

Apakah mereka berguna dalam bahasa prosedural?

Seperti yang dikatakan oleh Mike Vanier : dimungkinkan untuk mendefinisikan kombinator Y dalam banyak bahasa yang diketik secara statis, tetapi (setidaknya dalam contoh yang saya lihat) definisi seperti itu biasanya memerlukan beberapa jenis peretasan yang tidak jelas, karena kombinator Y sendiri tidak t memiliki tipe statis langsung. Itu di luar cakupan artikel ini, jadi saya tidak akan menyebutkannya lebih lanjut

Dan seperti yang disebutkan oleh Chris Ammerman : sebagian besar bahasa prosedural memiliki pengetikan statis.

Jadi jawab yang ini - tidak juga.

Y-combinator mengimplementasikan rekursi anonim. Jadi, bukannya

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

Anda dapat melakukan

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

tentu saja, y-combinator hanya berfungsi dalam bahasa panggilan-dengan-nama. Jika Anda ingin menggunakan ini dalam bahasa panggilan-menurut-nilai normal apa pun, maka Anda akan memerlukan z-combinator terkait (y-combinator akan berbeda / infinite-loop).

Combinator titik tetap (atau operator titik tetap) adalah fungsi tingkat tinggi yang menghitung titik tetap fungsi lainnya. Operasi ini relevan dalam teori bahasa pemrograman karena memungkinkan implementasi rekursi dalam bentuk aturan penulisan ulang, tanpa dukungan eksplisit dari mesin runtime bahasa. (src Wikipedia)

Operator ini dapat menyederhanakan hidup Anda:

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

Maka Anda menghindari fungsi ekstra:

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

Akhirnya, Anda menelepon fac(5).

Saya pikir cara terbaik untuk menjawab ini adalah dengan memilih bahasa, seperti 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));
    }
}

Sekarang tulis ulang sehingga tidak menggunakan nama fungsi di dalam fungsi, tetapi masih menyebutnya secara rekursif.

Satu-satunya tempat nama fungsi factorialharus dilihat adalah di situs panggilan.

Petunjuk: Anda tidak bisa menggunakan nama fungsi, tetapi Anda bisa menggunakan nama parameter.

Kerjakan masalahnya. Jangan mencarinya. Setelah Anda menyelesaikannya, Anda akan memahami masalah apa yang dipecahkan oleh kombinator-y.