Semantics of programming languages

In theoretical computing , formal semantics ( programming languages ) is the study of the meaning of computer programs seen as mathematical objects .

Link with linguistics

As in linguistics , here the semantics designate the link between a signifier, the program, and a signified, mathematical object that will depend on the properties that one wishes to know about the program.

The link between the signifying language (the programming language ) and the signified language ( Hoare logic , automata , or other) will also be called semantic .

Common semantics of a programming language

The most commonly used semantics to make sense of a programming language are the operational semantics , the denotational semantics and axiomatic semantics .

Operational semantics

In Operational Semantics 1 , the meaning of a program is the sequence of states of the machine running the program. In other words, a program is considered as the description of a state transition system . In this semantics, the programs:

a = 1; b = 0


a = 1;
b = 0

are equivalent (have the same meaning), but the program:

b = 0; a = 1

is not equivalent to them (even if in the end the result is the same, the actions do not take place in the same order).

We can abstract this semantics by observing only a part of the memory of the machine, or for example by observing only the interactions of the program with the outside (the trace of the program).

Denotational semantics

Main article: Denotational semantics .

Initiated by Christopher Strachey and Dana Scott , denotational semantics 2 is an approach in which a mathematical function called denotation is associated with each program, and represents in a way its effect, its meaning. This function takes for example the state of the memory before execution, and results in the state after execution.

In this semantics, all the examples given above for operational semantics are equivalent, but the program:

a = 1;
b = 1;

is not equivalent to them.

There are several variants of the denotational semantics, one of the most famous of which is the denotational continuation semantics , which instead of associating a function with a program that transforms the memory, associates a function that transforms the continuation (the future ) of the machine after execution of the program in the continuation before execution of the program. In other words, the denotational semantics by continuation runs counter to the program, it considers what happens after an instruction to deduce what must happen before this instruction 3 .

One of the important aspects of denotational semantics is the property of compositionality  : the denotation of a program is obtained by combining the denotations of its constituents.

Axiomatic semantics

Main article: Axiomatic semantics .

In axiomatic semantics 4 , the program is no more than a transformer of logical properties on the state of memory: if we have p true before execution, then we have q true after. We are no longer interested in the precise state of memory as long as we know whether the property holds.

If the property we are interested in is whether a and b are positive after execution of the program, then all the previous examples are equivalent in the sense that regardless of the state of the machine before program execution, the property in exit holds. What we note in Hoare’s logic  :

{\ displaystyle \ {{\ text {true}} \}}a = 1; b = 0{\ displaystyle \ {geq 0 \ land b \ geq 0 \}}

Relationship between different semantics

These three semantics, as the examples suggest, are not completely independent of each other, in fact:

  • two syntactically equivalent programs are operationally so;
  • two operationally equivalent programs are denotationally;
  • and two denotationally equivalent programs are axiomatically.

But the reciprocals are false.

Thus one can hierarchize the semantics by saying that a semantics is the abstraction of another if and only if two equivalent programs in the last are also in the first one. These relations have been formalized by the theory of abstract interpretation .

We can complete this hierarchy ( partial order ) on the semantic equivalences, by placing at the top the identity (two programs are identical if and only if they are the same sequence of characters), and at the bottom, the abstraction the most Coarse so-called chaos , where any program is equivalent to any other program.

Be the first to comment

Leave a Reply

Your email address will not be published.