I read tons of posts, questions and answers on the REST vs SOAP debate. I read a few REST supporters that claim that "well designed" REST Web Services are self explanatory and hardly need any documentation.
Can anyone point me to such a Web Service? Preferably a somewhat complicated one.
Here is an example of a complex API for a network video camera... I recommend looking at the VAPIX HTTP 3.0 API. It is pretty straightforward to follow, assuming you are familiar with the terms. Granted, it is about 60 pages, but much of it is just boilerplate to get the reader familiar with using a network API.
The Yahoo! Weather Feeds are an example of a simple, RESTful way to pull information from a service.
There are also examples of REST API's that essentially send XML-structured data back and forth. While these are technically REST, if you are going through the trouble to define an API using XML, I'd consider using web services.
I found Netflix's documentation to be very good and help you understand what goes into designing an API. The API is not perfect, but I think it is a good combination of practical and thoughtful.
The idea of a self documenting REST API is that one can be given a single entry point into a system and be able to discover all functionality available through the returned documents, combined with understanding of standard usage of the REST verbs (GET, PUT, DELETE). So that if you pulled up a list of employees from a RESTful system, the individual entries would point to the URL of that entry and the employer field would point to the URL for the employer. Do a search on HATEOAS for more details. But you might call "/employee" on a service and get:
<employees>
<employee id=132 name=bob url="/employee/132" employer="/employer/176"/>
<employee id=179 name=carl url="/employee/132" employer="/employer/122"/>
</employees>
You could view the complete employee record at /employee/132 and view the record of their employer at /employer/176. By convention, if you had permission, you could update the employee bob using PUT against /employee/132 or create a new employee with a POST to /employee. The content types accepted are queryable through the interface, also (using HEAD, I believe).