haskell - Probar si un valor ha sido evaluado en forma normal de cabeza débil

lazy-evaluation thunk

Question

En Haskell, ¿es posible probar si un valor se ha evaluado como una forma normal de cabeza débil? Si una función ya existe, esperaría que tuviera una firma como

evaluated :: a -> IO Bool

Hay algunos lugares donde vive una funcionalidad similar.

Una respuesta anterior me presentó al comando :sprint ghci, que imprimirá solo la parte de un valor que ya ha sido forzado a tener una forma normal de cabeza débil. :sprint puede observar si un valor ha sido evaluado o no:

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

Es posible en IO examinar propiedades que de otro modo estarían fuera de los límites. Por ejemplo, es posible comparar en IO para ver si dos valores provienen de la misma declaración. Esto es proporcionado por los StableName s en System.Mem.StableName y se usa de manera famosa para resolver el problema de intercambio observable en data-reify . El StablePtr relacionado no proporciona un mecanismo para verificar si el valor de referencia tiene una forma normal de cabeza débil.

Answer 1

La implementación de ghci para :sprint finalmente usa unpackClosure# de ghc-prim para inspeccionar un cierre. Esto se puede combinar con el conocimiento del formato de los objetos del montón para determinar si un cierre se ha evaluado hasta el final a la forma normal de cabeza débil.

Hay algunas formas de reproducir la inspección realizada por la implementación de ghci para :sprint . La api de GHC expone getClosureData :: DynFlags -> a -> IO Closure en RtClosureInspect . El paquete de vacuum , que solo depende de ghc-prim, reproduce el código de RtClosureInspect y expone getClosure :: a -> IO Closure . No es inmediatamente obvio cómo examinar cualquiera de estas representaciones de Closure para, por ejemplo, seguir una indirección. El ghc-heap-view inspecciona los cierres y expone tanto el getClosureData :: a -> IO Closure como una vista detallada del Closure . ghc-heap-view depende de la API de GHC.

Podemos escribir evaluated en términos de getBoxedClosureData de ghc-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

Este manejo de los cierres de agujero negro puede ser incorrecto mientras se está evaluando el agujero negro. El manejo de los cierres de selector puede ser incorrecto. La suposición de que los cierres AP no están en forma normal de cabeza débil puede ser incorrecta. La suposición de que todos los demás cierres están en WHNF es casi ciertamente incorrecta.

Ejemplo

Nuestro ejemplo requerirá dos subprocesos simultáneos para observar en un subproceso que el otro está evaluando expresiones.

import Data.Char
import Control.Concurrent

Podemos comunicar información fuera de una función sin recurrir a nada unsafe forzando selectivamente la evaluación. Lo siguiente construye un flujo de pares de thunks en los que podemos elegir forzar uno u otro del par.

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

zero obliga al primero y one obliga al segundo.

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

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

copy es una función de identidad malvada que tiene el efecto secundario de forzar bits en una secuencia basada en la inspección de los datos.

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 lee nuestro flujo de bits al verificar si se ha evaluated cada uno de los thunks en un par.

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

Forzar la copy cuando se imprime tiene el efecto secundario de imprimir la información observada sobre la cadena de lectura.

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

Si ejecutamos el programa y proporcionamos la entrada abc123 , observamos el efecto secundario correspondiente a verificar si cada uno de los caracteres es isAlpha

abc123
abc123
1
1
1
0
0
0

Answer 2

No estoy seguro de que haya algo preempaquetado para esto. Sin embargo, uno puede codificarlo:

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
        )

Aquí hay un ejemplo de uso en ghci:

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

Por supuesto, esto hará un seguimiento de si el valor de escritura envuelto y luego devuelto el valor original se evalúa como WHNF, no si la cosa que se pasa a track se evalúa como WHNF, por lo que querrá poner esto como cerca del thunk en el que está interesado, por ejemplo, no podrá decirle si un thunk hecho por alguien más ya ha sido evaluado por alguien antes de que comience el rastreo. Y, por supuesto, considere usar MVar lugar de IORef si necesita seguridad para subprocesos.

Answer 3

Recientemente se ha presentado una propuesta, tal vez ya se haya implementado en algún lugar https://mail.haskell.org/pipermail/libraries/2015-February/024917.html

Answer 4

Una respuesta negativa, para que quede constancia: no parece ser factible reutilizar el mecanismo del sprint , porque está estrechamente ligado a la evaluación interactiva interpretada en oposición a las estructuras de tiempo de ejecución primitivas, por lo que puedo decir; Nunca he mirado los internos de GHC antes.

Comencé buscando "sprint" en la fuente de GHC en GitHub , que resultó compartir una implementación con el comando "imprimir" pero para un indicador Bool llamado force , y seguí las definiciones hasta que llegué a RtClosureInspect.cvObtainTerm que parece ser Un evaluador especializado.