[Haskell-cafe] Denotational semantics for the lay man.

Albert Y. C. Lai trebla at vex.net
Mon Jan 17 21:06:12 CET 2011

On 11-01-17 01:55 PM, David Sankel wrote:
> I've recently had the opportunity to explain in prose what denotational
> semantics are to a person unfamiliar with it. I was trying to get across
> the concept of distilling the essence out of some problem domain. I
> wasn't able to get the idea across so I'm looking for some simple ways
> to explain it.
> Does anyone know of a way to explain what's the meaning and objective of
> "distilling the essence" without introducing more jargon. One thing that
> comes to mind is how Newton's equations for gravity were a distillation
> of the essence of the way things fall.

(I'm afraid Newton's equations introduced more jargon too.)

A denotational semantics maps programs to math things. The mapping has 
to be by structural recursion over program syntax.

Why math: it's the universal modelling language. Why do we model 
programs by a math model: to explain and predict.

Why structural recursion over syntax: to be compositional, the same 
reason we stay close to CFGs for syntax: you can build bottom-up and 
analyze top-down.

It also happens that the math things are given a partial order to help 
answer "what to do with loop constructs and/or cyclic definitions". A 
moment of trying to re-invent denotational semantics reveals that this 
is the only hard part, and so learning denotational semantics typically 
takes 90% of the time on this part.

More information about the Haskell-Cafe mailing list