理解Haskell中的评估顺序

Question

我试图了解Haskell中where子句的评估方式.假设我们得到了这个玩具示例,其中bar,baz和bat在某处定义了函数:

func x = foo i j k
  where
    foo i j k = i + j + k
    k = bat x
    j = baz k
    i = bar j

该线如何func x = foo i j k扩展？它是否评估为func x = foo(i(j(k)), j(k), k)或类似的东西func x = foo(i, j, k)？

Answer 1

介绍

我假设你打算写这段代码:

func :: Int -> Int
func x = foo
  where
    foo = i + j + k
    k = bat x
    j = baz k
    i = bar j

这样它将进行类型检查,并且where最终会调用在子句中定义的所有三个函数.如果这不是你的意思,仍然继续阅读,因为我不仅会给你一个代码评估方式的描述,而且还会给你一个自己确定答案的方法.这可能是一个长篇故事,但我希望它值得你的时间.

核心

代码的评估绝对取决于您对编译器的选择,但我想您将使用GHC,如果是这样,它会在将代码转换为机器代码之前将代码转换几次.

首先," where条款"将被" let条款"取代.这样做是为了将Haskell语法简化为更简单的Core语法.核心与称为lambda演算的数学理论相似,因为它最终的评估是根据这个坚实的基础进行的.此时,您的代码看起来有点像这样:

func = ?x ->
      let { k = bat x } in
      let { j = baz k } in
      +
        (+ (bar j) j)
        k

如您所见,whereHaskell代码子句中的一个函数定义在到达Core阶段时实际上完全消失(实际上,它被内联),其他函数定义被重写为let符号.二进制操作(+)被重写为抛光符号以使其明确(现在i + j应该首先计算).所有这些转换都是在不改变代码含义的情况下执行的.

图形机器

然后,得到的lambda表达式将被简化为有向图并由Spineless无标记图形机器执行.从某种意义上说,Core to STG机器是汇编程序对图灵机的作用,虽然前者是lambda表达式,而后者是一系列命令式指令.(正如您现在所看到的,功能语言和命令式语言之间的区别运行得相当深.)STG机器会将您提供的表达式转换为可在传统计算机上执行的命令性指令,通过严格定义的操作语义 -对于Core的每个语法特征(其中只有大约4个),有一条命令式汇编程序指令执行相同的操作,而Core程序将被转换为这些部分的组合.

Core的操作语义的关键特征是它的懒惰.如你所知,Haskell是一种懒惰的语言.这意味着要计算的函数和该函数的值看起来是一样的:作为RAM中的字节序列.当程序启动时,所有内容都被设置为函数(确切地说是闭包),但是一旦计算了函数的返回值,它就会被置于闭包的位置,以便所有对内存中此位置的进一步访问将立即收到价值.换句话说,仅在需要时才计算值,并且仅计算一次.

正如我所说,Core中的表达式将转向相互依赖的有向计算图.例如:

如果你仔细观察,我希望这个图表会提醒你我们开始的程序.请注意两个有关它的细节:

• 所有的箭头最终都会导致x,这与我们的观点一致,即供应x足以评估func.

• 有时两个箭头通向同一个盒子.这意味着这个盒子的价值将被评估一次,第二次我们将获得免费的价值.

因此,STG机器将采用一些核心代码并创建一个可执行程序,用于计算与图片中的图形或多或少类似的图形值.

执行

现在,当我们进入图表时,很容易看到计算将如此进行:

1. 如func所谓的,x接收值并将其放入相应的框中.
2. bat x 计算并放在一个盒子里.
3. k设置为相同bat x.(GHC在代码上运行的一些优化可能会删除此步骤,但字面上一个let子句要求将其值单独存储.)
4. baz k 计算并放在一个盒子里.
5. j被设置为baz k相同,与k步骤6中的相同.bar j计算并放入一个框中.
6. 与根据步骤3和5所预期的相反,i没有任何设定.正如我们在Core的列表中看到的那样,它已经被优化了.
7. + (bar j) j计算.j已经计算出,因此baz k将不会被调用这段时间,由于懒惰.
8. 计算最高值.同样,不需要计算bat x此时间,因为它是先前计算的并存储在右侧框中.
9. 现在,值func x本身就是一个盒子,准备好被调用者多次使用.

我要强调的是,这是在您执行程序时将要发生的事情,而不是编译它.

结语

据我所知,这就是故事.为了进一步澄清,我向读者介绍了Simon Peyton Jones的着作:关于Haskell设计的书和关于Graph机器设计的文章,共同描述了GHC对最小特性的所有内部工作原理.

要查看GHC生成的Core,只需在-ddump-simpl编译时传递标志.一开始会伤到你的眼睛,但人们会习惯它.

请享用!

postscriptum

正如@DanielWagner在评论中所指出的那样,Haskell的懒惰有一些我们应该考虑的进一步后果,我们要解剖一个不那么做作的案例.具体来说:计算可能不需要评估它指向的某些方框,甚至根本不需要评估任何方框.在这种情况下,这些框将保持不变和未评估,同时计算完成并且无论如何都实现其实际上独立于从属框的结果.这种功能的一个例子:f x = 3.这具有深远的影响:比如,如果x无法计算,就像在"无限循环"中那样 x,首先不使用的函数根本不会进入该循环.因此,有时希望详细地知道哪些子计算必须从给定的计算中启动而哪些子计算可能不会.这种错综复杂的程度比我在这个答案中准备描述的要远一点,所以在这个警示说明中我会结束.

Answer 2

首先，foo i j k将解析为((foo i) j) k. 这是因为 Haskell 中的所有函数都只接受一个参数。的第一个参数foo是i，那么结果(foo i)是一个函数，其第一个参数是j，等等。所以，它既不是foo(i(j(k)))也foo (i, j, k)；但是，我应该警告您，这((foo i) j) k最终在某种意义上等同于foo (i, j, k)如果您愿意的话我们可以讨论的原因。

其次，i、j和k不会作为简化值传递foo，而是作为表达式传递，并且由foo决定（通过foo的公式）如何以及何时评估每个提供的表达式进行计算。就 而言(+)，我很确定它只是从左到右。因此，i将首先被强制，但当然要评估i，所有其他的都需要评估，因此您将数据依赖树追踪到其叶子，其底部为x。

也许这里的微妙之处在于“减少”和“完全减少”之间存在区别。i将首先减少，从某种意义上说，一层抽象（名称i）被删除并替换为 的公式i，但此时它还没有完全减少，为了完全减少，i我们需要完全减少其数据依赖性。

Answer 3

未指定评估顺序(在Haskell报告中)以进行添加.因此,评估顺序取决于您的号码类型及其Num实例.

例如,下面是两种具有Num实例和反向评估顺序的类型.我使用了自定义的Show实例和调试打印输出,以便在输出中更容易看到.

import Debug.Trace

newtype LeftFirst = LF { unLF :: Integer }
instance Show LeftFirst where show (LF x) = x `seq` "LF"++show x
newtype RightFirst = RF { unRF :: Integer }
instance Show RightFirst where show (RF x) = x `seq` "RF"++show x

instance Num LeftFirst where
    (+) a b = a `seq` LF (unLF a + unLF b)
    fromInteger x = trace ("LF" ++ show x) (LF x)

instance Num RightFirst where
    (+) a b = b `seq` RF (unRF a + unRF b)
    fromInteger x = trace ("RF" ++ show x) (RF x)

func :: Num a => a -> a
func x = foo i j k
  where
    foo i j k = i + j + k
    k = bat x
    j = baz k
    i = bar j

bar,baz,bat :: Num a => a -> a
bar = (+1)
baz = (+2)
bat = (+3)

并注意输出:

*Main> func (0 :: LeftFirst)
LF0
LF3
LF2
LF1
LF14
*Main> func (0 :: RightFirst)
RF3
RF0
RF2
RF1
RF14