[technomancy]

Of course, it all depends on definitions; in this case things are fuzzy. Functional programming means a lot of things to a lot of people. "Supports higher-order functions" is necessary for pretty much any definition of FP, but it sets a very low bar.

My definition would have to include "supports pure functions idiomatically", which means it must be practical to write the bulk of your programs without side-effects. This is really only possible if you have persistent data structures that can efficiently share structure internally; otherwise avoiding side-effects involves lots of wasteful copying. (See http://technomancy.us/132 for an explanation of persistent data structures.)

Of course, if you asked a Haskell programmer, they would be mortified that you would leave monadic computation out of your definition, so no single definition is going to please everyone.