我想知道哪种并行策略、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 中处理这个问题?
最佳答案
如果我们可以放弃纯并行计算的世界,我们可以转向 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
关于用于条件/替代的推测执行的 Haskell 策略,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60194102/