Semantics of Imprecision

The challenge is to capture the imprecision of programming as a semantic notion. We have developed a theory which enables us to consider a domain in the sense of Dana Scott's lattice theory and to express the extent to which each element is partial. The partial metric is a generalisation of a metric in which the distance of each value from itself is not necessarily zero. This has been successfuly applied to proving absence of deadlock in certain lazy dataflow networks.

At the heart of this problem lies the concept of vagueness, a subject first studied by philosophers some 2000 years ago. Timothy Williamson argues that classical logic and formal semantics do not apply to vague languages, one of which would be a system to discuss the imprecise properties of programs such as it almost works. Such vagueness is an epistemic notion of ignorance, our inability to know certain things. In contrast traditional semantics presupposes that every aspect of a program can be formally specified. Examples as diverse as nondeterminism and neural networks can be cited as instances of programming concepts which leave us semantically ignorant to some degree.

Staff involved: Steve Matthews