A study of language representation of semantic domains with applications to language design and definition
Laurette Bradley · Deep Blue (University of Michigan) · 1985
Many different semantic descriptions have been proposed for programming languages and work has been done on the problem of showing equivalence between such descriptions or transforming a description to a form more suitable to some application. Here we develop a method of language description which is not directly a semantic description, but from which we can derive various equivalent alternative semantic definitions of a programming language. One of the alternatives is a st and ard denotational semantics; another is what we call a translation semantics which is particularly suited to use in implementations of a language. Languages are typically defined by giving a syntax and semantics. The foundation of our work is that a language can be defined by giving a description of how the language represents some "semantic domain". If we know what the semantic domain is (which we always take to be an algebra) and we know how the language (which we always take to be a term algebra) represents it, then we show that we can immediately derive either a denotational semantics (that is, a semantic description based on the structure of the language itself) or a translation semantics (in which the meanings of operators in the language are translation actions; a language term is first translated to the term algebra of the algebra it represents, then this term is evaluated in the original algebra giving the meaning of the language term). We give descriptions of many languages in this way, and show that they are extremely versatile: we can use such a description for a language to specify a multi-pass compiler for the language. Since we can also derive a denotational semantics from the same description, this makes such language descriptions useful for many applications.