GitLab

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