Skip to main content
2 of 2
added 6 characters in body
D.W.
  • 165.5k
  • 21
  • 230
  • 490

I'll write $O(p,\sigma)$ for the only $\sigma'$ so that $\langle p, \sigma \rangle \to \sigma'$ (and $\bot$ if it doesn't exist) and $D(p)$ for the denotational semantics of $p$. Note that if you define both semantics properly, you'll most likely have $O(p,\sigma)=D(p)(\sigma)$. I'll write $S(p)$ to mean either $\sigma\mapsto O(p,\sigma)$ or $D(p)$.

Now take a compiler $C:X \to X'$. Saying that it's a compiler means that it preserves semantics, i.e. $S(C(p))=S'(p)$. If you were to try to prove that using operational semantics, you'd have to prove that for any $p$ and for any $\sigma$, $O(C(p),\sigma)=O'(p,\sigma)$. To prove it using denotational semantics, you only have to prove that for any $p$, $D(C(p))=D'(p)$. Not having to quantify on $\sigma$ often saves a lot of work.

Silly example:

$C(p)=$ replace all $(q;q')$ by $(skip;q;skip;q';skip)$.

In denotational semantics, you'll just do a proof by induction on $p$ and you'll easily get that $C$ is a compiler. In operational semantics, you'll have to take your derivations and plug pieces of derivations everywhere to account for the skips and it'll be a nightmare.

xavierm02
  • 1.3k
  • 6
  • 14