That kind of response starts to sound like "no true Scotsman" pretty darn quick. How do you distinguish between state that is on the stack (which FP still has), state that is on the heap, or state that is on external storage? Are those the same distinctions/evasions that I'd get from the next three FP advocates I asked? I keep hearing about how FP saves us from all that evil mutable state, but every time I look at a program written in a functional language I see plenty of mutable state. Half of it is entangled with control flow, which I do not see as an unalloyed win. When that doesn't suffice, those same programs often resort to externalizing their state (e.g. into a database), often incurring a significant and unnecessary performance penalty just so they can give it a name and treat it as something outside of their program. Aristocrats never like to get their hands dirty, and that's exactly how most FP advocacy comes across. "Let them eat monads." Can't wait for the guillotine.
There are answers to those questions but they do not help you to understand functional programming as a practice. Because you're asking the equivalent of "But how does OOP distinguish stack from heap from storage?" and it's not a practical question.
The answer is something along the lines of: the compiler is usually very different from most, it uses graph reduction and rewriting techniques, garbage collectors optimized for block reusage for all the heap churn that all those function frames would generate if implemented naively (that's why recursion ends up being as fast as a loop); this is my cursory understanding of it. But yes, I would suggest Lisp in Small Pieces and Appel's compiler books.
For practical purposes what is important is that FP is inviting you to program in this world where it is not important to talk about how those things end up getting implemented on the machine. In fact it lets you quickly escape that world whenever possible by allowing you to alias the String type to FirstName for instance; so you can talk about the problem you're trying to solve, and not the computer that will run it. That's the point of declarative programming and FP is declarative.
It's the same in Prolog, I'd think. I'm sure they don't care about how these things are actually being created and destroyed on the machine; the power of Prolog's declarative style is precisely that it allows you to never talk about the machine if you don't want to. That ends up being more general than the usual abstractions of the day that still model themselves after the turing machine.
There's no state to speak of. FP builds the blueprint of the program (one level removed from the way OOP and procedural see things) and gives it to the computer to run it. Now we make the execution order implicit (it's now implicitly threaded through the functions' caller-callee relationships) and we lose the ability to do state (because state depends on ordering things, which can be represented by the semicolon in curly-brace languages). We also lose the ability to do one thing after the other. But although it sounds like a bad thing, it's actually a really good thing, because apparently most bugs live inside semicolons.
> That's the point of declarative programming and FP is declarative.
Declarative programming is a gradient. You can be exposed to a bunch of tedious details in FP and you can abstract over them in OOP. Saying FP is somehow magically declarative (as if that were a thing) leads to profound disappointment when complexity is inevitably encountered.
> It's the same in Prolog, I'd think.
"Cut" it out :) Also see taming space leaks in Haskell.
> There's no state to speak of. FP builds the blueprint of the program (one level removed from the way OOP and procedural see things) and gives it to the computer to run it.
The primary difference between pure FP and OOP is identity: there is no identity to speak of, things don't have names or addresses, they are just values whose equality is determined purely by structure. The inability to name things in FP is a huge drawback, because things actually have names in the real world.
State doesn't depend on ordering. It depends on time; imperative and even functional languages often convolute the two concepts, but not always (see real FRP, not fake FRP ala Rx). Functional languages eschew state are merely eschewing the notion of time, which makes equational reasoning hard; it takes something like FRP to bring time back into the fold by making it explicit. Still, its quite hard to program interactive apps in pure FP given the intrinsic aversion to time.
