IMHO it's better to use the positive definition "FP allows you to treat functions as data" than the negative one "FP is without side effects".
If you insisted on the negative definition then even most officialy functional languages would not be functional. And if the FP was only about the restriction it would not be very attractive ;-)
For me FP means two things. Higher order functions+closures (which is something we have in Perl) and a good general type system with real polymorphism (map: (( 'a -> 'b ), 'a list) -> 'b list) (which is something that we don't have in Perl, but since we have no types I don't feel restricted).
P.S.: It's a shame Microsloth did not steal either from FP for it's .Net :-(
C# still feels like something 30 years old :-(