I've wrote about the difference between imperative programs and functional ones (here, trying to explain why an imperative programmer might find functional programming difficult).

The main differences (do vs be, reversed order of reading, and heavy use of first class functions), make a quite sharp divide. Way sharper than other divides, such as "Object Oriented" versus the rest (though Alan Kay's original vision is probably more distinguishable than the current C++/Java vision).

Now when talking about programming an FAI, the most probable course of action will be to translate the math of FAI into a program. One thing I noticed about math formalism outside the specific field of computer programming, is that most formulations are either stateless, or explicit about state. When at some point we say X = some long expression, we know it won't change until the end of the assignment. The math I know tend to be functional by default.