NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/comp/compiler/1555

Internet Message Format | 1992-09-15 | 16.1 KB

Xref: sparky comp.compilers:1555 comp.theory:1927
Path: sparky!uunet!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!rutgers!faatcrl!iecc!compilers-sender
From: [e-mail] (bert thompson)
Newsgroups: comp.compilers,comp.theory
Subject: COMPILERS FROM DENOTATIONAL SEMANTICS: SUMMARY
Keywords: denotational semantics, summary, bibliography
Message-ID: <[e-mail]>
Date: 15 Sep 92 06:25:53 GMT
Sender: [e-mail]
Reply-To: [e-mail] (bert thompson)
Organization: Computer Science, University of Melbourne, Australia
Lines: 372
Approved: [e-mail]

Hi!

A number of people have asked me to summarize the responses I've received
on the topic of producing interpeters and compilers directly from a
language's denotational semantic definition.

There are some interesting responses that I have not included because I
haven't received an ok to post.

Some of the ideas suggested include writing the denotational description
directly in a lazy functional language such as Haskell. (In fact someone
even sent such a realization in Gofer for a small language --
unfortunately not included in this summary.)

Another idea is the automatic generation of compilers from interpreters
using a self-applicable partial evaluator. some such partial evaluators
I've heard of are Similix, Schism and Mix. (of these, I think Mix is the
only one that is strongly-typed -- please correct me if I'm wrong.)

Thanks to everyone who replied!

Here are the responses:

--------------------------------------------------------------------------------

Reply-To: [e-mail] (David Moore)

I do not know about tools specifically. There was an article on April TOPLAS
that is in this area: A Self-Applicable Partial Evaluator for the
Lambda Calculus:Correctness and Pragmatics. Carsten A Gomard.
acm Transactions on Programming Languages and Systems, Vol 14 No 2 pp 147-172
--------------------------------------------------------------------------------
From [e-mail] Wed Sep  9 04:42:40 1992

Hi, there, to my knowledge, there is a tool called Navel developed in UK
which can accept denotational description of a language and produce a
n interpreter for the language. The tool could only deal with context-free
semantics and then was improved by some Chinese to accept context-sensitive
semantics using attributed-grammar technique. For more information, you may
contact:
    Prof. Lin Xing-Liang
    Tsinghua Univ.
    Beijing 100084
    P.R.China

    Dr. Greg Michealson
    Dept of Computing
    Heriot-watt Univ.
    Edinburgh, UK
    [e-mail]

good luck,

Liming Cai
--------------------------------------------------------------------------------
Reply-To: [e-mail] (George Loegel)

There was a system developed about 1980 by Peter Mosses (Aahrus Univ)
that accepted a denotational semantic description of a language and
produced an interpreter for it. The system is called SIS (Semantic
Implementation System) and is described in Bodwin, J. et.al.
"Experience with an experimental compiler generator based on
denotational semantics" 1982 SIGPLAN Symposium on Compiler
Construction, SIGPLAN Notices 17,6 (1982)
--------------------------------------------------------------------------------
Reply-To: "Jeffrey V. Cook" <[e-mail]>

I don't know if this is what you want, but I have written a free tool in
Common Lisp that produces a Common Lisp IMPLEMENTATION of a denotational
semantic specification of a computer language.  This tool is called JADDS
(Jeff's Automated Denotational Definition System).  It has an internal
Lisp-like language that lets you define abstract syntax and specify
denotational semantic equations based on abstract syntax, and also lets you
define auxiliary functions.  The tool allows one to generate LaTeX
pretty-printed files holding the semantic definitions, for inclusion in
reports that discuss the semantics.  It also permits the generation of a
semantic implementation, by implementing the denotational semantic
specification in Common Lisp.  A semantic implementation, when applied to an
abstract syntax tree for a program, generates the denotation specified in the
semantics.  If the denotations generated are in machine language, then you
have a formal implementation of a compiler.

Now, if you are talking about generating an interpreter or a compiler from a
denotational semantic specification whose denotations are more abstract, this
is a totally different sort of problem.
--------------------------------------------------------------------------------

Reply-To: [e-mail] (Mike  Mc Gaughey)

It's relatively straightforward to translate denotational semantics
into a program in a lazy functional language (aka LML, haskell),
assuming you haven't buggered up the types in the DS definition (if you
_do_ want type-free DS, translate into lisp instead).  It would
probably take an afternoon or two to write such a tool in lex & yacc.
LML, yacc, and lisp compilers are generally free.

I write my semantics directly in LML, usually.
--------------------------------------------------------------------------------

Reply-To: Greg Michaelson <[e-mail]>

Hi! I built a system some years ago which given a grammar and semantic functions
implements an interpreter for the defined language.
--------------------------------------------------------------------------------

Reply-To: "Ramakumar Kosuru" <[e-mail]>


 Peter lee's Realistic Compiler geneartion should be a big help to you.
Call no: QA 76.76 C 65 L 44.

Hope this helps.

Ram
--------------------------------------------------------------------------------

Reply-To: [e-mail] (Asha V. Chapnerkar)

Bert,

There is a system known as SPS that is described in the
paper below that does exactly what you are looking
for:
   Wand, Mitchell, "A Semantic Prototyping System",
   Proceeding of the 1984 SIGPLAN Symposium on
   Compiler Construction, 1984, pp. 158-164.

It takes a denotational definition, written
in Scheme, and gives you an interpreter for the
language.

Dr. Asha V. Chapnerkar
--------------------------------------------------------------------------------
Reply-To: [e-mail] (Chrystopher L. Nehaniv)

Take a look at the book "Compiler Generators" by Mads Tofte. I believe it
has some material relevant to denotational semantics and compiler
generators (in particular the compiler generator CERES which he and others
developed). This book is EATCS 19 Monographs on THeoretical Computer
Science, published by Springer Verlag 1990. [The silver books with 3 red
stripes across the top].

Cheers,

Chrystopher Nehaniv
--------------------------------------------------------------------------------

Reply-To: [e-mail] (Peter Thiemann)

Several people are working on this:
- Jens Palsberg (generates SPARC code from action notation) see IEEE
International Conf. on Computer Lang.'92
- Mikael Peterson, see also ICCL92
- There is a group in Glasgow that also uses action notation, I think
it is headed by D. Watts, PLILP92 has a system description of an
interpreter, at least.

Sorry for not being more explicit, I don't have the refs at hand.

Cheers, Peter
--------------------------------------------------------------------------------

Reply-To: Frank Silbermann <[e-mail]>


You might try to contact Uwe F. Pleban or Peter Lee who wrote about it.
My addresses may be out of date, though.
In 1988, Pleban was at [e-mail],
and Lee was at [e-mail].

--------------------------------------------------------------------------------

Reply-To: [e-mail] (David Wilson)

Try to track down Peter Lee at Carnegie Mellon.  I think he is at least an
assistant prof by now.  I worked with him when he was just a summer
programmer while still in school.  I know his dissertation was along the
lines of what you're looking for.  Also, the last MIT Press catalog I saw
had a book or two on the subject authored (or maybe just edited) by him.

Sharpest kid I've ever run into.  If what you want is available, he will
know.  (He's not a kid anymore -- it was a dozen years ago when he worked
here).

Dave Wilson
--------------------------------------------------------------------------------


Reply-To: Greg Michaelson <[e-mail]>

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

------------------------------------------------------------------------




        References

        1.   L.  Allison,  A  practical   introduction   to   denotational
             semantics, CUP, (1986).

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

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

        4.   D. Bjorner, C. B. Jones, and (Eds.), The  Vienna  Development
             Method: the metalanguage, LNCS 61, Springer Verlag, (1978).

        5.   D.  Bjorner,  "Rigorous  development  of   interpreters   and
             compilers," in Formal specification and software development,
             ed. D. Bjorner & C.  B.  Jones,  pp. 271-320,  Prentice-Hall,
             (1982).

        6.   J. Bodwin, L. Bradley, K. Kanda, D. Little,  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).

        7.   S-J. Chao  and  B.  R.  Bryant,  Denotational  semantics  for
             program analysis, pp. 83-91, ??? ACM ???, (???).

        8.   I. Cottam, "discussed in  'Workshop  on  Software  Tools  for
             Formal Methods'," FACS FACTS, Vol. 8, (2), (February, 1986).

        9.   H.  Ganzinger,  "Some  principles  for  the  development   of
             compiler     descriptions    from    denotational    language
             definitions,"  TUM-I8006,  Technische  Universitat   Munchen,
             (May, 1980).

        10.  C. B. Jones, "Compiler design," in Formal  specification  and
             software  development, ed. D. Bjorner & C. B. Jones, pp. 253-
             269, Prentice-Hall, (1982).

        11.  N. D. Jones and D.  A.  Schmidt,  "Compiler  generation  from
             denotational   semantics,"  in  Semantics  directed  compiler
             generation, ed. N. D. Jones, pp. 70-93,  LNCS  94,  Springer-
             Verlag, (1980).

        12.  P.  Jouvelot,  Designing  new  languages  or   new   language
             manipulation   systems   using  ML,  21,  pp. 40-52,  SIGPLAN
             Notices, (August, 1986).

        13.  H.  A.  Klaeren  and  H.  Petzsch,  The  development  of   an
             interpreter   by   means   of   abstract  algebraic  software
             specifications, Lehrstuhl fur  Informatik  II,  RWTH  Aachen,
             (???).

        14.  R. E. Milne and C. Strachey, A theory of programming language
             semantics, Chapman and Hall, (1976).

        15.  G. O'Neill, "Automatoc translation of VDM specifications into
             Standard   ML   programs,"  DITC  196/92,  National  Physical
             Laboratory, (February, 1992).

        16.  L.   Paulson,   "Compiler   generation   from    denotational
             semantics,"  in  Methods and tools for compiler construction,
             ed. B. Lohro, pp. 219-250, CUP, (1984).

        17.  L. Paulson,  A  compiler  generator  for  semantic  grammars,
             Department   of   Computer   Science,   Stanford  University,
             (December, 1981).  PhD Thesis .

        18.  U. F. Pleban, "Compiler prototyping using formal  semantics,"
             SIGPLAN  Notices: Proceedings of the AC_M SIGPLAN'84 Symposium
             on Compiler Construction, Vol. 19,  (6),  pp. 94-105,  (June,
             1984).

        19.  M. Rakovsky and P. Collier, "From standard to  implementation
             denotational   semantics,"  in  Semantics  directed  compiler
             generation, ed. N. D. Jones, pp. 94-139, LNCS  94,  Springer-
             Verlag, (1980).

        20.  V.  Royer,  "Transformations  of  denotational  semantics  in
             semantics   directed   compilers,"  SIGPLAN  Notices:  ?????,
             Vol. 21, (7), p. ?????, (July, 1986).

        21.  K. Slonneger, Denotational Semantics in Prolog, University of
             Iowa, (1990).

        22.  S.  Stepney,  D.  Whitley,  D.  Cooper,  and  C.  Grant,   "A
             demonstrably  correct compiler," Formal Aspects of Computing,
             Vol. 3, (1), pp. 58-101, (Jan-March 1991).

        23.  J.  E.  Stoy,  Denotational  Semantics:  the   Scott-Strachey
             approach to programming language theory, MIT, (1977).

        24.  M. Takeichi,  Inserting  inject  operations  to  denotational
             semantics, 4, pp. 365-381, New Generation Computing, (1986).

        25.  M. Tofte, Compiler generators, Springer-Verlag, (1990).

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

--------------------------------------------------------------------------------
The GIPE group at CWI has a system that uses initial algebra specification,
called ASF+SDF, described in:

    J. A. Bergstra, J. Heering, and P. Klint (eds),
     Algebraic Specification,
     ACM Frontier Series, The ACM Press in cooperation with
     Addison-Wesley, 1989.

     P. Klint,
     A meta-environment for generating programming environments,
     In J.A. Bergstra and L.M.G. Feijs (eds), Proceedings of the
     METEOR workshop on Methods Based on Formal Specification,
     Springer LNCS Vol. 490, 105-124, 1991.
     (Revised version submitted to ACM TOSEM)
--------------------------------------------------------------------------------
From [e-mail] Mon Sep 14 23:50:11 1992

[Pau82a] Paulson, L.  {\it A Compiler Generator for Semantic
Grammars}, Ph.D.  dissertation, Stanford University, 1982
[Pau82b] Paulson, L. ``A Semantics-Directed Compiler Generator'', in
Conference Record of the Ninth Annual ACM Symposium on Principles of
Programming Languages, ACM, 1982, pp. 224-233

We used Paulson's system to generate Pcode in
[Mil84] Milos, D.  Pleban, U. and Loegel, G.  ``Direct Implementation
of compiler specifications, or: The Pascal P-compiler revisited'',
Conference Record of the 11th Annual ACM SIGPLAN/SIGACT Symposium on
Principles of Programming Languages, 1984, pp. 196-207

Another reference would be the papers in:
_Semantics-Directed Compiler Generation_, Jones, N. D. ed., Lecture
Notes in Computer Science no. 94, Springer-Verlag, Berlin, 1980

--------------------------------------------------------------------------------
Reply-To: [e-mail]

It is pretty trivial to transform denotational semantics into a Scheme
(or other Lisp) program implementing an interpreter for the language.
I did this in a graduate programming languages cource at MIT.

Compilers are harder.

But given a good enough Lisp compiler, the compiler itself can turn
the interpreter into a compiler!

(define (interpreter->compiler interpreter)
   (lambda (form)
       (lambda arguments
       (apply interpreter form arguments)))

(define my-compile (interpreter->compiler my-interpret))

(define my-compiled-form (my-compile my-form))

It all falls out as a consequence of aggressive procedure inlining,
constant-folding, and other optimizations.

Jeffrey Siegal
--
Send compilers articles to [e-mail] or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.