放宽单子计算中的顺序约束

Question

以下是一些值得思考的内容。

当我编写单子代码时，单子会对所执行的操作进行排序。例如，如果我在IO单子中编写：

do a <- doSomething
   b <- doSomethingElse
   return (a + b)

我知道doSomething会在doSomethingElse之前执行。

现在，考虑类似C语言的等效代码：

return (doSomething() + doSomethingElse());

C语言的语义实际上并未指定这两个函数调用的顺序，因此编译器可以自由地移动它所需的内容。

我的问题是：我该如何在Haskell中编写monadic代码，同时也将这种评估顺序保持为undefined？理想情况下，当我的编译器优化器查看代码并开始移动内容时，我希望获得一些好处。

以下是一些可能的技术，虽然没有完成任务，但都符合正确的“精神”：

• 以函子风格编写代码，即编写plus doSomething doSomethingElse，并让plus安排monadic calls。缺点：您会失去monadic actions结果的共享，并且plus仍然会决定何时进行评估。
• 使用lazy IO，即unsafeInterleaveIO，将调度推迟到评估的需求。但lazy和strict with undefined order是不同的：特别是我确实希望执行所有monadic actions。
• Lazy IO，结合立即seq'ing所有参数。特别地，seq不会强制排序约束。

在这种意义上，我需要比monadic ordering更灵活但比全面的laziness不那么灵活的东西。

- Edward Z. Yang

---

为什么它必须是单子的？为什么需要强制未定义的顺序？ - x13n

它并不会。从优化的角度来看，未定义的顺序大多是可取的。 - Edward Z. Yang

你想限制自己在可交换单子范畴内，还是想引入非确定性？ - augustss

mightybyte：是的。无论如何，你也不能保证在IO单子中确定性/正确性... hammar：谁知道呢？我希望编译器为我选择！augustss：IO已经是非确定性的了。对于其他单子呢？有趣的问题！ - Edward Z. Yang

@Edward：那么，如果这两个操作是“将一行追加到文件中”，你不关心文件中行的顺序，但如果它们并行运行，你可能会从两个操作中得到一些奇怪的字符交错，因此在这种情况下，您需要保证某些排序的语义，而如果您知道这些操作是独立的，您可以给编译器完全自由。 - hammar

Answer 1

这个问题称为“可交换单子问题”。可交换单子是指动作的顺序不影响结果的单子（它们是可交换的），也就是说，当执行以下代码时：

do a <- f x
   b <- g y
   m a b

就是相同的意思：

do b <- g y
   a <- f x
   m a b

有许多单子是可交换的(例如 Maybe, Random)。如果该单子是可交换的，那么其中包含的操作可以并行计算，这非常有用！

然而，我们还没有一个好的语法来处理可交换的单子，虽然很多人都提出过这样的需求——这仍然是一项开放性研究问题。

顺带一提，应用函子确实给了我们这种重新排序计算的自由，但是，您必须舍弃bind的概念（如对于 liftM2 的建议所示）。

- Don Stewart

---

对我来说，“Maybe”似乎不是可交换的：okay = do x <- Nothing ; y <- undefined ; return x与bad = do y <- undefined ; x <- Nothing ; return x。也许它在更严格的意义上是可交换的？ - acfoltzer

他们对所描述的效果进行通勤。在存在异常、非终止或其他未被单子跟踪的可观察效果的情况下，您就会遇到麻烦。 - Don Stewart

@DonStewart Tomas Petricek的博客链接已失效。 - jub0bs

Answer 2

这是一个深度而不择手段的黑客技巧，但在我看来，它似乎能够解决问题。

{-# OPTIONS_GHC -fglasgow-exts #-}
{-# LANGUAGE MagicHash #-}
module Unorder where
import GHC.Types

unorder :: IO a -> IO b -> IO (a, b)
unorder (IO f) (IO g) = IO $ \rw# ->
           let (# _, x #) = f rw#
               (# _, y #) = g rw#
           in (# rw# , (x,y) #)

既然这将不确定性置于编译器手中，它应该在控制流问题（即异常）方面表现得“正确”（即非确定性）。

另一方面，我们不能像大多数标准单子（如State和Either a）那样进行相同的技巧，因为我们实际上是依靠通过干扰RealWorld标记可用的恐怖远程操作。为了获得正确的行为，我们需要一些注释可用于优化器，表明我们对两个不等价替代品之间的非确定性选择感到满意。

- sclv

---

好的，那很棒。现在，请描述一下我们何时可以安全地使用它;-) - Edward Z. Yang

我不会声称在这里拥有专业知识，但我认为这是相当安全的，并且基本上提供了所需的语义。严格元组的条件应该提供我们想要的排序保证，而let子句的结构应该避免我们不需要的排序条件。 - sclv

我不理解这个。非常感谢详细解释一下这段代码的作用。 - user239558

Answer 3

C的语义实际上没有指定这两个函数调用的顺序，因此编译器可以自由地移动它想要的东西。但是，如果doSomething()引起的副作用会改变doSomethingElse()的行为，你真的希望编译器干扰顺序吗？（提示：不）你在单子中的事实表明可能存在这种情况。你关于“你失去了结果共享”的说明也表明了这一点。

然而，请注意，monadic并不总是意味着有序的。虽然与您所描述的不完全相同，但您可能会对Par monad感兴趣，它允许您以并行方式运行操作。

您有兴趣使顺序未定义，以便编译器可以神奇地优化它。也许，您应该使用像Par monad这样的东西来指示依赖项（某些东西不可避免地必须发生在其他事物之前），然后让其余的东西并行运行。

附注：不要将Haskell的return与C的return混淆。

- Dan Burton