- Stateless design. That means no state machine thinking! The client can't assume server state. 
- A uniform interface on resources, similar to CRUD
- Caching support for resource representations
- Navigation to server-named resources via server-controlled hypermedia
The last point is often misunderstood. Despite the fact that we call HTTP client messages requests, it's far more common for programmers and engineers to treat them as commands or instructions (SOAP and RPC illustrate this very well). Many APIs designed to be used over the Web assume that the client decides what should be done and tells the server to do it. This isn't RESTful, and it's not just a quibble: putting the client in control of the interactions puts the client in control of the server's performance and ability to scale.
I didn't understand this when I first read Roy's thesis or when I first worked on WebDAV. I needed examples to make sense of the principle and its utility, particularly when the server does not use HTML and the client is not driven by an active user clicking on links. Thus, this post has examples of non-RESTful navigation and state discovery, as well as RESTful examples:
- The Twitter API: not RESTful in resource naming or discovery
- WebDAV: somewhat RESTful but made a few mistakes in extending HTTP
- Atom: quite RESTful application that sits very lightly and comfortably on HTTP
The Twitter API has fixed resources. Those resources have URIs state which are known to the client in advance. For example, the account profile update resource is named "http://api.twitter.com/1/account/update_profile.format". This limits the Twitter API's ability to rejigger its namespace to add features or to scale by separating resources along a different axis. Next, the client must know a set of permanently-named parameters to be used in a POST request to the URI, to update the profile on the account. The programming model is clearly that twitter client controls the Twitter server by sending commands over HTTP POST. The idea of CRUD is vaguely there (many of the API resources can be retrieved in full with GET, others updated with POST) but diluted by the invention of special update URLs. Caching is possible, at least.
WebDAV is an IETF standard that follows the idea of a limited set of consistent methods well, but doesn't do resource discovery by server-controlled hypermedia. WebDAV set out to provide more authoring functionality such as functions to organize resources and interact with a file system model, so that Webmasters and other Web content creators could have something more suited to Web development than FTP. The WebDAV designers created the PROPFIND request which works a lot like most remote file systems file queries work. In other words, it puts control over querying server resources in the hands of the client. The client determines the scope of the request and the list of properties to be returned, and in the first implementations of WebDAV, the server had little choice but to comply or fail entirely. WebDAV servers had lots of code to handle all the different possible variations on the PROPFIND request, parse its body, and scale differentially based on the different characteristics of the properties that might be requested. All the information to reply to any PROPFIND request that the client might construct, had to be available to any server that might have that request made. Of course, this approach seriously affected performance and scaling.
Atom Feeds was the first standard I saw that did user-free resource discovery via server-controlled hypermedia. An Atom feed is a document offered by the server in XML format, containing links in semantic markup. So, instead of querying the server for blog entries that match a certain pattern, the client simply asks for a feed document via GET. With Atom, the server can precompute or do lazy computation of feed documents, can cache them, can break them down when a feed gets large. This design leaves the scope and detail level of collection membership documents entirely in the servers hands.
More examples can be found at a site that classifies APIs along a continuum of RESTfulness. My quibble with that site is that not all APIs fall along that linear spectrum. WebDAV would have a green box for RESTful identification of resources and a green box for self-descriptive messages, but it would have mixed results for manipulating resources through representations, because collections are not manipulated through representations. It would also have mixed results for using hypermedia "as the engine of application state" because the client makes assumptions about giving resources URIs based on what collection they were put in.
Clearly I need to work on a third post in this series and perhaps a fourth, because I would still like to talk about why constrained devices should operate in the role of the server and provide documents similar to Atom feeds about their state and data. I also have thoughts about a hypothetical framework and how it could be applied in a specific type of constrained device in a way that may not need any dynamic application memory. Hope you can stand to wait.
I think part of what took me so long to understand this was the amount of meaning packed into the word "state". Not only does this mean "what state is the server in, among the states in its state machine", but it also means "what are things named" and "what things exist". So unpacking the injunction that clients shouldn't presuppose state, also means that clients shouldn't presuppose names or existence of resources.