2 Search Results for "Creager, Douglas A."

Document
DOI: 10.4230/OASIcs.EVCS.2023.8
Stack Graphs: Name Resolution at Scale

Authors: Douglas A. Creager and Hendrik van Antwerpen

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract
We present stack graphs, an extension of Visser et al.’s scope graphs framework. Stack graphs power Precise Code Navigation at GitHub, allowing users to navigate name binding references both within and across repositories. Like scope graphs, stack graphs encode the name binding information about a program in a graph structure, in which paths represent valid name bindings. Resolving a reference to its definition is then implemented with a simple path-finding search. GitHub hosts millions of repositories, containing petabytes of total code, implemented in hundreds of different programming languages, and receiving thousands of pushes per minute. To support this scale, we ensure that the graph construction and path-finding judgments are file-incremental: for each source file, we create an isolated subgraph without any knowledge of, or visibility into, any other file in the program. This lets us eliminate the storage and compute costs of reanalyzing file versions that we have already seen. Since most commits change a small fraction of the files in a repository, this greatly amortizes the operational costs of indexing large, frequently changed repositories over time. To handle type-directed name lookups (which require "pausing" the current lookup to resolve another name), our name resolution algorithm maintains a stack of the currently paused (but still pending) lookups. Stack graphs can be constructed via a purely syntactic analysis of the program’s source code, using a new declarative graph construction language. This means that we can extract name binding information for every repository without any per-package configuration, and without having to invoke an arbitrary, untrusted, package-specific build process.
Cite as

Douglas A. Creager and Hendrik van Antwerpen. Stack Graphs: Name Resolution at Scale. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{creager_et_al:OASIcs.EVCS.2023.8,
  author =	{Creager, Douglas A. and van Antwerpen, Hendrik},
  title =	{{Stack Graphs: Name Resolution at Scale}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{8:1--8:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.8},
  URN =		{urn:nbn:de:0030-drops-177789},
  doi =		{10.4230/OASIcs.EVCS.2023.8},
  annote =	{Keywords: Scope graphs, name binding, code navigation}
}
Document
DOI: 10.4230/OASIcs.EVCS.2023.32
Scope Graphs: The Story so Far

Authors: Aron Zwaan and Hendrik van Antwerpen

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract
Static name binding (i.e., associating references with appropriate declarations) is an essential aspect of programming languages. However, it is usually treated in an unprincipled manner, often leaving a gap between formalization and implementation. The scope graph formalism mitigates these deficiencies by providing a well-defined, first-class, language-parametric representation of name binding. Scope graphs serve as a foundation for deriving type checkers from declarative type system specifications, reasoning about type soundness, and implementing editor services and refactorings. In this paper we present an overview of scope graphs, and, using examples, show how the ideas and notation of the formalism have evolved. We also briefly discuss follow-up research beyond type checking, and evaluate the formalism.
Cite as

Aron Zwaan and Hendrik van Antwerpen. Scope Graphs: The Story so Far. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zwaan_et_al:OASIcs.EVCS.2023.32,
  author =	{Zwaan, Aron and van Antwerpen, Hendrik},
  title =	{{Scope Graphs: The Story so Far}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{32:1--32:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.32},
  URN =		{urn:nbn:de:0030-drops-178020},
  doi =		{10.4230/OASIcs.EVCS.2023.32},
  annote =	{Keywords: scope graph, name binding, reference resolution, type system, static semantics}
}
  • Refine by Author
  • 2 van Antwerpen, Hendrik
  • 1 Creager, Douglas A.
  • 1 Zwaan, Aron

  • Refine by Classification
  • 2 Theory of computation → Program analysis
  • 1 Software and its engineering → Software libraries and repositories
  • 1 Theory of computation → Program semantics
  • 1 Theory of computation → Program specifications

  • Refine by Keyword
  • 2 name binding
  • 1 Scope graphs
  • 1 code navigation
  • 1 reference resolution
  • 1 scope graph
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact