我们都知道(或者应该知道)Haskell默认是惰性的。在必须评估之前,不会评估任何内容。
不。
Haskell不是一种惰性语言。
Haskell是一种无副作用的语言,因此评估顺序并不重要。
虽然语言允许无限循环,但评估顺序并不完全无关紧要。如果不小心,可能会陷入一个死胡同,在那里你会永远评估子表达式,而不是以有限时间终止的不同评估顺序。因此,更准确地说:
Haskell实现必须以可以终止的方式评估程序,如果存在任何终止的评估顺序,则只有在每个可能的评估顺序都无法终止时,实现才会失败。
这仍然为实现提供了巨大的自由度来评估程序。
Haskell程序是一个单一的表达式,即let {所有顶级绑定} in Main.main。评估可以被理解为一系列缩减(小)步骤,这些步骤改变了表达式(表示执行程序的当前状态)。
你可以将规约步骤分为两类:那些可以被证明是必要的(在任何终止规约序列中都是必须的),以及那些不是。你可以将可以被证明是必要的规约步骤有点模糊地分为两个子类:那些“显然”必要的,以及那些需要一些非平凡的分析来证明它们是必要的。
只执行显然必要的规约步骤就是所谓的“惰性求值”。我不知道是否存在纯粹的惰性求值实现Haskell。Hugs可能是其中之一。GHC肯定不是。
GHC在编译时执行了一些不可证明必要的规约步骤;例如,即使它无法证明结果将被使用,它也会用3::Int
替换1+2::Int
。
在某些情况下,GHC也可以在运行时执行不必要的规约。例如,在生成用于评估f(x+y)
的代码时,如果x
和y
是Int
类型,并且它们的值将在运行时知道,但无法证明f
使用其参数,则没有理由在调用f
之前不计算x+y
。即使不使用参数,它也使用更少的堆空间和代码空间,可能更快。但是,我不知道GHC是否实际利用这些优化机会。
GHC绝对会在运行时执行仅通过相当复杂的跨模块分析才被证明为必要的评估步骤。这是非常普遍的,可能代表了现实程序的大部分评估。惰性评估是一种最后的备用评估策略;这不是通常发生的事情。
曾经有一个 GHC 的 "乐观评估" 分支在运行时执行了更多推测性的求值。这个分支由于其复杂性和持续的维护负担而被放弃,而不是因为它表现不佳。如果 Haskell 和 Python 或 C++ 一样流行,那么肯定会有更复杂的运行时评估策略的实现,由深口袋的公司维护。非惰性求值并不是语言的改变,而只是一种工程挑战。
规约是由顶层 I/O 驱动的,没有其他驱动
您可以通过特殊的副作用约简规则来模拟与外部世界的交互,例如:“如果当前程序的形式为 getChar >>= <expr>
,则从标准输入获取一个字符并将程序约简为应用于所获得字符的 <expr>
。”
运行时系统的整个目标是对程序进行求值,直到它具有其中一些可能产生副作用的形式,然后执行副作用,然后重复此过程,直到程序呈现出一些暗示终止的形式,例如 return ()
。
关于什么时候缩减什么,没有其他规则。只有关于什么可以缩减成什么的规则。
例如,if
表达式的唯一规则是,if True then <expr1> else <expr2>
可以缩减为 <expr1>
,if False then <expr1> else <expr2>
可以缩减为 <expr2>
,而 if <exc> then <expr1> else <expr2>
,其中 <exc>
是异常值,可以缩减为一个异常值。
如果表示程序当前状态的表达式是一个 if
表达式,那么你别无选择,只能对条件执行缩减操作,直到它变成 True
或 False
或 <exc>
,因为这是你摆脱 if
表达式并希望达到与 I/O 规则之一匹配的状态的唯一方法。但是语言规范并没有用这么多的话告诉你要这样做。
这些隐式的排序约束是强制发生评估的唯一方式。这是初学者经常感到困惑的一个原因。例如,人们有时会尝试通过编写foldl (\x y -> x `seq` x+y)
而不是foldl (+)
来使foldl
更加严格。这是行不通的,也永远不可能行得通,因为没有表达式可以使自己评估。评估只能“从上面”进行。在这方面,seq
并没有任何特殊之处。
规约无处不在
Haskell中的规约(或评估)仅在严格性点发生。[...] 我的直觉是主函数、seq / bang模式、模式匹配以及通过主函数执行的任何IO操作都是主要的严格性点[...]。
我不明白如何理解这个说法。程序的每个部分都有一定的含义,并且该含义由规约规则定义,因此规约无处不在。
为了减少函数应用
<expr1> <expr2>
,您必须评估
<expr1>
,直到它具有类似于
(\x -> <expr1'>)
或
(getChar >>=)
的形式,或者其他与规则匹配的内容。但由于某种原因,函数应用不倾向于出现在声称“强制评估”的表达式列表中,而
case
总是会出现。
您可以在Haskell维基百科的一句话中看到这种误解,该语句在另一个答案中找到:
实际上,Haskell不是纯惰性语言:例如,模式匹配通常是严格的
我不明白谁写下这句话可能会被认为是“纯惰性语言”,除非是每个程序都挂起,因为运行时从未执行任何操作。如果模式匹配是您的语言的特性,则必须在某个时候实际执行它。要执行它,您必须评估足够的scrutinee以确定它是否与模式匹配。这是原则上可能的最懒惰的匹配模式的方法。
~
前缀模式通常被程序员称为“懒惰”,但语言规范将其称为“不可反驳的”。它们的定义属性是始终匹配。由于它们总是匹配,因此您不必评估检查者以确定它们是否匹配,因此懒惰实现不会这样做。普通模式和不可反驳的模式之间的区别在于它们匹配的表达式,而不是您应该使用的评估策略。规格说明没有提到任何评估策略。
main
是一个严格性点。它被特别指定为其上下文(程序)的主要严格性点。当程序(main
的上下文)被评估时,激活了main
的严格性点。[...] Main通常由IO操作组成,这些操作也是严格性点,其上下文是main
。
我不确定这些内容是否有任何意义。
main
的深度是最大的:必须完全评估。
不,main
只需要进行“浅层次”的评估,以使I/O操作出现在顶层。 main
是整个程序,而程序并非在每次运行时都完全评估,因为不是所有代码都与每次运行相关(一般情况下)。
用这些术语讨论seq
和模式匹配。
我已经谈到了模式匹配。 seq
可以通过类似于 case
和应用的规则来定义:例如,(\x -> <expr1>) `seq` <expr2>
简化为 <expr2>
。这样做可以“强制评估”,就像 case
和应用程序一样。 WHNF 只是这些表达式“强制评估”的名称。
解释函数应用的细微差别:它如何严格? 它又如何不是?
它在左侧表达式中是严格的,就像 case
在其选择器中是严格的一样。在替换后的函数体中也是严格的,就像在替换后的选定替代品的 RHS 中一样。
deepseq
呢?
它只是一个库函数,而不是内置函数。
顺便提一下,deepseq
的语义很奇怪。它应该只接受一个参数。我认为发明它的人只是盲目地复制了 seq
,并没有理解为什么 seq
需要两个参数。我认为 deepseq
的名称和规范表明,即使是经验丰富的 Haskell 程序员也普遍存在对 Haskell 评估的理解不足。
let
和 case
语句?
我谈到了 case
。在展开和类型检查之后,let
只是一种以树形式编写任意表达式图的方式。这里有一篇论文。
unsafePerformIO
?
在某种程度上,它可以通过规约规则来定义。例如,
case unsafePerformIO <expr> of <alts>
规约为
unsafePerformIO (<expr> >>= \x -> return (case x of <alts>))
,而仅在顶层,
unsafePerformIO <expr>
规约为
<expr>
。
这不会进行任何记忆化。您可以尝试通过将每个
unsafePerformIO
表达式重写为显式记忆化自身,并创建相关的
IORef
... 在某个地方来模拟记忆化。但是,您永远无法复制 GHC 的记忆化行为,因为它取决于优化过程的不可预测细节,并且甚至不是类型安全的(正如 GHC 文档中臭名昭著的多态
IORef
示例所示)。
Debug.Trace
?
Debug.Trace.trace
只是unsafePerformIO
的一个简单包装器。
顶层定义?
顶层变量绑定与嵌套的let
绑定相同。data
,class
,import
等则完全不同。
严格数据类型?Bang模式?
只是seq
的语法糖。
seq
和模式匹配已足够,其余部分可以根据这些定义。我认为模式匹配可以确保IO
操作的脊柱严格性,例如。 - C. A. McCann+
运算符也会强制执行严格性,我认为纯 FFI 调用也是如此。 - hammar