发布网友
发布时间：2024-10-21 08:37
共1个回答
热心网友
时间：2024-11-16 19:48
lambda演算关注的是一类称为lambda项的对象。这些对象可以是简单的变量vλv.E1(E1 E2)，其中v是取自预定义变量集合的变量名字，而E1和E2是lambda项。抽象是形如λv.E1的项，其中v是形式参数，E1是主体。应用则表示函数调用，形如(E1 E2)。
抽象表示函数，将参数应用于形式参数v，并计算主体E1的结果。应用则建模函数调用，计算代表E1函数的函数，带有E2作为参数的结果。如果E1是一个抽象，则该项可以被归约，参数E2可以替代E1主体中形式参数的位置，结果是一个新的lambda项。如果lambda项不包含形如(λv.E1 E2)的子项，则它不能被归约，被称为范式。
表达式E[v := a]表示接受项E，并将v的所有自由出现替换为a的结果。因此，我们有(λv.E a) => E[v := a]。应用是左结合的，可以简写为(a b c d ... z)。
归约的定义旨在捕捉所有数学函数的本质行为。例如，计算数的平方的函数可以表示为x*x。插入特定参数，如3，可以得到3的平方是3*3。计算表达式3*3的结果依赖于我们对乘法和数3的了解。任何计算都可以表示为适当基本参数上适当函数计算的复合。在lambda演算中，3和*等概念不需要额外定义基本运算符或常量。
lambda演算在计算性上等价于任何其他计算模型，包括图灵机。邱奇-图灵论题表明这些模型可以表达任何可能的计算。
令人惊讶的是，只使用基于对项中变量的简单文字替换的函数抽象和应用的概念，lambda演算可以表达任何可想象的计算。更令人惊奇的是，抽象甚至不是必需的。组合子逻辑等价于lambda演算的计算模型，它不需要抽象。
组合子逻辑是 Moses Schönfinkel 和 哈斯凯尔·加里 介入的一种符号系统，用来消除数理逻辑中对变量的需要。它最近在计算机科学中被用做计算的理论模型和设计函数式编程语言的基础。它所基于的组合子是只使用函数应用或早先定义的组合子来定义从它们的参数得出的结果的高阶函数。
Copyright © 2019-2022 51dongshi.com 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
