Article

Static analysis for syntax objects

Authors:

Olin ShiversAuthors Info & Claims

ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming

Pages 111 - 121

https://doi.org/10.1145/1159803.1159817

Published: 16 September 2006 Publication History

Abstract

We describe an s-expression based syntax-extension framework much like Scheme macros, with a key additional facility: the ability to define static semantics, such as type systems or program analysis, for the new, user-defined forms or embedded languages, thus allowing us to construct "towers" of language levels. In addition, the static semantics of the languages at two adjacent levels in the tower can be connected, allowing improved reasoning power at a higher (and perhaps more restricted) level to be reflected down to the static semantics of the language level below. We demonstrate our system by designing macros for an assembly language, together with some example static analyses (termination analysis, type inference and control-flow analysis).

References

[1]

Alan Bawden. Reification without evaluation. In LFP '88: Proceedings of the 1988 ACM conference on LISP and functional programming, pages 342--349, New York, NY, USA, 1988. ACM Press.]]

Digital Library

[2]

William Clinger. Macros that work. In POPL '91: Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 155--162, New York, NY, USA, 1991. ACM Press.]]

Digital Library

[3]

R. Kent Dybvig, Robert Hieb, and Carl Bruggeman. Syntactic abstraction in scheme. Lisp Symb. Comput., 5(4):295--326, 1992.]]

Digital Library

[4]

Robert Bruce Findler, John Clements, Matthew Flatt Cormac Flanagan, Shriram Krishnamurthi, Paul Steckler, and Matthias Felleisen. DrScheme: A progamming environment for Scheme. Journal of Functional Programming, 12(2):159--182, March 2002.]]

Digital Library

[5]

Matthew Flatt. Composable and compilable macros: you want it when? In ICFP '02: Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, pages 72--83, New York, NY, USA, 2002. ACM Press.]]

Digital Library

[6]

Dan Friedman. Object-oriented style. Invited talk at International LISP Conference, October 2003.]]

[7]

Daniel P. Friedman, William E. Byrd, and Oleg Kiselyov. The Reasoned Schemer. The MIT Press, Cambridge, MA, 2005.]]

Digital Library

[8]

Kathryn E Gray and Matthew Flatt. Compiling Java to PLT Scheme. In Proceedings of the 2004 Scheme Workshop, September 2004.]]

[9]

Graham Hutton and ErikMeijer. Monadic Parsing in Haskell. Journal of Functional Programming, 8(4):437--444, July 1998.]]

Digital Library

[10]

R. Kelsey, W. Clinger, and J. Rees (eds.). Revised5 report on the algorithmic language Scheme. Higher-Order and Symbolic Computations, 11(1), August 1998.]]

Digital Library

[11]

Shriram Krishnamurthi, Yan-David Erlich, and Matthias Felleisen. Expressing structural properties as language constructs. In ESOP '99: Proceedings of the 8th European Symposium on Programming Languages and Systems, pages 258--272, London, UK, 1999. Springer-Verlag.]]

Digital Library

[12]

Shriram Krishnamurthi and Matthias Felleisen. Toward a formal theory of extensible software. In SIGSOFT '98/FSE-6: Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, pages 88--98, New York, NY, USA, 1998. ACM Press.]]

Digital Library

[13]

Shriram Krishnamurthi, Matthias Felleisen, and Bruce F. Duba. From macros to reusable generative programming. In GCSE '99: Proceedings of the First International Symposium on Generative and Component-Based Software Engineering, pages 105--120, London, UK, 2000. Springer-Verlag.]]

Digital Library

[14]

Daan Leijen and Erik Meijer. Parsec: Direct style monadic parser combinators for the real world. Technical Report UU-CS-2001-27, Department of Computer Science, Universiteit Utrecht, 2001.]]

[15]

William Maddox. Semantically-sensitive macroprocessing. Technical report, University of California at Berkeley, Berkeley, CA, USA, 1989.]]

Digital Library

[16]

Greg Morrisett, David Walker, Karl Crary, and Neal Glew. From system F to typed assembly language. ACM Trans. Program. Lang. Syst., 21(3):527--568, 1999.]]

Digital Library

[17]

Ravi A. Nanavati. Extensible syntax in the presence of static analysis. MasterÆs thesis, Massachusetts Institute of Technology, September 2000.]]

[18]

Benjamin Pierce, editor. Advanced Topics in Types and Programming Languages. The MIT Press, Cambridge, MA, 2005.]]

Digital Library

[19]

Francois Pottier and Didier Remy. The Essence of ML Type Inference, pages 389--489. In Pierce {18}, 2005.]]

[20]

Olin Shivers. Control-Flow Analysis of Higher-Order Languages, or Taming Lambda. PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1991. Technical Report CMU-CS-91-145.]]

Digital Library

[21]

Olin Shivers. The anatomy of a loop: a story of scope and control. In Proceedings of the 10th ACM SIGPLAN International Conference on Functional Programming (ICFP 2005), pages 2--14, Tallinn, Estonia, September 2005. ACM Press.]]

Digital Library

[22]

Randall B. Smith and David Ungar. Programming as an experience: The inspiration for Self. In ECOOP '95: Proceedings of the 9th European Conference on Object-Oriented Programming, pages 303--330, London, UK, 1995. Springer-Verlag.]]

Digital Library

[23]

Walid Taha and Tim Sheard. Multi-stage programming with explicit annotations. In PEPM '97: Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, pages 203--217, New York, NY, USA, 1997. ACM Press.]]

Digital Library

[24]

David Ungar and Randall B. Smith. Self: The power of simplicity. In OOPSLA '87: Conference proceedings on Object-oriented programming systems, languages and applications, pages 227--242, New York, NY, USA, 1987. ACM Press.]]

Digital Library

[25]

Dale Vaillancourt. ACL2 in DrScheme. http://www.ccs.neu.edu/home/dalev/acl2-drscheme/.]]

[26]

Mitchell Wand. Complete type inference for simple objects. In Proceedings of the IEEE Symposium on Logic in Computer Science, June 1987.]]

[27]

Daniel Weise and Roger Crew. Programmable syntax macros. SIGPLAN Not., 28(6):156--165, 1993.]]

Digital Library

[28]

Eric Van Wyk, Oege de Moor, Kevin Backhouse, and Paul Kwiatkowski. Forwarding in attribute grammars for modular language design. In CC '02:Proceedings of the 11th International Conference on Compiler Construction, pages 128--142, London, UK, 2002. Springer-Verlag.]]

Digital Library

Cited By

Yang ZXiao YGuan ZHu Z(2022)A Lazy Desugaring System for Evaluating Programs with SugarsFunctional and Logic Programming10.1007/978-3-030-99461-7_14(243-261)Online publication date: 3-May-2022
https://doi.org/10.1007/978-3-030-99461-7_14
Pombrio JKrishnamurthi S(2018)Inferring type rules for syntactic sugarACM SIGPLAN Notices10.1145/3296979.319239853:4(812-825)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192398
Pombrio JKrishnamurthi SFoster JGrossman D(2018)Inferring type rules for syntactic sugarProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192398(812-825)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192398
Show More Cited By

Recommendations

Static analysis for syntax objects
Proceedings of the 2006 ICFP conference

We describe an s-expression based syntax-extension framework much like Scheme macros, with a key additional facility: the ability to define static semantics, such as type systems or program analysis, for the new, user-defined forms or embedded languages,...
Concrete syntax for objects: domain-specific language embedding and assimilation without restrictions
OOPSLA '04

Application programmer's interfaces give access to domain knowledge encapsulated in class libraries without providing the appropriate notation for expressing domain composition. Since object-oriented languages are designed for extensibility and reuse, ...
Composable and hygienic typed syntax macros
SAC '15: Proceedings of the 30th Annual ACM Symposium on Applied Computing

Syntax extension mechanisms are powerful, but reasoning about syntax extensions can be difficult. Recent work on type-specific languages (TSLs) addressed reasoning about composition, hygiene and typing for extensions introducing new literal forms. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming

September 2006

308 pages

ISBN:1595933093

DOI:10.1145/1159803

General Chair:
John Reppy
University of Chicago, USA
,
Program Chair:
Julia Lawall
University of Copenhagen, Denmark

ACM SIGPLAN Notices Volume 41, Issue 9
Proceedings of the 2006 ICFP conference
September 2006
296 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1160074
Issue’s Table of Contents

Copyright © 2006 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: 16 September 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICFP06

Sponsor:

ICFP06: ACM SIGPLAN International Conference on Functional Programming

September 16 - 21, 2006

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
542
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang ZXiao YGuan ZHu Z(2022)A Lazy Desugaring System for Evaluating Programs with SugarsFunctional and Logic Programming10.1007/978-3-030-99461-7_14(243-261)Online publication date: 3-May-2022
https://doi.org/10.1007/978-3-030-99461-7_14
Pombrio JKrishnamurthi S(2018)Inferring type rules for syntactic sugarACM SIGPLAN Notices10.1145/3296979.319239853:4(812-825)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192398
Pombrio JKrishnamurthi SFoster JGrossman D(2018)Inferring type rules for syntactic sugarProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192398(812-825)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192398
Pombrio JKrishnamurthi SWand M(2017)Inferring scope through syntactic sugarProceedings of the ACM on Programming Languages10.1145/31102881:ICFP(1-28)Online publication date: 29-Aug-2017
https://dl.acm.org/doi/10.1145/3110288
Chang SKnauth AGreenman B(2017)Type systems as macrosACM SIGPLAN Notices10.1145/3093333.300988652:1(694-705)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3093333.3009886
Chang SKnauth AGreenman BCastagna GGordon A(2017)Type systems as macrosProceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages10.1145/3009837.3009886(694-705)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3009837.3009886
Pombrio JKrishnamurthi S(2014)ResugaringACM SIGPLAN Notices10.1145/2666356.259431949:6(361-371)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2666356.2594319
Pombrio JKrishnamurthi SO'Boyle MPingali K(2014)ResugaringProceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2594291.2594319(361-371)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2594291.2594319
Viera MSwierstra SPlasmeijer R(2013)First Class Syntax, Semantics, and Their CompositionProceedings of the 25th symposium on Implementation and Application of Functional Languages10.1145/2620678.2620686(73-84)Online publication date: 28-Aug-2013
https://dl.acm.org/doi/10.1145/2620678.2620686
Lorenzen FErdweg S(2013)Modular and automated type-soundness verification for language extensionsACM SIGPLAN Notices10.1145/2544174.250059648:9(331-342)Online publication date: 25-Sep-2013
https://dl.acm.org/doi/10.1145/2544174.2500596
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.

Figures

Tables

Media

View Table of Conten