haskell - Test if a value has been evaluated to weak head normal form

Question

In Haskell, is it possible to test if a value has been evaluated to weak head normal form? If a function already exists, I would expect it to have a signature like

evaluated :: a -> IO Bool

There are a few places that similar functionality lives.

A previous answer introduced me to the :sprint ghci command, which will print only the portion of a value that has already been forced to weak head normal form. :sprint can observe whether or not a value has been evaluated:

> let l = ['a'..]
> :sprint l
l = _
> head l
'a'
> :sprint l
l = 'a' : _

It's possible in IO to examine properties that would otherwise be off-limits. For example, it's possible to compare in IO to see if two values came from the same declaration. This is provided by the StableNames in System.Mem.StableName and used famously to solve the observable sharing problem in data-reify. The related StablePtr does not provide a mechanism to check if the referenced value is in weak head normal form.

score 12 · Accepted Answer

我不确定是否为此预先包装了任何东西。但是，可以对其进行编码：

import Data.IORef
import System.IO.Unsafe

track :: a -> IO (a, IO Bool)
track val = do
    ref <- newIORef False
    return
        ( unsafePerformIO (writeIORef ref True) `seq` val
        , readIORef ref
        )

这是 ghci 中的一个示例用法：

*NFTrack> (value, isEvaluated) <- track (undefined:undefined)
*NFTrack> isEvaluated
False
*NFTrack> case value of _:_ -> "neat!"
"neat!"
*NFTrack> isEvaluated
True

当然，这将跟踪包装后的 write-and-then-return-the-original-value thunk 是否被评估为 WHNF，而不是传递给的事物是否track被评估为 WHNF，因此您希望将其设为 close尽可能向您感兴趣的 thunk 发送 - 例如，它无法告诉您在跟踪开始之前，其他人制作的 thunk 是否已经被其他人评估过。如果您需要线程安全，当然可以考虑使用MVar而不是。IORef

score 9 · Accepted Answer

最终使用来自 ghc-prim的ghci 实现:sprintunpackClosure#来检查闭包。这可以与堆对象格式的知识相结合，以确定闭包是否一直被评估为弱头范式。

有几种方法可以重现 ghci 实现对:sprint. GHC api 公开getClosureData :: DynFlags -> a -> IO Closure在RtClosureInspect. 仅依赖于ghc -prim的Vacuum包从. 如何检查这些表示中的任何一个以例如遵循间接性并不是很明显。ghc-heap-view 包检查闭包并公开. ghc-heap-view 依赖于 GHC api。RtClosureInspectgetClosure :: a -> IO ClosureClosuregetClosureData :: a -> IO ClosureClosure

我们可以evaluated根据getBoxedClosureDataghc-heap-view 来写。

import GHC.HeapView

evaluated :: a -> IO Bool
evaluated = go . asBox
    where
        go box = do
            c <- getBoxedClosureData box
            case c of
                ThunkClosure     {} -> return False
                SelectorClosure  {} -> return False
                APClosure        {} -> return False
                APStackClosure   {} -> return False
                IndClosure       {indirectee = b'} -> go b'
                BlackholeClosure {indirectee = b'} -> go b'
                _ -> return True

在评估黑洞时，这种对黑洞闭合的处理可能是不正确的。选择器闭包的处理可能不正确。AP闭包不是弱头正常形式的假设可能是不正确的。所有其他闭包都在 WHNF 中的假设几乎可以肯定是不正确的。

例子

我们的示例将需要两个并发线程在一个线程中观察另一个线程正在评估表达式。

import Data.Char
import Control.Concurrent

unsafe我们可以通过选择性地强制评估，在不诉诸任何东西的情况下，在函数之外传递信息。下面构建了一对 thunk 流，我们可以在其中选择强制一对中的一个或另一个。

mkBitStream :: Integer -> [(Integer, Integer)]
mkBitStream a = (a+2, a+3) : mkBitStream (a+1)

zero强制第一个并one强制第二个。

zero :: [(x, y)] -> [(x, y)]
zero ((x, _):t) = x `seq` t

one :: [(x, y)] -> [(x, y)]
one ((_, y):t) = y `seq` t

copy是一个邪恶的身份函数，它具有基于检查数据强制流中的位的副作用。

copy :: (a -> Bool) -> [(x, y)] -> [a] -> [a]
copy f bs []     = []
copy f bs (x:xs) = let bs' = if f x then one bs else zero bs
                   in bs' `seq` (x:copy f bs' xs)

readBs通过检查一对中的每个 thunk 是否都已读取我们的比特流evaluated。

readBs :: [(x, y)] -> IO ()
readBs bs@((f, t):bs') = do
    f' <- evaluated f
    if f'
    then putStrLn "0" >> readBs bs'
    else do
        t' <- evaluated t
        if t'
        then putStrLn "1" >> readBs bs'
        else readBs bs

打印时强制copy具有打印所观察到的有关读取字符串的信息的副作用。

main = do
    let bs = mkBitStream 0
    forkIO (readBs bs)
    text <- getLine
    putStrLn (copy isAlpha bs text)
    getLine

如果我们运行程序并提供输入abc123，我们会观察到与检查每个字符是否对应的副作用isAlpha

abc123
abc123
1
1
1
0
0
0

score 7 · Accepted Answer

一个否定的答案，记录在案：重用的机制似乎不可行sprint，因为它与解释的交互式评估紧密相关，而不是原始的运行时结构——据我所知；我以前从未看过 GHC 内部结构。

我首先在 GitHub 上的 GHC 源中搜索“sprint” ，结果与“print”命令共享一个实现，但使用了一个Bool名为评估者。force

score 1 · Accepted Answer

最近有一个提案，也许它已经在某个地方实施了https://mail.haskell.org/pipermail/libraries/2015-February/024917.html

haskell - Test if a value has been evaluated to weak head normal form

4 回答 4

例子

Related

Reference