infinite loop in functional programming ?

Question

• I was wondering: can infinite loops be done in functional programming?

example: when using the windows API to get windows messages, it is usually implemented in a loop.

I know it is possible to make a function that will keep going into recursion indefinitely. I expect that this will result in a stack overflow.

• are infinite loop the wrong mind-set for functional programming ?

• is the interface of the operating system or the hardware the problem ?

it doesn't seem to me like a functional program/o.s. could keep running by itself

I have a tiny bit of experience writing functional programs but this has always bothered me. please share your thoughts/insights about these issues

Answer 1

You can have infinite tail recursion if your compiler recognizes it. Some languages, e.g. scheme, require that compilers recognize tail recursion and allocate no stack space for it.

Edit I do not mean to disagree with the other answers, but "infinite" tail recursive loops with are a common idiom for dealing with the outside world. The following example is taken from Real World Haskell, and is representative of the idiom.

mainloop :: Handle -> Handle -> IO ()
mainloop inh outh = 
    do ineof <- hIsEOF inh
       if ineof
           then return ()
           else do inpStr <- hGetLine inh
                   hPutStrLn outh (map toUpper inpStr)
                   mainloop inh outh

We are essentially considering the outside world as a stream.

Answer 2

If you use tail recursion, you effectively have an iteration, like a for/while loop. Therefore, I guess you can have an infinite loop without getting stack overflow.

To your question: "are infinite loop the wrong mind-set for functional programming?" maybe this will help: - While or Tail Recursion in F#, what to use when?

Answer 3

As others have posted, an infinite loop is possible through tail recursions.

E.g. loop() will effectively run as an infinite loop (in constant stack space) since the compiler can optimize out the tail-recursive call of loop at the end.

let loop() = do {
  println("foo")
  loop()
}

But

are infinite loop the wrong mind-set for functional programming ?

still got a point. Consider your Windows-API example with the infinite loop. That's anything but functional. Remember - functional means thinking in values (and what they mean). Therefore, one would rather go a reactive/event-based approach like that [Pseudo-functional code]

  (onClick form1)
|> Event.subscribe (\pt-> do { print $ "I was clicked at " ++ (show pt) })

So

it doesn't seem to me like a functional program/o.s. could keep running by itself

is technically wrong - you can implement infinite loops - but there is often no (functional) point in doing so. Why should one need that except for some kind of IO polling? Transforming values in a purely functional way should terminate to be meaningful.

Answer 4

Most if not all uses of "infinite loops" in functional programming can be modeled by co-recursion. Other answers so far have pointed to general recursion, but unrestricted use of recursion is arguably a poor approach as it can lead to poorly structured code.

The vast majority of code in a purely functional program should be written in the total subset, i.e. use patterns such as structural recursion or co-recursion (which ensure termination and progress) rather than falling back to general recursion. Hopefully, future versions of GHC will include direct support for detecting some total subset of Haskell and emitting warnings for code which cannot be proven to terminate or progress.