research-article

Xoc, an extension-oriented compiler for systems programming

Authors:

Austin T. Clements,

Frans Kaashoek,

Eddie KohlerAuthors Info & Claims

ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systems

Pages 244 - 254

https://doi.org/10.1145/1346281.1346312

Published: 01 March 2008 Publication History

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

index.html (index.html)

Slides from the presentation

Download
.98 KB

ZIP File (p244-cox-slides.zip)

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[10]

Robert Grimm. Better extensibility through modular syntax. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006.

Digital Library

[11]

Michael Hammer. An alternative approach to macro processing. In Proceedings of the International Symposium on Extensible Languages, Grenoble, France, 1971.

Digital Library

[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).

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[18]

Max Krohn, Eddie Kohler, and M. Frans Kaashoek. Events can make sense. In Proceedings of the 2007 USENIX Annual Technical Conference, 2007.

Digital Library

[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.

Digital Library

[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.

Digital Library

[21]

Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, New Jersey, 1997.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[25]

Jukka Paakki. Attribute grammar paradigm: a high-level methodology in language implementation. ACM Computing Surveys, 27(2):196--255, June 1995.

Digital Library

[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.

Digital Library

[27]

W. Teitelman. Pilot: A step towards man-computer symbiosis. Technical Report AITR-221, Massachusetts Institute of Technology, 1966.

Digital Library

[28]

Masaru Tomita. An efficient augmented context-free parsing algorithm. Computational Linguistics, 13(1-2):31--46, January-June 1987.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[35]

Daniel Weise and Roger Crew. Programmable syntax macros. In Proceedings of the 1993 ACMSIGPLAN Conference on Programming Language Design and Implementation, 1993.

Digital Library

[36]

Phil Winterbottom. Alef reference manual. In Plan 9 Programmers Manual, Volume Two. Harcourt Brace Jovanovich, 1995.

Cited By

Seitz KFoley TPorumbescu SOwens J(2019)Staged metaprogramming for shader system developmentACM Transactions on Graphics10.1145/3355089.335655438:6(1-15)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3355089.3356554
Carlson TVan Wyk E(2017)Type qualifiers as composable language extensionsACM SIGPLAN Notices10.1145/3170492.313605552:12(91-103)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3170492.3136055
Kaminski TKramer LCarlson TVan Wyk E(2017)Reliable and automatic composition of language extensions to C: the ableC extensible language frameworkProceedings of the ACM on Programming Languages10.1145/31382241:OOPSLA(1-29)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3138224
Show More Cited By

Index Terms

Xoc, an extension-oriented compiler for systems programming
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Xoc, an extension-oriented compiler for systems programming
ASPLOS '08

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. ...
Xoc, an extension-oriented compiler for systems programming
ASPLOS '08

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. ...
Xoc, an extension-oriented compiler for systems programming
ASPLOS '08

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. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systems

March 2008

352 pages

ISBN:9781595939586

DOI:10.1145/1346281

General Chair:
Susan Eggers
University of Washington, USA
,
Program Chair:
James Larus
Microsoft Research, USA

ACM SIGPLAN Notices Volume 43, Issue 3
ASPLOS '08
March 2008
339 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1353536
Issue’s Table of Contents
ACM SIGARCH Computer Architecture News Volume 36, Issue 1
ASPLOS '08
March 2008
339 pages
ISSN:0163-5964
DOI:10.1145/1353534
Issue’s Table of Contents
ACM SIGOPS Operating Systems Review Volume 42, Issue 2
ASPLOS '08
March 2008
339 pages
ISSN:0163-5980
DOI:10.1145/1353535
Issue’s Table of Contents

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

extension-oriented compilers

Qualifiers

Research-article

Conference

ASPLOS08

Sponsor:

ASPLOS08: Architectural Support for Programming Languages and Operating Systems

March 1 - 5, 2008

WA, Seattle, USA

Acceptance Rates

ASPLOS XIII Paper Acceptance Rate 31 of 127 submissions, 24%;

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
884
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Seitz KFoley TPorumbescu SOwens J(2019)Staged metaprogramming for shader system developmentACM Transactions on Graphics10.1145/3355089.335655438:6(1-15)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3355089.3356554
Carlson TVan Wyk E(2017)Type qualifiers as composable language extensionsACM SIGPLAN Notices10.1145/3170492.313605552:12(91-103)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3170492.3136055
Kaminski TKramer LCarlson TVan Wyk E(2017)Reliable and automatic composition of language extensions to C: the ableC extensible language frameworkProceedings of the ACM on Programming Languages10.1145/31382241:OOPSLA(1-29)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3138224
Carlson TVan Wyk EFlatt MErdweg S(2017)Type qualifiers as composable language extensionsProceedings of the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3136040.3136055(91-103)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3136040.3136055
Omar CAldrich J(2016)Programmable semantic fragments: the design and implementation of typyACM SIGPLAN Notices10.1145/3093335.299324552:3(81-92)Online publication date: 20-Oct-2016
https://dl.acm.org/doi/10.1145/3093335.2993245
Omar CAldrich JFischer BSchaefer I(2016)Programmable semantic fragments: the design and implementation of typyProceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/2993236.2993245(81-92)Online publication date: 20-Oct-2016
https://dl.acm.org/doi/10.1145/2993236.2993245
Lorenzen FErdweg S(2016)Sound type-dependent syntactic language extensionACM SIGPLAN Notices10.1145/2914770.283764451:1(204-216)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2914770.2837644
Lorenzen FErdweg SBodik RMajumdar R(2016)Sound type-dependent syntactic language extensionProceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2837614.2837644(204-216)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2837614.2837644
Voelter MDeursen AKolb BEberle S(2015)Using C language extensions for developing embedded software: a case studyACM SIGPLAN Notices10.1145/2858965.281427650:10(655-674)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814276
Voelter MMolotnikov ZKolb BGray JSprinkle JTolvanen JRossi M(2015)Towards improving software security using language engineering and mbeddr CProceedings of the Workshop on Domain-Specific Modeling10.1145/2846696.2846698(55-62)Online publication date: 27-Oct-2015
https://dl.acm.org/doi/10.1145/2846696.2846698
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents