gotchaMinor
What's the difference between: operational, denotational and axiomatic semantics?
Viewed 0 times
denotationalthewhatsemanticsaxiomaticdifferencebetweenandoperational
Problem
Recap of the terms from the dictionary:
Wikipedia's main article about: semantics.
Operational semantics:
This says that the meaning of a language construct is specified by the computation it induces. It is of interest how the effect of a computation is produced. My understanding of this is that this basically describes the meaning of all the operations involved in a program (from the most basic to the most complex).
Examples:
arithmetic operations:
assignment operations:
augmented assignment operations:
etc.
Denotational semantics:
This says that meanings are modelled by mathematical objects that represent the effect of executing the constructs. It is of interest only the effect of a computation, not how it is produced. My understanding of this is basically that it's related to mathematical functions, which take
- semantics: the study of meaning in a language (words, phrases, etc) and of language constructs in programming languages (basically any syntactically valid part of a program that generates an instruction or a sequence of instructions that perform a specific task when executed by the CPU)
- operational: related to the activities involved in doing or producing something
- denotational: the main meaning of a word
- axiomatic: obviously true and therefore not needing to be proved
Wikipedia's main article about: semantics.
Operational semantics:
This says that the meaning of a language construct is specified by the computation it induces. It is of interest how the effect of a computation is produced. My understanding of this is that this basically describes the meaning of all the operations involved in a program (from the most basic to the most complex).
Examples:
arithmetic operations:
1 + 1, 10 ** 2, 19 // 3 etc. In this case it analyzes the meaning of the steps involved in producing a result given n operands and n operators. This can be further boiled down to what each operand means (so in my examples each number is defined in the domain of natural numbers [1, 2, ..., n], etc.assignment operations:
x = 5, y = 5 2, z = 10 2 // 3 * (99 + 1024) etc. In this case it involves an evaluation of the value of the mathematical expression on the right and assigning it to the identifier on the left.augmented assignment operations:
x += y, z *= t etc. In this case it involves an evaluation of each identifier once, and performing an arithmetic operation first, followed by an assignment operation last.etc.
Denotational semantics:
This says that meanings are modelled by mathematical objects that represent the effect of executing the constructs. It is of interest only the effect of a computation, not how it is produced. My understanding of this is basically that it's related to mathematical functions, which take
Solution
I think your examples show you do somehow understand the basic points of the several styles of semantics. Still, note that the whole point of having a semantics of a programming language is to have a formal, mathematically rigorous description of the program behavior. That inherently involves math and several formulae -- one can't really do without math. Math is used as the foundation of every science, and computer science is no exception to this fact.
You are correct when you say that the denotational semantics for a program is, very roughly, a function from its input to its output. E.g. "this program computes the factorial function on naturals". Things start being more complex here when we want to model that the program might not terminate, or when the result is not a simple number but rather a record (an object, if you prefer) containing functions, which in turn might not terminate (or return another record which ...). The mathematical models which arise there become less and less trivial as soon as you allow for more complex data types (e.g. polymorphic functions).
Operational semantics of imperative programs roughly relates the initial variables state to the final one. E.g. "if we start the program with $x=3,y=4$ we end up with $x=7,y=2$". If the semantics is in "small step" style, we further get to see all the intermediate values of variables, as if we were running a debugger and stepping through each program line, so to speak. Such "small step" semantics allows to count, say, the number of multiplications performed by the program, which can not be seen in its denotation alone (however, note that, if we consider that count to be a kind of "observable output", we could define another denotational semantics returning that count as well -- the semantics styles are rather flexible).
Axiomatic semantics instead roughly works with set of states instead of single ones. It can express statements like "if we start the program with variables having any value satisfying $x>y>5$ we end up with $x<100,y=x^2$". Note that we do not know the exact value of each variable here, but only a property that variables satisfy, expressed using logic.
That being said, if you want to achieve a solid understanding, you really have to read about the technical details: all the mathematical definitions and basic theorems. This is not hard, but is also not trivial either -- typically, a single university course can cover the basics of each style.
You are correct when you say that the denotational semantics for a program is, very roughly, a function from its input to its output. E.g. "this program computes the factorial function on naturals". Things start being more complex here when we want to model that the program might not terminate, or when the result is not a simple number but rather a record (an object, if you prefer) containing functions, which in turn might not terminate (or return another record which ...). The mathematical models which arise there become less and less trivial as soon as you allow for more complex data types (e.g. polymorphic functions).
Operational semantics of imperative programs roughly relates the initial variables state to the final one. E.g. "if we start the program with $x=3,y=4$ we end up with $x=7,y=2$". If the semantics is in "small step" style, we further get to see all the intermediate values of variables, as if we were running a debugger and stepping through each program line, so to speak. Such "small step" semantics allows to count, say, the number of multiplications performed by the program, which can not be seen in its denotation alone (however, note that, if we consider that count to be a kind of "observable output", we could define another denotational semantics returning that count as well -- the semantics styles are rather flexible).
Axiomatic semantics instead roughly works with set of states instead of single ones. It can express statements like "if we start the program with variables having any value satisfying $x>y>5$ we end up with $x<100,y=x^2$". Note that we do not know the exact value of each variable here, but only a property that variables satisfy, expressed using logic.
That being said, if you want to achieve a solid understanding, you really have to read about the technical details: all the mathematical definitions and basic theorems. This is not hard, but is also not trivial either -- typically, a single university course can cover the basics of each style.
Context
StackExchange Computer Science Q#105910, answer score: 6
Revisions (0)
No revisions yet.