<p>I am going to attempt an answer, or more precisely a clarification, but one should keep in mind that most ingredients of the question (<em>semantics</em>, <em>operational</em>, <em>behavior</em>, <em>structure</em>) do not have a clear and unambiguous definition, so the question is not really well defined. It is however a legitimate question. I have also been puzzled by the confusing terminology, and it took me some 15 years of research in the field to come to the (hopefully meaningful) clarification described here.</p>
<p><em>Denotational semantics</em> is probably the term that is less ambiguous. Roughly, it amounts to associate to each program <span class="math-container">$p$</span> a mathematical entity <span class="math-container">$[p]$</span>, its denotation, in a way that the denotation is invariant by evaluation (whatever evaluation is, typically a rewriting system of some sort, so that for a denotational semantics one requires that if p -&gt; p' then [p]=[p']) and veryfing some contextual properties. These requirements are meant to ensure that the equality <span class="math-container">$=_{[\cdot]}$</span> induced by the denotational semantics (that is, defined as <span class="math-container">$p =_{[\cdot]} p'$</span> if <span class="math-container">$[p]=[p']$</span>) is an equational theory for programs (that is, an equivalence relation containing evaluation and stable by context closure), that is, that the denotational semantics induces an <em>equational semantics</em>. The contextual aspect is what is generally intended as <em>compositionality</em> and somewhat forces denotational semantics to be defined also for open terms.</p>
<p>The <em>categorical semantics</em> of a language tends to describe the general algebraic structure of the denotational models of a language. This notion of semantics thus somehow describes the underlying <em>structure</em> of programs. It is often considered as part of the study of denotational semantics, even if it is different from it, hence the idea that denotational semantics is about <em>structure</em>.</p>
<p><em>Operational semantics</em> is an overloaded terminology. <em>Operational</em> suggests that one does some operation, so that, at times, the rewriting rules defining the evaluation of programs are considered to be their operational semantics.</p>
<p>Some other times, <em>operational semantics</em> refers to a more specialized version in which one also takes into account some further restriction such as the fact that one considers only closed programs and that the rules are applied only in some evaluation contexts (that is, one considers an evaluation <em>strategy</em> rather than allowing the rewriting rules to be applied everywhere in a program).</p>
<p>Wanting to dive into the operational aspect, one might decompose more and more the operations defining the evaluation of programs, obtaining some form of abstract machine, or even an implementation, which is why <em>operational semantics</em> is also used in these cases. I would say however that most people would not use <em>operational semantics</em> to refer to abstract machines and implementations. Probably, <em>machine semantics</em> would be a better term, but it is not really in use.</p>
<p>Some other times, <em>operational semantics</em> is used in reference to some non-denotationally-defined notions of equational semantics, such as <em>contextual equivalences</em>, relating programs that behave the same when plugged in the same contexts, or forms of <em>bisimilarity</em>, where the meaning <span class="math-container">$[p]$</span> of a program  <span class="math-container">$p$</span> is the class of programs to which <span class="math-container">$p$</span> is bisimilar to. The point here is that these relations are usually defined via the evaluation one, so that they are <em>operational</em> (because of evaluation) (equational) <em>semantics</em>. Contextual equivalences and bisimilarities are the best candidates for modeling <em>behavior</em>, and indeed they are sometimes referred to as <em>behavioral semantics</em>.</p>
<p>Now, the use of the terminology (and the informal references to structure and behavior) are complicated by the fact that in many cases a semantics can be expressed in more than one way. Typically, a certain evaluation strategy (an operational notion), say weak head reduction <span class="math-container">$\to_{wh}$</span> in the <span class="math-container">$\lambda$</span>-calculus, characterizes exactly the programs that have non-empty denotation in a denotational semantics, for instance in a certain relational denotational model, the equational theory of which is normal form bisimilarity. It is also the evaluation implemented by Krivine abstract machine. So all these semantics are different ways of looking at the same computational phenomenon.</p>
<p>Finally, there also are concepts that are somewhat <em>in-between</em>, generating further confusion. For instance, what is referred to as <em>big-step operational semantics</em> amounts to associates to each program <span class="math-container">$p$</span> the result <span class="math-container">$[p]$</span> of its evaluation, if it exists, and <em>undefined</em> (or <span class="math-container">$\bot$</span>) otherwise. It looks very much as a form of denotational semantics (where the mathematical entities of the denotational layer are the programs themselves, which is not forbidden), because it is invariant by evaluation, and yet it is called <em>operational</em> because it is defined as an evaluation mechanism, and because its compositional/contextual aspect is not evident.</p>

CC BY-SA 4.0
2024-05-25T06:45:56.247Z
This is a nice overview. I think it's useful to emphasise that the definition of *denotational* by requiring invariance under evaluation, immediately rules out denotational semantics for models of parallel computing, such as process calculi. E.g. $x \ |\ \overline{x}$ $\rightarrow 0$.
Martin Berger
CC BY-SA 4.0
2024-05-29T10:16:26.753Z
I would say that Martin's comment is misleading / unclear. The idea that I think Martin wants to suggest is that if the evaluation of the calculus is non-confluent, then there is a problem with defining denotational semantics as invariant by evaluation, since the interpretation of the different normal forms (if any) should coincide. In fact, parallelism is not an issue in itself, if the parallel calculus is confluent. The issue is with concurrency, and in particular with races, which tend to break confluence of evaluation.
Beniamino Accattoli
CC BY-SA 4.0
2024-05-29T10:16:47.087Z
Denotational semantics has its roots in the modeling of confluent calculi. In inherently non-confluent settings, denotational semantics needs to be adapted as to assign to a term a set (or multiset, or formal sum) of the elements of the denotational layer and weakening invariance by evaluation to some form of 'containment by evaluation', that is, to something like if $t \rightarrow t'$ then $[t] \supseteq [t']$.
Beniamino Accattoli
CC BY-SA 4.0
2024-05-29T15:06:38.247Z
Parallelism is rarely confluent in practise. Containment by evaluation is better than invariance under evaluation, but the relationship obtained by non-confluent reductions is usually more complex than subset inclusion.
Martin Berger
CC BY-SA 4.0
2024-05-24T11:17:33.743Z
2024-05-24T12:07:38.970Z
2024-05-24T12:07:38.970Z
Beniamino Accattoli
<p>From Nielson and Nielson, 1995, by way of Burgin, 2009:</p>
<ul>
<li>Operational semantics is the field where the meaning of a construct is specified by the computation it induces when it is executed on a machine. In particular, it is of interest how the effect of a computation is produced.</li>
<li>Denotational semantics is the field where meanings are modeled by mathematical objects that represent the effect of executing the constructs. Thus, only the effect is of interest, not how it is obtained.</li>
<li>Axiomatic semantics is the field where specific properties of the effect of executing the constructs represent meaning and are expressed as assertions. Thus, there are always aspects of the executions that are ignored.</li>
</ul>

CC BY-SA 4.0
2024-08-19T07:35:23.017Z
2024-08-19T07:35:23.017Z
The Pointer
<p>I was under the impression that <em>operational semantics</em> describes the <em>behaviour</em> of a program (so it includes the implementation details / the implementation matters), whereas <em>denotational semantics</em> describes the <em>structure</em> of a program (so it doesn't include the implementation details / it is implementation agnostic). But I recently read something that seems to imply that denotational semantics <em>also</em> describes the behaviour of programs. Was my original understanding correct, or is it correct that denotational semantics actually describes the <em>behaviour</em> of programs rather than the structure? And, if the latter is true, what describes the <em>structure</em> of programs / how do/can we model the <em>structure</em> of programs?</p>

CC BY-SA 4.0
2023-12-31T12:26:18.673Z
There is no agreement on what denotational semantics is. I think what Dana Scott, who may have coined or at least popularised the term, had in mind what a map from programs to some 'mathematical' domain (some set $U$ with additional structure, such as a topology or partial order), assumed to be well understood, such that (1) the map from programs to $U$ is compositional (a variant of the concept of homomorphim from algebra) and (2) the desired program equality is normal (set-theoretic) equality in the target domain (i.e. $U$).
Martin Berger
CC BY-SA 4.0
2023-12-31T12:29:47.027Z
Note that, as of 31 Dec 2023, no widely used programming language (such as C++, Rust, Python, Ocaml or Haskell) has a denotational semantics in this strict sense of Scott's.
Martin Berger
CC BY-SA 4.0
2023-12-31T12:33:13.310Z
Regarding what counts as an implementation detail or not, is in the eye of the beholder. If you don't want your $5B rocket to explode on launch because of an uncaught exception, you will have to consider things like the finite precision nature of integers and floats, and their overflow and rounding behaviour. And the 2nd biggest reason for the success of deep learning in recent years was the invention of new floating point formats.
Martin Berger
CC BY-SA 4.0
2023-12-31T12:47:46.687Z
@MartinBerger Thanks for the information. So how do we model the structure (the static view) of a program as opposed to its behaviour (the dynamic view)?
The Pointer
CC BY-SA 4.0
2023-12-31T15:40:12.110Z
@MartinBerger: can you give a reference for these new floating point formats?
Andrej Bauer
CC BY-SA 4.0
2023-12-31T16:32:10.303Z
@AndrejBauer I am not aware of  survey. This is an active area of research. I quickly sketched [here](https://cstheory.stackexchange.com/a/53345/898). Nvidia Chief
scientist Bill Dally recently gave a presentation (MICRO'23?) where he said something like *"By and large, the biggest gain [Nvidia] got was from better number representation"*. I can't find the video at the moment, but [this article](https://spectrum.ieee.org/nvidia-gpu) mentions this. Nigel Higham is an active researcher maybe [this blog](https://nhigham.com/2020/06/02/what-is-bfloat16-arithmetic/) is  relevant?
Martin Berger
CC BY-SA 4.0
2023-12-31T16:47:11.167Z
@ThePointer I'm not sure what exactly you mean by static. For syntax we use grammars. Inbetween syntax and execution we have types.
Martin Berger
CC BY-SA 4.0
2024-01-01T10:01:45.517Z
"Static semantics" is a term sometimes used to describe typing information, as opposed to "dynamic semantics" which is about the dynamic behavior of the program, i.e., operational semantics.
Andrej Bauer
CC BY-SA 4.0
2024-01-03T20:25:53.603Z
I've deleted my answer because it doesn't hold water on reflection the next day, but this is a good question.
J D
CC BY-SA 4.0
2024-01-07T10:42:07.467Z
What do you mean by "structure" of programs?  Like Martin Berger said, denotational semantics typically maps a program $P:B$ with parameters $x_1:A_1,\ldots,x_n:A_n$ to some kind of map $[P]:[A_1]\times\cdots\times[A_n]\to[B]$, where $[T]$ is the interpretation of type $T$.  The function $[P]$ represents the input/output behavior of $P$. For example, if $S_1,S_2$ are two sorting programs, $[S_1]=[S_2]$ even if maybe they implement completely different sorting algorithms, and have therefore completely different "structure".  So I don't see how denotational semantics describes "structure".
Damiano Mazza
<semantics><formal-methods><denotational-semantics><operational-semantics>
Operational semantics and denotational semantics and describing the behaviour and structure of programs
The Pointer
# Operational semantics and denotational semantics and describing the behaviour and structure of programs

(Asked by: username_0 on 2023-12-31)

I was under the impression that *operational semantics* describes the *behaviour* of a program (so it includes the implementation details / the implementation matters), whereas *denotational semantics* describes the *structure* of a program (so it doesn't include the implementation details / it is implementation agnostic). But I recently read something that seems to imply that denotational semantics *also* describes the behaviour of programs. Was my original understanding correct, or is it correct that denotational semantics actually describes the *behaviour* of programs rather than the structure? And, if the latter is true, what describes the *structure* of programs / how do/can we model the *structure* of programs?

**Tags:** semantics, formal-methods, denotational-semantics, operational-semantics
> **Comments:**
> **username_1**: There is no agreement on what denotational semantics is. I think what Dana Scott, who may have coined or at least popularised the term, had in mind what a map from programs to some 'mathematical' domain (some set $U$ with additional structure, such as a topology or partial order), assumed to be well understood, such that (1) the map from programs to $U$ is compositional (a variant of the concept of homomorphim from algebra) and (2) the desired program equality is normal (set-theoretic) equality in the target domain (i.e. $U$).  
> **username_1**: Note that, as of 31 Dec 2023, no widely used programming language (such as C++, Rust, Python, Ocaml or Haskell) has a denotational semantics in this strict sense of Scott's.  
> **username_1**: Regarding what counts as an implementation detail or not, is in the eye of the beholder. If you don't want your $5B rocket to explode on launch because of an uncaught exception, you will have to consider things like the finite precision nature of integers and floats, and their overflow and rounding behaviour. And the 2nd biggest reason for the success of deep learning in recent years was the invention of new floating point formats.  
> **username_0**: @MartinBerger Thanks for the information. So how do we model the structure (the static view) of a program as opposed to its behaviour (the dynamic view)?  
> **username_2**: @MartinBerger: can you give a reference for these new floating point formats?  
> **username_1**: @AndrejBauer I am not aware of  survey. This is an active area of research. I quickly sketched [here](https://cstheory.stackexchange.com/a/53345/898). Nvidia Chief scientist Bill Dally recently gave a presentation (MICRO'23?) where he said something like *"By and large, the biggest gain [Nvidia] got was from better number representation"*. I can't find the video at the moment, but [this article](https://spectrum.ieee.org/nvidia-gpu) mentions this. Nigel Higham is an active researcher maybe [this blog](https://nhigham.com/2020/06/02/what-is-bfloat16-arithmetic/) is  relevant?  
> **username_1**: @ThePointer I'm not sure what exactly you mean by static. For syntax we use grammars. Inbetween syntax and execution we have types.  
> **username_2**: "Static semantics" is a term sometimes used to describe typing information, as opposed to "dynamic semantics" which is about the dynamic behavior of the program, i.e., operational semantics.  
> **username_3**: I've deleted my answer because it doesn't hold water on reflection the next day, but this is a good question.  
> **username_4**: What do you mean by "structure" of programs?  Like Martin Berger said, denotational semantics typically maps a program $P:B$ with parameters $x_1:A_1,\ldots,x_n:A_n$ to some kind of map $[P]:[A_1]\times\cdots\times[A_n]\to[B]$, where $[T]$ is the interpretation of type $T$.  The function $[P]$ represents the input/output behavior of $P$. For example, if $S_1,S_2$ are two sorting programs, $[S_1]=[S_2]$ even if maybe they implement completely different sorting algorithms, and have therefore completely different "structure".  So I don't see how denotational semantics describes "structure".  

---

## 2 answers

### Answer by username_5 on 2024-05-24. Score: 4

I am going to attempt an answer, or more precisely a clarification, but one should keep in mind that most ingredients of the question (*semantics*, *operational*, *behavior*, *structure*) do not have a clear and unambiguous definition, so the question is not really well defined. It is however a legitimate question. I have also been puzzled by the confusing terminology, and it took me some 15 years of research in the field to come to the (hopefully meaningful) clarification described here.

*Denotational semantics* is probably the term that is less ambiguous. Roughly, it amounts to associate to each program $p$ a mathematical entity $[p]$, its denotation, in a way that the denotation is invariant by evaluation (whatever evaluation is, typically a rewriting system of some sort, so that for a denotational semantics one requires that if p -> p' then [p]=[p']) and veryfing some contextual properties. These requirements are meant to ensure that the equality $=\_{[\cdot]}$ induced by the denotational semantics (that is, defined as $p =\_{[\cdot]} p'$ if $[p]=[p']$) is an equational theory for programs (that is, an equivalence relation containing evaluation and stable by context closure), that is, that the denotational semantics induces an *equational semantics*. The contextual aspect is what is generally intended as *compositionality* and somewhat forces denotational semantics to be defined also for open terms.

The *categorical semantics* of a language tends to describe the general algebraic structure of the denotational models of a language. This notion of semantics thus somehow describes the underlying *structure* of programs. It is often considered as part of the study of denotational semantics, even if it is different from it, hence the idea that denotational semantics is about *structure*.

*Operational semantics* is an overloaded terminology. *Operational* suggests that one does some operation, so that, at times, the rewriting rules defining the evaluation of programs are considered to be their operational semantics.

Some other times, *operational semantics* refers to a more specialized version in which one also takes into account some further restriction such as the fact that one considers only closed programs and that the rules are applied only in some evaluation contexts (that is, one considers an evaluation *strategy* rather than allowing the rewriting rules to be applied everywhere in a program).

Wanting to dive into the operational aspect, one might decompose more and more the operations defining the evaluation of programs, obtaining some form of abstract machine, or even an implementation, which is why *operational semantics* is also used in these cases. I would say however that most people would not use *operational semantics* to refer to abstract machines and implementations. Probably, *machine semantics* would be a better term, but it is not really in use.

Some other times, *operational semantics* is used in reference to some non-denotationally-defined notions of equational semantics, such as *contextual equivalences*, relating programs that behave the same when plugged in the same contexts, or forms of *bisimilarity*, where the meaning $[p]$ of a program $p$ is the class of programs to which $p$ is bisimilar to. The point here is that these relations are usually defined via the evaluation one, so that they are *operational* (because of evaluation) (equational) *semantics*. Contextual equivalences and bisimilarities are the best candidates for modeling *behavior*, and indeed they are sometimes referred to as *behavioral semantics*.

Now, the use of the terminology (and the informal references to structure and behavior) are complicated by the fact that in many cases a semantics can be expressed in more than one way. Typically, a certain evaluation strategy (an operational notion), say weak head reduction $\to\_{wh}$ in the $\lambda$-calculus, characterizes exactly the programs that have non-empty denotation in a denotational semantics, for instance in a certain relational denotational model, the equational theory of which is normal form bisimilarity. It is also the evaluation implemented by Krivine abstract machine. So all these semantics are different ways of looking at the same computational phenomenon.

Finally, there also are concepts that are somewhat *in-between*, generating further confusion. For instance, what is referred to as *big-step operational semantics* amounts to associates to each program $p$ the result $[p]$ of its evaluation, if it exists, and *undefined* (or $\bot$) otherwise. It looks very much as a form of denotational semantics (where the mathematical entities of the denotational layer are the programs themselves, which is not forbidden), because it is invariant by evaluation, and yet it is called *operational* because it is defined as an evaluation mechanism, and because its compositional/contextual aspect is not evident.

> **Comments:**
> **username_1**: This is a nice overview. I think it's useful to emphasise that the definition of *denotational* by requiring invariance under evaluation, immediately rules out denotational semantics for models of parallel computing, such as process calculi. E.g. $x \ |\ \overline{x}$ $\rightarrow 0$.  
> **username_5**: I would say that Martin's comment is misleading / unclear. The idea that I think Martin wants to suggest is that if the evaluation of the calculus is non-confluent, then there is a problem with defining denotational semantics as invariant by evaluation, since the interpretation of the different normal forms (if any) should coincide. In fact, parallelism is not an issue in itself, if the parallel calculus is confluent. The issue is with concurrency, and in particular with races, which tend to break confluence of evaluation.  
> **username_5**: Denotational semantics has its roots in the modeling of confluent calculi. In inherently non-confluent settings, denotational semantics needs to be adapted as to assign to a term a set (or multiset, or formal sum) of the elements of the denotational layer and weakening invariance by evaluation to some form of 'containment by evaluation', that is, to something like if $t \rightarrow t'$ then $[t] \supseteq [t']$.  
> **username_1**: Parallelism is rarely confluent in practise. Containment by evaluation is better than invariance under evaluation, but the relationship obtained by non-confluent reductions is usually more complex than subset inclusion.  

---

### Answer by username_0 on 2024-08-19. Score: 0

From Nielson and Nielson, 1995, by way of Burgin, 2009:

* Operational semantics is the field where the meaning of a construct is specified by the computation it induces when it is executed on a machine. In particular, it is of interest how the effect of a computation is produced.
* Denotational semantics is the field where meanings are modeled by mathematical objects that represent the effect of executing the constructs. Thus, only the effect is of interest, not how it is obtained.
* Axiomatic semantics is the field where specific properties of the effect of executing the constructs represent meaning and are expressed as assertions. Thus, there are always aspects of the executions that are ignored.


---

