References

Almost every hard problem in gen was solved by somebody else first, and usually decades ago. Configuration resolution is name resolution. Incremental rebuild is self-adjusting computation. Policies producing edges is Datalog with negation, with the termination question that comes with it.

Treating those as solved problems is a design decision, and it is the one this page documents. Each library below points at the result it implements, so a question about gen’s behaviour has somewhere to go beyond the source: a paper with a proof in it, and our reading of what that proof commits us to.

New here?

The reading list is the guided path — which papers matter for which part of gen, and the order to take them in. This page is the full bibliography.

The traditions

Attribute grammarsValues computed over a tree by local rules, demanded rather than scheduled. Knuth 1968 onward; the reference and higher-order extensions are what make it fit a configuration graph.

Scope graphsName resolution as a graph query, separated from the syntax tree. This is what gen's resolution actually is.

Logic programmingPolicies are rules producing edges. Negation is where the semantics get delicate, and the well-founded and stable-model results are why gen refuses rather than guesses.

Incremental computationDemand-driven recomputation with early cutoff. Adapton's demanded-computation graph is the shape gen's memo plane takes.

Algebraic graphsGraphs as an algebra with total constructors, so a malformed graph is unrepresentable rather than merely rejected.

Feature orientationComposing a system from features that cut across its modules — the problem aspects exist to solve, and the literature on what goes wrong.

How to read an entry

Each entry gives the citation, a link to read the paper where one is publicly available, and a link to our reading of it where we have written one. The readings say what the paper argues and which part of gen it shaped; they are working notes, not peer review, and they are no substitute for the paper.

On copies

We hold PDFs and full-text transcriptions of most of these papers. Those are the publishers’ to distribute and are not republished here — links go to the DOI, or to a copy the authors or publisher have already made public. Where the archive recorded no source for a scan, no link is given rather than a guessed one.

Cited by the libraries

Papers a gen library implements or is directly shaped by.

1. 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.
   doi:10.1145/503272.503296 · our reading
2. 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.
   doi:10.1145/2847538.2847543 · read the paper · our reading
3. 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.
   doi:10.1145/3276484 · our reading
4. 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.
   doi:10.1016/b978-0-934613-40-8.50006-3 · read the paper · our reading
5. M. Arntzenius and N. R. Krishnaswami, “Datafun: a functional Datalog,” ICFP’16: ACM SIGPLAN International Conference on Functional Programming, pp. 214–227, 2016.
   doi:10.1145/2951913.2951948 · read the paper · our reading
6. D. Batory, “Feature-oriented programming and the AHEAD tool suite,” vol. 26, pp. 702–703, 2004.
   doi:10.5555/998675.999478 · our reading
7. J. Boyland, “Remote attribute grammars,” Journal of the ACM, vol. 52, no. 4, pp. 627–687, 2005.
   doi:10.1145/1082036.1082042
8. G. Bracha and W. R. Cook, “Mixin-based inheritance,” OOPSLA/ECOOP ‘90: Object-oriented programming systems, languages, and applications, pp. 303–311, 1990.
   doi:10.1145/97945.97982 · our reading
9. J. Brzozowski, “Derivatives of Regular Expressions,” Journal of the ACM, vol. 11, no. 4, pp. 481–494, 1964.
   doi:10.1145/321239.321249 · read the paper
10. L. Cardelli, “Program fragments, linking, and modularization,” the 24th ACM SIGPLAN-SIGACT symposium, pp. 266–277, 1997.
    doi:10.1145/263699.263735 · our reading
11. O. Chitil, “Practical typed lazy contracts,” ICFP’12: ACM SIGPLAN International Conference on Functional Programming, pp. 67–76, 2012.
    doi:10.1145/2364527.2364539 · our reading
12. H. Ehrig, K. Ehrig, U. Prange, and G. Taentzer, “Fundamentals of Algebraic Graph Transformation,” Monographs in Theoretical Computer Science. An EATCS Series, 2006.
    doi:10.1007/3-540-31188-2 · our reading
13. R. B. Findler and M. Felleisen, “Contracts for higher-order functions,” ICFP02: International Conference on Functional Programming, pp. 48–59, 2002.
    doi:10.1145/581478.581484 · our reading
14. 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.
    doi:10.1016/0004-3702(82)90020-0 · our reading
15. 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.
    doi:10.1145/116825.116838 · read the paper
16. 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.
    doi:10.1016/0022-0000(93)90024-q · read the paper · our reading
17. M. Gelfond and V. Lifschitz, “The stable model semantics for logic programming,” 1988.
    read the paper
18. G. Hedin, “Reference Attributed Grammars,” 2000.
    our reading
19. G. Hedin and E. Magnusson, “JastAdd—an aspect-oriented compiler construction system,” Science of Computer Programming, vol. 47, no. 1, pp. 37–58, 2003.
    doi:10.1016/s0167-6423(02)00109-0 · read the paper · our reading
20. A. B. Kahn, “Topological sorting of large networks,” Communications of the ACM, vol. 5, no. 11, pp. 558–562, 1962.
    doi:10.1145/368996.369025 · read the paper
21. G. Kahn, “The Semantics of a Simple Language for Parallel Programming.,” IFIP Congress, 1974.
    our reading
22. D. E. Knuth, “Semantics of context-free languages,” Theory of Computing Systems, vol. 2, no. 2, pp. 127–145, 1968.
    doi:10.1007/bf01692511
23. D. E. Knuth, “Semantics of context-free languages: Correction,” Theory of Computing Systems, vol. 5, no. 2, pp. 95–96, 1971.
    doi:10.1007/bf01702865 · read the paper
24. L. Krishnan and E. Van Wyk, “Termination analysis for higher-order attribute grammars,” Software Language Engineering (SLE 2012), LNCS 7745, pp. 44–63, 2013.
    doi:10.1007/978-3-642-36089-3_4 · read the paper · our reading
25. D. Leijen, “Extensible records with scoped labels.,” 2005.
    our reading
26. 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.
    doi:10.1145/3747530 · read the paper · our reading
27. 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
28. W. M. McKeeman, “Differential Testing for Software.,” 1998.
29. A. Mokhov, “Algebraic graphs with class (functional pearl),” ICFP ‘17: ACM SIGPLAN International Conference on Functional Programming, pp. 2–13, 2017.
    doi:10.1145/3122955.3122956 · our reading
30. 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.
    doi:10.1145/3236774 · read the paper · our reading
31. P. Néron, A. Tolmach, E. Visser, and G. Wachsmuth, “A Theory of Name Resolution,” Lecture notes in computer science, pp. 205–231, 2015.
    doi:10.1007/978-3-662-46669-8_9 · read the paper · our reading
32. S. Owens, J. Reppy, and A. Turon, “Regular-expression derivatives re-examined,” Journal of Functional Programming, vol. 19, no. 2, pp. 173–190, 2009.
    doi:10.1017/S0956796808007090 · read the paper
33. 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.
    doi:10.1145/3689714 · read the paper
34. Z. Palmer, N. W. Filardo, and K. Wu, “Intensional functions,” Proceedings of the ACM on Programming Languages, vol. 8, no. OOPSLA2, art. 274, 2024.
    doi:10.1145/3689714 · our reading
35. 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
36. A. Radul and G. J. Sussman, “The art of the propagator,” MIT CSAIL Technical Report MIT-CSAIL-TR-2009-002, 2009.
    read the paper · our reading
37. 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.
    doi:10.1145/2166.357218 · read the paper · our reading
38. J. Reynolds, “Definitional interpreters for higher-order programming languages,” the ACM annual conference, vol. 2, pp. 717–740, 1972.
    doi:10.1145/800194.805852 · our reading
39. J. C. Reynolds, “Definitional interpreters revisited,” Higher-Order and Symbolic Computation, vol. 11, no. 4, pp. 355–361, 1998.
40. 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.
    doi:10.1145/1375581.1375602 · our reading
41. 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
42. 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.
    doi:10.1016/j.entcs.2010.08.043 · our reading
43. E. Söderberg and G. Hedin, “Circular Higher-Order Reference Attribute Grammars,” Lecture notes in computer science, pp. 302–321, 2013.
    doi:10.1007/978-3-319-02654-1_17 · our reading
44. 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
45. 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.
    doi:10.1145/302405.302457 · read the paper
46. H. Vogt, S. D. Swierstra, and M. Kuiper, “Higher order attribute grammars,” PLDI89: Programming Language Design & Implementation, pp. 131–145, 1989.
    doi:10.1145/73141.74830 · read the paper · our reading
47. 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.
    doi:10.1016/j.scico.2009.07.004 · read the paper · our reading

Background

Read while the design was being settled, and informing it, without a library implementing them directly.

48. S. Apel and C. Kaestner, “An overview of feature-oriented software development,” Journal of Object Technology, vol. 8, no. 4, pp. 1–36, 2009.
    doi:10.5381/jot.2009.8.5.c5 · our reading
49. D. Batory, J. Liu, and J. N. Sarvela, “Refinements and multi-dimensional separation of concerns,” ESEC/FSE03: Joint 9th European Software Engineering Conference 2003, pp. 48–57, 2003.
    doi:10.1145/940071.940079 · our reading
50. S. Erdweg et al., “Evaluating and comparing language workbenches,” Computer Languages, Systems & Structures, vol. 44, pp. 24–47, 2015.
    doi:10.1016/j.cl.2015.08.007 · read the paper · our reading
51. 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.
    doi:10.1145/2594291.2594324 · our reading
52. N. D. Jones, C. K. Gomard, and P. Sestoft, “Partial Evaluation and Automatic Program Generation,” Prentice Hall International, ISBN 0-13-020249-5, 1993.
    our reading
53. G. Kiczales et al., “Aspect-oriented programming,” ECOOP’97, LNCS 1241, pp. 220–242, 1997.
    doi:10.1007/BFb0053381 · our reading
54. D. E. Knuth, “The genesis of attribute grammars,” Lecture notes in computer science, pp. 1–12, 1990.
    doi:10.1007/3-540-53101-7_1 · our reading
55. P. J. Landin, “The next 700 programming languages,” Communications of the ACM, vol. 9, no. 3, pp. 157–166, 1966.
    doi:10.1145/365230.365257 · read the paper
56. J. R. Lewis, M. B. Shields, E. Meijer, and J. Launchbury, “Implicit parameters: dynamic scoping with static types,” POPL’00: Symposium on Principles of Programming Languages, pp. 108–118, 2000.
    doi:10.1145/325694.325708 · read the paper · our reading
57. J. McCarthy, “Recursive functions of symbolic expressions and their computation by machine, Part I,” Communications of the ACM, vol. 3, no. 4, pp. 184–195, 1960.
    doi:10.1145/367177.367199 · read the paper
58. J. McCarthy, “Towards a Mathematical Science of Computation.,” 1962.
59. R. Milner, “A theory of type polymorphism in programming,” Journal of Computer and System Sciences, vol. 17, no. 3, pp. 348–375, 1978.
    doi:10.1016/0022-0000(78)90014-4 · read the paper
60. J. Minker, Ed., Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann, Los Altos, CA, ISBN 0-934613-40-0, 1988.
61. G. Plotkin, “Call-by-name, call-by-value and the λ-calculus,” Theoretical Computer Science, vol. 1, no. 2, pp. 125–159, 1975.
    doi:10.1016/0304-3975(75)90017-1 · read the paper
62. J. Reynolds, “The discoveries of continuations,” LISP and Symbolic Computation, vol. 6, no. 3-4, pp. 233–247, 1993.
    doi:10.1007/bf01019459
63. D. A. R. Salvadori, ”∆-Nets: Interaction-based system for optimal parallel λ-reduction,” arXiv:2505.20314 [cs.LO], 2025.
    doi:10.48550/arXiv.2505.20314 · read the paper
64. A. M. Sloane, “Lightweight language processing in Kiama,” GTTSE 2009, LNCS 6491, pp. 408–425, 2011.
    doi:10.1007/978-3-642-18023-1_12 · our reading
65. T. Thüm, S. Apel, C. Kästner, I. Schaefer, and G. Saake, “A Classification and Survey of Analysis Strategies for Software Product Lines,” ACM Computing Surveys, vol. 47, no. 1, pp. 1–45, 2014.
    doi:10.1145/2580950 · our reading

On the accuracy of this list

Citations here were resolved against OpenAlex and Crossref and then checked against the archive’s own recorded author and year, and where the archive has a hand-recorded citation that one wins. The check is not ceremony. A title search returned a silver-electrode paper for Hedin’s reference attribute grammars and a dental-implant study for Krishnan’s termination analysis — both confident, both unrelated. Two entries had the archive’s own filename wrong about the year.