Tuesday, May 4, 2010

Denotational semantics

You're given diagrams of some Haskell types ordered by semantic order. Vertices are inhabitants of a datatype, and the lines point upwards, from less defined to more defined. (See Wikibooks for an introduction and examples.) Your objective is to construct a type corresponding to the diagram, or show that is impossible.


I've done the first one - it is obviously Bool. Good luck!

DiagramType


Bool



Solution




Solution




Solution



Solution

Solution

Solution


Solution


Solution


Solution

Solution

Solution

Solution


This is a variant of NaturalsDown and will require cheating a little. Create a module that will export a data type, and only a "smart constructor" that will equate undefined and const undefined.

Solution



Application

A great application of denotational semantics is doing numerical integration exactly.

2 comments:

Conal said...

Wow -- what a fun way to get a feeling for domains that come up regularly in Haskell programming. Thanks!

And it gives me an idea: write a book on denotational semantics in the style of "The Little Lisper".

Jeremy said...

@conal I would buy that book ;)

Followers