代码之家 › 专栏 › 技术社区 › Martin

哈斯克尔“源头削减”

reduction evaluation terminology haskell

4

Martin · 技术社区 · 16 年前

我正在为即将到来的哈斯凯尔考试复习,我不懂过去试卷上的一道题。谷歌出现了 nothing useful

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

i) Source reduce,使用Haskells lazy求值,表达式:

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

iii)说明懒惰评价的一个优点和严格评价的一个优点

是源头减少?

2 回复 | 直到 13 年前

1

10

Norman Ramsey 16 年前

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

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

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

(\x. e) m

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

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

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

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

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

使用对应于Haskell的lazy求值的缩减策略,将下面的表达式缩减为弱头范式。按缩减顺序显示每个步骤。
使用与严格函数语言中的求值相对应的约简策略,将下面的表达式约简为head范式。

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

2

7

kennytm 16 年前

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

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)