> How in this more expressive language would you represent pure functions or deeply immutable datastructures if it only offered flexible/mutable ones
With a function that doesn't cause any mutations and a set of classes/interfaces that offer no mutator methods.
My point is that you don't need to be able to have the compiler enforce constraints in order to express an algorithm—you just write the code. Having the compiler enforce constraints is often helpful but comes with decreased ability to express other types of algorithms that rely on breaking those constraints, so the language as a whole is less expressive. In order for a programmer to accept those limitations there need to be clear advantages, and the advantages that functional programming proponents have put forward so far haven't been persuasive to most developers.
By the definition I'm working with, the most expressive languages are the ones that offer the fewest constraints to what the code can do—LISP would be a top contender. Expressivity isn't the highest virtue, but it is valuable and programmers don't give it up unless they can be persuaded it will be worth it.