A talk about scope graphs at Curry On 2017 in Barcelona

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. In this talk I present scope graphs, 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. I will demonstrate how the Spoofax language workbench uses scope graphs to implement name resolution in IDEs and memory models in interpreters.

Talk by Casper Bach Poulsen at ECOOP 2016 about the paper:

Casper Bach Poulsen, Pierre Néron, Andrew P. Tolmach, Eelco Visser. Scopes Describe Frames: A Uniform Model for Memory Layout in Dynamic Semantics. In Shriram Krishnamurthi, Benjamin S. Lerner, editors, 30th European Conference on Object-Oriented Programming, ECOOP 2016, July 18-22, 2016, Rome, Italy. Volume 56 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. [PDF] [researchr]

Abstract: Semantic specifications do not make a systematic connection between the names and scopes in the static structure of a program and memory layout, and access during its execution. In this paper, we introduce a systematic approach to the alignment of names in static semantics and memory in dynamic semantics, building on the scope graph framework for name resolution. We develop a uniform memory model consisting of frames that instantiate the scopes in the scope graph of a program. This provides a language-independent correspondence between static scopes and run-time memory layout, and between static resolution paths and run-time memory access paths. The approach scales to a range of binding features, supports straightforward type soundness proofs, and provides the basis for a language-independent specification of sound reachability-based garbage collection.

Talk by Daco Harkes at ECOOP 2016 about the paper:

Daco Harkes, Danny M. Groenewegen, Eelco Visser. IceDust: Incremental and Eventual Computation of Derived Values in Persistent Object Graphs. In Shriram Krishnamurthi, Benjamin S. Lerner, editors, 30th European Conference on Object-Oriented Programming, ECOOP 2016, July 18-22, 2016, Rome, Italy. Volume 56 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.b [doi]

Abstract: Derived values are values calculated from base values. They can be expressed in object-oriented languages by means of getters calculating the derived value, and in relational or logic databases by means of (materialized) views. However, switching to a different calculation strategy (for example caching) in object-oriented programming requires invasive code changes, and the databases limit expressiveness by disallowing recursive aggregation. In this paper, we present IceDust, a data modeling language for expressing derived attribute values without committing to a calculation strategy. IceDust provides three strategies for calculating derived values in persistent object graphs: Calculate-on-Read, Calculate-on-Write, and Calculate-Eventually. We have developed a path-based abstract interpretation that provides static dependency analysis to generate code for these strategies. Benchmarks show that different strategies perform better in different scenarios. In addition we have conducted a case study that suggests that derived value calculations of systems used in practice can be expressed in IceDust.

most of tu delft pl group

An incomplete group photo of the SLDE research group at TU Delft. From left to right:

  • Hendrik van Antwerpen
  • Guido Wachsmuth
  • Martijn Dwars
  • Jeff Smits
  • Gabriël Konat
  • Casper Bach Poulsen
  • Vlad Vergu
  • Eduardo Amorim
  • Daco Harkes

Missing are

  • Elmer van Chastelet
  • Danny Groenewegen
  • Jeffrey Goderie
  • Voker Lanting
  • Daniël Pelsmaeker
  • Joey Ezechiëls

and the photographer

  • Eelco Visser