Moreover

There are a couple threads that could be tied together.

Radovan Janecek writes about REST...

A resource has to return not only 'data' but also a contract that tells how to work with this resource further - i.e. what to POST and when. In case of browser-based applications, this is somehow solved by HTML. Otherwise, I think WSDL can be used.

I don't think this is quite so. The browser is interpreting representations at runtime. WSDL will present a description of the shape of the runtime data, but the application using the WSDL will still have to do the interpreting.

The choice is definitely not confined to a browser interpreting HTML or something else interpreting WSDL. No, there are many potential examples of other runtime interpreters. I think a good example is a "workflow engine" that interprets workflow descriptions. Let's say a workflow is stored on a server somewhere. The engine GET's a description of the workflow. Let's say the representation is a collection of RDF triples, some of which describe the orchestration of the workflow. Others describe the procedures being orchestrated, and still others may describe some of the work-in-progress.

The workflow engine, like the browser, is a runtime interpreter of state representations. The browser interprets HTML pages. The engine interprets workflows. The browser understands HTML. The engine understands the orchestration triples. When a procedure is encountered the engine interprets that by invoking the procedure at the given location (or perhaps just abstractly "on the grid") with the given work-in-progress triples as parameters of the procedure.

The RDF triples are runtime state representation, analogous to HTML. The workflow engine is the runtime interpreter, analogous to the browser. An infinite variety of runtime interpreters is imagineable. Mapping engines to interpret locations, ledgers to interpret sequences of transactions, purchasing agents to interpret items for sale.

So are there an infinite variety of state representations. The interpreters will vary by purpose, but their interfaces should be fairly constrained (i.e. RESTful). The state representations will be more broadly useful if they too are somewhat constrained, i.e. if your restful interpreter and mine can understand some of the same state then they can cooperate. This is the idea behind these interpreters sharing partial ontologies or even being able to translate parts of one to another.

Meanwhile Mark Baker quotes Hugh Winkler and then notes...

"When you sit down to write a description language for REST services (a IDL or WSDL for REST), you discover that doing so is unnecessary." Absolutely. The application state machine needs describing (at runtime), not the services (at design time).

The web is a dynamic, distributed runtime. We need to act like language designers and we need to understand dynamic languages.