不动点组合子

✍ dations ◷ 2024-12-23 09:14:37 #Lambda演算,不动点,组合子逻辑

不动点组合子(英语:Fixed-point combinator,或不动点算子)是计算其他函数的一个不动点的高阶函数。

函数 f 的不动点是将函数应用在输入值 x 时,会传回与输入值相同的值,使得 f(x) = x。例如,0 和 1 是函数 f(x) = x2 的不动点,因为 02 = 0 而 12 = 1。鉴于一阶函数(在简单值比如整数上的函数)的不动点是个一阶值,高阶函数 f 的不动点是另一个函数 g 使得 f(g) = g。那么,不动点算子 fix 的定义是

使得对于任何函数 f

不动点组合子它们可以用非递归的 lambda抽象来定义,在 lambda演算中的函数都是匿名的。然而在命令式编程语言中的递归,或许限制只能以呼叫函数名称作为参数来实作。在函数式编程语言中的不动点,以 lambda抽象来定义的Y组合子为:

则允许匿名函数足够逹成递归的作用,即递归函数。应用于带有一个变量的函数,Y组合子通常不会终止。将 Y组合子应用于二或更多个变量的函数,会获得更有趣的结果。第二个变量可当作计数器或索引。由此产生的函数行为,表现出如命令式语言中一个whilefor循环。

这个组合子也是 Curry悖论的核心,演示了无型别的 lambda演算是一个不稳固的推论系统,因由 Y组合子允许一个匿名表达式来表示零或者甚至许多值,这在数理逻辑上是不一致的。

在无类型lambda演算中众所周知的(可能是最简单的)不动点组合子叫做Y组合子。它是Haskell B. Curry发现的,定义为

注意Y组合子意图用于传名求值策略,因为 (Y g)在传值设置下会发散(对于任何g)。

在数学的特定形式化中,比如无类型lambda演算和组合演算中,所有表达式都被当作高阶函数。在这些形式化中,不动点组合子的存在性意味着“所有函数都至少有一个不动点”,函数可以有多于一个不同的不动点。

在其他系统中,比如简单类型lambda演算,不能写出有良好类型(well-typed)的不动点组合子。在这些系统中对递归的任何支持都必须明确的增加到语言中。带有扩展的递归类型的简单类型lambda演算,可以写出不动点算子,“有用的”不动点算子(它的应用总是会返回)的类型将是有限制的。

例如,在Standard ML中Y组合子的传值调用变体有类型∀a.∀b.((a→b)→(a→b))→(a→b),而传名调用变体有类型∀a.(a→a)→a。传名调用(正则序)变体在应用于传值调用的语言的时候将永远循环下去 -- 所有应用Y(f)展开为f(Y(f))。按传值调用语言的要求,到f的参数将接着展开,生成f(f(Y(f)))。这个过程永远重复下去(直到系统耗尽内存),而不会实际上求值f的主体。

考虑阶乘函数(使用邱奇数)。平常的递归数学等式

可以用lambda演算把这个递归的一个“单一步骤”表达为

这里的"f"是给阶乘函数的占位参数,用于传递给自身。函数F进行求值递归公式中的一个单一步骤。应用fix算子得到

Y组合子的可以在传值调用的应用序求值中使用的变体,由普通Y组合子的部分的η-展开给出:

Y组合子用SKI-演算表达为

另一个常见不动点组合子是图灵不动点组合子(阿兰·图灵发现的):

相关

  • 时间囊时间囊是一个贮藏货物或资料用的物品,作为一个与未来的人沟通用的方法。它一般在世界博览会此类大型展览中制作并埋下,等待下一次的机缘令它们再次被发现。它们有时会无意地被
  • 宗人府宗人府是中国明清时期管理皇家宗室事务的机构。掌管皇帝九族的宗族名册,按时撰写帝王族谱,记录宗室子女嫡庶、名字、封号、世袭爵位、生死时间、婚嫁、谥号安葬的事。凡是宗室
  • ASU-57空降自走炮 苏联、 埃及、 越南、 ASU-57空降自走炮(俄文:АСУ-57 (Объект 572))是第二次世界大战后的1950年由苏联为其伞兵发展的超轻型自走炮,但由于自身体积太小而作用不大,
  • 林家圣林家圣(Lin Chia-sheng,1980年7月12日-)是一名台湾足球运动员,主要位置是前锋和左翼。林家圣以优越的爆发力及西方球员的体型获得瞩目。林家圣就读于台南市胜利国小,在1990年参加
  • 楚门-玉环半岛楚门-玉环半岛位于浙江省玉环市,是浙江省较大的半岛之一。楚门-玉环半岛是玉环市的主体,北部是雁荡山余脉,南部是原来的玉环岛。半岛原为分离的楚门半岛和玉环岛,因漩门大坝修建后
  • 石毛秀树石毛秀树(1994年9月21日-),日本足球运动员,司职中场,现效力于日本职业足球联赛球队清水心跳。石毛秀树小学时代在富士第一SSS开始接受专业足球训练,中学时代转到和清水心跳相关联的
  • 约翰·施耐德-阿曼约翰·尼古拉斯·施奈德-阿曼(德语:Johann Niklaus Schneider-Ammann;1952年2月18日-),是一名瑞士政治人物、瑞士自由民主党党员。施奈德-阿曼是伯恩州苏米斯瓦尔德一名兽医的儿子
  • 日本漫画杂志日本漫画杂志(日语:日本の漫画雑誌),主要以“读者对象”和“出版频率”分类。以“读者对像”分类,可分为:少年漫画、少女漫画、青年漫画、男性漫画、女性漫画等;以“出版频率”分类
  • 刘明让刘明让(1896年8月-1938年4月),字孟和。山东省东平县商老庄乡李桥村人。他为抗日战争期间阵亡的中国军方高级将领之一。毕业于东北讲武堂,抗战时任陆军第51军114师340旅684团上校
  • 卡尔·古斯塔夫 (伊森堡-比丁根)卡尔·古斯塔夫(Carl Gustav;1875年9月11日-1941年5月15日),出生于法兰克福。伊森堡-比丁根亲王。伊森堡-比丁根亲王阿尔弗莱德与卡斯特尔-吕登豪森鲁特迦德女伯爵的长子。1920年