Reading List

This list isn’t meant to be exhaustive or comprehensive or, frankly, coherent. The idea is to include resources that I found either insightful on their own or representative of an insightful larger body of work. Alternatively, I list things that are under-appreciated but significant. The goal here is to have resources that are fairly concentrated.

CS

I highly recommend reading specifications, e.g. the W3C specs, the RFCs, the Haskell Report, or the C# spec.

The Analytics library’s reading list is another good resource.

Object Capabilities

• erights.org
  • Ode to a Granovetter Diagram
  • Robust Composition: Towards a Unified Approach to Access Control and Concurrency Control - Mark Miller’s thesis
• waterken.com
  • ACLs Don’t
  • Mashing with Permission
  • The Confused Deputy Rides Again!
• A Security Kernel Based on the Lambda Calculus - Jonathan Rees’ thesis
• Capability Myths Demolished
• Videos
  • The Lazy Programmer’s Guide to Secure Computing (Marc Stiegler)
  • Secure distributed programming with object-capabilities in Javascript (Mark Miller)
  • Object Capabilities for Security (David Wagner)
  • Paradigm Regained (Mark Miller)

Type Theory

• Lectures on the Curry-Howard Isomorphism
• Homotopy Type Theory (Chapter 1/2/5)
• Subtyping, Subclassing, and Trouble with OOP
• Subclassing errors, OOP style and practically checkable rules to prevent them
• Types and Programming Languages by Benjamin Pierce
• Theorems for Free! by Phil Wadler
• Categorical Logic and Type Theory by Bart Jacobs or his thesis
• Monadic and Substructural Type Systems for Region-based Memory Management

Computer Graphics

• Metropolis Light Transport
• Compressive Rendering of Multidimensional Scenes - Pradeep Sen (compressive sensing applied to computer graphics)
• http://graphics.berkeley.edu/ was BCAM

Concurrency/Parallelism

• Practical Lock-freedom - Keir Fraser’s thesis
• Understanding and Expressing Scalable Concurrency - Aaron Turon’s thesis
• A Language-based Approach to Unifying Threads and Events
• On the duality of operating system structures - Lauer-Needham duality
• A Concurrent Window System
• Higher Order Concurrency - John Reppy’s thesis
• The Join Calculus
• The Polymorphic Pi-Calculus - David Turner’s thesis
• Languages: Pict, Funnel/JoCaml

Programming Language Theory

• Concept, Techniques, and Models of Computer Programming - Peter van Roy and Seif Haridi
• Structure and Interpretation of Computer Programs and videos - Harold Abelson and Gerald Sussman
• Programming Languages: Application and Interpretation by Shriram Krishnamurthi
• Declarative Continuations and Categorical Duality and Representing Monads - Andrzej Filinski’s Master’s and PhD theses
• Newspeak
• Open Extensible Object Models
• Avalanche-Safe Linq Compilation
• Lambda papers:
  • Lambda the Ultimate Imperative
  • Lambda the Ultimate Declarative
• First class patterns - The pattern calculus
• Out of the Tar Pit
• Assignment Calculus: A Pure Imperative Reasoning Language - Mark Bender’s thesis

Distributed Computing

• Fallacies of Distributed Computing Explained
• SELFMAN Project
• Enhanced Paxos Commit for Transactions on DHTs
• The Relaxed-Ring: A fault-tolerant topology for structured overlay networks
• In Search of an Understandable Consensus Algorithm (Extended Version)
• Consensus: Bridging Theory and Practice - Diego Ongaro’s thesis
• The Network is Reliable by Peter Bailis and Kyle Kingsbury
• Viewstamped Replication Revisited
• A Comprehensive study of Convergent and Commutative Replicated Data Types See also this reading list.
• Virtually Synchronous Methodology for Dynamic Service Replication
• The Log: What every software engineer should know about real-time data’s unifying abstraction
• Making reliable systems in the presence of software errors - Joe Armstrong’s thesis
• Rumor Spreading with No Dependence on Conductance - (2017) Simulates the LOCAL model with the GOSSIP model surprisingly efficiently. Improves on earlier work.
• Optimal Gossip with Direct Addressing - (2014) Round-, message-, and bit-complexity optimal GOSSIP when you can directly address nodes you’ve learned of before.
• Simple, fast, and deterministic gossip and rumor spreading - (2014) The first efficient, fully deterministic GOSSIP protocol.
• CORFU: A Shared Log Design for Flash Clusters - I’m less interested in the flash specific parts, but the use of the sequencer is a good trick.
• Tango: Distributed Data Structures over a Shared Log - Related to CORFU, but any shared log (e.g. Kafka) would do.

Datalog

• Foundations of Databases covers Datalog (a bit dated, 1995) and much more about database queries in general.
• Dedalus: Datalog in Time and Space and Hellerstein’s “The Declarative Imperative” pdf
• Extending the Power of Datalog Recursion by Carlo Zaniolo
• On Active Deductive Databases: The Statelog Approach

Miscellaneous

• On Buffon Machines and Numbers
• Highly Available Transactions: Virtues and Limitations (Extended Version)
• The Power of Two Random Choices: A Survey of Techniques and Results
• Join-Idle-Queue: A Novel Load Balancing Algorithm for Dynamically Scalable Web Services
• Observed Universality of Phase Transitions in High-Dimensional Geometry, With Implications for Modern Data Analysis and Signal Processing
• “Synthesis: An Efficient Implementation of Fundamental Operating System Services”. The ideas in this have since been elaborated, but it is a pretty fun and accessible read.
• Do the Middle Letters of ‘OLAP’ stand for Linear Algebra (‘LA’)? (and other work by Jose Nuno Oliveira)
• Typing Linear Algebra: A Biproduct-oriented Approach
• Pointfree Foundations for (Generic) Lossless Decomposition
• A Paintable Computer
• SPIN model checker
• Sting: An End-to-End Self-healing System for Defending against Zero-day Worm Attacks on Commodity Software
• HAKMEM
• Mocks Aren’t Stubs by Martin Fowler
• Purely Functional Data Structures by Chris Okasaki (thesis or book)
• Deprecating the Observer Pattern
• Theorem Proving and Algebra by Joseph Goguen (unfinish book)
• Dawson Engler:
  • https://pdos.csail.mit.edu/~engler/ and https://www.stanford.edu/~engler/
  • KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs
  • Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code
  • Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions
  • The Exokernel Operating System Architecture - PhD thesis
• The AI Architecture of Versu by Richard Prideaux Evans and Emily Short

Garbage Collection

• A Unified Theory of Garbage Collection
• C4: the continuously, concurrent, compacting collector

Cryptography

• Daniel Bernstein - https://cr.yp.to/djb.html https://cr.yp.to/
• Rethinking Public Key Infrastructure and Digital Certificates - UProve
• Malicious Cryptography
• Noise Protocol - Some implemented and analyzed building block cryptographic protocols.

DBMS Implementation

• ARIES protocol (maybe “Stasis: Flexible Transactional Storage” as well)
• Architecture of a Database System
• Generalized Search Tree
• Joins via Geometric Resolutions: Worst-case and Beyond
• Recovery Algorithms for In-Memory OLTP Databases by Nirmesh Malviya
• Rich Hickey: Deconstructing the Database
• FASTER: A Concurrent Key-Value Store with In-Place Updates - Very slick epoch management that is key to the whole design

Floating Point

Interval Arithmetic, Affine Arithmetic, Automatic Differentiation (Levi-Civita Field, Taylor models), Pade approximants

• Chebfun
• On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations by Douglas Priest (1992)
• What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg
• The work of Siegfried Rump e.g. Accurate Floating-Point Summation I: Faithful Rounding
• The work of William Kahan e.g. Branch Cuts for Complex Elementary Functions or Much Ado About Nothing’s Sign Bit

Digital Signal Processing

• Ptolemy II
• System Design, Modeling, and Simulation using Ptolemy II
• Structure and Interpretation of Signals and Systems
• Simple and Practical Algorithm for Sparse Fourier Transform
• Spinal Codes
• StreamIT
• Foundations of Total Functional Data-Flow Programming and other papers on Sig.
• Arrp Jakob Leben’s thesis, also see the Arrp site

Compiler Implementation

• Equality Saturation: A New Approach to Optimization and related work
• The Static Single Information Form (also Static Single Information from a Functional Perspective also CPS and SSA)
• A Functional Correspondence between Evaluators and Abstract Machines (see this LtU comment for related papers)
• Definitional Interpreters for Higher-Order Programming Languages - John Reynolds
• Principles and Implementation of Deductive Parsing

UI/UX Design

• Bret Victor’s site
  • Magic Ink
  • Inventing on Principle
• Edward Tufte
  • “The Visual Display of Quantitative Information”
  • “Envisioning Information”
  • “Visual Explanations”
• Scott McCloud “Understanding Comics”

Physics

• E. T. Jaynes
  • “Probability Theory: the Logic of Science”
  • Clearing up Mysteries
  • The evolution of Carnot’s principle
  • Predictive statistical mechanics
  • The Gibbs Paradox
  • Macroscopic Prediction
  • The Well-Posed Problem, but see Failure and Uses of Jaynes’ Principle of Transformation Groups
  • Confidence Intervals vs Bayesian Intervals
• David Hestenes’ Geometric Calculus
• Judea Pearl “Causality: Models, Reasoning, and Inference”
• “Entropy and the Time Evolution of Macroscopic Systems” by Walter T. Grandy Jr.
• Physical Audio Signal Processing by Julius O. Smith
• Entropic Inference and the Foundations of Physics by Ariel Caticha or the older Lectures on Probability, Entropy, and Statistical Physics.

Mathematics

• generatingfunctionology
• Category Theory:
  • Category Theory Lecture Notes for ESSLLI by Barr and Wells
  • Reason Isomorphically! by Ralf Hinze
  • Coend Calculus by Fosco Loregian
  • Basic Concepts of Enriched Category Theory by G. M. Kelly
  • Toposes, Triples, and Theories by Michael Barr and Charles Wells
  • Homotopy Type Theory
  • Category Theory as Coherently, Constructive Lattice Theory
  • Modular correspondence between dependent type theories and categories including pretopoi and topoi by Maria Maietti
  • Sheaves and Homotopy Theory by Daniel Dugger has an excellent, well understood but not often mentioned description of sheaves.
• Multidigit Multiplication for Mathematicians
• The Unscented Kalman Filter for Nonlinear Estimation by Wan and van der Merwe
• Unscented Filtering and Nonlinear Estimation by Simon Julier and Jeffrey Uhlmann
• The Scaled Unscented Transform by Simon Julier
• Imre Lakatos’ “Proofs and Refutations”
• “Where Mathematics Comes From” by Nunez and Lakoff
• Bayesian Spectrum Analysis and Parameter Estimation by George Bretthorst
• Synthetic Differential Geometry by Anders Kock
• Universal Algorithmic Intelligence: Sequential Decisions Based on Algorithmic Probability by Marcus Hutter (AIXI)
• The Fastest and Shortest Algorithm for All Well-Defined Problems by Marcus Hutter
• The behavioral approach to open and interconnected systems by Jan C. Willems
• Behavioural differential equations: a coinductive calculus of streams, automata, and power series by J. J. M. M. Rutten
• The Method of Coalgebra: exercises in coinduction - (2019) Book by J. J. M. M. Rutten
• A=B by Petkovsek, Wilf, Zeilberger
• Synthetic topology of data types and classical spaces
• Internal Set Theory and Radically Elementary Probability Theory by Edward Nelson
• On Feasible Numbers by Vladimir Sazonov (available as a chapter in Logical and Computational Complexity)
• Nick Trefethen
  • Approximation Theory and Approximation Practice (book)
  • Barycentric Lagrange Interpolation
  • The exponentially convergent trapezoid rule (expository)
  • Computing |A^\alpha|, |\log(A)|, and related matrix functions by contour integrals
  • Numerical algorithms based on analytic function values at roots of unity

Process/Leadership

• Characterizing people as non-linear, first-order components in software development by Alistair Cockburn
• How Complex Systems Fail by Richard Cook
• “Switch: How to change things when change is hard” by Chip and Dan Heath
• “Don’t think of an elephant: know your values and frame the debate” by George Lakoff
• “Helping” by Edgar Schein
• “Process Consultation Revisited” by Edgar Schein
• “How to win friends and influence people” by Dale Carnegie
• Valve’s New Employee Handbook
• “Thinking, Fast and Slow” by Daniel Kahneman
• “Predictably Irrational” by Dan Ariely
• John Sterman’s work e.g. 
  • Nobody ever gets credit for fixing problems that never happened
  • Learning in and about complex systems
• “Resonate” by Nancy Duarte
• “Cradle to Cradle” and “The Upcycle”
• “Emotional First Aid: Healing Rejection, Guilt, Failure, and Other Everyday Hurts” by Guy Winch
• “The Squeaky Wheel” by Guy Winch
• “Influence” and “Presuasion” by Robert Cialdini

Education

• Kieran Egan’s work
  • An Imaginative Approach to Teaching
  • The Educated Mind: How Cognitive Tools Shape Our Understanding
• “Mindstorms” by Seymour Papert

Miscellaneous

• “The Gift of Pain” by Dr. Paul Brand
• Why Most Published Research Findings Are False by John P. A. Ioannidis
• Deming, data and observational studies: a process out of control and needing fixing
• How to Write a Great Research Paper by Simon Peyton Jones