Does REST need a service description language? Great question. And one I would have initially said a most emphatic "yes" to. Now I'd probably so "no". Or more accurately - "you're asking the wrong question".
I think some of the fundamental differences between WS-* and REST are finally beginning to sink in. I've been viewing them as pretty much the same thing, just with different formats and tool support and stuff. But conceptually, they're actually pretty orthogonal.
WS-* is all about messaging. You send and receive messages to and from an endpoint. That endpoint is simply a processor - by and of itself, it means nothing. It's just an address. The interesting stuff is in the message. This tells the service what to do and with what data. The reply message contains the data relevant to the operation - what happened, the returned data, whatever.
REST is all about interacting with resources. You POST, PUT, GET or DELETE resources. The url is all-important - this identifies the resource. As the above post mentions:
The consequence of [this] is that there isn't much to describe; there aren't any methods or signatures thereof to document, since access to resources is uniform and governed by the verbs defined in RFC 2616 (in the case of HTTP, anyway)
You don't need a service description language, because there isn't a service. You're accessing and operating on resources. The service is pretty much implicit in the HTTP verb.
What you do need is a specification for the media type. And preferably in a machine readable format that can be used to generate code for interacting with the resource's data.
This is the question you should be asking.
The Atom Publishing Protocol is one such media type, and there are libraries (not necessarily tools) for working with that. Interestingly, following the small flurry of (*cough*knee-jerk*cough*) reactions to Dare Obasanjo's posts on Google's (out of date) implementation of the APP spec, (and without reading the spec at all!) it looks like APP is able to act as a kind of REST envelope. By which I mean when you POST a new customer to a resource (such as a collection of users), you can get an Atom doc back detailing the url of the newly added resource (customer). My knee-jerk reaction - is APP REST's SOAP?
I'm being kinda oblique with this - I know I need to study the APP before I can really make remarks like this, and I think this example was how to use the Atom Publishing Protocol to publish non Atom (as in RSS-like media type) entries. But if the cap fits...
(One point made that I really like is how the http protocol provides the optimistic concurrency for the updates via the humble etag. Very clever of the http people, and this really helped with defining the REST ideals for me. But it does mean state is maintained at the transport level, rather than at the resource level, something which SOAP has worked around by trying to be transport neutral. Another difference for you to weigh up.)
I don't buy that a client shouldn't know about the URI space of the server. For individual resources, yes. But for collections, or resources such as locks or printers, then surely the client needs to know about these (or how else does it add a new customer? Print?) So a description/discovery language of some sort is needed here too - at the least a means of knowing what media type + verb a particular resource endpoint accepts. Perhaps this is where WADL comes in (but I have to agree with Don Box's analysis of WADL vs WSDL)?
And I don't know how security and authentication is solved, either. Whatever happens, this will demand a spec at the least.
So, with all of this, is REST any simpler than WS-*? Or is it just an orthogonal concept, but just as complex?