Jan Willem Klop的"(LL L ...)"Y组合器如何工作？

Question

我理解Y Combinator是什么,但我不理解维基百科页面中这个"小说"组合子的例子:

 Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L)

Where:

    L = ?abcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

这是如何运作的？

Answer 1

定点组合C器的本质是C f减少到f (C f).只要这样做,你所接受的并不重要C.而不是

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

你也可以

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

基本上你需要一些形式

C t1 t2 ... tN

其中ti = C一些i和

C = \x1 x2 .. xN f. f (xi u1 u2 ... xi ... u(N-1) f)

其他条款tj并uj没有实际"使用".你可以看到Klop L有这种形式(虽然他使用的事实是所有这些ti都是L第二种xi也可以是任何其他形式xj).