A conversation definition language (CDL) is disclosed that programmers may use to define sequences of interactions for communicating with a web service to facilitate use of the web service. CDL enables web services provided by different entities to engage in flexible and autonomous interactions. Using CDL, services can communicate by exchanging messages, and the message exchanges are expected to follow a specific pattern (i.e., a conversation). CDL is used to define the conversation, such that a service may expect a particular message in response to transmitting a particular message. CDL includes document type descriptions, interactions and transitions for describing a conversation. The document type descriptions describe the messages that may be exchanged. The interactions describe the type of actions (e.g., receive and/or transmit a message) that may be performed, and the transitions describe the possible sequences of the interactions.