[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
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