Наблюдение за тем, как часто значение оценивалось в Haskell

С небольшим количеством unsafe вы можете увидеть, сколько много ленивого значения было вычислено в 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), встроенные прагмы, очень небезопасные функции и т. д.

РЕДАКТИРОВАТЬ: Карл указал, что я, возможно, недостаточно четко изложил ограничения того, что искал. Требование состоит в том, что функция, которую magic задает в качестве аргумента, не может быть изменена (хотя можно предположить, что ее аргумент ленив). magic будет частью библиотеки, которую вы можете вызывать со своими собственными функциями.

Тем не менее, хаки, специфичные для GHC, и вещи, которые работают только ненадежно, определенно все еще в игре.


thunk lazy-evaluation haskell
person user2141650    schedule 05.08.2020    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Как уже говорилось, это невозможно сделать в 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 не сможет этого сделать. чтобы убрать его, потому что выражения разные. При использовании с оптимизацией полная ленивость может помешать плавающему natTester ref из лямбды в newNatTester. Чтобы предотвратить это, я добавил прагму для отключения этой оптимизации в этом модуле. В ghci по умолчанию это не имеет значения, так как он не использует оптимизации. Это может иметь значение, если этот модуль будет скомпилирован, поэтому я добавил прагму, чтобы быть уверенным.

person Carl    schedule 05.08.2020
comment
Спасибо! Сначала я тоже использовал функцию с фиктивным аргументом, но этого недостаточно для моего варианта использования. Я нашел hackage.haskell.org/package/ghc-dup-0.1 - который, кажется, довольно глубоко проникает внутрь ghc и не очень надежен, но делает то, на что я надеялся (за исключением того, что он не компилируется с последними GHC...) - person user2141650; 06.08.2020
comment
В каком смысле недостаточно? Это звучит как ограничение, не включенное в исходный вопрос... - person Carl; 06.08.2020
comment
Ах. При этих ограничениях применяется первая часть моего ответа. Нет. Вы не можете этого сделать. На самом деле GHC гарантирует обратное. - person Carl; 06.08.2020