Reading list

The references page is the full bibliography. This one is the path through it: what each tradition contributes, which papers carry the weight, and where our own reading of them sits.

Attribute grammars

Knuth’s question was how to give a grammar a semantics: attach attributes to the nodes of a parse tree and define each one by a local rule over its neighbours, then let the values fall out by demand rather than by a schedule you wrote. The 1968 paper is the origin and the 1971 note is its correction — the well-definedness test in the original was wrong, which is worth knowing before citing it.

Everything after that is the tradition making the idea survive contact with real languages. Reference attribute grammars let a rule name a node elsewhere in the tree rather than only a neighbour, which is what turns a tree walk into a graph query. Higher-order attribute grammars let a computed value be a tree that is itself attributed. Both are load-bearing for configuration, where the thing you are resolving is a graph and the answer to one question builds the structure the next question is asked over. Termination is the price: once a rule can reach anywhere, showing the evaluation stops is a real proof obligation.

D. E. Knuth, “Semantics of context-free languages,” Theory of Computing Systems, vol. 2, no. 2, pp. 127–145, 1968.
doi:10.1007/bf01692511
D. E. Knuth, “Semantics of context-free languages: Correction,” Theory of Computing Systems, vol. 5, no. 2, pp. 95–96, 1971.
read the paper
L. Krishnan and E. Van Wyk, “Termination analysis for higher-order attribute grammars,” Software Language Engineering (SLE 2012), LNCS 7745, pp. 44–63, 2013.
our reading · read the paper
H. Vogt, S. D. Swierstra, and M. Kuiper, “Higher order attribute grammars,” PLDI89: Programming Language Design & Implementation, pp. 131–145, 1989.
our reading · read the paper
G. Hedin, “Reference Attributed Grammars,” 2000.
our reading
G. Hedin and E. Magnusson, “JastAdd—an aspect-oriented compiler construction system,” Science of Computer Programming, vol. 47, no. 1, pp. 37–58, 2003.
our reading · read the paper
E. Van Wyk, D. Bodin, J. Gao, and L. Krishnan, “Silver: An extensible attribute grammar system,” Science of Computer Programming, vol. 75, no. 1-2, pp. 39–54, 2010.
our reading · read the paper
A. M. Sloane, L. C. L. Kats, and E. Visser, “A pure object-oriented embedding of attribute grammars,” Electronic Notes in Theoretical Computer Science, vol. 253, no. 7, pp. 205–219, 2010.
our reading · doi:10.1016/j.entcs.2010.08.043
E. Söderberg and G. Hedin, “Circular Higher-Order Reference Attribute Grammars,” Lecture notes in computer science, pp. 302–321, 2013.
our reading · doi:10.1007/978-3-319-02654-1_17
J. Boyland, “Remote attribute grammars,” Journal of the ACM, vol. 52, no. 4, pp. 627–687, 2005.
doi:10.1145/1082036.1082042
T. Reps, T. Teitelbaum, and A. Demers, “Incremental Context-Dependent Analysis for Language-Based Editors,” ACM Transactions on Programming Languages and Systems, vol. 5, no. 3, pp. 449–477, 1983.
our reading · read the paper

Scope graphs

The direct answer to “what does this name refer to?” without walking a syntax tree. Néron et al. separate binding structure from the AST entirely: scopes are nodes, declarations and references hang off them, and resolution becomes a reachability query over labelled edges with a well-formedness condition on the paths. Statix then makes the resolution constraint-based, and Scopes as Types pushes the same machinery into type checking.

This is the closest thing in the literature to what gen’s resolution actually is, and the correspondence is structural rather than an analogy.

P. Néron, A. Tolmach, E. Visser, and G. Wachsmuth, “A Theory of Name Resolution,” Lecture notes in computer science, pp. 205–231, 2015.
our reading · read the paper
H. van Antwerpen, P. Néron, A. Tolmach, E. Visser, and G. Wachsmuth, “A constraint language for static semantic analysis based on scope graphs,” PEPM’16: Workshop on Partial Evaluation and Program Manipulation, pp. 49–60, 2016.
our reading · read the paper
H. van Antwerpen, C. Bach Poulsen, A. Rouvoet, and E. Visser, “Scopes as types,” Proceedings of the ACM on Programming Languages, vol. 2, no. OOPSLA, art. 114, 2018.
our reading · doi:10.1145/3276484

Rule systems and logic programming

A policy is a rule that produces edges, which makes the policy layer a logic program and inherits every question logic programming has already answered.

The delicate one is negation. A rule that fires on the absence of something can make a program have several equally good models, or none, and the literature’s answers — well-founded semantics, stable models, the alternating fixpoint, the stratification conditions — are about which of those you are allowed to call the answer. This is why a policy layer that admits negation has to either restrict what you can write or refuse a program it cannot decide. Datafun is the modern type-theoretic framing; Rete is the efficient matching algorithm; the graph transformation work is the same question asked about rewriting rather than deduction.

C. L. Forgy, “Rete: A fast algorithm for the many pattern/many object pattern match problem,” Artificial Intelligence, vol. 19, no. 1, pp. 17–37, 1982.
our reading · doi:10.1016/0004-3702(82)90020-0
H. Ehrig, K. Ehrig, U. Prange, and G. Taentzer, “Fundamentals of Algebraic Graph Transformation,” Monographs in Theoretical Computer Science. An EATCS Series, 2006.
our reading · doi:10.1007/3-540-31188-2
M. Arntzenius and N. R. Krishnaswami, “Datafun: a functional Datalog,” ICFP’16: ACM SIGPLAN International Conference on Functional Programming, pp. 214–227, 2016.
our reading · read the paper
K. R. Apt, H. A. Blair, and A. Walker, “Towards a Theory of Declarative Knowledge,” Foundations of Deductive Databases and Logic Programming, pp. 89–148, 1988.
our reading · read the paper
A. Van Gelder, K. A. Ross, and J. S. Schlipf, “The well-founded semantics for general logic programs,” Journal of the ACM, vol. 38, no. 3, pp. 619–649, 1991.
read the paper
A. Van Gelder, “The alternating fixpoint of logic programs with negation,” Journal of Computer and System Sciences, vol. 47, no. 1, pp. 185–221, 1993.
our reading · read the paper
M. Gelfond and V. Lifschitz, “The stable model semantics for logic programming,” 1988.
read the paper
T. C. Przymusiński, “On the Declarative Semantics of Deductive Databases and Logic Programs,” Foundations of Deductive Databases and Logic Programming, pp. 193–216, 1988.
doi:10.1016/b978-0-934613-40-8.50009-9
S. Manchanda and D. S. Warren, “A Logic-based Language for Database Updates,” Foundations of Deductive Databases and Logic Programming, pp. 363–394, 1988.
doi:10.1016/b978-0-934613-40-8.50014-2
Y. Sagiv, “Optimizing Datalog Programs,” Foundations of Deductive Databases and Logic Programming, pp. 659–698, 1988.
doi:10.1016/b978-0-934613-40-8.50021-x

Algebraic graphs

Mokhov’s construction gives graphs an algebra — overlay and connect, with laws — so that every expression denotes a graph and there is no partial constructor to misuse. A malformed graph is not rejected at runtime; it cannot be written.

Alongside it sit the two classical results any graph substrate needs: Kahn’s topological sort, and Tarjan’s depth-first search with the strongly-connected components it finds in linear time. Cycle detection and condensation are not optional extras when policies can produce edges that close a loop.

A. Mokhov, “Algebraic graphs with class (functional pearl),” ICFP ‘17: ACM SIGPLAN International Conference on Functional Programming, pp. 2–13, 2017.
our reading · doi:10.1145/3122955.3122956
R. E. Tarjan, “Depth-First Search and Linear Graph Algorithms,” SIAM Journal on Computing, vol. 1, no. 2, pp. 146–160, 1972.
doi:10.1137/0201010
A. B. Kahn, “Topological sorting of large networks,” Communications of the ACM, vol. 5, no. 11, pp. 558–562, 1962.
read the paper
G. Kahn, “The Semantics of a Simple Language for Parallel Programming.,” IFIP Congress, 1974.
our reading

Incremental computation and build systems

The question is how to avoid recomputing a configuration from scratch when one input changed. Acar’s self-adjusting computation is the foundation. Adapton is the one to read closely: it separates dirtying from propagation, so a change marks a path as suspect cheaply and the actual repair happens only where someone demands a value — and an edge that still carries the same value cuts the repair off there. Build Systems à la Carte is the comparative frame, factoring real build systems into a scheduler and a rebuilder so the design space is visible rather than folkloric.

A. Mokhov, N. Mitchell, and S. P. Jones, “Build systems à la carte,” Proceedings of the ACM on Programming Languages, vol. 2, no. ICFP, pp. 1–29, 2018.
our reading · read the paper
M. A. Hammer, K. Y. Phang, M. Hicks, and J. S. Foster, “Adapton,” PLDI ‘14: ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 156–166, 2014.
our reading · doi:10.1145/2594291.2594324
U. A. Acar, G. E. Blelloch, and R. Harper, “Adaptive functional programming,” POPL02: The 29th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages 2002, pp. 247–259, 2002.
our reading · doi:10.1145/503272.503296

Defunctionalization and intensional functions

A closure you cannot look inside is a problem for a system that wants to inspect configuration before evaluating it. Reynolds’ defunctionalization is the classical answer — represent each function as tagged data plus an explicit apply — and the 1998 revisitation is his own account of what the 1972 paper did and did not establish. Palmer’s intensional functions are the modern treatment of functions that can be compared and inspected, and Lorenzen’s first-order laziness is the same instinct applied to lazy constructors: keep the thing inspectable until somebody forces it.

J. Reynolds, “Definitional interpreters for higher-order programming languages,” the ACM annual conference, vol. 2, pp. 717–740, 1972.
our reading · doi:10.1145/800194.805852
J. C. Reynolds, “Definitional interpreters revisited,” Higher-Order and Symbolic Computation, vol. 11, no. 4, pp. 355–361, 1998.
Z. Palmer, N. W. Filardo, and K. Wu, “Intensional functions,” Proceedings of the ACM on Programming Languages, vol. 8, no. OOPSLA2, art. 274, 2024.
our reading · doi:10.1145/3689714
Z. Palmer, N. W. Filardo, and K. Wu, “Intensional functions,” Proceedings of the ACM on Programming Languages, vol. 8, no. OOPSLA2, art. 274; extended version, 46 pp., 2024.
read the paper
A. Lorenzen, D. Leijen, W. Swierstra, and S. Lindley, “First-order laziness,” Proceedings of the ACM on Programming Languages, vol. 9, no. ICFP, art. 261, 29 pp., 2025.
our reading · read the paper

Feature-oriented and aspect-oriented

The problem aspects exist for: some concerns do not fit the module boundary, and composing a system out of features means every feature touches many modules. Kiczales’ original AOP paper states the problem; Batory’s AHEAD gives it an algebra where a feature is a function that refines a program; Apel and Kästner survey what the field learned. The analysis-strategies survey is the useful counterweight — it is a catalogue of what gets hard once a system has many optional features, which is the failure mode a configuration framework is walking into.

D. Batory, “Feature-oriented programming and the AHEAD tool suite,” vol. 26, pp. 702–703, 2004.
our reading · doi:10.5555/998675.999478
S. Apel and C. Kaestner, “An overview of feature-oriented software development,” Journal of Object Technology, vol. 8, no. 4, pp. 1–36, 2009.
our reading · doi:10.5381/jot.2009.8.5.c5
P. Tarr, H. Ossher, W. Harrison, and S. M. Sutton, “N degrees of separation,” ICSE99: 1999 International Conference on Software Engineering, pp. 107–119, 1999.
read the paper

Contracts, types and records

What a boundary should check, and when. Findler and Felleisen’s higher-order contracts are the source of blame — when a contract fails, saying which side broke it. Liquid types and lazy contracts are two different bets on how much can be moved to static checking. Leijen’s scoped labels and Bracha’s mixins are the composition side: how to extend a record or a class without the extension silently shadowing what was there.

R. B. Findler and M. Felleisen, “Contracts for higher-order functions,” ICFP02: International Conference on Functional Programming, pp. 48–59, 2002.
our reading · doi:10.1145/581478.581484
O. Chitil, “Practical typed lazy contracts,” ICFP’12: ACM SIGPLAN International Conference on Functional Programming, pp. 67–76, 2012.
our reading · doi:10.1145/2364527.2364539
P. M. Rondon, M. Kawaguchi, and R. Jhala, “Liquid types,” PLDI ‘08: ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 159–169, 2008.
our reading · doi:10.1145/1375581.1375602

Module linking and dataflow

Cardelli’s separation of compilation from linking is the frame for any boundary where a fragment is prepared with explicit knowledge of what it needs and what it supplies, and something else resolves the rest later. The propagator model and Kahn’s process networks are the dataflow counterpart: computation as a network of cells and the semantics that make it deterministic.

L. Cardelli, “Program fragments, linking, and modularization,” the 24th ACM SIGPLAN-SIGACT symposium, pp. 266–277, 1997.
our reading · doi:10.1145/263699.263735

Regular-expression derivatives

Brzozowski’s derivative construction, and Owens, Reppy and Turon’s demonstration that it is both practical and considerably simpler than the textbook automaton construction. Relevant wherever matching is done over a structure rather than a string.

J. Brzozowski, “Derivatives of Regular Expressions,” Journal of the ACM, vol. 11, no. 4, pp. 481–494, 1964.
read the paper
S. Owens, J. Reppy, and A. Turon, “Regular-expression derivatives re-examined,” Journal of Functional Programming, vol. 19, no. 2, pp. 173–190, 2009.
read the paper

Testing

McKeeman’s differential testing: when you have two implementations that should agree, disagreement is a test oracle you did not have to write.

W. M. McKeeman, “Differential Testing for Software.,” 1998.