I've been contributing to the Clojure community lately. My experience working with hash-maps as the primary data structure has been entirely liberating.
At my startup, we've got an app with Sinatra services, a Rails API, a Node.js web frontend, and Backbone client code. JSON gets passed between them. Being forced to encode keys as strings is a mild annoyance that Clojure's reader syntax avoids, but the real issue is that I've got raw JSON, Javascript domain objects (Backbone.Model), Ruby models (ActiveRecord), and Ruby hashes (hashie/mash/similar). Each has their own idiosyncrasies and interfaces. Of all of them, the raw JSON is most pleasurable to work with. CoffeeScript & Underscore.js roughly approximate 10% of the awesomeness that is Clojure's core data structures, including maps, sets, vectors, and lazy-seqs.
ActiveRecord, for example, makes it super easy to tangle a bunch of objects up. If we had a big bag of functions, they could operate on in-memory hashes, or they could operate on database rows, or they could operate on the result of an API call. It would be so much simpler to reuse code between our main Rails API and our Sinatra service. And we could one-for-one translate functions for non-Ruby services. Instead of requiring a crazy tangled ness of polymorphism and mutable state.
> Every non-trivial program is going to have to define abstract datatypes
Absolutely true. However, Clojure has taught me that you really aught to only define a very small number of those. It's been said that it's much better to have 100 functions which operate on 1 data structures, than to have 10 functions that operate on 10. Clojure's get-in function for example: (get-in some-hash [:some :key :path]) is glorious compared to Ruby's some_hash[:some][:key][:path] because you don't need to go monkey patch in a get_path method. And even if you did monkey patch that in, it won't work for the some_object.some.key.path case, unless you got fancy with object.send and yet another monkey patch.
Look at some of the substantial pieces of Clojure code out there. They may only define a small handful of data structures, but most of those are even defined with defrecord, which produces a hash-like object, which all those 100s of functions work on. The rest are tiny primitives that compose in powerful an interesting ways.
> I'm not sure how embedding and dispatching on a type tag in a hash is any better than using the more explicit support for dynamic dispatch you find in typical OO languages
Because you may want differing dispatch & single-dispatch inheritance doesn't let you change your mind as easily. Those dynamic dispatches in Ruby/Python whatever are simply hash lookups anyway. You'll get the same performance either way. Look at the output of the ClojureScript compiler for example. Most code paths dispatch on :op, but you could just as easily dispatch on some bit of metadata, maybe the [:meta :dynamic] key path to have a function that runs differently on static vars than dynamic ones. People are also working on advanced predicate dispatch systems.
> The real problem with most OO is that it mashes a lot of interdependent, mutable state together.
That's a real problem. But it's not the real one :-)