research-article

Open access

A constraint language for static semantic analysis based on scope graphs

Authors:

Hendrik van Antwerpen,

Andrew Tolmach,

Guido WachsmuthAuthors Info & Claims

PEPM '16: Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

Pages 49 - 60

https://doi.org/10.1145/2847538.2847543

Published: 11 January 2016 Publication History

Abstract

In previous work, we introduced scope graphs as a formalism for describing program binding structure and performing name resolution in an AST-independent way. In this paper, we show how to use scope graphs to build static semantic analyzers. We use constraints extracted from the AST to specify facts about binding, typing, and initialization. We treat name and type resolution as separate building blocks, but our approach can handle language constructs---such as record field access---for which binding and typing are mutually dependent. We also refine and extend our previous scope graph theory to address practical concerns including ambiguity checking and support for a wider range of scope relationships. We describe the details of constraint generation for a model language that illustrates many of the interesting static analysis issues associated with modules and records.

References

[1]

F. Baader and T. Nipkow. Term rewriting and all that. Cambridge University Press, 1998.

Digital Library

[2]

J. A. Brzozowski. Derivatives of regular expressions. JACM, 11(4):481–494, 1964.

Digital Library

[3]

T. Ekman and G. Hedin. Modular name analysis for Java using JastAdd. In GTTSE, pages 422–436, 2006.

Digital Library

[4]

T. Ekman and G. Hedin. The JastAdd extensible Java compiler. In OOPSLA, pages 1–18, 2007.

Digital Library

[5]

S. Erdweg, O. Bracevac, E. Kuci, M. Krebs, and M. Mezini. A cocontextual formulation of type rules and its application to incremental type checking. In OOPSLA, pages 880–897, 2015.

Digital Library

[6]

S. Erdweg, T. van der Storm, M. Völter, L. Tratt, et al. Evaluating and comparing language workbenches: Existing results and benchmarks for the future. Computer Languages, Systems & Structures, 44:24–– 47, 2015.

Digital Library

[7]

G. Hedin. Reference attributed grammars. informaticaSI, 24(3), 2000.

[8]

B. Heeren, J. Hage, and S. D. Swierstra. Scripting the type inference process. In ICFP, pages 3–13, 2003.

Digital Library

[9]

U. Kastens and W. M. Waite. An abstract data type for name analysis. ACTA, 28(6):539–558, 1991.

Digital Library

[10]

L. C. L. Kats and E. Visser. The Spoofax language workbench: rules for declarative specification of languages and IDEs. In OOPSLA, pages 444–463, 2010.

Digital Library

[11]

D. E. Knuth. Semantics of context-free languages. mst, 2(2):127–145, 1968.

[12]

G. D. P. Konat, L. C. L. Kats, G. Wachsmuth, and E. Visser. Declarative name binding and scope rules. In SLE, pages 311–331, 2012.

[13]

R. Milner. A theory of type polymorphism in programming. jcss, 17(3):348–375, 1978.

[14]

P. Neron, A. P. Tolmach, E. Visser, and G. Wachsmuth. A theory of name resolution. In ESOP, pages 205–231, 2015.

[15]

J. Palsberg and M. I. Schwartzbach. Object-oriented type inference. In OOPSLA, pages 146–161, 1991.

Digital Library

[16]

J. Palsberg and M. I. Schwartzbach. Object-oriented type systems. Wiley professional computing. Wiley, 1994.

Digital Library

[17]

H. van Antwerpen, P. Neron, A. P. Tolmach, E. Visser, and G. Wachsmuth. A constraint language for static semantic analysis based on scope graphs with proofs. Technical Report TUD-SERG-2015-012, Software Engineering Research Group, Delft University of Technology, 2015. Available at http://swerl.tudelft.nl/twiki/pub/ Main/TechnicalReports/TUD-SERG-2015-012.pdf.

[18]

E. Visser, G. Wachsmuth, A. P. Tolmach, P. Neron, V. A. Vergu, A. Passalaqua, and G. D. P. Konat. A language designer’s workbench: A one-stop-shop for implementation and verification of language designs. In OOPSLA, pages 95–111, 2014.

Digital Library

[19]

G. Wachsmuth, G. D. P. Konat, V. A. Vergu, D. M. Groenewegen, and E. Visser. A language independent task engine for incremental name and type analysis. In SLE, pages 260–280, 2013.

[20]

D. Zhang and A. C. Myers. Toward general diagnosis of static errors. In POPL, pages 569–582, 2014.

Digital Library

[21]

D. Zhang, A. C. Myers, D. Vytiniotis, and S. L. P. Jones. Diagnosing type errors with class. In PLDI, pages 12–21, 2015.

Digital Library

Cited By

Frölich Dvan Binsbergen LChiba SThüm T(2024)On the Soundness of Auto-completion Services for Dynamically Typed LanguagesProceedings of the 23rd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3689484.3690734(107-120)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3689484.3690734
Bunte ODenkers Jvan Gool LVinju JVisser EWillemse TZaidman A(2024)OIL: an industrial case study in language engineering with SpoofaxSoftware and Systems Modeling10.1007/s10270-024-01185-xOnline publication date: 3-Jun-2024
https://doi.org/10.1007/s10270-024-01185-x
Bach Poulsen CZwaan AHübner PDe Roover CRumpe BShaikhha A(2023)A Monadic Framework for Name Resolution in Multi-phased Type CheckersProceedings of the 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3624007.3624051(14-28)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3624007.3624051
Show More Cited By

Index Terms

A constraint language for static semantic analysis based on scope graphs
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation

Recommendations

A Language Designer's Workbench: A One-Stop-Shop for Implementation and Verification of Language Designs
Onward! 2014: Proceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software

The realization of a language design requires multiple artifacts that redundantly encode the same information. This entails significant effort for language implementors, and often results in late detection of errors in language definitions. In this ...
The spoofax name binding language
SPLASH '12: Proceedings of the 3rd annual conference on Systems, programming, and applications: software for humanity

In textual software languages, names are used to identify program elements such as variables, methods, and classes. Name analysis algorithms resolve names in order to establish references between definitions and uses of names. In this poster, we present ...
Binders unbound
ICFP '11: Proceedings of the 16th ACM SIGPLAN international conference on Functional programming

Implementors of compilers, program refactorers, theorem provers, proof checkers, and other systems that manipulate syntax know that dealing with name binding is difficult to do well. Operations such as α-equivalence and capture-avoiding substitution ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '16: Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

January 2016

108 pages

ISBN:9781450340977

DOI:10.1145/2847538

Program Chairs:
Martin Erwig
Oregon State University, USA
,
Tiark Rompf
Purdue University, USA

Copyright © 2016 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 January 2016

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL '16

Sponsor:

SIGPLAN

POPL '16: The 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 18 - 19, 2016

FL, St. Petersburg, USA

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
1,636
Total Downloads

Downloads (Last 12 months)231
Downloads (Last 6 weeks)26

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Frölich Dvan Binsbergen LChiba SThüm T(2024)On the Soundness of Auto-completion Services for Dynamically Typed LanguagesProceedings of the 23rd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3689484.3690734(107-120)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3689484.3690734
Bunte ODenkers Jvan Gool LVinju JVisser EWillemse TZaidman A(2024)OIL: an industrial case study in language engineering with SpoofaxSoftware and Systems Modeling10.1007/s10270-024-01185-xOnline publication date: 3-Jun-2024
https://doi.org/10.1007/s10270-024-01185-x
Bach Poulsen CZwaan AHübner PDe Roover CRumpe BShaikhha A(2023)A Monadic Framework for Name Resolution in Multi-phased Type CheckersProceedings of the 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3624007.3624051(14-28)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3624007.3624051
Miljak LBach Poulsen Cvan Spaendonck FTomb A(2023)Verifying Well-Typedness Preservation of Refactorings using Scope GraphsProceedings of the 25th ACM International Workshop on Formal Techniques for Java-like Programs10.1145/3605156.3606455(44-50)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3605156.3606455
Zwaan AFischer BBurgueño LCazzola W(2022)Specializing Scope Graph Resolution QueriesProceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3567512.3567523(121-133)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3567512.3567523
Pelsmaeker Dvan Antwerpen HPoulsen CVisser E(2022)Language-parametric static semantic code completionProceedings of the ACM on Programming Languages10.1145/35273296:OOPSLA1(1-30)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527329
Denkers JBrunner Mvan Gool LVisser E(2021)Configuration Space Exploration for Digital Printing SystemsSoftware Engineering and Formal Methods10.1007/978-3-030-92124-8_24(423-442)Online publication date: 3-Dec-2021
https://doi.org/10.1007/978-3-030-92124-8_24
Ballantyne MKing AFelleisen M(2020)Macros for domain-specific languagesProceedings of the ACM on Programming Languages10.1145/34282974:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428297
Rouvoet Avan Antwerpen HBach Poulsen CKrebbers RVisser E(2020)Knowing when to ask: sound scheduling of name resolution in type checkers derived from declarative specificationsProceedings of the ACM on Programming Languages10.1145/34282484:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428248
de Souza Amorim LVisser E(2020)Multi-purpose Syntax Definition with SDF3Software Engineering and Formal Methods10.1007/978-3-030-58768-0_1(1-23)Online publication date: 8-Sep-2020
https://doi.org/10.1007/978-3-030-58768-0_1
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents