Functional programming is expressing computations as the evaluation of mathematical functions whenever it's possible. Sure, some operations are intrinsically not mathematical functions (like sending data over a network, returning the system date, you name it), but, in general, data structures and algorithms should be implemented as values and mathematical functions on them.
Mathematical functions are mappings from values of a domain to values of a codomain. Naturally, if we want mathematical functions to be a basic building block for programs, we need a rich set of values on which said functions may operate.
Now, here's the thing: Lisp doesn't have compound values. The only values Lisp has are numbers, characters and references to objects. All of them are primitive and indivisible.
“But, catnaroek, what the hell are you smoking? Aren't lists, structs and vectors compound values?”
No, in Lisp, they're not. They're mutable objects whose state at any given point in time may be interpreted as a value in your favorite metalanguage of choice. Maybe if the metalanguage isn't Lisp itself, you can interpret the object's state as a useful value!
In case the above wasn't too clear, let's review the difference between values and objects:
(0) A value is something you can bind to a variable. (At least in a call-by-value language, which Lisp most definitely is.) It doesn't matter, or even make sense, to ask whether “this 2” is different from “that 2”. There is always one number 2, regardless of how many times the number 2 is stored in physical memory. Nor does it make sense to ask whether 2 will suddenly become 3 tomorrow. 2 and 3 are always distinct values.
(1) An object is an abstract memory region. Every object has an identity and a current state. The identity is always a primitive, indecomposable value. The state may be compound, but it isn't always a value. (This depends on the language.) Even if the current state is a value, the state at a later point in time might be a different value. Objects with immutable state are largely impractical - why bother distinguishing the physical identities of entities that never change?
Now it becomes perfectly clear that, while Lisp has compound objects, it doesn't have compound values. Sadly, without compound values, you can't have functions taking compound values as arguments, or returning compound values as result. Since compound entities are unavoidable in practical programming, this means you pretty much have to use objects.
“But, catnaroek, what if we encode compound values as Gödel numbers?”
Hah! Have fun with that!
---
As an exercise for the reader, for each of the following languages, determine whether it's functional or not: Scheme, Racket, Clojure, Scala, F#, Erlang, JavaScript. Justify your answers.