When you say having no side effects is not a FP characteristic, then I say Hindley-Milner type inference, option types, pattern matching and algebraic data types aren't either. Many functional programming languages aren't even statically typed.
I'd go a step further and say that controlling side effects, as a consequence of pure-functional design, is a bigger part of FP than any given type system. But hey, what do I know, I just did the SICP exercises a decade ago and forgot about it afterwards.
You're saying that the type system has something to do with functional programming.
I'm saying that if Scheme, LISP and Haskell are all functional languages, obviously the type system is besides the point -- they're radically different in that aspect. Functional programming is about functions.
I'd say Scheme and Haskell are functional languages, as they emphasize programming in a functional style: Composing functions to process values. "Value-oriented programming".
I never understood why anyone classified Lisp (typically CL) as a functional language, as it isn't any more functional than Python, Ruby or Perl.
