哈斯克尔“源头削减”

还原 是lambda演算中的一个术语,它涉及一个语义保持转换,用一个等价的术语替换一个术语。对于你给出的例子,最重要的一种缩减是

• 用名称的定义替换名称(用equals代替equals的实例)。
• 函数应用程序的Beta缩减。

Beta约简是lambda演算中的基本规则,在Haskell这样的纯惰性语言中,它始终保持语义。贝塔法则是这样的:

(\x. e) m

e 具有 m 代替 x . (替换必须避免“捕获”的自由实例 在里面 米

很有可能你的导师希望你把减量合并如下:

1. 查找要应用的函数是名称的函数应用程序。
2. 将名称替换为其定义,该定义将是lambda抽象。

注意你经常有 选择 square 其中一个 fst 以这种方式可以减少(+的应用也可以减少,但涉及常量的减少需要不同的规则。)

从这些问题中我看到你的导师希望你 反复减少每一项直到它达到一个标准形式 你的导师希望你展示你对 不同的 削减战略。 “源减”中的“源”字是多余的; 减少 方法 在某些语言中对源词的操纵。我会把问题表述如下:

• 使用对应于Haskell的lazy求值的缩减策略,将下面的表达式缩减为弱头范式。按缩减顺序显示每个步骤。

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

我可能会选择不那么害羞,只说出减少策略:按需减少策略和按价值减少策略。

从问题的结构来看 意思是“用手评估表达式”。

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 d O)