|
Different kinds of relations have been used as
formal semantic models of values in programming languages.
Especially an entire group of relations is used
to model the different types of values in the language.
These relations are connected by functions
(or by relations) as a model of program functions/procedures.
The combination of relations and connections between them gives a category.
One wants to be able to express in the model (some of) the following operations:
- x and (x):
cartesian product (for lazy tuples) and smash products (eager tuples)
- + and (+):
categorial sum (lazy "disjoint union") and coalesced sum (eager union)
- -> and o->:
non-strict function space constructor
and strict (call by value) function space constructor
There are two approaches:
find a category closed these operations on relations
(esp., find a CCC = cartesian closed category),
or find a catagory ("universal domain") which is isomorphic
to its own function space and cartesian product.
Much attention has been given to the category Poset
of partial ordered sets (ordered by ``definedness'')
and monotone mappings.
Several proposed subcategories of Poset
drop some of Poset's relations and/or functions.
The following image shows (a 200% magnification of)
my attempt of Aug. 22, 1998
to structure my knowledge about relational models
and put them onto one page (letter size).
On the right side is shows stylized examples
for many combinations of interesting properties.
|
