Welcome to MathOverflow

Question

3

1

I'm a computer programmer who's caught on to denotational semantics. I mostly work with Ruby, JavaScript and C, but I know a little Haskell and ML. I've taken my first steps towards reasoning about what my software means, but my knowledge of domain theory is weak. DCPOs, chains, new notation – can you recommend a coherent introduction to this stuff?

flag	asked May 14 2010 at 20:47 jvoorhis 33●3

Have you tried the references given in the Wikipedia article? – Qiaochu Yuan May 14 2010 at 22:02

Andrej Bauer · Accepted Answer · 2010-05-15 06:46:07Z UTC

The book recommended by jef is the domain-theory bible. It may be a bit overwhelming for a beginner. For an easier and more compressed introduction I recommend that you have a look at Abramsky and Jung's chapter on domain theory from the Handbook of Logic in Computer Science. It is available in gzipped Postscript from Achim's home page, and CiteSeerX has it in PDF here.

jef · Answer 2 · 2010-05-15 01:01:13Z UTC

2

http://www.amazon.com/exec/obidos/ASIN/0521803381/

I read this book for a course when I was an undergraduate and it is a very good introduction for all the things you mentioned.

answered May 15 2010 at 1:01

jef
166●2●7

Antonio E. Porreca · Answer 3 · 2010-05-15 08:57:57Z UTC

I used the book The Formal Semantics of Programming Languages by G. Winskel for an undergraduate course, and I found it a reasonably good introduction to the topic; it also covers operational semantics and its relationship with denotational semantics, which I found quite enlightening since the former one is probably easier to grasp initially.

supercooldave · Answer 4 · 2010-05-15 18:33:27Z UTC

Semantics with Applications: An Appetizer by Hanne Riis Nielson and Flemming Nielson provides a rudimentary introduction, also linking denotational semantics to program analysis via abstract interpretation. Plotkin's notes are excellent, more comprehensive, and more theoretically bent.

Weng Kin Ho · Answer 5 · 2013-05-17 02:00:16Z UTC

Another good book that teaches the ropes of domain theory for a beginner is Thomas Streicher's "Domain-Theoretic Foundations of Functional Programming", World Scientific. I highly recommend this book because of its clarity and rigour. Please look up the link at http://www.worldscientific.com/worldscibooks/10.1142/6284 for information on this book. The functional language it works with is a prototypical simply-typed lambda calculus, called PCF (Programming language for Computable Functionals). The domain theory developed in it and the denotational semantics defined is systematic in its organization.

Resources for learning domain theory?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

5 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.