The essence of REST is to make the states of the protocol explicit and addressible by URIs.
Unfortunately, the official REST terminology obscures this fact by using the indecipherable phrase “Hypermedia as the Engine of Application State.”
Whatever it is called, having states addressable by URIs is one of the best parts of the Web. When you do a search on Google, the state of your interaction with Google is returned in the web page of results you get back. That page contains many other links, each of which moves you to a new state. Thus its easy to jump from state-to-state, directly leading to the magic of the Web.
The same thing is true for automated systems as Peter explains. However, I disagree with part of what Peter writes:
With a truly REST based architecture you are free to change just about anything about the disposition and naming of resources in the system, except for a few well known start point URIs. You can change the URI shapes (for example, if you decide that you really hate the currently scheme). You can relocate resources to different servers (for example, if you need to partition you data). Best of all, you can do those things without asking any ones permission, because clients will not even notice the difference.
If I understand him correctly, Peter is arguing that as long as you provide and unchaning “start” link then you are free to change the embedded links in the result pages. I understand what Peter is getting at, as long as the top URI doesn’t change, then clients can pick out the next set of URIs and proceed on their way.
However, I still think this is a bad idea. As Tim Berners-Lee famously wrote, Cool URIs don’t change. A URI is a contract between you and the world – people expect to be able to bookmark it, write it down a napkin, tatoo it on their bodies, and come back many months later and have the URI work. In a scheme like Peter’s, that breaks.
Now, for the work Peter is doing that might be ok – perhaps this system is only for internal consumption. And of course a world of never-changing URIs is nothing but an ideal. In the real world companies go out of business, processes are time-limited (like reserving an airline ticket), etc.
But I still think you should try your best to keep your URIs. If they have to change, then at least redirect the old ones to the new ones, or put a page up saying whatever you were doing is no longer valid.