Xoc, an extension-oriented compiler for systems programming
Authors: 
Russ Cox, Tom Bergan, Austin T. Clements, Frans Kaashoek, Eddie KohlerAuthors Info & Claims
Pages 244 - 254
Abstract
Today's system programmers go to great lengths to extend the languages in which they program. For instance, system-specific compilers find errors in Linux and other systems, and add support for specialized control flow to Qt and event-based programs. These compilers are difficult to build and cannot always understand each other's language changes. However, they can greatly improve code understandability and correctness, advantages that should be accessible to all programmers.
We describe an extension-oriented compiler for C called xoc. An extension-oriented compiler, unlike a conventional extensible compiler, implements new features via many small extensions that are loaded together as needed. Xoc gives extension writers full control over program syntax and semantics while hiding many compiler internals. Xoc programmers concisely define powerful compiler extensions that, by construction, can be combined; even some parts of the base compiler, such as GNU C compatibility, are structured as extensions.
Xoc is based on two key interfaces. Syntax patterns allow extension writers to manipulate language fragments using concrete syntax. Lazy computation of attributes allows extension writers to use the results of analyses by other extensions or the core without needing to worry about pass scheduling.
Extensions built using xoc include xsparse, a 345-line extension that mimics Sparse, Linux's C front end, and xlambda, a 170-line extension that adds function expressions to C. An evaluation of xoc using these and 13 other extensions shows that xoc extensions are typically more concise than equivalent extensions written for conventional extensible compilers and that it is possible to compose extensions.
Supplementary Material
JPG File (1346312.jpg)
- Download
- 10.54 KB
Slides from the presentation
- Download
- .98 KB
Supplemental material for Xoc, an extension-oriented compiler for systems programming
- Download
- 21.39 MB
Audio only (1346312.mp3)
- Download
- 10.29 MB
Video (1346312.mp4)
- Download
- 142.07 MB
References
[1]
Jonathan Bachrach and Keith Playford. The Java syntactic extender (JSE). In Proceedings of the 16th annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, 2001.
[2]
Jason Baker and Wilson C. Hsieh. Maya: Multiple dispatch syntax extension in Java. In Proceedings of the 2002 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2002.
[3]
Tom Bergan. Typmix: a framework for implementing modular, extensible type systems. Master's thesis, University of California Los Angeles, 2007.
[4]
Martin Bravenboer and Eelco Visser. Concrete syntax for objects: domainspecific language embedding and assimilation without restrictions. In Proceedings of the 19th annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, 2004.
[5]
Brian Chin, Shane Markstrum, and Todd Millstein. Semantic type qualifiers. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2005.
[6]
Robert DeLine and Manuel Fahndrich. Enforcing high-level protocols in low-level software. In Proceedings of the 2001 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2001.
[7]
Bryan Ford. Parsing expression grammars: a recognition-based syntactic foundation. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2004.
[8]
Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns. Addison-Wesley, Reading, Massachusetts, 1994.
[9]
Paul Graham. On LISP: Advanced Techniques for Common LISP. Prentice-Hall, 1996.
[10]
Robert Grimm. Better extensibility through modular syntax. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006.
[11]
Michael Hammer. An alternative approach to macro processing. In Proceedings of the International Symposium on Extensible Languages, Grenoble, France, 1971.
[12]
Timothy P. Hart. MACRO definitions for LISP. AI Memo 57, MIT AI Project-RLE and MIT Computation Center, 1973. (reproduced in Steele and Gabriel 1993).
[13]
Martin Hirzel and Robert Grimm. Jeannie: Granting Java native interface developers their wishes. In Proceedings of the 22nd annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, 2007.
[14]
Gregor Kiczales, John Lamping, Anurag Menhdhekar, Chris Maeda, Cristina Lopes, Jean-Marc Loingtier, and John Irwin. Aspect-oriented programming. In Proceedings of the European Conference on Object-Oriented Programming, 1997.
[15]
Charles Edwin Killian, James W. Anderson, Ryan Braud, Ranjit Jhala, and Amin M. Vahdat. Mace: language support for building distributed systems. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2007.
[16]
Donald E. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2(2):127--145, 1968.
[17]
Eugene Kohlbecker, Daniel P. Friedman, Matthias Felleisen, and Bruce Duba. Hygienic macro expansion. In Proceedings of the 1986 ACM Conference on LISP and Functional Programming, 1986.
[18]
Max Krohn, Eddie Kohler, and M. Frans Kaashoek. Events can make sense. In Proceedings of the 2007 USENIX Annual Technical Conference, 2007.
[19]
Sorin Lerner, Todd Millstein, and Craig Chambers. Automatically proving the correctness of compiler optimizations. In Proceedings of the 2003 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2003.
[20]
Sorin Lerner, Todd Millstein, Erika Rice, and Craig Chambers. Automated soundness proofs for dataflow analyses and transformations via local rules. In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2005.
[21]
Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, New Jersey, 1997.
[22]
George C. Necula, Scott McPeak, S. P. Rahul, and Westley Weimer. Cil: Intermediate language and tools for analysis and transformation of C programs. In Proceedings of the 11th International Conference on Compiler Construction, 2002.
[23]
Nathanial Nystrom, Michael Clarkson, and Andrew Myers. Polyglot: an extensible compiler framework for Java. In Proceedings of the 12th International Conference on Compiler Construction, 2003.
[24]
Nathanial Nystrom, Xin Qi, and Andrew Myers. J&: nested intersection for scalable software composiiton. In Proceedings of the 21st annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, 2006.
[25]
Jukka Paakki. Attribute grammar paradigm: a high-level methodology in language implementation. ACM Computing Surveys, 27(2):196--255, June 1995.
[26]
Guy L. Steele, Jr. and Richard P. Gabriel. The evolution of Lisp. In Proceedings of the 2nd ACM SIGPLAN Conference on History of Programming Languages, 1993.
[27]
W. Teitelman. Pilot: A step towards man-computer symbiosis. Technical Report AITR-221, Massachusetts Institute of Technology, 1966.
[28]
Masaru Tomita. An efficient augmented context-free parsing algorithm. Computational Linguistics, 13(1-2):31--46, January-June 1987.
[29]
Linus Torvalds and Josh Triplett. Sparse -- a semantic parser for C. http://www.kernel.org/pub/software/devel/sparse/ (retrieved December 2007), 2007.
[30]
Mark van den Brand, Jeroen Scheerder, Jurgen J. Vinju, and Eelco Visser. Disambiguation filters for scannerless generalized LR parsers. In Proceedings of the 11th International Conference on Compiler Construction, pages 143--158, 2002.
[31]
E. Van Wyk, D. Bodin, L. Krishnan, and J. Gao. Silver: an extensible attribute grammar system. In Proceedings of the 7th Workshop on Language Descriptions, Tools, and Analysis, 2007a.
[32]
Eric Van Wyk, Lijesh Krishnan, August Schwerdfeger, and Derek Bodin. Attribute grammar-based language extensions for Java. In Proceedings of the European Conference on Object-Oriented Programming, 2007b.
[33]
Eelco Visser. Program transformation with Stratego/XT. rules, strategies, tools, and systems in Stratego/XT 0.9. Technical Report UU-CS-2004-011, Institute of Information and Computing Sciences, Utrecht University, 2004.
[34]
Alessandro Warth, Milan Stanojević, and Todd Millstein. Statically scoped object adaptation with expanders. In Proceedings of the 21st annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, 2006.
[35]
Daniel Weise and Roger Crew. Programmable syntax macros. In Proceedings of the 1993 ACMSIGPLAN Conference on Programming Language Design and Implementation, 1993.
[36]
Phil Winterbottom. Alef reference manual. In Plan 9 Programmers Manual, Volume Two. Harcourt Brace Jovanovich, 1995.
Index Terms
- Xoc, an extension-oriented compiler for systems programming
Recommendations
Xoc, an extension-oriented compiler for systems programming
ASPLOS '08Today's system programmers go to great lengths to extend the languages in which they program. For instance, system-specific compilers find errors in Linux and other systems, and add support for specialized control flow to Qt and event-based programs. ...
Xoc, an extension-oriented compiler for systems programming
ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systemsToday's system programmers go to great lengths to extend the languages in which they program. For instance, system-specific compilers find errors in Linux and other systems, and add support for specialized control flow to Qt and event-based programs. ...
Xoc, an extension-oriented compiler for systems programming
ASPLOS '08Today's system programmers go to great lengths to extend the languages in which they program. For instance, system-specific compilers find errors in Linux and other systems, and add support for specialized control flow to Qt and event-based programs. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2008352 pages
Copyright © 2008 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 ACM 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]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 March 2008
Published in SIGOPS Volume 42, Issue 2
Check for updates
Author Tag
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations32Total Citations
- 884Total Downloads
- Downloads (Last 12 months)10
- Downloads (Last 6 weeks)2
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in