haskell - Haskell“资源缩减”

Question

我正在为即将到来的 Haskell 考试进行复习，但我不理解过去论文中的一个问题。谷歌没有发现任何有用的东西

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

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

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（替换必须避免“捕获” in 的免费实例m。）

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

1. 查找一个函数应用程序，其中应用的函数是一个名称。
2. 用它的定义替换名称，这将是一个 lambda 抽象。
3. Beta-reduce 应用程序。
4. 一步完成。

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

从这些问题中，我看到您的老师希望您重复减少每个学期，直到达到正常形式，并且您的老师希望您展示您对不同减少策略的理解。 “source reduce”中的“source”二字是多余的；简化意味着对某种语言的源术语进行操作。我会将问题表述如下：

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

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

我可能会选择不那么腼腆，只命名减少策略：按需减少策略和按价值减少策略。

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)