Compiler Construction bio photo

Compiler Construction

Twitter Github

Edit on GitHub

Lecture 8: Constraint Semantics & Resolution

In this lecture we study constraint-based static semantic analysis using the scope graph framework for name resolution.


Compiler Construction | Lecture 8 | Type Constraints from Eelco Visser
Compiler Construction | Lecture 9 | Constraint Resolution from Eelco Visser

Reading Material

  • Hendrik van Antwerpen, Casper Bach Poulsen, Arjen Rouvoet, Eelco Visser. Scopes as types. Proceedings of the ACM on Programming Languages, 2 (OOPSLA), 2018. This paper introduces Statix, a language for writing static semantics specifications.

  • Pierre Néron, Andrew P. Tolmach, Eelco Visser, Guido Wachsmuth. A Theory of Name Resolution. In Jan Vitek, editor, Programming Languages and Systems - 24th European Symposium on Programming, ESOP 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015. Proceedings. Volume 9032 of Lecture Notes in Computer Science, pages 205-231, Springer, 2015. This paper introduces the scope graph model for the representation of name binding facts in programs and the resolution calculus to resolve names in scope graphs.

  • Baader, Franz, Wayne Snyder, Paliath Narendran, Manfred Schmidt-Schauss, and Klaus Schulz. “Chapter 8 - Unification Theory.” In Handbook of Automated Reasoning, edited by Alan Robinson and Andrei Voronkov, 445–533. Handbook of Automated Reasoning. Amsterdam: North-Holland, 2001. This is a good introduction to term unification. The course material is covered in §1 and §2.

Additional Reading Material

  • Hendrik van Antwerpen, Pierre Néron, Andrew P. Tolmach, Eelco Visser, Guido Wachsmuth. A constraint language for static semantic analysis based on scope graphs. In Martin Erwig, Tiark Rompf, editors, Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2016, St. Petersburg, FL, USA, January 20 - 22, 2016. pages 49-60, ACM, 2016. This paper develops a constraint language for description of type system using scope graph constraints for the definition of name binding. These constraints are the basis for the NaBL2 language.

  • Gabriël Konat, Lennart C. L. Kats, Guido Wachsmuth, Eelco Visser. Declarative Name Binding and Scope Rules. In Krzysztof Czarnecki, Görel Hedin, editors, Software Language Engineering, 5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers. Volume 7745 of Lecture Notes in Computer Science, pages 311-331, Springer, 2012. This paper introduces the NaBL language for describing the name binding rules of programming languages. This work inspired the development of the scope graph model.