2

In this example, action is an infinite loop created by mistake. Is there a way to detect such loops in a GHC program?

   action bucket manager url = catch
      (action bucket manager url)
      (\(e :: HttpException) -> Logger.warn $ "Problems with " ++ url)
sevo
  • 4,559
  • 1
  • 15
  • 31
  • 1
    Some languages like Idris support totality checking - and it would surely be possible to write a totality checking extension for GHC, although I don't know of one. However, due to the undecidability of the halting problem, there is no totality checker that will accept all programs that halt while rejecting all programs that do not halt. – jcarpenter2 Nov 06 '17 at 04:11

2 Answers2

4

Short answer: no.

It certainly isn't possible to notice every infinite loop one could write down; this is famously known as the halting problem and the formal proof that one cannot write a loop-detecting program is so famous that there's even a Dr. Seuss version of it.

Of course, there's also an entire branch of computer science devoted to taking best-effort approaches to undecidable problems, and in theory we know a lot about ways to detect simple versions of such infinite loops. However, as far as I know nobody has done the engineering work needed to turn that theory into a tool that one can easily run on Haskell source.

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • Agreed. Actually I was hoping that in case of `GHC` there would be some runtime hints about behavior of a program that is unproductively consuming CPU. In particular I saw no memory consuption profile before it ran out of it. Did my thread miss some "safe-points" for example? – sevo Nov 06 '17 at 17:45
  • @sevo I'm not sure I understood that question. Are you saying you ran with profiling, but did not see any profiling output? If so, that seems like a completely different question, and I encourage you to open a fresh SO post with a minimal reproducing example. – Daniel Wagner Nov 06 '17 at 17:56
  • "However, as far as I know nobody has done the engineering work needed to turn that theory into a tool that one can easily run on Haskell source." -- perhaps not at the compile stage, but GHC's runtime system has been doing simple "blackhole" infinite loop detection for quite a while. See http://mainisusuallyafunction.blogspot.com/2011/10/thunks-and-lazy-blackholes-introduction.html for some info. – Desty Jun 10 '18 at 20:53
  • @Desty Which is, unfortunately, *so* simple that it won't even catch the example given in the question, where a function literally calls itself with the exact same arguments. – Daniel Wagner Jun 10 '18 at 23:09
  • @DanielWagner indeed; perhaps something about the function or how it's wrapped in a "catch" means it isn't noticed by the detector. Just pointing out that work has been done to make it possible in *some* cases. – Desty Jun 12 '18 at 23:23
0

I presume this is a follow up to What is the format of GHC hp profile?.

In general there is no way to automatically detect every infinite loop. In practice and not specific to GHC, I think it is commonly reasonable to detect them manually by looking at the CPU and memory usage. This particular case should exhaust memory because it is not tail recursive (at least, I think that's the reason). Something like action x y z = action x y z won't allocate and so would spin indefinitely, maxing the CPU with no increase in memory usage. It would be up to you to have an expectation of execution time and memory usage and investigate any deviations.

I haven't tried this, but if you suspect an infinite loop perhaps you could use the xc RTS option and interrupt the execution to get a stack trace.

ryachza
  • 4,460
  • 18
  • 28