提问人：Jason 提问时间：10/3/2023 最后编辑：WyckJason 更新时间：10/3/2023 访问量：38
Valid Lambda Expressions [已关闭]
Valid Lambda Expressions [closed]
问：
关于lambda表达式的有效性，我有两个问题。
首先，变量本身是否是有效的 lambda 表达式（例如：λx）
其次，以这两个 lambda 表达式（λx.fxya 和 λz.fxya）为例。除了有界变量不同之外，它们是相同的。这会影响其有效性吗？
另外，如果这些都有效，有没有办法查看一些无效的 lambda 表达式，以便我可以了解有效和无效表达式的外观？
答：
1赞
Silvio Mayolo
10/3/2023
#1
这取决于你所说的有效是什么意思。让我们从“句法有效”开始。有效 lambda 表达式的定义是归纳法的。
- 任何术语本身都是有效的 lambda 表达式。这些是我们语言的原子，出于我们的目的，我们只说所有的小写字母都是有效的术语。但实际上，只要你保持一致，你的条款可以是你选择的任何条款。
- 如果 和 是两个有效的 lambda 表达式，则 也是 。我们将其称为 to 的应用。
αβα βαβ - 如果是某个术语（如上定义）并且是任何 lambda 表达式，则为有效的 lambda 表达式。我们称之为 over 的抽象。
tαλt. ααt
根据这个定义，是一个有效的 lambda 表达式，因为它只是一个术语。如此，也是。，就其本身而言，并非如此。它看起来像一个抽象的开始，但我们从未完成它，所以它只是一个无意义的字母序列。但是，它本身就是一个表达式，也是 .eλf. f xa b c d e fλ xxλx. x
根据这个定义，和都是 lambda 表达式。具体来说，它们是术语的几种应用的抽象。λx. f x y aλz. f x y a
现在，出于多种目的，我们还希望 lambda 表达式没有自由变量。自由变量是出现在它的任何抽象绑定之外的变量。自由变量的对立面是绑定变量。所以在 中，是绑定的（由 lambda 抽象），而 、 和 是自由的。在 中，所有 、 、 和 都是免费的。拥有未使用的抽象是完全可以接受的。λx. f x y axfyaλz. f x y afxyaz
评论