(who is in fact quoting a medieval author refering to their reliance on the ancient philosophers like Aristotle!)
Introduction
Relational semantics is an extension of Denotational semantics where the
denotation of a component of a language can be either a function (total,
many to one) or a relation (any to any). Here I show that the result
unifies the natural operational semantics with the denotational method
giving simple, structural, natural and compositional semantics can be if
one uses mathematical relations.
Natural operational semantics is defined by giving a set of derivation rules and axioms for expressions written like this < S, s > -> s. The formula means that the statement S in state s terminates and leaves the system in state s'. The axioms and rules are not difficult to accept. But they are not easy to reason with and are not compositional. On the other hand denotational semantics gives a set of equations which define a set of partial functions D\[S\] that map s into s'. Denotational semantics uses from Dana Scott's work on complete partial orders and fixed points. For more see Nielsen and Nielsen 92
In my approach Relational Semantics you present a set of equations that define a map from each statement S into a relationship between s and s'. The equations define the relationship associated with S in terms of the components of S. Thus we get a set of compositional equations for the natural semantics. Indeed the equations are expressed in an extended form of Backus-Naur-Form. To show this I define the syntax and semantics the classic "While" Language used in all theoretical work and textbooks of programming language semantics: [ grammar_of_While ]
Relations
This form of semantics benefits from the well developed theory and calculus
of binary relations. I exploit the isomorphism between relations and sets
of pairs, and the fact that functions (partial or total) are special kinds
of relations. The key concepts and notations are listed below:
[ Calculus of Relations ]
The set of relations on a set is a ready made domain or complete partial ordered set in the following sense. First, the set of binary relations on a set X is a partial order under inclusion(==>). The relations form a poset [ poset in math_21_Order ] Second, there is a unique bottom and top element: the bottom(greatest lower bound) of the poset is the null relation and the top(least upper bound) the anything-to-anything relation. Finally, given any relation, R on X, the Kleene sequence:
Syntax and Semantics
Method
I use a generalized version of BNF to define Syntax and Semantics called
XBNF. The syntax is defined in a form close to traditional EBNF. The
semantics is defined by a grammar of functions and relations. The details
are below:
[ XBNF ]
I use the symbol m to indicate denotations: m(C) indicates the "meaning of C". The symbol m indicates the function that maps C into m(C). For each syntactic category Syn, there is a set of meanings - a semantic domain Sem say, and m maps each element of Syn into and element of Sem:
The semantic domain is determined by the Syntax of the argument to which m is applied: For example m("101") gives a number but m("while 1<x do x:=x-1") is a relationship between describing what can possibly happen. See [ CoProducts ] for the justification of this idea.
Two items C1, C2 in the same syntactic category are equivalent if and
only if m(C1) = m(C2). Items in different syntactic categories can not
be equivalent.
Abstract Syntax of While
After Neilsen & Neilsen 92.
Suppose Var={"x", "y" , "z" } and F:="(z:=1; y:=x); while ( 1 <= y ) do ( z:=z*y; y:=y-1 ))", then F \in Stm.
Terminology
The following words are used for talking about the While language:
Semantic Domains
In the following I assume that we have the whole of abstract algebra
available to us when we wish to define how a program behaves. The
alternative is to spend time re-inventing wheels. The necessary algebras
are listed in this section. They are used in the following section:
[ Semantic Equations ]
Numbers
I assume that a number is in a ring with addition, subtraction,
multiplication, zero, and unit - with the usual rules and assumptions:
We normally assume some extra rules: Here I need there to exist a distinct number
This is so that I can formally define the meaning of a binary (base 2) Num as a distinct element of the ring number.
Normally the numbers are taken to be the integers, however see Hoare 69, C.A.R. Hoare, An Axiomatic Basis for Computer Programming, Commun ACM V12 n10 Oct 69.
Variables
In the While language without declarations, each identifier always
identifies the same variable. I introduce a function that associates each
symbol in Var with a corresponding name of a field in record structure
(or labeled tuple). The set of all possible records is called the State:
This is not the traditional approaches where a state is a function mapping elements of Var into current values, or where a state associates Vars with locations and locations with current values..
Example of a State Space
Suppose Var={"x", "y" , "z" } then State = ${ x,y,z::number }, and a
typical state would be State(x=>1, y=>2, z=>3). The function
m:Var->{x,y,z} then maps "x" into x, "y" into y, and "z" into y:
Expressions
The semantic domain for Aexp is typically those of numbers - values in
the target algebra. However because I start from assuming that we have an
abstract algebra (not just an abstract data type) we can associate each
Aexp in While to an expression in the algebra of number -- in the set
expression(number). We can now use these expressions in predicates and
get simpler rules defining the behavior of assignments.
Change of State
The heart of relational semantics is the natural model for change: a
relation between two states, before and after:
A relation R:Change is [ determinstic ] when for each s there is no more than one s' such that s R s'. A relation is [ total ] when for each s there is at least one s'. Functions are both total and deterministic. Partial functions are deterministic but not total. One to one relations are determinsistic, and so are there inverse or converse.
Exercise: Show that all conditions are deterministic. Show that all Actions are deterministic.
Exercise: Are all Actions functions? Are any Conditions functions?
. . . . . . . . . ( end of section Semantic Domains) <<Contents | Index>>
Semantic Equations
Semantic Equations for Num
These are a simple introduction to the method, not a useful notation.
For n:Num, m(n)::number.
Exercises on the Semantics of Num
Exercise: Is m on Num a total function or a partial function? Is it a
one-to-one function or many-to-one function? If many to one derive a
congruence so that strings modulo the congruence are semantically
equivalent.
Semantics of Var
Example of Semantics of Var
Suppose Var={"x", "y" , "z" } then State = ${ x,y,z::number }, and a
typical state would be s=State(x=>1, y=>2, z=>3). The function
m:Var->{x,y,z} then maps "x" into x, "y" into y, and "z" into y:
Hence, m("x") =x and s.m("x")=1 and s.m("y")=2 and s.m("z")=3.
However, m("x+y") is not 3 but x+y. In state s=(x=>1, y=>2, z=>3), though, x+y does have the value 3. By mapping strings in While into mathematical expressions (rather than values) we can use the algebra of the expressions to reason about Aexps.
Exercises on Semantics of Aexp
Exercise: Is m on Aexp a total function or a partial function? Is it a
one-to-one function or many-to-one function? If it is one to one prove
that it, otherwise find a equivalence relation so that semantically
equivalent Aexp's are equivalent.
Exercise: How do you prove the following Aexp are equivalent?
Exercise: Do these semantics force the implementor to provide infinite precision arithmetic or not? Prove your claim.
The Boolean operations (and,or) on predicates define conditions that are related to the set theoretic operators of intersection and union:
I define m:(Aexp Op Aexp)->Condition in terms of two auxiliary functions:
This definition constructs a predicate on the state, and this predicate defines the set of states that satisfy the relationship. The underlying formalism is described below: [ Dynamic Predicates ]
Example of Semantics of Bexp
Suppose Var={"x", "y" , "z" } then State = ${ x,y,z::number }, and a
typical state would be s=State(x=>1, y=>2, z=>3). The function
m:Var->{x,y,z} then maps "x" into x, "y" into y, and "z" into y:
So "x>y /\ z<2" means the relation that does not change states and where (x>y and x<2). So
Exercises on Semantics of Bexp
Exercise: Is m on Bexp a total function or a partial function? Is it a
one-to-one function or many-to-one function? If one to one prove that it,
otherwise find a equivalence relation so that semantically equivalent Aexp's
are equivalent.
Exercise: Show that for all b, m(b) is a Condition. Prove that it is there deterministic but not total. For which Bexp is m(b) a function? and which function is it?
Relational Semantics of Stm
The following relational semantics of While is a natural and denotational
semantics. The meaning of a statement is a relation that is defined to
hold between s and s' precisely when the statement terminates in state
s' when started in s'. It seems possible to develop a set of
relational equations that define the structural operational semantics of
a statement - where the relation holds between successive states as the
program executes. To find out more see
[ Structural Operational Semantics ]
below.
Notation: Id, ;, |, do, no, ;, etc. are from the calculus of Relations, see [ Calculus of Relations ]
Note. These form a compositional definition: the meaning of each statement is expressed in terms of the meanings of its components in the syntax. In other words the definition is driven by the structure of the data.
Example of Semantics of a Program
When Var={"x", "y" , "z" } and F="(z:=1; y:=x); while ( y > 1 ) do (
z:=z*y; y:=y-1 ))".
So
Exercises on the Relational Semantics of Aexp
Exercise: Is m on Stm a total function or a partial function? Is it a
one-to-one function or many-to-one function? If many to one derive a
congruence so that modulus the congruence semantically equivalent, ,
otherwise prove that the function is one-one.
Exercise: Show that all assignments are Actions.
We say that a statement S is deterministic if m(S) is a deterministic relation.
Exercise: Show that x:=a and skip are deterministic. Show that if the components of a sequence, selection, or iteration are deterministic then so are the compound statement.
Exercise: From the previous exercise, can we deduce that all While programs are deterministic? Can you explain your answer? Can you present a formal proof of your answer?
Exercise(For Mathematicians) : In how many different senses is m a homomorphism between two systems? Is it a isomorphism, monomorphism, homeomorphism, etc.
Exercise(Advanced) : Suppose one started by defining m as function mapping some strings into a family of disjoint meanings, as above. Further suppose that every partial definition is compositional. Show that a context free grammar can be deconstructed from the functions. Show that m is total on the language of your deconstructed grammar.
. . . . . . . . . ( end of section Semantic Equations) <<Contents | Index>>
. . . . . . . . . ( end of section Syntax and Semantics) <<Contents | Index>>
Conclusion
In the above collection of semantic equations m is nearly always
distributed to all the parts of the construct being assigned a meaning. A
few examples would show that every construct in While is mapped directly
into a simple expression in the calculus of relations.
I conclude that we could use the calculus of relations as our ultimate semantic metalanguage. I claim that, relations even form an uniquely interesting and powerful programming language of their own. They are interesting because they are the only piece of existing mathematics is already a programming language. They are powerful because they can express concurrency and non-determinism.
. . . . . . . . . ( end of section Main Text) <<Contents | Index>>
Footnotes
XBNF
EBNF uses
The general XBNF form is For D, term(p)::T=e.
where D declares the names and types of the parameters p (if any) and T is the type. In theory however this is the same as term:: P->T = fun[D](e).
The notation term::T associates a type with a term.
. . . . . . . . . ( end of section XBNF) <<Contents | Index>>
The defining property of do(R) is a second order property that x do(R) y iff all invariant(or closed) sets under R that contain x also contain y. Whitehead & Russell Circa 1930
For more information see: [ logic_41_HomogenRelations.html ]
(deterministic): A relation R is deterministic if for all x, there is
no more than one y such that x R y.
(total): A relation R is total if for all x, there is at least one y
such that x R y.
For more information on the calculus of relations see [ Relations in math_10_STANDARD ]
. . . . . . . . . ( end of section Calculus of Relations) <<Contents | Index>>
State Space
The formal model usually presented of a variable is a function s:Var->Val
for some set of values. Thus if v:Var then s(v) \in Val. I assume
that there is a labeled Cartesian Product or tuple where each v:Var has
an associated label l and if 's:State' then s.l \in Val indicates the
value of v in state s. I claim that this is effectively a simple
change of notation.
The notation is described informally in [ intro_records.html ]
. . . . . . . . . ( end of section State Space) <<Contents | Index>>
Dynamic Predicates
A dynamic predicate is a predicate that contains constants and variables
(labels) from the state space, where a predicate is a formula that is
either true or false. One special notation is added: if a variable appears
with a prime then that variable is said to be dynamic in that predicate and
may change. Other variable in the predicate are said to be static and may
not change. The occurrences of dynamic variables without a prime indicate
the old values of the variable and the occurrences with a prime indicate the
new values - values in the
new state. For more see
[ math_14_Dynamics.html ]
Conditions as Static Predicates
When a predicate has no dynamic variables then it expresses a condition - a set of states that will not change, but can only be satisfied by some states and not others (in general). For example x+y>0 is satisfied by the set of states { s || s.x+s.y >0} and defines the relationship { s,s' || s=s' and s.x+s.y >0}.
Assignments
The formula
General Form
This section goes beyond the goal of expressing the semantics of a simple
programming language.
It is worth developing a theory of general dynamic predicates because they form a precise yet concise way of documenting and specifying code.
. . . . . . . . . ( end of section Dynamic Predicates) <<Contents | Index>>
CoProducts
In this document I define a function m piecemeal by giving a series of
definitions each defined on a subset of the set of strings of characters.
In traditional semantics a different symbol would be used for each case.
Each piece of m however can have different type of codomain. For
example, if the strings are divided into As and Bs then m:A->X and
m:B->Y. To justify mathematically the abuse of notation of having a
single symbol I have to argue that m is a well defined function from a
domain to a (single) codomain. We know from Ada and C++ that a function
can be overloaded unambiguously in this way... as long as A and B do
not overlap. Since A and B are both sets of strings it is clear that
there is a common domain A|B. However the two images of these
sets m(A), m(B) are different types of things
- numbers vs sets of states for example. To
maintain strong typing and allow the use of single symbol I suppose that
for any pair of types T1 and T2 there exists a different type called
the coproduct
that a the theoretical model of the discriminated union (Ada), union(Algol
68 and C), or tagged record(Pascal). The theory of such coproducts is part
of category theory.
[ math_25_Categories.html ]
. . . . . . . . . ( end of section CoProducts) <<Contents | Index>>
Structural Operational Semantics
Here I explore a less abstract and more detailed form of semantics. I want
to see how a relation between successive states can be defined using the
calculus of relations.
Here a change is expressed in terms of a change in two components: the statement being executed and the state in which the execution starts. This is called a configuration and is written: (S,s)
The configurations of form ( done, s) are called terminal states and indicate that the program has terminated:
In texts (done, s) is often written s.
where x'=e is defined above: [ Dynamic Predicates ]
For S1,S2,S3:Stm, s1,s2:State, if (S1, s1) Next (S3, s2) then (S1 ";" S2, s1) Next (S3 ";" S2, s2).
For b:Bexp, S1,S2:Stm, s1,s2:State, if m(b)=Id then ("if" b "then" S1 "else" S2, s1) Next (S1, s1). For b:Bexp, S1,S2:Stm, s1,s2:State, if m(b)={} then ("if" b "then" S1 "else" S2, s1) Next (S2, s1).
For b:Bexp, S:Stm, s:State, ("while" b "do" S, s) Next ("if" b "then" "(" S";" "while" b "do" S")" "else" "skip", s).
Exercise on Structural Operational Semantics
Prove that for all S:Stm, s1,s2:State, (S,s1) do(Next) (done, s2) iff s1
m(S) s2.
Note: This is true for While, but is not true for some extensions of While.
It might be wondered why it is worth have a more complex and less abstract way of stating the semantics of a programming language. One reason is that Natural semantics can not express the idea of a single step in a program and so can not define the idea of interleaving the steps from two parallel programs.
An interesting question for further research is to find a set of compositional equations for the Next relation to replace the derivation rules for ";", "if", and "while".
. . . . . . . . . ( end of section Structural Operational Semantics) <<Contents | Index>>
. . . . . . . . . ( end of section Footnotes) <<Contents | Index>>
. . . . . . . . . ( end of section Relational Semantics of The While Language) <<Contents | Index>>