Compilation of Tail-Call optimization in mutual recursion through C and Haskell

Question

I am experimenting with an external function interface in Haskell. I wanted to implement a simple test to see if I could do mutual recursion. So, I created the following Haskell code:

module MutualRecursion where import Data.Int foreign import ccall countdownC::Int32->IO () foreign export ccall countdownHaskell::Int32->IO() countdownHaskell::Int32->IO() countdownHaskell n = print n >> if n > 0 then countdownC (pred n) else return () 

Note that the recursive case is a call to countdownC, so it must be tail recursive.

In my C code, I have

 #include <stdio.h> #include "MutualRecursionHaskell_stub.h" void countdownC(int count) { printf("%d\n", count); if(count > 0) return countdownHaskell(count-1); } int main(int argc, char* argv[]) { hs_init(&argc, &argv); countdownHaskell(10000); hs_exit(); return 0; } 

Same as tail recursive. So i do

 MutualRecursion: MutualRecursionHaskell_stub ghc -O2 -no-hs-main MutualRecursionC.c MutualRecursionHaskell.o -o MutualRecursion MutualRecursionHaskell_stub: ghc -O2 -c MutualRecursionHaskell.hs 

and compile with make MutualRecursion .

And ... at startup, it disappears after printing 8991 . Just like a test, to make sure gcc itself can handle tco in mutual recursion, I did

 void countdownC2(int); void countdownC(int count) { printf("%d\n", count); if(count > 0) return countdownC2(count-1); } void countdownC2(int count) { printf("%d\n", count); if(count > 0) return countdownC(count-1); } 

and it worked pretty well. It also works with single recursion only in C and only in Haskell.

So my question is, is there a way to tell GHC that calling an external C function is tail recursive? I assume that the stack frame comes from a call from Haskell to C, and not vice versa, since the C code very clearly returns a function call.

Answer 1

I find C-Haskell's cross-language tail calls very, very difficult to achieve.

I don't know the exact data, but the C runtime and Haskell runtime are very different. As far as I can see, the main factors of this difference are:

• another paradigm: purely functional and imperative
• garbage collection versus manual memory management
• lazy semantics versus strict

The types of optimization that are likely to survive on language boundaries, given these differences, are close to zero. It could theoretically be possible to invent a special C working environment along with the Haskell runtime so that some optimizations are feasible, but the GHC and GCC were not designed that way.

To show an example of potential differences, suppose we have the following Haskell code

 p :: Int -> Bool px = x==42 main = if p 42 then putStrLn "A" -- A else putStrLn "B" -- B 

A possible implementation of main may be as follows:

• push address A on the stack
• push address B on the stack
• press 42 on the stack
• go to p
• A : type "A", go to the end
• B : type "B", go to the end

whereas p is implemented as follows:

• p: pop x from the stack
• pop B from the stack
• pop A from the stack
• test x vs 42
• if equal, go to A
• go to B

Notice how p is called with two return addresses, one for each possible result. This is different from C, whose standard implementation uses only one return address. When crossing borders, the compiler must take this difference into account and compensate.

Above, I also did not take into account the case where the argument p is thunk, so that it is simple. The GHC dispenser can also trigger garbage collection.

Note that the aforementioned fictitious implementation was actually used in the past by the GHC (the so-called STG push / enter machine). Even if it is no longer in use now, the STG "eval / apply" machine is only a little closer to the C runtime. I'm not even sure that GHC uses a regular C-stack: I think this is not the case using its own.

You can check out the GHC developer wiki to see gory details.

Answer 2

While I am not an expert in the Haskel-C interop, I do not think that a call from C to Haskel may be a direct function call - most likely, it must go through an intermediary to configure the environment. As a result, your call to haskel would actually consist of calling this intermediary. This call was probably optimized by gcc. But the call from the intermediary to the real Haskel routine has not been optimized, so I assume that this is what you are dealing with. You can check the assembly to make sure.