Haskell“源减少”

Question

我正在复习即将到来的 Haskell 考试，但我不明白过去试卷上的一个问题。 Google 出现 没什么用

fst(x, y) = x
square i = i * i

i) 源reduce，使用Haskells惰性求值，表达式：

fst(square(3+4), square 8)

ii) 源归约，使用严格求值，相同的表达式

iii) 说明惰性求值的一项优点和严格求值的一项优点

我不明白什么是源归约？

Answer 1

归约是 lambda 演算中的一个术语，它涉及一种语义保留转换，即用等效术语替换一个术语。对于您给出的示例，最重要的简化是

• 用其定义替换名称（用 equals 替换 equals 的实例）。
• 函数应用程序的 Beta 缩减。

Beta 约简是 lambda 演算的基本规则，在像 Haskell 这样的纯粹、惰性语言中，它总是保留语义。 beta 规则是这样的：

(\x. e) m

可以用 e 替换，用 m 替换 x。 （替换必须避免在 m 中“捕获”x 的自由实例。）

您的讲师很可能希望您按如下方式组合归约：

1. 找到一个函数应用程序，其中正在应用的函数是一个名称。
2. 将名称替换为其定义，这将是 lambda 抽象。
3. Beta-减少应用程序。
4. 一步完成这一切。

请注意，您经常可以选择减少哪个应用程序；例如，在您给出的术语中，有两个 square 应用程序和一个 fst 应用程序可以通过这种方式减少。 （+的应用也可以减少，但是涉及常量的减少需要不同的规则。）

从问题中我看到你的老师希望你重复减少每个术语，直到它达到正常形式并且你的讲师希望您展示您对不同减少策略的理解。 “源缩减”中的“源”一词是多余的；缩减意味着在某些语言中对源术语进行操作。我会将问题表述如下：

• 使用与 Haskell 的惰性求值相对应的归约策略，将以下表达式归约为弱头范式。显示归约序列中的每个步骤。

• 使用与严格函数语言中的求值相对应的归约策略，将以下表达式归约为 head 范式。

  使用与严格函数语言中的求值相对应的归约策略

我可能会选择不那么含糊其辞，只说出减少策略：按需求减少呼叫策略和按价值呼叫减少策略。

Answer 2

从问题的结构来看，它可能只是意味着“手动评估表达式”，例如

head (map primeTest (enumFromTo 1000 2000))

在惰性评估中（仅在需要时评估），

  head (map primeTest (enumFromTo 1000 2000))
= head (map primeTest (1000 : enumFromTo 1001 2000))
= head (primeTest 1000 : map primeTest (enumFromTo 1001 2000))
= primeTest 1000
= False

在严格评估中（首先评估所有内容） ）评估

  head (map primeTest (enumFromTo 1000 2000))
= head (map primeTest (1000 : enumFromTo 1001 2000))
= ...
= head (map primeTest [1000, 1001, ..., 2000])
= head (primeTest 1000 : map primeTest [1001, 1002, ..., 2000])
= head (False : map primeTest [1001, 1002, ..., 2000])
= ...
= head [False, False, ..., False]
= False

我能找到的唯一相关的地方是 http:// www.cs.bham.ac.uk/internal/modules/2009/11582.html 其中“源代码缩减”被列为“编程技术”。 (O_O)