用于条件/替代的推测执行的 Haskell 策略

Question

我想知道哪种并行策略、spark 或其他任何策略可用于递归地推测执行由大量条件测试组成的 Haskell 程序。

假设一个程序有很多递归的条件测试。我想如果使用 Spark ，那么大多数 Spark 将在无用的 Twig 上工作。 spark lifecycle不包括取消。

可行的策略必须能够在依赖树中高效地创建和取消工作单元。

例如，考虑解析文本的问题。解析器基本上由一棵巨大的树组成:

if <looks-like-1> then
   if <looks-like 1.1> then
     if <looks-like 1.1.1> then
       success
     else failure
   else if <looks-like 1.1> ...
else if ...

在给定的条件下，我们要等到很久以后才能知道我们是否会回溯。通过推测性地执行另一个分支，我们可以更快地解决这个问题。

但是，如果我们只使用 spark，无用的工作会呈指数级增长，我们不会得到太多的加速。当我们知道它永远不会被采用时，必须有一种方法可以取消在分支上开始的工作。

对此的概括是对任何实现 Alternative 的数据类型的推测执行。 ，想法是取消从未观察到的替代方案不会改变程序的语义。所以a <|> b其中 b不从表达式返回，可以短路，比如通过在推测执行期间抛出异常，而不影响语义。

你会如何在 Haskell 中处理这个问题？

Answer 1

如果我们可以放弃纯并行计算的世界，我们可以转向 async包，它允许取消异步任务。

例如，这是一个推测性的“if”，它允许计算需要一段时间的条件。它同时启动两个分支，当条件结果已知时立即杀死失败的分支:

{-# LANGUAGE BlockArguments #-}
{-# LANGUAGE NumDecimals #-}
import Control.Concurrent (threadDelay)
import Control.Concurrent.Async
import Control.Exception (onException)

iffy :: IO Bool -> IO a -> IO a -> IO a
iffy test left right =
    withAsync left \leftAsync ->
    withAsync right \rightAsync ->
        do testResult <- test
           let (shouldWait,shouldCancel) =
                    if testResult then (leftAsync,rightAsync)
                                  else (rightAsync,leftAsync)
           cancel shouldCancel
           wait shouldWait

iffyTest :: Bool -> IO Int
iffyTest b =
    iffy do threadDelay 1e6 >> pure b
         do (threadDelay 2e6 >> pure 5) `onException` putStrLn "cancelled L"
         do (threadDelay 2e6 >> pure 2) `onException` putStrLn "cancelled R"

投入使用:

λ iffyTest True
cancelled R
5
λ iffyTest False
cancelled L
2