|Implementing formal semantics firstname.lastname@example.org (1994-01-20)|
|From:||email@example.com (Greg Michaelson)|
|Keywords:||report, denotational semantics, bibliography|
|Organization:||Dept of Computing & Elec Eng, Heriot-Watt University, Scotland|
|Date:||Thu, 20 Jan 1994 16:58:49 GMT|
The following is extracted from Chapter 2 of my PhD: "Interpreter prototypes
from formal language definitions", Heriot-Watt University, 1993.
My Navel system is described in:
G.Michaelson, `Interpreters from functions & grammars', Computer
Languages, Vol. 11, No. 2, pp. 85-104, 1986
G.Michaelson, `Interpreter prototypes from language definition style
specifications', Information & Software Technology, Vol. 30, No. 1,
pp. 23-31, 1988
G.Michaelson, `Text generation from grammars', Information and
Software Technology, Vol. 32, No. 8, pp 566-568, October 1990
as well as in the PhD. I'll either email the PhD in PostScript to the
people that requested it or stick it on a local friendly FTP site.
2. Denotational semantics and its implementation
2.8. Implementations from denotational semantics
DS has also been used directly as the basis of a number of
automatic language implementation systems using both compilation
and interpretation. Five of these are now considered in more
detail. Tofte  provides summary overviews of other related
Mosses' Semantics Implementation System(SIS) , built in the
late 1970's, was the first compiler generator based on DS.
Definitions written in a DS style are used to implement a compiler
from the defined language to LAMB, a variant of the Scott-Strachey
L calculus based LAMBDA semantic notation. LAMB output from the
compiler is subsequently interpreted through call by need
LAMB is an extended L notation, providing non-negative integers,
quotations, truth values, tuples, parse trees and functions. In
form, LAMB is, like many DS notations, akin to a functional
language with constructs including infix and prefix arithmetic,
logical and comparison operators, operators for tuple and parse
tree manipulation, conditional expressions, and pattern matching.
SIS definitions have two stages. Syntax is written in GRAM, a
context-free notation related to BNF with constructs for iteration
(Kleene star) and ranges for ordered sequences of base lexical
items, like digits or letters. A GRAM definition, in turn,
consists of LEXIS, for defining lexical items, and SYNTAX, for
syntax proper. GRAM is used to generate SLR(1) parse tables which
are then used to generate LAMB parse trees from program texts.
Internally, LEXIS is used to generate LAMB tuples to represent
lexemes which are then parsed via the SYNTAX parse tables. SYNTAX
includes notation for describing the form of parse trees, hence
enabling the specification of the concrete/abstract syntax
Semantics is specified in the Denotational Semantics
Language(DSL), which is LAMB augmented with domain and function
definitions, a case construct, function updating and ranges for
SIS has no provision for context sensitive aspects of syntax.
These may either be ignored, or implemented as an explicit
additional stage or pushed into the semantics.
SIS is written in BCPL and has been ported to a number of
platforms. It is a multi-pass batch system.
Bodwin et al  made an extensive study of SIS in a teaching
environment. They found that full SIS based language
implementations are very large, even for small languages. They
- 2 -
highlighted a number of annoying restrictions, in particular the
adherence to SLR(1) syntax, limited semantic domains and the
handling of separated sums of domains through parse trees. They
also comment on the poor provision for error handling, in
particular the lack of semantic equation type checking, and on the
SIS implementation's general inefficiency. They conclude that
while SIS is only suitable for experimentation with small DS
definitions, it is, none the less, an important first step.
Peter Mosses himself has stopped working on SIS as he sees
inherent problems with manipulating large DS. (These comments were
made in unpublished electronic mail to me on 29/8/90)
Paulson's PSP system [56,55] is based on semantic grammars which
are DS definitions written as attribute grammars. Generated
compilers produce SECD machine code for subsequent interpretation
using call by value reduction.
The semantic grammar notation enables function and type
definitions, and rules specifying context free and context
sensitive syntax, and semantics. As with SIS, the base semantic
notation is similar to a functional language, providing boolean,
integer string, tuple and union types, L abstraction, function
updating, and conditional and case control constructs.
The system consists of three stages. The Grammar Analyser produces
parse and compilation tables from a semantic grammar. The
Universal Translator then reads the tables and generates SECD
machine code from a program. Finally, the Stack Machine optimises
and interprets the SECD code. PSP is another batch system.
Pleban, a member of the group which investigated SIS, has also
used PSP extensively. He reports  that PSP enables
considerable experimentation, that attribute grammar and DS
definitions may be readily implemented and that type checking
enables many bugs to be located quickly. He also comments that
testing a DS helps establish confidence in its correctness.
Overall, he thinks that PSP is flexible enough to enable
experimentation with a wide variety of definitional styles.
However, he draws attention to the lack of an interactive
interface, the absence of good error handling, the limited number
of built in domains and the lack of support for the modular form
of DS definitions.
Bahlke and Snelting's Programming System Generator(PSG) [4,5]
generates interactive programming environments from DS definitions
augmented with attribute grammars. These environments include
structure editors and what are effectively interpreters for the
defined language, which enable experimentation with language
fragments as well as with entire languages. A library system
supports previously developed language fragments for incorporation
in new languages. The system generates a compiler from a DS
which, in turn, generates functional code from a program for
- 3 -
interpretation in SECD machine style using call by need reduction.
Definitions consist of syntax, context conditions and semantics.
The syntax consists of lexical structure, concrete syntax
augmented with format syntax, abstract syntax, and titles and
menus for the interactive environment. The concrete syntax is
LL(1). The context conditions consist of scope and visibility
rules and a data attribute grammar, augmented with format syntax
for attributes. The semantics consist of domain definitions,
auxiliary functions, semantic functions for the whole language and
meanings for executable fragments.
The semantic notation is a functional language based on an
applicative subset of META-IV . It provides integer, real,
boolean and string domains, lists, tuples and map data types,
higher order functions, definitions and conditional expressions.
The authors comment  that the use of a modular approach to
language design improves readability and reliability, and that a
system like PSG eases rapid prototyping of new languages.
2.12. Wand's semantic prototyping system
Wand's semantic prototyping system  is based on Scheme, a
dialect of LISP with simplified constructs for handling functions
as values. Definitions are based on transducers, which are DS
style definitions written in Scheme as associations between
syntactic constructs and semantic equations. Transducers are
processed to produce a parser for the language. Programs are then
parsed to generate L calculus in Scheme form for call by value
reduction by the Scheme interpreter. The notation includes domain
equations which are used for what is effectively type checking.
Like Pleban, Wand notes that type checking greatly eases error
detection in definitions. There is no abstract syntax stage. Wand
comments that its use is cumbersome, preferring the direct use of
Lee and Pleban [42,59] criticise the use of L calculus based
notations for all levels of semantic description. They argue for
the separation of underlying semantic models from semantic
descriptions of particular languages. Macrosemantics, concerned
with compile time issues, should refer to action based operators
whose microsemantic details are hidden. These operators might
realise run-time actions in arbitrary paradigms, for example
declarative or imperative. Language definitions should be
modularised, to separate out distinct components for semantically
distinct constructs, thus enabling incremental language
Their Modular Extensible Separable Semantics(MESS) system reflects
these concerns. It generates abstract syntax trees from which the
macrosemantics produces prefix-form operator expressions(POEs).
The microsemantics then specify the meanings of the operators.
To begin with, macro- and micro-semantic definitions were written
- 4 -
in a case based functional style accompanied by semantic domain
signatures for semantic functions. Subsequently, an extension to a
pure functional subset of SML has been used. It is not clear how
concrete syntax is defined or whether there is any provision for
The MESS syntax analyser generator is written in and produces
Pascal syntax analysers which in turn generate abstract syntax
trees represented as Scheme S-expressions. Abstract syntax
descriptions are generated automatically by the analyser
generator. The semantic analyser is written in Scheme. The
microsemantics is processed to generate an interface file
containing the names and signatures of operators. An
implementation of the operators in Scheme is also generated. The
macrosemantics is processed with the interface file to produce a
compiler core in Scheme.
A program is translated into an abstract syntax tree from which
POEs are generated in Scheme by the compiler core. These may be
executed directly as Scheme programs together with the Scheme for
the operators. Alternatively, code may be generated from the POEs.
Initially, code generators were written in Prolog. MESS has now
been extended to allow different styles of microsemantics, for
example to produce L calculus for interpretation or machine code
for direct execution.
Lee and Pleban show that MESS generated code runs faster than that
from PSP, which, they state, generated the fastest code prior to
4. R. Bahlke and G. Snelting, "The PSG - Programming System
Generator," ACM SIGPLAN Notices, Vol. 20, (7), pp. 28-33,
5. R. Bahlke and G. Snelting, "The PSG system: from formal
language definitions to interactive programming
environments," ACM Transactions on Programming Languages and
Systems, Vol. 8, (4), pp. 547-576, (October, 1986).
10. J. Bodwin, L. Bradley, K. Kanda, D. Litle, and U. Pleban,
"Experience with an experimental compiler generator based on
denotational semantics," SIGPLAN Notices: Proceedings of
SIGPLAN'82 Symposium on Compiler Construction, Vol. 17, (6), pp.
216-229, (June, 1982).
42. P. Lee and U. Pleban, "A realistic compiler generator based
on high-level semantics," in Proceedings of 14th ACM
SIGACT/SIGPLAN Symposium on Principles of Programming
Languages, pp. 284-295, Munich, West Germany, (January 1987).
50. P. Mosses, "SIS - Semantics Implementation System: Reference
Manual and User Guide," DAIMI MD-30, Computer Science Dept.,
Aarhus University, Denmark, (August 1979).
55. L. Paulson, "Compiler generation from denotational
- 5 -
semantics," in Methods and tools for compiler construction, ed.
B. Lohro, pp. 219-250, CUP, (1984).
56. L. Paulson, A compiler generator for semantic grammars,
Department of Computer Science, Stanford University,
(December, 1981). PhD Thesis .
58. U. F. Pleban, "Compiler prototyping using formal semantics,"
SIGPLAN Notices: Proceedings of the ACM SIGPLAN'84 Symposium on
Compiler Construction, Vol. 19, (6), pp. 94-105, (June, 1984).
59. U. F. Pleban and P. Lee, "An automatically generated
realistic compiler for an imperative language," in
Proceedings of SIGPLAN'88 Conference on Programming Language
Design and Implementation, pp. 222-232, Atlanta, USA, (June
79. M. Tofte, Compiler generators, Springer-Verlag, (1990).
81. M. Wand, "A semantic prototyping system," SIGPLAN Notices:
Proceedings of the SIGPLAN '84 Symposium on Compiler
Construction, Vol. 19, (6), pp. 213-221, (June, 1984).
Return to the
Search the comp.compilers archives again.