减少Lambda微积分

Question

我最近一直在研究lambda计算,我对减少和替换有很多疑问.什么是alpha和beta减少？他们何时以及为何使用？

如果有人能说出有关lambda caculus的减少和替代的任何好资源,那就太好了.

Answer 1

Beta降低只是lambda演算中用于计算的主要应用规则.它通过替换应用,如下所示:

如果你有lambda术语:(\ xx)和右边的一些值:y

然后,您将所有绑定变量替换为lambda术语中(.)的右侧.绑定变量是与(.)左边的变量匹配的变量,因此在这种情况下为x.

The reduction would be of the form:
(\x.x)y    //y gets bound to all occurences of x to the right of the period
y

其中y绑定到lambda表达式中所有出现的x.这是身份功能.

Alpha"减少"通常称为alpha等价或alpha重写规则.它们声明您可以更改任何lambda术语及其绑定变量的名称,而无需更改表达式的含义.

例如,使用上面的标识函数,我们可以很容易地将lambda术语写成(\ jj).它不会改变我们的应用程序的结果,如下所示:

(\j.j)y    //y gets bound to all occurrences of j to the right of the period
y

至于学习资源:维基百科页面非常详细,但符号很重,可能需要一些好的重读.

如果你只是在寻找关于lambda演算如何工作的更好的直觉,那么大多数计算机科学系都有幻灯片.