What Lisps are you thinking of? In Common Lisp, Scheme, and Emacs Lisp, at least (IIRC), all composite data structures (strings, vectors, etc) are mutable, or can be. The only Lisp I can think of in which "nearly all structures are immutable" is Clojure.