COMPILERS FROM DENOTATIONAL SEMANTICS: SUMMARY

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: davidm@ctbu.rational.com (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 cailm@cs.tamu.edu 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


Mr. Greg Michaelson
Dept of Computing
Heriot-watt Univ.
Edinburgh, UK
greg@cs.heriot-watt.ac.uk


good luck,


Liming Cai
--------------------------------------------------------------------------------
Reply-To: loegel@fegatello.ssc.gov (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" <jvc@la.TIS.COM>


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: mmcg@bruce.cs.monash.edu.au (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 <greg@cs.heriot-watt.ac.uk>


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" <kosuru@point.cs.uwm.edu>




  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: chapnerk@bambi.WG.WAII.COM (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: nehaniv@math.berkeley.edu (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: thiemann@informatik.uni-tuebingen.de (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 <fs@rex.cs.tulane.edu>




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 uwe%tekchips.tek.com@relay.cs.net,
and Lee was at Peter.Lee@cs.cmu.edu.


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


Reply-To: wilson@mailhost.aa.cad.slb.com (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 <greg@cs.heriot-watt.ac.uk>


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 loegel@fegatello.ssc.gov 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: jbs@congruent.com


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

Return to the comp.compilers page.
Search the comp.compilers archives again.