Language-Based Environments

History and Bibliography

Software

The Synthesizer Generator --- A general tool for creating language-based environments from formal specifications. Using a declarative language, an editor designer prepares a specification that includes rules defining a language's context-free abstract syntax, context-sensitive attributions, concrete input syntax, concrete display format, and transformations. From this specification, the Generator creates a full-screen editor for manipulating objects according to these rules. The Synthesizer Generator uses attribute grammars to compute derived information about the object being edited. The fundamental algorithmic importance of the Synthesizer Generator are its algorithms that incrementally recompute attribute values after an editing change. These incremental algorithms permit immediate response when objects are being manipulated through a generated editor.
The Synthesizer Generator is currently licensed to more than 320 sites worldwide. A wide variety of editors have been written using the Synthesizer Generator including ones for high-level languages like ADA, C, FORTRAN 77, and PASCAL; an editor for partial-correctness program proofs in Hoare-style logic; and proof editors based on the Theory of Constructions and the Logical Framework. Commercial products implemented with the Synthesizer Generator include Ada-ASSURED, an editor for Ada that enforces style guidelines and coding standards (GrammaTech); Crie, a LOTOS integrated editor (ITA); Penelope, an Ada formal verification system (ORA); Raise, a rigorous approach to industrial software engineering (CRI); Z, an editor for the Z specification language (Intecs Sistemi)
Release 1.0, December 1985 (Cornell); Release 2.0, July 1987 (Cornell); Release 3.0, April 1989 (Cornell); Release 3.4, April 1991 (Cornell); Release 3.5, September 1991 (GrammaTech); Release 4.0, December 1992 (GrammaTech); Release 4.1, August 1993 (GrammaTech); Release 4.2, January 1995 (GrammaTech); Release 5.0, January 1997 (GrammaTech).
The Cornell Program Synthesizer --- A microcomputer-based programming environment for a small dialect of PL/I. The Program Synthesizer was first used at Cornell University in June, 1979. After its introduction, it served over 20,000 introductory programming students at Cornell and at some 110 sites worldwide where it was licensed. It demonstrated the feasibility of building a self-contained, highly interactive environment for a statically-scoped, block-structured programming language and stimulated further research in programming environments and incremental compilation techniques.
Version 1, June 1979; Version 1.02, September 1980; Version 1.03, September 1981.

Publications

Books

T. Reps and T. Teitelbaum. The Synthsizer Generator: A System for Constructing Language-Based Editors, 315 pages, Springer-Verlag, NY, 1988.
T. Reps and T. Teitelbaum. The Synthesizer Generator Reference Manual. Department of Computer Science, Cornell University, August, 1985; Second edition, June 1987; Third Edition, 171 pages, Springer-Verlag, 1988.
T. Reps. Generating Language-Based Environments, 138 pages, MIT Press, 1984.

Journals

J. Dill. A Counterexample for ``A Simpler Construction for Showing the Intrinsically Complexity of the Circularity Problem for Attribute Grammars''. JACM 36(1), pages 92--96, January 1989.
T. Reps and T. Teitelbaum. Language processing in program editors. IEEE Computer 20(11), pages 29--40, November 1987.
T. Reps and A. Demers. Sublinear space evaluation algorithms for attribute grammars. TOPLAS 9(3), pages 408--440, July 1987.
S. Horwitz, A. Demers, and T. Teitelbaum. An efficient general iterative algorithm for data-flow analysis. ACTA Informatica 24(6), pages 679--694, July 1987.
S. Horwitz and T. Teitelbaum. Generating editing environments based on relations and attributes. TOPLAS 9(3), pages 577--608, October 1986.
T. Reps, T. Teitelbaum, and A. Demers. Incremental context-dependent analysis for language-based editors. TOPLAS 5(3), pages 449--477, July 1983.
T. Teitelbaum and T. Reps. The Cornell Program Synthesizer: a syntax-directed programming environment. CACM 24(9), pages 563--573, September 1981. (Reprinted in Interactive Programming Environments, Barsow, D.R., Sanderwall, E., and Shrobe, H., McGraw Hill, 1984.)

Refereed Conference Proceedings

J. Field and T. Teitelbaum. Incremental Reduction in the Lambda Calculus. 1990 Lisp and Functional Programming Conference, Nice, France, June 1990.
T. Teitelbaum and R. Chapman. Higher-order Attribute Grammars and Editing Environments. Proceedings of ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, White Plains, NY, pages 197-208, June 1990. Also, Cornell University Technical Report 90-1091.
B. Alpern, R. Hoover, B. Rosen, P. Sweeney, and F. Zadeck. Incremental Evaluation of Computational Circuits. Proc. of First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 22-24 January 1990, pages 32-42.
J. Field, On Laziness and Optimality in Lambda Interpreters: Tools for Specification and Analysis. Presented at the PROC of the Seventeenth POPL, San Francisco, January 1990.
W. Pugh and T. Teitelbaum. Incremental computation via function caching. PROC of the Sixteenth POPL, pages 315--328, 1989.
W. Pugh. An Improved Replacement Strategy for Function Caching. 1988 LISP and Functional Programming Conference, pages 269--276, 1988.
R. Hoover and T. Teitelbaum. Efficient incremental evaluation of aggregate values in attribute grammars. PROC of the SIGPLAN 86 Symposium on Compiler Construction, SIGPLAN Notices, pages 39--50, 1986.
R. Hoover. Dynamically bypassing copy rule chains in attribute grammars. PROC of the Thirteenth POPL, pages 14--25, 1986.
T. Reps, C. Marceau, and T. Teitelbaum. Remote attribute updating for language-based editors. PROC of the Thirteenth POPL, pages 1--13, 1986.
S. Horwitz and T. Teitelbaum. Relations and attributes: a symbiotic basis for editing environments. PROC of the SIGPLAN `85 Symp. on Language Issues in Programming Environments, SIGPLAN Notices, pages 93--106, 1985.
K. Mughal. Control flow aspects of generating runtime facilities for language-based programming environments. PROC 1985 IEEE Computer Society Conference on Software Tools, pages 85--91, 1985.
T. Reps and B. Alpern. Interactive proof checking. PROC of the Eleventh POPL, pages 36--45, 1984.
T. Reps and T. Teitelbaum. The synthesizer generator. PROC of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, SIGPLAN Notices, pages 42--48, 1984.
T. Reps. Static-semantic analysis in language-based editors. Digest of Papers Spring Compcon 83, pages 411--414, 1983.
T. Reps. Optimal-time incremental semantic analysis for syntax-directed editors. PROC of the Ninth POPL, pages 169--176, 1982.
A. Demers, T. Reps, and T. Teitelbaum. Incremental evaluation for attribute grammars with application to syntax-directed editors. PROC of the Eighth POPL, pages 105--116, 1981.
S. Horwitz, T. Reps, and T. Teitelbaum. The why and wherefore of the Cornell Program Synthesizer. PROC ACM SIGPLAN SIGOA Symp. on Text Manipulation, SIGPLAN Notices, 16(6), pages 8--16, June 1981. (Reprinted in Tutorial: Software Development Environments, Wasserman, A.I., IEEE Computer Society Press, pages 64--72, 1981.)

Dissertations

By project members

J. Reppy. Higher Order Concurrency. Ph.D. Thesis, Cornell University, 1992.
J. Field. Incremental Reduction in the Lambda Calculus and Related Reduction Systems. Ph.D. Thesis, Cornell University 1991.
A. Zaring. Parallel Evaluation in Attribute Grammar-Based Systems. Ph.D. Thesis, Cornell University, 1990.
S. Peckham. Incremental Attribute Evaluation and Multiple Subtree Replacements. Ph.D. Thesis, Cornell University, 1990.
W. Pugh. Incremental Computation and the Incremental Evaluation of Functional Programs. Ph.D. Thesis, Cornell University, 1988.
R. Hoover. Incremental Graph Evaluation. Ph.D. Thesis, Cornell University, 1987.
S. Horwitz. Generating Language-Based Editors: A Relationally-Attributed Approach. Ph.D. thesis, Cornell University, 1985.
T. Reps. Generating Language-Based Environments. Ph.D. Thesis, Cornell University, 1982 (Winner of the ACM Doctoral Dissertation Award, 1983).

By project affiliates

C.-K. Chang. A High-Level Synthesis System Incorporating an Interactive Editor Built with the Synthesizer Generator. Masters Thesis, Cornell University, 1990.
T. Griffin. Notational Definition and Top-Down Refinement for Interactive Proof Development Systems. Ph.D. Thesis, Cornell University, 1989.
B. Vander Zanden. Incremental Constraint Satisfaction and its Application to Graphic Interfaces. Ph.D. Thesis, Cornell University, 1988.
K. Mughal. Generation of Runtime Facilities for Program Editors. Ph.D. Thesis, U. of Bergen, Norway, 1988.
D. Krafft. Avid: A System for the Interactive Development of Verifiably Correct Programs. Ph.D. Thesis, Cornell University, 1981.
J. Archer. The Design and Implementation of a Cooperative Program Development Environment. Ph.D. Thesis, Cornell University, 1981.

Technical Reports and Other Publications

J. Reppy. A Foundation for User Interface Construction. In Languages for Developing User Interfaces, edited by Brad A. Myers, Boston, Jones and Bartlett, 1992.
J. Reppy. Asynchronous Signals in Standard ML. Technical Report 90-1144, Cornell University, 1990.
J. Reppy. First-class Synchronous Operations in Standard ML. Technical Report 89-1068, Cornell University, 1989.
S. Peckham. Maintaining Tree Projections in Amortized O(log n) Time. Technical Report 89-1034, Cornell University, 1989.
M. Belmonte. A Practical Attribute Grammar Circularity Test. Technical Report 88-920, Cornell University, 1988.
B. Vander Zanden. An Incremental Planning Algorithm for Ordering Equations in a Multilinear System of Constraints. Technical Report 88-910, Cornell University, 1988.
T. Griffin. An environment for formal systems. Technical Report 87-846, Cornell University, 1987. (Also, U. of Edinburgh Technical Report.)
L. A. Barford and B. Vander Zanden. Attribute Grammars in Constraint-Based Graphic Systems. Technical Report 87-838, Cornell University, 1987.
W. Pugh. Efficient concatenable lists. Technical Report 87-831, Cornell University, 1987.
J. Dill. A counter-example for `a simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars'.
W. Pugh and S. Sinofsky. A new language-independent prettyprinting algorithm. Technical Report 87-808, Cornell University, 1987. (Submitted to TOPLAS.)
T. Reps and T. Teitelbaum. Immediate computation, or how to keep a personal computer busy. Cornell University Engineering Quarterly, 1985.
T. Teitelbaum. The Cornell Program Synthesizer: a tutorial introduction. Department of Computer Science, Cornell University, July, 1979 (Fifth Edition, May 1983).
T. Teitelbaum and T. Reps. On the value of syntax-directed editors. CACM 25(5) pages 351--352, May 1982.
T. Teitelbaum. The Cornell Program Synthesizer: a microcomputer implementation of PL/CS. Technical Report 79-370, Cornell University, 1979.

Synthesizer Generator User Papers

The following papers have been written by users of the Synthesizer Generator describing their work.

R. Paredes. A System for Developing an Environment for Experimenting with Editor Designs, McMaster University, 1993.
R. K. Hall. A System for Developing an Environment for Experimenting with Editor Designs, McMaster University, 1993.
A. Lakhotia. Improved interprocedural slicing algorithm, University of Southwestern Louisiana, 1993.
G. Watson. A Denotational Semantics Editor, University of Queensland, November, 1993.
J. Abrams. On the Implementation of a Syntax-Directed Editor for the Basic COSY Notation with the Synthesizer Generator, Department of Computer Science and Systems, McMaster University, 1993.
J. Smith. EZ: An Editor for the Z Formal Specification Language, University of Queensland, November 1992.
B. L. Kurtz, J. B. Johnston and W. Johnson. Using the Synthesizer-Generator to Teach Principles of Programming Language Semantics, Computer Science Department, New Mexico State University, 1992.
R. Custeau and C. Shelley. Development of an Editor for Proving Theorems of First-Order Logic, Department of Computer Science and Systems, McMaster University, 1990.
H. Korte. Identifier-binding Mechanisms in the Cornell Synthesizer Generator. Master's Thesis, University of Twente, The Netherlands.
van Eijk, P. Attribute Grammar Applications in Prototyping LOTOS Tools, 90-03, Universiteit Twente, 1990.
J. de Miguel. CSG Scripts Language Reference Manual, PROSPECTRA Report S.1.5.C2-R-9.0, ALCATEL Standard Electricia, S.A., Madrid, Spain, March 1990.
J. de Miguel. An Improved Language for CSG Scripts, PROSPECTRA Report S.1.5.C2-SN-7.0, ALCATEL Standard Electricia, S.A., Madrid, Spain, September 1989.
J. de Miguel. Last Improvements to CSG, PROSPECTRA Report S.1.5.C2-SN-7.0, ALCATEL Standard Electricia, S.A., Madrid, Spain, September 1989.
J. de Miguel. A Language for CSG Scripts, PROSPECTRA Report S.1.5.SN-R-6.0, ALCATEL Standard Electricia, S.A., Madrid, Spain, January 1989.
van Eijk, P. LOTOS Tools based on the Cornell Synthesizer Generator, 89-5, Universiteit Twente, 1989.
van Eijk, P. Tools for LOTOS Specification Style Transformation, 89-35, Universiteit Twente, 1989.
P. Franchi-Zannettacci and B. Chabrier and V. Lextrait. GIGAS: A Graphical Interface Generator from Attribute Specifications, Software Engineering and its Applications, Toulouse, France, December 1988.
M. Nielsen and S Lynenskjold. RAISE Project Overview, report 315, Dansk Datamatik Center, November 1988.
D. Guaspari and W. Polak. Summary: The Odyssey Research Associates Ada Verification Project, Ada Letters: July/August 1988, Presented at Formal Methods Committee Report during March SIGAda meeting.
M. D. Capdevil. Read/Write Extended Format, ALCATEL Standard Electrica, S.A., Madrid, Spain, PROSPECTRA Report S.1.5.C2-R-10.0, June 1988.
M. Nielsen and K. Havelund and K.R. Wagner and C. George. The RAISE Language, Method and Tools, Lecture Notes in Computer Science 328, Proceedings of 2ndVDM-Europe Symposium, Springer-Verlag, eds. R. Bloomfield, L. Marshall, and R. Jones, pages 376-403, 1988.
R. Santos. Conditional and parameterized transformations with CSG, PROSPECTRA Study Note S.1.5.C2-SN-2.0, ALCATEL Standard Electricia, S.A., Madrid, Spain, 1988.
G. E. Kaiser, S.M. Kaplan, and J. Micallef. Multiuser, Distributed Language-Based Environments, IEEE Software, 20:4, November 1987, pages 58-67.
D. Carrington and K. Robinson. A Prototype Program Refinement Editor, Department of Computer Science, University of New South Wales, 1987.
T. G. Griffin. An Environment for Formal Systems, Cornell University, TR 87-846, June 1987.
E.J. Slotboom. An Editor for Process Algebra Dynamic Semantics, Unversiteit Twente, 1987.
M. Pfreundschuh. A Model for Building Modular Systems Based on Attribute Grammars, Ph.D. Thesis, The University of Iowa, 1986.
P. Henderson, et al. Programming Environments Course Project Studies, SUNY Stony Brook, TR 85/26, December 1985.
Klint, P. A survey of three language-independent programming environments, IW 240/83, The Mathematical Center, Amsterdam, The Netherlands, November 1983.