haskell "Source reduction"

Question

我正在为即将到来的 Haskell 考试复习，但我不明白过去论文中的一个问题。谷歌出现 nothing useful

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

i) Source reduce，使用 Haskell 惰性求值，表达式:

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

ii) Source reduce，使用严格求值，同样的表达式

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

我不明白的是什么是源头减少？

Answer 1

减价是 lambda 演算中的一个术语，它涉及一种保留语义的转换，该转换将一个术语替换为一个等效术语。对于你给出的例子，最重要的减少是

用它的定义替换一个名字(用equals 替换equals 的一个实例)。

功能应用程序的 Beta 减少。

Beta-reduction 是 lambda 演算中的基本规则，在像 Haskell 这样纯粹、懒惰的语言中，它始终保留语义。测试版规则是这样说的:

(\x. e) m

可以用 e代替与 m代替 x . (替换必须避免在 x 中“捕获” m 的免费实例。)

您的讲师很可能希望您按如下方式组合减少:

查找所应用的函数是名称的函数应用程序。

用它的定义替换名称，这将是一个 lambda 抽象。

Beta-reduce 应用程序。

一步完成这一切。

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

从问题中我看到您的导师希望您 重复减少每一项，直到它达到正常形式 并且您的讲师希望您展示您对不同减少策略的理解。 “源减少”中的“源”二字是多余的； 减少意味着对某些语言中的源术语进行操作。我会按如下方式表述这些问题:

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

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

我可能会选择不那么腼腆，只命名减少策略:按需调用减少策略和按值(value)调用减少策略。