1

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?

The Pointer
  • 141
  • 5
  • 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$). – Martin Berger Dec 31 '23 at 12:26
  • 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 Dec 31 '23 at 12:29
  • 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 Dec 31 '23 at 12:33
  • @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 Dec 31 '23 at 12:47
  • @MartinBerger: can you give a reference for these new floating point formats? – Andrej Bauer Dec 31 '23 at 15:40
  • 1
    @AndrejBauer I am not aware of survey. This is an active area of research. I quickly sketched here. 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 mentions this. Nigel Higham is an active researcher maybe this blog is relevant? – Martin Berger Dec 31 '23 at 16:32
  • @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 Dec 31 '23 at 16:47
  • 1
    "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 Jan 01 '24 at 10:01
  • 1
    I've deleted my answer because it doesn't hold water on reflection the next day, but this is a good question. – J D Jan 03 '24 at 20:25
  • 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 Jan 07 '24 at 10:42

0 Answers0