# Denotational Semantics

Denotational semantics is a formal method for expressing the semantic definition of a
programming language (or a program in that language).

Other approaches are axiomatic (Hoare methods), algebraic (Guttag ADTs), and
operational (a virtual machine, Java).

In denotational semantics,
the idea is to map every syntactic entity in a PL into some appropriate
mathematical entity. The math is the "denotation" for the syntax,
of the "syntax denotes the semantic entity."

Each denotational semantic definition consists of 5 parts:

- syntactic categories
- BNF defining the structure of the syntactic categories
- value domains (the mathmatical entities to be mapped)
- semantic functions (signatures for mappings from syntax to semantic domains)
- semantic equations (the rules defining the semantic functions)
mappings )

In general, there will be one semantic function for each syntax category,
and one semantic equation for every production in the syntax
grammar.

### Example: language of non-negative integers

**Syntactic Categories**
D in Digits (decimal digits)
N in Num (decimal natural numbers)

**Syntax BNF**
D ::= 0 | 1 | ... | 9
N ::= D | N D

**Value Domains**
Nat = { 0, 1, 2, 3, 4, ... } natural numbers

**Semantic Functions**
DD : Digits --> Nat
MM : Num --> Nat

**Semantic Equations**
DD [0] = 0
DD [1] = 1
DD [2] = 2
...
DD [9] = 9
MM [D] = DD [D]
MM [N D] = 10 * MM [N] + MM [D]