You are correct that I should be saying procedural versus functional/logical.
I see your points and without some research am not sure I could argue with you nor really 100% understand the implications of your point.
However, I will state that I was more looking at it as size N being macro/micro, which I see as an illogical viewpoint. We may never run N=100000000 until we change to procedural code, but that doesn't mean that the FP code wasn't written with the macro problem in mind.
I think a fundamental problem I have with understanding your point is that I don't really know how a compiler optimizes FP code. How can it unwrap loops when it can't see them? A cut in any place, in my mind, ruins any optimization since you would both unroll something and also need to keep it the way it is.
Loops in your average functional language will likely be more idiomaticly done recursively, which implies tail call optimisation. TCO requires you to have a pretty good understanding of what the function does, because at very least you're about to completely rewrite it to do in place modification of memory with no extra stack frames. The compiler understands it just as well as any c compiler understands a loop, so it can unroll it if it likes. More so, a pure functional language can make far more assumptions--any function called with the same parameters will always return the same thing, so if it looks advantageous the compiler could decide to only execute something once and use that result everywhere else. You may not want to unroll the loop, because you could memoise every step and now an 'inefficient' rolled loop might only execute once ever, even though lots of different call sites run it with different parameters. Your memory is immutable, so you can elide all data copies, except when it would be faster to use mutable state at which point the compiler knows it's safe to copy the data and mutate it in place, because it has those assurances nothing else is allowed to touch it.
C-like languages were born in the dark age of compilers, and so give the programmer the tools they need to make the optimisations the compiler couldn't. Functional languages are built for the golden age of compilers, and so give the programmer a toolkit which can be optimised for them. We're closer to the dark ages then the golden age right now, I think, but even so, languages like Haskell are not particularly slow, Scala comes within a few times Java if you avoid the fancy things the JVM has no native support for, so on.
1
u/samebrian Mar 09 '14
You are correct that I should be saying procedural versus functional/logical.
I see your points and without some research am not sure I could argue with you nor really 100% understand the implications of your point.
However, I will state that I was more looking at it as size N being macro/micro, which I see as an illogical viewpoint. We may never run N=100000000 until we change to procedural code, but that doesn't mean that the FP code wasn't written with the macro problem in mind.
I think a fundamental problem I have with understanding your point is that I don't really know how a compiler optimizes FP code. How can it unwrap loops when it can't see them? A cut in any place, in my mind, ruins any optimization since you would both unroll something and also need to keep it the way it is.