GHC fails to make function tail recursive
Sometimes GHC does not compile function as tail recursive despite it looks like tail recursive. Here is simplified example.
{-# LANGUAGE BangPatterns #-}
incompleteBetaWorker :: Double -> Double
incompleteBetaWorker _ = loop 1 1 1 1
where
-- Constants
eps = 1e-15
-- Loop
loop :: Double -> Int -> Double -> Double -> Double
loop !psq !ns !term !betain
| done = betain'
| otherwise = loop psq' (ns - 1) term' betain'
where
-- New values
term' = term
betain' = betain
psq' = if ns < 0 then psq + 1 else psq
-- This condition cause stack overflow
done = db <= eps && db <= eps*betain' where db = abs term'
-- With this it loops endlessly
-- done = db <= eps * betain' where db = abs term'
main :: IO ()
main = print $ incompleteBetaWorker 0
If second equation for done is used function is tail recursive and works in constant space. if first one (uncommented) is used it isn't. From looking at the it looks loop is converted to several corecursive functions.
Such loops appear frequently in numerical code and it's important to ensure that worker function is tail recursive since getting answer may require a lot of iteration.
I've tested it with GHC 7.2.2 and 7.4.1. Both are affected. Example was compiled with -O2.
Trac metadata
Trac field | Value |
---|---|
Version | 7.4.1 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |