The canonical source is Roy Fielding's thesis, in particular chapters 5 and 6.

https://www.ics.uci.edu/~fielding/pubs/dissertation/top.htm

This is a great question. Any answers would be illuminating. I've largely given up on the idea of hypermedia APIs that work like this, because the mindshare and tooling just doesn't appear to be there for it. I've never seen a client library that is based on following rels from a root, rather than generating URLs based on out-of-band information.

> Are there any extant REST API's for which one could programmatically generate a client library based purely upon the root URL and media types?

For a truly RESTful API, the question you ask is somewhat incoherent. A client for a RESTful API consists of two key sets of components: functionality for sending and receiving resource representations to and from locations identified by URIs, and functionality for handling resource representations of particular media types. Assuming you have those, you don't need to "programmatically generate a client library" with the particular base URL of a particular API root, you access a URL that provides resources of any of the supported media types and your off to the races without programmatically generating anything.

Is this possible in practice for real implementations of RESTful principles? Yes, including the one that motivated the articulation of the REST principles, the WWW.

Is REST appropriate for all APIs? Maybe, maybe not. But its probably not useful to anyone to just call every web service that uses HTTP and isn't SOAP "RESTful".