Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is GHC able to tail-call optimize IO actions?

Will GHC perform tail-call optimization on the following function by default? The only weird thing about it is that it is recursively defining an IO action, but I don't see why this couldn't be TCO'd.

import Control.Concurrent.MVar

consume :: MVar a -> [a] -> IO ()
consume _ [] = return ()
consume store (x:xs) = do putMVar store x
                          consume store xs
like image 866
Geoff Avatar asked Apr 27 '09 03:04

Geoff


People also ask

Does gcc do tail call optimization?

Some C compilers, such as gcc and clang, can perform tail call optimization (TCO).

Does Golang have tail call optimization?

Go, however, does not implement tail-call optimization, and you will eventually run out of memory.

Does F# have tail call optimization?

Because F# is a language that heavily uses recursion, its compiler employs a trick that is called "tail call optimization". With this trick, the last function a function calls (even when it is not herself) does not burden the stack. This allows tail recursion to be essentially a loop, in terms of stack pressure.

Does V8 support tail call optimization?

Tail-call optimization is a part of the ES2015-ES6 specification. Supporting it isn't a NodeJS thing, it's something the V8 engine that NodeJS uses needs to support.


1 Answers

Since your code is equivalent to

consume store (x:xs) = putMVar store >> consume store xs

the call does not actually occur in tail position. But if you run ghc -O and turn on the optimizer, the -ddump-simpl option will show you the output of GHC's intermediate code, and it does indeed optimize into a tail-recursive function, which will compile into a loop.

So the answer is GHC won't optimize this by default; you need the -O option.

(Experiments done with GHC version 6.10.1.)

like image 155
Norman Ramsey Avatar answered Oct 27 '22 01:10

Norman Ramsey