Incremental Semantics

Photograph of Peter Mosses

Peter Mosses


Formal semantic descriptions of programming languages are highly desirable. Unfortunately, the engineering aspects of most semantic description frameworks are far from ideal: little reuse of parts of descriptions, no repositories of validated descriptions, poor tool support, etc.

Suppose, however, that we focus on describing the semantics of individual programming constructs, instead of trying to describe an entire language all at once. Many constructs have essentially the same intended interpretation in all the languages where they occur (sometimes with minor variants, e.g., conditionals might have boolean or numerical tests). If one could describe each construct (variant) independently, so that its description would never need reformulating -- regardless of which other kinds of constructs might be included with it in the same language -- it would allow semantic descriptions to be given incrementally, with radical improvements to their engineering aspects. For instance, there would be no need to reformulate the description of the constructs of Standard ML when giving a description of its extension to Concurrent ML.

After briefly illustrating the problems of giving independent descriptions of individual constructs using conventional semantic frameworks, we take a closer look at MSOS, which is an incremental variant of the well-known Structural Operational Semantics. We also discuss the pros and cons of our incremental approach.
Wednesday 9th June 2004, 14:00
Robert Recorde Room
Department of Computer Science