On September 28, 2021, I asked on Twitter:
PL Twitter:
you get to recommend one published PL paper for an undergrad to read with oversight by someone experienced. the paper should be interesting, approachable, and (mostly) self-contained.
what paper do you recommend?
I received quite a few suggestions from various people in PL. Below, I've listed all the responses received with links to the papers (where available) and links to the suggestion tweets. If you've got a suggestion you don't see below, feel free to reply to the original question on Twitter and I'll add it here!
NOTE: I have not necessarily read all of the papers below, and I do not personally vouch that they are approachable to undergraduate students. I am relying on participants' desire to be reasonable. If you feel strongly that a paper does not belong on this list, feel free to send me a direct message and I will take it into consideration.
- Propositions as Types
- Philip Wadler
- Suggested by Jonathan @ionathanch Chan
- From System F to Typed Assembly Language
- Greg Morrisett, David Walker, Karl Crary, Neal Glew
- Suggested by John @johnbender Bender
- Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints
- Patrick Cousot, Radhia Cousot
- Suggested by Hila @HilaCodes Peleg
- NOTE: Hila later confessed she suggested the paper in jest, but some discussion suggests the early parts of the paper are approachable and good and the rest can be skipped.
- Types, Abstraction and Parametric Polymorphism
- John C. Reynolds
- Suggested by Jon @jonmsterling Sterling
- The varieties of programming language
- C.A.R. Hoare
- Springer
- Suggested by George @GeorgePirlea Pîrlea
- Definitional interpreters for higher-order programming languages
- John C. Reynolds
- Suggested by David @lambda_calculus Van Horn
- A Perspective of Generative Reuse
- Ted J. Biggerstaff
- Suggested by Jurgen @jurgenvinju Vinju
- Resources, Concurrency and Local Reasoning
- Peter W. O'Hearn
- Suggested by Derek @HerrDryer Dryer
- Nesl: A Nested Data-Parallel Language
- Guy E. Blelloch
- Suggested by Leo @lmeyerov Meyerovich
- More types for nested data parallel programming
- Manuel M. T. Chakravarty, Gabriele Keller
- ACM DL
- Suggested by Leo @lmeyerov Meyerovich
- Verifying Properties of Parallel Programs: An Axiomatic Approach
- Susan Owicki, David Gries
- Suggested by Ilya @ilyasergey Sergey
- 1ML – Core and Modules United (F-ing First-class Modules)
- Andreas Rossberg
- Suggested by Tom @tomprimozic Primožič
- NOTE: There are follow-up papers available here.
- The Essence of Compiling with Continuations
- Cormac Flanagan, Amr Sabry, Bruce F. Duba, Matthias Felleisen
- ACM DL
- Suggested by Ilya @ilyasergey Sergey
- Defunctionalization at Work
- Olivier Danvy, Lasse R. Nielsen
- Suggested by Marisa @MarisaVeryMoe Kirisame
- Functional Reactive Animation
- Conal Elliott, Paul Hudak
- Suggested by Harley @heades Eades
- On Understanding Types, Data Abstraction, and Polymorphism
- Luca Cardelli, Peter Wegner
- Suggested by Graydon @graydon_pub Hoare
- Separation Logic: A Logic for Shared Mutable Data Structures
- John C. Reynoldes
- Suggested by John @johnbender Bender
- Proof Pearl: Magic Wand as Frame
- Qinxiang Cao, Shengyi Wang, Aquinas Hobor, Andrew W. Appel
- Suggested by John @johnbender Bender
- A prettier printer
- Philip Wadler
- Suggested by Kwanghoon @LazySwamp Choi
- An Incremental Approach to Compiler Construction
- Abdulaziz Ghuloum
- Suggested by @bay17777
- Gradual Typing for Functional Languages
- Jeremy G. Siek, Walid Taha
- Suggested by David @dmolnar Molnar
- Structured Programming with go to Statements
- Donald E. Knuth
- ACM DL
- Suggested by Robert @FUZxxl Clausecker
- A History of Haskell: Being Lazy With Class
- Paul Hudak, John Hughes, Simon Peyton Jones, Philip Wadler
- Suggested by Nicholas @nnethercote Nethercote
- NOTE: This is a HOPL paper, so it's not a typical research paper (though it is very good and worth reading).
- The computational content of isomorphisms
- Roshan P. James
- Semantic Scholar
- Suggested by Nicole @strega_nil Mazzuca
- A theory of qualified types
- Mark P. Jones
- Suggested by Apoorv @fxdpntthm