Haskell的“源码简化”

Question

我正在为即将到来的Haskell考试做准备，但是我不理解一道过去试卷上的问题。谷歌搜索没有有用的结果

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

i）使用Haskell的惰性求值，简化以下表达式：

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

ii) 使用严格求值的方式减少源代码，使相同的表达式

iii) 惰性求值的优点和严格求值的优点各列举一个

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

- Martin

Answer 1

归约是来自于Lambda演算的一个术语，它包括一种保留语义的转换，将一个术语替换为等价的术语。对于您提供的示例，最重要的归约类型为：

• 用定义替换名称（将等效项替换为等效项的实例）。
• 函数应用的Beta归约。

Beta归约是Lambda演算中的基本规则，在类似Haskell这样的纯惰性语言中，它始终保留语义。Beta规则是指：

(\x. e) m

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

很可能你的讲师希望你按以下方式组合规约：

1. 查找函数应用程序，其中应用的函数是一个名称。 2. 用其定义（一个 lambda 抽象）替换该名称。 3. 对应用程序进行 beta 规约。 4. 执行以上所有步骤。

请注意，通常有关于哪个应用程序要规约的选择；例如，在您给出的表达式中，有两个 square 应用程序可以按此方式缩减，并且有一个 fst 应用程序可以按此方式缩减。（+ 的应用程序也可以被缩减，但包括常量的缩减需要不同的规则。）

从我看到的问题中，您的讲师希望您反复缩减每个术语直到达到标准形式，并且您的讲师希望您展示对不同规约策略的理解。 “源”一词在“源规约”中是多余的；规约意味着在某种语言中操纵源术语。我会这样来表述问题：

1. 使用对应于 Haskell 惰性评估的规约策略将以下表达式缩减为弱头标准形式。显示每个缩减步骤。 2. 使用与严格功能语言中的求值相对应的规约策略将以下表达式缩减为头标准形式。

我可能会选择更加明确地命名规约策略：call-by-need 规约策略和 call-by-value 规约策略。

- Norman Ramsey

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)

- kennytm

---

我希望他在论文中直接说出来，“评估这个”会更有意义！ - Martin

你找到的笔记：我在伯明翰学习计算机科学，这些是我所学模块的笔记。我喜欢那些胡说八道的讲师。 - Martin