Haskell

Question

我有一个作业要编写一个 Haskell 程序，该程序能够将 De Bruijn 项转换为 Lambda 项，并将 Lambda 项转换为 De Bruijn 项，并检查这些项是否 'closed'.

我不是在找人替我做这个作业，但如有任何帮助，我们将不胜感激！我什至不知道如何开始使用它。

所以，我最大的问题是：De Bruijn 项和 Lambda 项有什么区别？我了解变量 'closed' 的含义，但我如何在 Haskell 中检查它？

如能提供任何其他帮助，我们将不胜感激。

这是完整的作业：

The (usual) lambda terms are defined as the data type:
data Term = Var Int | Lam Int Term | App Term Term deriving (Eq, Show, Read)
where variables are represented as integers. A term is called closed if for every i in Var i there's a term of the from Lam i <subterm> on the path from it to the root, providing it a binding.

De Bruijn terms are defined as the data type:
data BTerm =BVar Int | BLam BTerm | BApp BTerm BTerm deriving (Eq,  Show, Read)
Write a Haskell function db2lam that transforms a de Bruijn term into a lambda term. Write a Haskell function lam2db that transforms a lambda term into a Bruijn term.

Write a function isClosed that tests if a lambda term is closed. Write a function isClosed that tests if a de Bruijn term is closed.

Chose one of the following two subjects:

a) Implement normal order beta reduction for de Bruijn terms b) Implement normal order beta reduction for (the usual) lambda terms

非常感谢您的任何帮助（无论大小）！我正处于学习 Haskell 的早期阶段，很抱歉我不确定！这个作业现在让我头疼。

Answer 1

带有 De Bruijn index 的变量指的是距离它很多步的 lambda。最简单的例子就是BLam (BVar 0)，就是恒等函数。（我喜欢从 0 skipped lambda 开始计数，其他作者从 1st lambda 开始计数。）变量 BVar 0 由中间没有 lambda 的 lambda。

通常的 lambda 术语中的变量指的是最接近的同名 lambda。最简单的例子就是恒等函数Lam 1 (Var 1)，可以写成我们想要的任何变量名； Lam 2 (Var 2), Lam 3 (Var 3), ... 都是相同的恒等函数。通常的 lambda 术语中的 lambda 需要知道它们绑定的变量的名称。 De Bruijn 索引术语中的 lambda 不需要变量名，它们总是开始绑定变量 BVar 0.

Answer 2

本质上，您的作业要求您探索 "named" 和 "nameless" lambda 演算实现之间的区别。通常，当我们作为人类编写 lambda 项时，我们会使用命名变量来编写它们，例如

(\g -> (\f -> f (\x -> g x))) (\m -> m)

它的工作原理是，只要一个名字被 lambda "bound" 那么我们就可以去唯一地追踪在 lambda 主体中使用该名字的所有地方。特别是，像 "shadowing" 这样的概念变得很重要。

作为一个小切线，当我们写下命名的 lambda 项时，请务必注意它们是非唯一的。如果我们真的很迂腐，那么我们会注意到 (\x -> x) 和 (\y -> y) 是不同的术语。我们知道它们最终表示相同的 "process"，因此引入了 alpha-equivalence 的概念来处理两个相似命名的 lambda 项实际上在功能上可能相同的事实。这是命名 lambda 项是 "unique up to renaming" 的声明，其中 "renaming" 以您认为应该的方式工作。

命名 lambda 项的一个更重要的方面是 "capture via substitution"，这是天真的实现中的一个缺陷。特别是，虽然 alpha 等价表明两个术语等于重命名，但某些病态的冲突重命名可能会违反这一点，例如

(\x -> (\q -> q x))  ====>  (\x -> (\x -> x x))

虽然重命名 q -> x 似乎是允许的，但因为我更改了 q-lambda 项 "captures" 变量的方式，所以它导致我的程序的含义发生了变化。这在这里显然是病态的，但在实施替换时也很容易意外实施。

避免捕获替换通常是一件很重要的事情。当你的 LC ADT 的片段四处移动并在它们新的、替代的上下文中被解释时，它们的含义会发生变化，并且必须考虑到这种变化。也就是说，使用命名术语避免捕获替换可能代价高昂，因为必须了解整个术语的上下文才能识别哪些名称存在捕获风险。

因此，由于这两个原因，alpha 等价的需要和捕获命名术语的风险，尽管它们在人类语言中很熟悉，但并不总是最佳选择。

所以现在我们转向无名术语。你的作业要求你实现的 de Bruijn 术语是一个无名的变体。特别是，如果您查看 ADT，就会清楚地看到 BLam 不再指定哪个变量受它们约束——相反，我们被迫单独从 ADT 的结构中确定变量的含义。

特别是，规则是变量是指向绑定它们的 lambda 的指针。 BVar n 绑定到其上方 n BLam 的 lambda。所以如果我们要制作一个从有名术语到无名术语的翻译器，它们看起来像

(\x -> x)            ===>  (\ 0)
(\x -> (\q -> q x))  ===>  (\ (\ 0 1))

(\g -> (\f -> f (\x -> g x))) (\m -> m)
===>
(\ (\ 0 (\ 2 0))) (\ 0)

无名术语对于人类来说有点难以阅读，但它们有两个优点：

不再有 alpha 等效这样的东西；两个无名项在结构上相等时恰好表示相同的计算
由于变量非常系统化"named"正是由于实施捕获避免的术语结构更简单。

Answer 3

（所有家庭作业类问题的通用答案）

"This assignment is way over my head at this time."

你确定吗？你的老师布置这些作业是有原因的：它们与讲座有关。你有 99.99% 的机会可以利用你所拥有的知识来完成它们。

检查你的讲义，检查课程中给出的参考文献（也就是说，去图书馆）。我很确定 "what's the difference between a De Bruijn term and a Lambda term?" 的答案就在某处。

如果经过合理的努力还是找不到，请与同学核对，然后与助教核对，最后与老师核对。

可悲的是，SO 容忍（甚至吸引）家庭作业类型的问题（并奖励回答这些问题），原因很明显（它增加了他们的点击次数）。这对 SO（短期）有帮助，但对学生没有帮助（长期运行）。

Haskell - 将 De Bruijn 术语转换为 Lambda 术语（反之亦然）

Haskell - Convert De Bruijn terms to Lambda terms (and vice-versa)

lambda