The connection between Axiomatic and Denotational Semantics of Programming Languages

Abstract

Systems of proof rules are sometimes called “axiomatic semantics”, and are developed from intuitively or explicitly known, e.g. denotational or operational, semantical models. Reversely, it has so far not been clear under what conditions systems of proof rules actually do specify the semantics of a programming language. This is clarified by the following results:

• 1. There are conditions s.t. a system of proof rules is a syntactic specification of a predicate transformer semantics (PTS).

• 2. Denotational semantics (DS) and PTS may both constitute forward or backward semantics, depending on whether initial states resp. pre-conditions are transformed into final states resp. post-conditions, or reversely.

• 3. Any proper axiomatic semantics has the ws-property, i.e. any pre- is transformed into a strongest post-condition, and any post-condition is transformed into a weakest pre-condition.

• 4. [ws-Lemma] For any pre- resp, post-conditions P.Q which are tight w.r.t. a construct cs: P is weakest pre-condition of Q iff Q is strongest post-condition of P (w.r.t.cs).

• 5. Forward DS and forward/backward PTS can be transformed into each other so that DS and PTS are equivalent specifications of semantics.