Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute Grammars
Pages 56 - 69
Abstract
It is not uncommon to design a programming language as a core language with additional features that define some semantic analyses, but delegate others to their translation to the core. Many analyses require contextual information, such as a typing environment. When this is the same for a term under a new feature and under that feature's core translation, then the term (and computations over it) can be shared, with context provided by the translation. This avoids redundant, and sometimes exponential computations. This paper brings sharing of terms and specification of context to forwarding, a language extensibility mechanism in attribute grammars. Here context is defined by equations for inherited attributes that provide (the same) values to shared trees. Applying these techniques to the ableC extensible C compiler replaced around 80% of the cases in which tree sharing was achieved by a crude mechanism that prevented sharing context specifications and limited language extensibility. It also replaced all cases in which this mechanism was used to avoid exponential computations and allowed the removal of many, now unneeded, inherited attribute equations.
References
[1]
John Tang Boyland. Remote attribute grammars. Journal of the ACM, 52 (4): 627–687, 2005.
[2]
Russel Cox, Tom Bergany, Austin Clements, Frans Kaashoek, and Eddie Kohlery. Xoc, an extension-oriented compiler for systems programming. In Proceedings of Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 244–254, 2008.
[3]
Torbjörn Ekman and Görel Hedin. The JastAdd extensible Java compiler. In Proceedings of the 22nd annual ACM SIGPLAN Conference on Object Oriented Programming Systems and Applications (OOPSLA), pages 1–18. ACM, 2007.
[4]
Torbjörn Ekman and Görel Hedin. The JastAdd system - modular extensible compiler construction. Science of Computer Programming, 69: 14–26, December 2007.
[5]
Sebastian Erdweg, Tillmann Rendel, Christian Kastner, and Klaus Ostermann. SugarJ: Library-based syntactic language extensibility. In Proceedings of the Conference on Object Oriented Programming, Systems, Languages, and Systems (OOPSLA), pages 391–406. ACM, 2011.
[6]
R. Farrow. Automatic generation of fixed-point-finding evaluators for circular, but well-defined, attribute grammars. ACM SIGPLAN Notices, 21 (7), 1986.
[7]
Görel Hedin. Reference attribute grammars. Informatica, 24 (3): 301–317, 2000.
[8]
T. Johnsson. Attribute grammars as a functional programming paradigm. In Proc. of Functional Programming Languages and Computer Architecture, volume 274 of Lecture Notes in Computer Science, pages 154–173. Springer-Verlag, 1987.
[9]
Ted Kaminski. Reliably Composable Language Extensions. PhD thesis, University of Minnesota, Minneapolis, Minnesota, USA, 2017. URL http://hdl.handle.net/11299/188954.
[10]
Ted Kaminski and Eric Van Wyk. Modular well-definedness analysis for attribute grammars. In Proceedings of the 5th International Conference on Software Language Engineering (SLE), volume 7745 of Lecture Notes in Computer Science, pages 352–371. Springer, September 2012.
[11]
Ted Kaminski and Eric Van Wyk. Ensuring non-interference of composable language extensions. In Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering (SLE), pages 163–174. ACM, October 2017.
[12]
Ted Kaminski, Lucas Kramer, Travis Carlson, and Eric Van Wyk. Reliable and automatic composition of language extensions to C: The ableC extensible language framework. Proceedings of the ACM on Programming Languages, 1 (OOPSLA): 98:1–98:29, October 2017.
[13]
Ted Kaminski, Lucas Kramer, Travis Carlson, and Eric Van Wyk. Reliable and automatic composition of language extensions to C — supplemental material. Technical Report 17-009, University of Minnesota, Department of Computer Science and Engineering, 2017. Available at https://hdl.handle.net/11299/216011.
[14]
Uwe Kastens. Ordered attributed grammars. Acta Informatica, 13: 229–256, 1980.
[15]
Donald E. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2 (2): 127–145, 1968. Corrections in 5(1971) pp. 95–96.
[16]
Donald E. Knuth. Semantics of context-free languages: Correction. Mathematical Systems Theory, 5 (2): 95–96, 1971. Corrections to knuth1968mst.
[17]
Lucas Kramer and Eric Van Wyk. Parallel nondeterministic programming as a language extension to C (short paper). In Proceedings of the International Conference on Generative Programming: Concepts & Experience (GPCE), pages 20–26. ACM, 2019.
[18]
Lucas Kramer and Eric Van Wyk. Strategic tree rewriting in attribute grammars. In Proceedings of the ACM SIGPLAN International Conference on Software Language Engineering (SLE), pages 210–229, November 2020.
[19]
Eva Magnusson and Görel Hedin. Circular reference attributed grammars - their evaluation and applications. Science of Computer Programming, 68 (1): 21–37, 2007. Special Issue on the ETAPS 2003 Workshop on Language Descriptions, Tools and Applications (LDTA ’03).
[20]
Charles Simonyi, Magnus Christerson, and Shane Clifford. Intentional software. SIGPLAN Notices, 41 (10): 451–464, 2006. ISSN 0362-1340.
[21]
Anthony M. Sloane. Lightweight language processing in Kiama. In Proceedings of the 3rd summer school on Generative and Transformational Techniques in Software Engineering III (GTTSE ’09), volume 6491 of Lecture Notes in Computer Science, pages 408–425. Springer, 2011.
[22]
Anthony M. Sloane, Matthew Roberts, and Leonard G. C. Hamey. Respect your parents: How attribution and rewriting can get along. In Benoît Combemale, David J. Pearce, Olivier Barais, and Jurgen J. Vinju, editors, Software Language Engineering, volume 8706 of Lecture Notes in Computer Science, pages 191–210. Springer, 2014.
[23]
Emma Söderberg and Görel Hedin. Declarative rewriting through circular nonterminal attributes. Computer Languages, Systems & Structures, 44: 3 – 23, 2015. Special issue on the 6th and 7th International Conference on Software Language Engineering (SLE 2013 and SLE 2014).
[24]
Mark G.J. van den Brand and Paul Klint. Aterms for manipulation and exchange of structured data: It’s all about sharing. Information and Software Technology, 49 (1): 55–64, 2007.
[25]
E. Van Wyk, O. de Moor, G. Sittampalam, I. Sanabria-Piretti, K. Backhouse, and P. Kwiatkowski. Intentional Programming: a host of language features. Technical Report PRG-RR-01-21, Computing Laboratory, University of Oxford, 2001.
[26]
Eric Van Wyk, Oege de Moor, Kevin Backhouse, and Paul Kwiatkowski. Forwarding in attribute grammars for modular language design. In Proceedings of the 11th Conference on Compiler Construction (CC), volume 2304 of Lecture Notes in Computer Science, pages 128–142. Springer-Verlag, 2002.
[27]
Eric Van Wyk, Derek Bodin, Jimin Gao, and Lijesh Krishnan. Silver: an extensible attribute grammar system. Science of Computer Programming, 75 (1–2): 39–54, January 2010.
[28]
Eelco Visser. Stratego: A language for program transformation based on rewriting strategies. System description of Stratego 0.5. In A. Middeldorp, editor, Rewriting Techniques and Applications (RTA’01), volume 2051 of Lecture Notes in Computer Science, pages 357–361. Springer-Verlag, May 2001.
[29]
Harold H. Vogt, S. Doaitse Swierstra, and Matthijs F. Kuiper. Higher order attribute grammars. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 131–145. ACM, 1989.
Index Terms
- Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute Grammars
Recommendations
Nanopass Attribute Grammars
SLE 2023: Proceedings of the 16th ACM SIGPLAN International Conference on Software Language EngineeringCompilers for feature-rich languages are complex; they perform many analyses and optimizations, and often lower complex language constructs into simpler ones. The nanopass compiler architecture manages this complexity by specifying the compiler as a ...
Linearly Ordered Attribute Grammars: with Automatic Augmenting Dependency Selection
PEPM '15: Proceedings of the 2015 Workshop on Partial Evaluation and Program ManipulationAttribute Grammars (AGs) extend Context-Free Grammars with attributes: information gathered on the syntax tree that adds semantics to the syntax. AGs are very well suited for describing static analyses, code-generation and other phases incorporated in a ...
Conditional attribute grammars
Attribute grammars are a useful formalism for the specification of computations on structured terms. The classical definition of attribute grammars, however, has no way of treating conditionals nonstrictly. Consequently, the natural way of expressing ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2023
231 pages
ISBN:9798400703966
DOI:10.1145/3623476
- General Chair:
- João Saraiva,
- Program Chairs:
- Thomas Degueule,
- Elizabeth Scott
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 October 2023
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
Conference
SLE '23
Sponsor:
SLE '23: 16th ACM SIGPLAN International Conference on Software Language Engineering
October 23 - 24, 2023
Cascais, Portugal
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 51Total Downloads
- Downloads (Last 12 months)28
- Downloads (Last 6 weeks)2
Reflects downloads up to 01 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in