ghc-whole-program-compiler-project icon indicating copy to clipboard operation
ghc-whole-program-compiler-project copied to clipboard

ext-STG interpreter: Wrong output on NoFib's `bernoulli`

Open sgraf812 opened this issue 2 years ago • 2 comments

Here's a complete reproducer:

import Data.Ratio
import System.Environment
import Control.Monad
import Data.Char
import Data.List

hash :: String -> Int
hash = foldl' (\acc c -> ord c + acc*31) 0

-- powers = [[r^n | r<-[2..]] | n<-1..]
-- type signature required for compilers lacking the monomorphism restriction
powers :: [[Integer]]
powers = [2..] : map (zipWith (*) (head powers)) powers

-- powers = [[(-1)^r * r^n | r<-[2..]] | n<-1..]
-- type signature required for compilers lacking the monomorphism restriction
neg_powers :: [[Integer]]
neg_powers =
  map (zipWith (\n x -> if n then x else -x) (iterate not True)) powers

pascal:: [[Integer]]
pascal = [1,2,1] : map (\line -> zipWith (+) (line++[0]) (0:line)) pascal

bernoulli 0 = 1
bernoulli 1 = -(1%2)
bernoulli n | odd n = 0
bernoulli n =
   (-1)%2
     + sum [ fromIntegral ((sum $ zipWith (*) powers (tail $ tail combs)) -
                            fromIntegral k) %
             fromIntegral (k+1)
     | (k,combs)<- zip [2..n] pascal]
  where powers = (neg_powers!!(n-1))

main = replicateM_ 20 $ do
 [arg] <- getArgs
 let n = (read arg)::Int
 print (hash (show (bernoulli n)))

When compiled with GHC and then run with ./prog 60, this program emits 20 identical lines of output

4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515
4837159772545863515

But with the external STG interpreter, I get seemingly random output

-8217654781975423434
-1601202432573694520
6544427287528505721
-6637178930954800059
1417607460360768286
7114115951822130902
-3876087935213532440
1230325754489347080
7641514400317302877
-490070737175279921
-488139356046772070
1268233930116665531
-7339682831372768951
846923374074735722
8970076170777687451
-4360391709750620227
9025066669033851438
6887950169961887397
7866087271730774952
-1888317243837475367

It's not terribly important for our use case to have correct output, but it would be great nonetheless.

sgraf812 avatar Apr 14 '22 13:04 sgraf812

Well, the interpreter on my machine produces the correct output. Which commit/version are you using?

csabahruska avatar Apr 14 '22 14:04 csabahruska

OK, I could reproduce this bug using the https://github.com/grin-compiler/ext-stg-interpreter-presentation-demos version. Since then I've updated GHC-WPC to GHC 9.0.2 and it fixes this issue. I'll release the update version soon.

csabahruska avatar Apr 18 '22 16:04 csabahruska