Implementing formal semantics

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


                <text omitted>


                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 [79] provides summary overviews of other related
                systems.


                2.9. SIS


                Mosses' Semantics Implementation System(SIS) [50], 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
                reduction.


                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
                correspondence.


                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
                nodes.


                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 [10] 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)


                2.10. PSP


                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 [58] 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.


                2.11. PSG


                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 [8]. It provides integer, real,
                boolean and string domains, lists, tuples and map data types,
                higher order functions, definitions and conditional expressions.


                The authors comment [4] 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 [81] 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
                concrete syntax.


                2.13. MESS


                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
                definition.


                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
                context sensitivity.


                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
                MESS.


                References


                4. R. Bahlke and G. Snelting, "The PSG - Programming System
                Generator," ACM SIGPLAN Notices, Vol. 20, (7), pp. 28-33,
                (July 1985).


                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
                1988).


                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 comp.compilers page.
Search the comp.compilers archives again.