见证一个值在 Haskell 中被评估的频率

Question

有了一点点 unsafe，您可以看到 much 的惰性值在 Haskell

中是如何计算的

import Data.IORef
import System.IO.Unsafe

data Nat = Z | S Nat
  deriving (Eq, Show, Read, Ord)

natTester :: IORef Nat -> Nat
natTester ref =
  let inf = natTester ref
   in unsafePerformIO $ do
        modifyIORef ref S
        pure $ S inf

newNatTester :: IO (Nat, IORef Nat)
newNatTester = do
  ref <- newIORef Z
  pure (natTester ref, ref)

howMuchWasEvaled :: (Nat -> b) -> IO Nat
howMuchWasEvaled f = do
  (inf, infRef) <- newNatTester
  f inf `seq` readIORef infRef

与：

ghci> howMuchWasEvaled $ \x -> x > S (S Z)
S (S (S Z))

表示只计算了infinity :: Nat的前四个构造函数。

如果 x 被使用两次，我们仍然得到所需的总评估：

> howMuchWasEvaled $ \x -> x > Z && x > S (S Z)
S (S (S Z))

这是有道理的 - 一旦我们对 x 进行了评估，我们就不必重新开始。咚咚已经被逼了

但是是有一种方法可以检查次构造函数被求值了吗？即，函数 magic 的行为如下：

> magic $ \x -> x > Z 
S Z
> magic $ \x -> x > Z && x > Z
S (S Z)
...

我知道这可能涉及编译器标志（可能 no-cse）、内联编译指示、非常不安全的函数等。

编辑：Carl 指出我可能对我正在寻找的内容的限制不够清楚。要求是 function 不能更改 magic 作为参数给出（尽管可以假定它的参数是惰性的）。 magic 将成为您可以使用自己的函数调用的库的一部分。

也就是说，特定于 GHC 的 hack 和只能不可靠地工作的东西绝对仍然是游戏。

Answer 1

如前所述，这不能在 ghc 中完成。同名的两次使用，例如您示例中的 x，将始终与 ghc 对 haskell 的评估模型的实现共享。这是为确保共享是提供关键构建块的保证。至少，让它做你想做的事需要传入多个值，每个值对应一个你想使用命名值的独立位置。

然后您必须确保在调用方，值在传递给函数之前不会意外共享。这可以做到，但它是可能需要使用 -fno-cse 或 -fno-full-laziness 等选项的地方，具体取决于您如何实现它以及 ghc 运行处于什么优化级别。

这里是对你在 ghci 中有效的起点的一个小修改，至少：

{-# OPTIONS_GHC -fno-full-laziness #-}

import Data.IORef
import System.IO.Unsafe

data Nat = Z | S Nat
    deriving (Eq, Show, Read, Ord)

natTester :: IORef Nat -> Nat
natTester ref =
    let inf = natTester ref
    in unsafePerformIO $ do
        modifyIORef ref S
        pure $ S inf

newNatTester :: IO ((a -> Nat), IORef Nat)
newNatTester = do
    ref <- newIORef Z
    pure (\x -> x `seq` natTester ref, ref)

howMuchWasEvaled :: ((a -> Nat) -> b) -> IO Nat
howMuchWasEvaled f = do
    (infGen, infRef) <- newNatTester
    f infGen `seq` readIORef infRef

在 ghci 中使用：

*Main> howMuchWasEvaled $ \gen -> let x = gen 1 ; y = gen 2 in x > Z && y > Z
S (S Z)
*Main> howMuchWasEvaled $ \gen -> let x = gen 1 in x > Z && x > Z
S Z

我用一个无穷大生成器代替了将单个无穷大传递给函数。生成器不关心它调用的参数是什么，只要它不是底值即可。（seq 是为了确保函数实际使用它的参数，以防止 ghc 在参数未使用时可能进行的一些优化。）只要每次调用时都使用不同的值，ghc 就赢了' 能够把它 cse 掉，因为表达方式不同。如果与优化一起使用，完全惰性可能会干扰 natTester ref 从 newNatTester 中的 lambda 中浮动。为防止这种情况，我添加了一个 pragma 以关闭此模块中的优化。默认情况下在 ghci 中无关紧要，因为它不使用优化。这个模块是否被编译可能很重要，所以我加入了 pragma 只是为了确定。

见证一个值在 Haskell 中被评估的频率

Witnessing how frequently a value has been evaluated in Haskell

haskell

lazy-evaluation

thunk