I'm currently working the integration API for Gliffy, which is a REST-based service. The API is fairly stable and we're readying a few ancillary things for release. One of those is the documentation for the API. I found it quite difficult to completely describe the REST services and ultimately ended up creating something that lists out "objects" and "methods", even though the API is not really object-based. For example, the object "Diagram" has a "method" called "list"; to "call" it, you do an HTTP GET to accounts/your account name/diagrams.
The original spec I created to work against (and thus, our initial draft of API documentation) was basically a list of URLs and the HTTP methods they responded to. Not very easy to navigate or understand on a first sitting. Some sort of schema to describe the REST API would have been really helpful (along the lines of an XML Schema). Such a schema could facilitate documentation, testing, code generation.
As an example, consider some features of the Gliffy API: you can list the users in an account, list the diagrams in an account and reference an individual diagram via id. Here's a YAML-esque description of these services: Since "accounts" is the only top-level element, we are saying that every request to this service must start with accounts/. It has one child, which is a variable value for the account name. It is untyped, so any potential string is allowed. That element has two possible children: diagrams and users. diagrams indicates that it responds to the HTTP methods POST and GET. A POST requires the parameter diagram_name, while the parameter version is optional.
A standard format like this could easily be used to generate documentation, expectations, test cases, and even stub code. This format could even be delivered by an OPTIONS call to a resource. I realize there is not much standardization around how to design and implement a REST service, but something like this could at least be a stake in the ground and support a specific method.