Scope Graphs | A Theory of Name Resolution
Names are crucial for organizing and understanding programs. Yet names and name binding get a second class treatment in programming language definition. We have a fairly standardized approach based on context-free grammars to provide tool independent descriptions of the syntax of programming languages. There is no analog for describing the name binding rules of programming languages. It is hard to explain the rules and they are encoded in many different ways in implementations of programming language tools.
Scope graphs provide a new approach to defining the name binding rules of programming languages. A scope graph represents the name binding facts of a program using the basic concepts of declarations and reference associated with scopes that are connected by edges. Name resolution is defined by searching for paths from references to declarations in a scope graph. Scope graph diagrams provide an illuminating visual notation for explaining the bindings in programs. But scope graphs are more than pretty pictures. The foundational resolution calculus provides the basis for generic, language-independent implementation of a range of tools involving name binding. The Spoofax language workbench uses scope graphs to implement name resolution in IDEs and memory models in interpreters.
Blog Posts | Slides | Talk Videos
- Declarative Type System Specification with Statix at WG2.16 in Portland February 2016
- Scopes as Types at OOPSLA 2018
- Spoofax: Live Programming Language Design at Curry On 2018
- Intrinsically Typed Definitional Interpreters for Imperative Languages at POPL 2018
- Scope Graphs: A Fresh Look at Name Binding in Programming Languages at Cury On 2017
- Scopes Describe Frames: A Uniform Model for Memory Layout in Dynamic Semantics at ECOOP 2016
- A Constraint-based Approach to Name Binding and Type Checking using Scope Graphs
- A Constraint Language for Static Semantic Analysis based on Scope Graphs
- Type-Dependent Name Resolution
Publications
2023
2022
- Incremental type-checking for free: using scope graphs to derive incremental type-checkersPACMPL, 6(OOPSLA2):424-448, 2022. [doi]
2021
2020
2019
2018
- Intrinsically-typed definitional interpreters for imperative languagesPACMPL, 2(POPL), 2018. [doi]
- Scopes as typesPACMPL, 2(OOPSLA), 2018. [doi]
2017
2016
- Scopes Describe Frames: A Uniform Model for Memory Layout in Dynamic SemanticsECOOP 2016: [doi]
- Scopes Describe Frames: A Uniform Model for Memory Layout in Dynamic Semantics (Artifact)darts, 2(1), 2016. [doi]
- A Constraint-based Approach to Name Binding and Type Checking using Scope GraphsMaster's thesis, Delft University of Technology, January 2016.
- A constraint language for static semantic analysis based on scope graphsPEPM 2016: 49-60 [doi]
2015
- A Theory of Name ResolutionESOP 2015: 205-231 [doi]
- Language-Independent Type-Dependent Name ResolutionTechnical Report TUD-SERG-2015-006, 2015.
- A Constraint Language for Static Semantic Analysis based on Scope Graphs with ProofsTechnical Report TUD-SERG-2015-009, 2015.
2013
2012
- A language generic solution for name binding preservation in refactoringsLDTA 2012: 2 [doi]
- The Spoofax Name Binding LanguageIn Companion to the 27th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2011, part of SPLASH 2012, Tucson, AR, USA, October 19 - 26, 2012. 2012: [doi]
- Declarative Name Binding and Scope RulesSLE 2012: 311-331 [doi]
2006
- Program Transformation with Scoped Dynamic Rewrite RulesFUIN, 69(1-2):123-178, 2006. [doi]
2001
- Scoped Dynamic Rewrite RulesENTCS, 59(4):375-396, 2001. [doi]