[Haskell-beginners] Compiling C into Haskell

[Brent Yorgey]

On Tue, Apr 13, 2010 at 05:39:04AM -0700, Hein Hundal wrote:
> Thanks Allan!
>  
>    I was hoping the C-Haskell mix would work.  I am glad to hear that you have good things to say about it.
> 
>    My main reason for thinking about the C-to-Haskell compiler was to address the question "Say you had a C program.  Can you always convert it to Haskell in such a way that the compiled Haskell is not too slow and does not need too much memory?"  Supposing that too slow means slower than 1/4 the speed of C and too much memory means twice the memory of C.  
> 
>    Do you know the answer to this question?

My guess is that the answer is technically "no".  If I recall
correctly, there are some imperative data structures where the best
known time complexity for a functional version is worse than the
imperative version by a factor of (log n), so in that case you
wouldn't be able to stay within a constant factor of C.

However, I think in practice the answer is usually "yes"; but it might
be hard to do it via a mechanical compilation. Idiomatic (and fast)
Haskell is often organized very differently than corresponding C code.

So if you want to know whether you will necessarily be taking a big
performance hit in moving from C to Haskell, the answer is usually no,
if the translation is sufficiently intelligent --- which a
straightforward C-to-Haskell compiler is (probably) not.

-Brent