Y-combinator是一种来自事物"功能"方面的计算机科学概念.大多数程序员对组合器一无所知,如果他们甚至听说过它们的话.
什么是Y-combinator？
组合器如何工作？
它们有什么用？
它们在程序语言中有用吗？
Chris Ammerm.. 285
Y-combinator是一个"功能"(对其他函数起作用的函数),当你无法从内部引用函数时,它会启用递归.在计算机科学理论中,它概括了递归,抽象了它的实现,从而将它与所讨论的函数的实际工作分开.不需要递归函数的编译时名称的好处是一种奖励.=)
这适用于支持lambda函数的语言.基于表达的lambdas本质通常意味着他们不能通过名字来引用自己.通过声明变量,引用它,然后将lambda分配给它来完成自引用循环来解决这个问题是很脆弱的.可以复制lambda变量,并重新分配原始变量,这会破坏自引用.
Y组合器在静态类型语言(通常是程序语言)中实现并且经常使用是很麻烦的,因为通常的类型限制要求在编译时知道所讨论的函数的参数的数量.这意味着必须为需要使用的任何参数计数编写y组合子.
下面是C#中Y-Combinator的使用和工作方式的示例.
使用Y组合器涉及构造递归函数的"不寻常"方式.首先,您必须将函数编写为调用预先存在的函数的代码,而不是自身:
// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);
然后将其转换为一个函数,它接受一个函数来调用,并返回一个执行此操作的函数.这称为功能,因为它需要一个函数,并执行一个操作,导致另一个函数.
// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func, Func> fact =
(recurs) =>
(x) =>
x == 0 ? 1 : x * recurs(x - 1);
现在你有一个函数,它的功能,并返回另一个功能之类的,看起来像一个因子,但不是自称,它调用传递到外部函数的参数.你如何使这成为阶乘？将内部函数传递给自己.Y-Combinator是一个具有永久名称的函数,可以引入递归.
// One-argument Y-Combinator.
public static Func Y(Func, Func> 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.
}
而不是因子调用本身,发生的是因子调用阶乘生成器(由递归调用Y-Combinator返回).并且根据t的当前值,从生成器返回的函数将再次调用生成器,使用t - 1,或者只返回1,终止递归.
它既复杂又神秘,但它在运行时都会抖动,其工作的关键是"延迟执行",以及分解两个函数的递归.内部F 作为参数传递,仅在必要时才在下一次迭代中调用.
Y-combinator是一个"功能"(对其他函数起作用的函数),当你无法从内部引用函数时,它会启用递归.在计算机科学理论中,它概括了递归,抽象了它的实现,从而将它与所讨论的函数的实际工作分开.不需要递归函数的编译时名称的好处是一种奖励.=)
这适用于支持lambda函数的语言.基于表达的lambdas本质通常意味着他们不能通过名字来引用自己.通过声明变量,引用它,然后将lambda分配给它来完成自引用循环来解决这个问题是很脆弱的.可以复制lambda变量,并重新分配原始变量,这会破坏自引用.
Y组合器在静态类型语言(通常是程序语言)中实现并且经常使用是很麻烦的,因为通常的类型限制要求在编译时知道所讨论的函数的参数的数量.这意味着必须为需要使用的任何参数计数编写y组合子.
下面是C#中Y-Combinator的使用和工作方式的示例.
使用Y组合器涉及构造递归函数的"不寻常"方式.首先,您必须将函数编写为调用预先存在的函数的代码,而不是自身:
// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);
然后将其转换为一个函数,它接受一个函数来调用,并返回一个执行此操作的函数.这称为功能,因为它需要一个函数,并执行一个操作,导致另一个函数.
// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func, Func> fact =
(recurs) =>
(x) =>
x == 0 ? 1 : x * recurs(x - 1);
现在你有一个函数,它的功能,并返回另一个功能之类的,看起来像一个因子,但不是自称,它调用传递到外部函数的参数.你如何使这成为阶乘？将内部函数传递给自己.Y-Combinator是一个具有永久名称的函数,可以引入递归.
// One-argument Y-Combinator.
public static Func Y(Func, Func> 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.
}
而不是因子调用本身,发生的是因子调用阶乘生成器(由递归调用Y-Combinator返回).并且根据t的当前值,从生成器返回的函数将再次调用生成器,使用t - 1,或者只返回1,终止递归.
它既复杂又神秘,但它在运行时都会抖动,其工作的关键是"延迟执行",以及分解两个函数的递归.内部F 作为参数传递,仅在必要时才在下一次迭代中调用.
如果你准备好长时间阅读,Mike Vanier有一个很好的解释.简而言之,它允许您使用一种本身不一定支持它的语言来实现递归.
我从http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html解除了这个问题,这是我几年前写的一个解释.
我将在此示例中使用JavaScript,但许多其他语言也可以使用.
我们的目标是能够仅使用1个变量的函数编写1变量的递归函数,没有赋值,按名称定义事物等.(为什么这是我们的目标是另一个问题,让我们把它作为我们的挑战"给了."似乎不可能,是吧？举个例子,让我们实现阶乘.
第1步就是说,如果我们作弊一点,我们就可以轻松地做到这一点.使用2个变量和赋值的函数,我们至少可以避免使用赋值来设置递归.
// 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
);
现在让我们看看我们是否可以减少欺骗.首先,我们正在使用任务,但我们不需要.我们可以直接写X和Y.
// 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
);
但是我们使用2个变量的函数来获得1个变量的函数.我们可以修复吗？一个名叫Haskell Curry的聪明人有一个巧妙的技巧,如果你有更好的高阶函数,那么你只需要1个变量的函数.证明是你可以从2(或一般情况下更多)变量的函数到1变量,并进行纯机械文本转换,如下所示:
// Original
F = function (i, j) {
...
};
F(i,j);
// Transformed
F = function (i) { return function (j) {
...
}};
F(i)(j);
哪里......保持完全相同.(这个技巧在其发明者之后被称为"currying".语言Haskell也以Haskell Curry命名.文件在无用的琐事下.)现在只需将这个转换应用到各处,我们得到我们的最终版本.
// 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
);
随意试试吧.alert()返回,将它绑定到一个按钮,无论如何.该代码以递归方式计算阶乘,而不使用2个变量的赋值,声明或函数.(但是试图追踪它是如何工作的可能会使你的头部旋转.并且在没有推导的情况下处理它,只是稍微重新格式化将导致代码肯定会让人感到困惑和混淆.)
您可以使用所需的任何其他递归函数替换递归定义阶乘的4行.
我想知道从头开始构建这个是否有任何用处.让我们来看看.这是一个基本的递归因子函数:
function factorial(n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
让我们重构并创建一个名为的新函数fact,它返回一个匿名析因计算函数,而不是执行计算本身:
function fact() {
return function(n) {
return n == 0 ? 1 : n * fact()(n - 1);
};
}
var factorial = fact();
这有点奇怪,但它并没有错.我们只是在每一步产生一个新的阶乘函数.
此阶段的递归仍然相当明确.该fact函数需要知道自己的名字.让我们参数化递归调用:
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);
这很好,但recurser仍需要知道自己的名字.我们也要参数化:
function recurser(f) {
return fact(function(x) {
return f(f)(x);
});
}
var factorial = recurser(recurser);
现在,recurser(recurser)让我们创建一个返回其结果的包装函数,而不是直接调用:
function Y() {
return (function(f) {
return f(f);
})(recurser);
}
var factorial = Y();
我们现在可以recurser完全摆脱这个名字; 它只是Y的内部函数的一个参数,可以用函数本身代替:
function Y() {
return (function(f) {
return f(f);
})(function(f) {
return fact(function(x) {
return f(f)(x);
});
});
}
var factorial = Y();
唯一仍然引用的外部名称是fact,但现在应该很清楚,这也很容易参数化,创建完整的通用解决方案:
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);
};
});
上面的大多数答案都描述了Y-combinator 是什么,但不是它的用途.
固定点组合器用于表明lambda演算是完整的.这是计算理论中非常重要的结果,为函数式编程提供了理论基础.
学习定点组合器也帮助我真正理解函数式编程.我在实际编程中从未发现它们有任何用处.
JavaScript中的 y-combinator :
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
编辑:我从查看代码中学到了很多东西,但是如果没有一些背景知识,这一点有点难以接受 - 抱歉.通过其他答案提供的一些常识,您可以开始挑选正在发生的事情.
Y函数是"y组合子".现在看一下var factorial使用Y 的行.请注意,您将一个函数传递给它,该函数具有一个参数(在此示例中recurse),该函数稍后也会在内部函数中使用.参数名称基本上成为内部函数的名称,允许它执行递归调用(因为它使用recurse()了它的定义.)y-combinator执行将其他匿名内部函数与传递给函数的函数的参数名称相关联的魔力. Y.
有关Y如何完成魔法的完整解释,请查看链接的文章(不是我的btw).
对于那些没有深入体验过函数式编程的程序员而言,现在并不关心,但是有点好奇:
Y组合子是一个公式,它允许您在函数不能具有名称但可以作为参数传递,用作返回值并在其他函数中定义的情况下实现递归.
它通过将函数作为参数传递给自身来工作,因此它可以调用自身.
它是lambda演算的一部分,它实际上是数学,但实际上是一种编程语言,对于计算机科学尤其是函数式编程来说是非常基础的.
Y组合器的日常实用价值是有限的,因为编程语言倾向于让您命名功能.
如果您需要在警察阵容中识别它,它看起来像这样:
Y =λf.(λx.f(xx))(λx.f(xx))
你可以经常发现它,因为重复(?x.f (x x)).
该?符号是希腊字母拉姆达,这给演算它的名字,并且有很多的(?x.t)风格上,因为这是演算的样子.
其他答案提供了非常简洁的答案,没有一个重要的事实:你不需要用这种复杂的方式用任何实用语言实现定点组合器,这样做没有实际意义(除了"看,我知道Y-combinator是什么)是").这是重要的理论概念,但没有什么实际价值.
定点组合器是fix根据定义满足等价关系的高阶函数
forall f. fix f = f (fix f)
fix f表示x定点方程的解
x = f x
自然数的阶乘可以通过以下方式证明
fact 0 = 1 fact n = n * fact (n - 1)
使用fix，可以得出关于通用/？递归函数的任意构造证明，而不会产生非对称的自我指称性。
fact n = (fix fact') n
哪里
fact' rec n = if n == 0
then 1
else n * rec (n - 1)
这样
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
这种形式上的证明
fact 3 = 6
有条不紊地使用定点组合器等效项进行重写
fix fact' -> fact' (fix fact')
未类型化的lambda演算形式主义在于上下文无关的语法
E ::= v Variable | ? v. E Abstraction | E E Application
其中v变量的范围，以及beta和eta减少规则
(? x. B) E -> B[x := E] Beta ? x. E x -> E if x doesn’t occur free in E Eta
Beta减少将表达式（“参数”）替换x为抽象（“函数”）主体中变量的所有自由出现。减少Eta消除了多余的抽象。有时从形式主义中将其省略。没有归约规则的不可归约表达式为正则或规范形式。BE
? x y. E
是的简写
? x. ? y. E
（抽象多元性），
E F G
是的简写
(E F) G
（应用程序左关联），
? x. x
和
? y. y
是与alpha等效的。
抽象和应用是lambda演算的两个唯一的“语言原语”，但是它们允许对任意复杂的数据和操作进行编码。
教堂数字是自然数的编码，类似于Peano-axiomatic自然数。
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
. . .
正式证明
1 + 2 = 3
使用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
在lambda演算中，组合器是不包含自由变量的抽象。最简单的：I身份组合器
? x. x
身份函数同构
id x = x
这样的组合器是像SKI系统一样的组合器结石的原始运算符。
S = ? x y z. x z (y z) K = ? x y. x I = ? x. x
Beta的减少不是很正常的；并非所有可还原的表达式“ redexes”在beta还原下都收敛为正常形式。一个简单的例子是omega ?组合器的不同应用
? x. x x
对自己：
(? x. x x) (? y. y y) = (? y. y y) (? y. y y) . . . = _|_ Bottom
优先考虑最左边子表达式（“ heads”）的减少。应用顺序在替换之前将参数标准化，而正常顺序则不会。这两种策略类似于热切评估（例如C）和惰性评估（例如Haskell）。
K (I a) (? ?) = (? k l. k) ((? i. i) a) ((? x. x x) (? y. y y))
在急切的应用顺序Beta减少下产生分歧
= (? 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)) . . . = _|_
因为严格的语义
forall f. f _|_ = _|_
但收敛于懒惰的正序beta减少
= (? l. ((? i. i) a)) ((? x. x x) (? y. y y)) = (? l. a) ((? x. x x) (? y. y y)) = a
如果表达式具有正常形式，则可以找到正常顺序的beta减少形式。
定点组合器的基本属性Y
? f. (? x. f (x x)) (? x. f (x x))
是（谁）给的
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)) . . . . . .
等价
Y g = g (Y g)
同构
fix f = f (fix f)
未类型化的lambda演算可以对通用/β递归函数上的任意构造性证明进行编码。
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
（乘法延迟，合流）
对于Churchian无类型的Lambda演算，除之外，还存在定点组合子的递归可枚举无穷大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)) . . .
正常顺序的beta减少使未扩展的未类型化lambda演算成为图灵完全重写系统。
在Haskell中，定点组合器可以轻松实现
forall f. fix f = f (fix f)
在评估所有子表达式之前，Haskell的懒惰会归一化为无穷大。
x = f x
大卫·特纳（David Turner）：丘奇的论文和函数式编程
阿隆佐·丘奇：基本数论的一个无法解决的问题
λ演算
丘奇-罗瑟定理
这是Y-Combinator和Factorial函数的JavaScript实现(来自Douglas Crockford的文章,可从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是磁通电容器的另一个名称.
我在Clojure和Scheme中为Y-Combinator写了一篇"白痴指南",以帮助自己掌握它.他们受到"The Little Schemer"中材料的影响
在Scheme中:https: //gist.github.com/z5h/238891
或Clojure:https: //gist.github.com/z5h/5102747
这两个教程都是散布着注释的代码,应该剪切并粘贴到您喜欢的编辑器中.
京公网安备 11010802040832号 | 京ICP备19059560号-6 