Category Theory And Programming Language Semantics - An Overview - Peter Dybjer.pdf

PART il
RESEARCH CONTRIBUTIONS
Category Theory
and Programming Language Semantics:
an Overview
Peter Dybjer
Programming Methodology Group
Department puter Sciences
Chalmers University of Technology
and University of
S-412 96 , Sweden
1. Some Generalities
Is category theory relevant to the semantics of programming languages? Yes, this seems to be the case,
at least if we judge by the role of category theory in the development of mathematical semantics. This
kind of semantics concerns methods for interpreting programming languages in mathematical structures.
Such e from set theory, algebra, topology and category theory, etc. The influence of
category theory on operational semantics seems indirect and less important.
What makes a good mathematical semantics? Both mathematical putational e to
mind. The interplay between these two kinds of criteria can be seen throughout the development of
mathematical semantics.
The mathematical criteria state that the constructed model should be simple and mathematically
elegant. It is also an advantage if the concepts used are well-known and have been studied in other con-
texts. It is interesting that we can observe that category theory has achieved a special role in providing
such mathematical criteria.
putational criteria state that the constructed model should reflect putational proper-
ties of the programming language in question. It is not necessary, but possible, to interpret this as imply-
ing that operational semantics is prior to mathematical semantics, a point which has been discussed by
Abramsky (1985). Topological ideas clearly putational significance (see, for example, Smyth
(1983a)). Categorical ideas, however, seem to have a less important role here.
The two main approaches to mathematical semantics are the topological approach, that is, denota-
tional semantics and domain theory, and the algebraic approach.
There is also a third