Skip to content
GitLab
Projects Groups Topics Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Register
  • Sign in
  • GHC GHC
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributor statistics
    • Graph
    • Compare revisions
    • Locked files
  • Issues 5.5k
    • Issues 5.5k
    • List
    • Boards
    • Service Desk
    • Milestones
    • Iterations
  • Merge requests 629
    • Merge requests 629
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Artifacts
    • Schedules
    • Test cases
  • Deployments
    • Deployments
    • Releases
  • Analytics
    • Analytics
    • CI/CD
    • Code review
    • Insights
    • Issue
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell CompilerGlasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #5997
Closed
Open
Issue created Apr 11, 2012 by Khudyakov@trac-Khudyakov

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
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking