Russ Cox
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.
Supplemental Material
Available for Download
Slides from the presentation
Supplemental material for Xoc, an extension-oriented compiler for systems programming
- 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. Google Scholar
Digital Library
- 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. Google ScholarDigital Library
- Tom Bergan. Typmix: a framework for implementing modular, extensible type systems. Master's thesis, University of California Los Angeles, 2007.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns. Addison-Wesley, Reading, Massachusetts, 1994.Google Scholar
- Paul Graham. On LISP: Advanced Techniques for Common LISP. Prentice-Hall, 1996. Google ScholarDigital Library
- Robert Grimm. Better extensibility through modular syntax. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006. Google ScholarDigital Library
- Michael Hammer. An alternative approach to macro processing. In Proceedings of the International Symposium on Extensible Languages, Grenoble, France, 1971. Google ScholarDigital Library
- 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). Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Donald E. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2(2):127--145, 1968.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Max Krohn, Eddie Kohler, and M. Frans Kaashoek. Events can make sense. In Proceedings of the 2007 USENIX Annual Technical Conference, 2007. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, New Jersey, 1997. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Jukka Paakki. Attribute grammar paradigm: a high-level methodology in language implementation. ACM Computing Surveys, 27(2):196--255, June 1995. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- W. Teitelman. Pilot: A step towards man-computer symbiosis. Technical Report AITR-221, Massachusetts Institute of Technology, 1966. Google ScholarDigital Library
- Masaru Tomita. An efficient augmented context-free parsing algorithm. Computational Linguistics, 13(1-2):31--46, January-June 1987. Google ScholarDigital Library
- Linus Torvalds and Josh Triplett. Sparse -- a semantic parser for C. http://www.kernel.org/pub/software/devel/sparse/ (retrieved December 2007), 2007.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Daniel Weise and Roger Crew. Programmable syntax macros. In Proceedings of the 1993 ACMSIGPLAN Conference on Programming Language Design and Implementation, 1993. Google ScholarDigital Library
- Phil Winterbottom. Alef reference manual. In Plan 9 Programmers Manual, Volume Two. Harcourt Brace Jovanovich, 1995.Google Scholar
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 '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 '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