John Shutt's Mostly Offline Sources

This page is Copyright John N. Shutt 1996-2001, 2004, 2012. Here's what you're allowed to do with it.
Last modified: 31-May-12.


References from my Web pages to offline sources are directed to the appropriate items here.

Most but not all of these references, and their annotations, are from my Master's thesis. Some of the annotations have been changed.

See also: my pages on adaptive grammars.

[Burs 90]
Boris Burshteyn, ``Generation and Recognition of Formal Languages by Modifiable Grammars'', SIGPLAN Notices 25 no. 12 (December 1990), pp. 45-53.

This paper defines Burshteyn's Modifiable Grammar formalism. A correction to one of the definitions appears in [Burs 92].

[Burs 92]
Boris Burshteyn, ``USSA - Universal Syntax and Semantics Analyzer'', SIGPLAN Notices 27 no. 1 (January 1992), pp. 42-60.

Burshteyn's metacompiler language, ostensibly based on his Modifiable Grammar formalism. Includes a correction to [Burs 90], and suggests a generalization to multipass parsing (in response to [Robe 91]).

[Cara 63]
Alfonso Caracciolo di Forino, ``Some Remarks on the Syntax of Symbolic Programming Languages'', Communications of the ACM 6 no. 8 (August 1963), pp. 456-460.

A lucid articulation and advocacy of the principle of grammar adaptivity. Well thought out, and still worth reading.

[Cara 66]
Alfonso Caracciolo di Forino, ``Formal Language Description Languages for Computer Programming'', in T. B. Steel Jr., editor, Proceedings of the IFIP Working Conference on Formal Language Description Languages, Amsterdam: North-Holland, 1966, pp. 37-51.

Proposes a class of two-level grammars. The conference was held in Vienna in September of 1964.

[Chri 69]
Carlos Christensen and Christopher J. Shaw, editors, Proceedings of the Extensible Languages Symposium, Boston, Massachusetts, May 13, 1969 [SIGPLAN Notices 4 no. 8 (August 1969)].

One of two symposia on extensible languages; the other is [Schu 71].

[Chri 85]
Henning Christiansen, ``Syntax, semantics, and implementation strategies for programming languages with powerful abstraction mechanisms'', Proceedings of the Eighteenth Annual Hawaii International Conference on System Sciences volume 2: Software (1985), pp. 57-66.

Also appears as: datalogiske skrifter no. 1, Roskilde University Centre, 1985.

The original paper on Christiansen grammars. An oversight in the treatment of recursive structures is discussed in [Chri 88a].

[Chri 86]
Henning Christiansen, ``Parsing and compilation of generative languages'', datalogiske skrifter no. 3, Roskilde University Centre, 1986.

An abridged version appears as: Henning Christiansen, ``Recognition of generative languages'', in H. Ganzinger and N. D. Jones, editors, Programs as Data Objects [Proceedings of a Workshop, Copenhagen, Denmark, October 17-19, 1985] [Lecture Notes in Computer Science 217], New York: Springer-Verlag, 1986, pp. 63-81.

[Chri 88a]
Henning Christiansen, ``The syntax and semantics of extensible programming languages'', datalogiske skrifter no. 14, Roskilde University Centre, 1988.

Much more developed than the original paper, [Chri 85]. Uses the AG-based notation for Christiansen grammars, but a section re logic programming foreshadows the later development of the DCG-based notation.

[Chri 88b]
Henning Christiansen, ``Programming as language development'', datalogiske skrifter no. 15, Roskilde University Centre, February 1988.

Christiansen's licentiat thesis is made up of this and six other separate papers, including [Chri 85], [Chri 86], and [Chri 88a]. This is the one that ties all of them together.

[Chri 90]
Henning Christiansen, ``A Survey of Adaptable Grammars'', SIGPLAN Notices 25 no. 11 (November 1990), pp. 35-44.

Papers on adaptive grammars tend to be highly insular, rarely mentioning other work on the subject. This paper is an exception. It provides a refreshingly broad perspective on the subject, including a thoughtful (and candid) assessment of the formalisms surveyed, including Christiansen's own.

[Chri 92a]
Henning Christiansen, ``Models and resolution principles for logical meta-programming languages'', INRIA report no. 1594, Institut National de Recherche en Informatique et en Automatique, February 1992.

See remarks for [Chri 92b].

[Chri 92b]
Henning Christiansen, ``A complete resolution method for logical meta-programming languages'', in Alberto Pettorossi, editor, Meta-Programming in Logic: Third International Workshop [Proceedings of META-92, Uppsala, Sweden, June 10-12, 1992] [Lecture Notes in Computer Science 649], New York: Springer-Verlag, 1992, pp. 205-219.

This work can be viewed in terms of meta-programs or adaptive grammars, depending mostly on whether one uses the word ``program'' or ``grammar''; the content is the same either way.

Christiansen has developed a very elegant generalized resolution method for logic meta-programming (roughly, automated proof of general statements about the possibility of proving statements under different sets of axioms).

[Clea 76]
J. Craig Cleaveland and Robert C. Uzgalis, Grammars for Programming Languages [Programming languages series 4], New York: American Elsevier Publishing Company, 1976.

The focus of the book is on W-grammars. The presentation is extremely lucid, which is remarkable for a treatment of W-grammars, especially when burdened with the old terminology. The treatment of the Chomsky hierarchy is also well done.

[Cohe 88]
Jacques Cohen, ``A View of the Origins and Development of Prolog'', Communications of the ACM 31 no. 1 (January 1988), pp. 26-36.

[Dahl 72]
O.-J. Dahl and C. A. R. Hoare, ``Hierarchical Program Structures'', in O.-J. Dahl, E. W. Dijkstra, and C. A. R. Hoare, Structured Programming [A.P.I.C. Studies in Data Processing 8], New York: Academic Press, 1972, pp. 208-220.

The notion of programming as language development is recommended. It may be less than conincidence that the programming language used as a framework for this volume is SIMULA.

[Dawk 89]
Richard Dawkins, The Selfish Gene, new edition, New York: Oxford University Press, 1989.

The eminently readable classic work on reductionism. Introduces the word and concept of memes. Adds several chapters and copious informational endnotes to the original 1976 edition.

[Demb 78]
Piotr Dembinski and Jan Maluszynski, ``Attribute grammars and two-level grammars: A unifying approach'', in J. Winkowski, editor, Mathematical Foundations of Computer Science 1978 [Proceedings, 7th Symposium, Zakopane, Poland, September 4-8, 1978] [Lecture Notes in Computer Science 64], Berlin: Springer-Verlag, 1978, pp. 143-154.

Proves the equivalence of attribute grammars and W-grammars.

[Hanf 73]
K. V. Hanford and C. B. Jones, ``Dynamic Syntax: A Concept for the Definition of the Syntax of Programming Languages'', Annual Review in Automatic Programming 7 no 2. (1973), pp. 115-142.

[Katz 71]
Jacob Katzenelson and Elie Milgrom, ``A Short Presentation of the Main Features of AEPL - An Extensible Programming Language'', in [Schu 71], pp. 23-25.

[Kost 91]
C. H. A. Koster, ``Affix Grammars for Programming Languages'', in Henk Alblas and Borivoj Melichar, editors, Attribute Grammars, Applications and Systems [International Summer School SAGA, Prague, Czechoslovakia, June 4-13, 1991] [Lecture Notes in Computer Science 545], New York: Springer-Verlag, 1991.

Koster lumps attribute, affix, and W-grammars all into the class of ``two-level grammars''. In this paper, he underlines the point by applying each of three formalisms to the definition of a toy language. The three definitions are dramatically alike.

Koster was one of the signators of the Revised Report on ALGOL 68.

Thomas S. Kuhn, The Structure of Scientific Revolutions, Second Edition, Enlarged [International Encyclopedia of Unified Science, Volume 2 Number 2], 1970.

Proposes the notion of scientific paradigms. Written for scientists, it works very hard at debunking the myth of science as absolute truth, and doesn't bother to say certain very important things that all scientists already know. A science-nonliterate reader might come away with the impression that scientific theories have nothing to do with reality, which was not I think the author's intent.

The first edition was published in 1962.

[Mads 80]
Ole Lehrmann Madsen, ``On Defining Semantics by Means of Extended Attribute Grammars'', in Neil D. Jones, editor, Semantics-Directed Compiler Generation [Proceedings of a Workshop, Aarhus, Denmark, January, 1980] [Lecture Notes in Computer Science 94], New York: Springer-Verlag, 1980, pp. 259-299.

See also [Watt 77].

[Maso 84]
K. P. Mason, Dynamic Template Translators: A Useful Model for the Definition of Programming Languages, Ph.D. thesis, University of Adelaide, Australia, 1984.

[Maso 87]
K. P. Mason, ``Dynamic Template Translators - A New Device for Specifying Programming Languages'', International Journal of Computer Mathematics 22 nos. 3+4 (1987), pp. 199-212.

Anyone planning to read this paper should be warned that Mason's style is rather opaque, sometimes bordering on the obtuse. Also, a number of significant details of the DTT formalism are missing or incomplete.

[Robe 91]
George H. Roberts, ``A Note on Modifiable Grammars'', SIGPLAN Notices 26 no. 3 (March 1991), p. 18.

Criticizes Burshteyn's formalism as presented in [Burs 90], because it assumed that the parser would proceed from left to right in a single pass. Naturally, Burshteyn's response in [Burs 92] was to generalize his model to allow multipass parsing.

[Schu 71]
Stephen A. Schuman, Proceedings of the International Symposium on Extensible Languages, Grenoble, France, September 6-8, 1971 [SIGPLAN Notices 6 no. 12 (December 1971)].

One of two symposia on extensible languages; the other is [Chri 69].

Includes [Katz 71].

[Shut 93]
John N. Shutt, ``Recursive Adaptable Grammars'', M.S. Thesis, Computer Science Department, Worcester Polytechnic Institute, Worcester Massachusetts, 1993. Emended 16 December 2003.

Note that in my more recent work I have switched from the term adaptable, which I originally used for compatibility with [Chri 90], to the more technically accurate adaptive.

[Stan 75]
Thomas A. Standish, ``Extensibility in Programming Language Design'', SIGPLAN Notices 10 no. 7 (July 1975), pp. 18-21.

A retrospective survey of the subject, somewhat in the nature of a postmortem.

[Watt 77]
David A. Watt and Ole Lehrmann Madsen, ``Extended attribute grammars'', University of Glasgow, Report no. 10, July 1977. (revised version: Computer Science Department, Aarhus University, DAIMI PB-105, November 1979.)

The original paper on extended attribute grammars.

[Wegb 70]
Ben Wegbreit, Studies in Extensible Programming Languages, ESD-TR-70-297, Harvard University, Cambridge, Massachusetts, May 1970.

Reprinted as: Ben Wegbreit, Studies in Extensible Programming Languages [Outstanding Dissertations in the Computer Sciences], New York: Garland Publishing, Inc., 1980.

[Wijn 65]
Adriaan van Wijngaarden, ``Orthogonal design and description of a formal language'', Technical Report MR 76, Mathematisch Centrum, Amsterdam, 1965.

The original paper on W-grammars.

[Wino 79]
Terry Winograd, ``Beyond Programming Languages'', Communications of the ACM 22 no. 7 (July 1979), pp. 391-401.

This space intentionally left blank.