The Lost Art of Denotational Semantics

Erik Meijer seems to have a knack for explaining complex theory in an entertaining way. When I first saw Erik speak in person at Lang.NEXT 2014, I couldn’t help but smile in nerdy glee: he was unafraid to wade deep into the theory while being enjoyable and occasionally irreverent. While I’d love to cover that talk at a later date, for this post I’d like to focus on another talk he gave his year, entitled The Lost Art of Denotational Semantics. Erik does an excellent job explaining the concept and application of denotational semantics, which I’d never heard of before.

The talk serves as a good introduction to continuation-passing style, which is often used in compiler construction. It also shows the beauty and power of functional programming in solving complex problems. A mix of Scala and a more abstract math-like notation are used.

Notes:

• How do we determine what our programming language actually does? Define it in terms of code!
• In more concrete terms, denotational semantics is realized by writing an interpreter for a programming language.
• To start, Erik derives sequential composition (do this, then that) via continuation passing.
• How do we handle return statements? Easy: pass in another continuation!
• Exception handling can be expressed succinctly via denotational semantics as well.
• “Look how deeply nested these lambdas are!”
• Contiuation passing is really powerful, but how do we simplify the machinery involved in continuation passing?
• Erik backs into a simplified intermediate representation (IR) that is simpler to define the semantics for.
• The IR ends up being imperative: gotos + hidden global variables!
• What we’re really doing is defining the semantics of something complicated (try/finally) in terms of something very simple (IR).
• This desugaring makes it much easier to generate a compiler from an interpreter.
• Discussion of catamorphism and anamorphism, which I’m unable to appreciate at this time.