A short-list of short, grokkable, & influential CS papers

2021-09-19

This post is a running list of research papers I’m collecting for self-study with the following qualities:

They include source code [S] or (at minimum) pseudo-code [P] of the core insight of the system / design / algorithm.
They do not overwhelm the reader with mathematical notation.
The majority are, by my highly subjective account, “foundational” papers, in that they have had some important influence on their respective subdisciplines.
Most are less than 30 pages

Languages & Runtimes

The Smalltalk-76 Programming System Design and Implementation, Ingals

[S] Describes the Smalltalk system of communicating objects, and includes an example of the Smalltalk-76 interpreter written in itself in the appendix.

An Incremental Approach to Compiler Construction, Ghuloum

[S] The authors walk the reader thru building a simple Scheme compiler in C and Assembly.

From Variadic Functions to Variadic Relations: A miniKanren Perspective, Byrd & Friedman

[S] The authors present an implementation of miniKanren, a Prolog-influenced relational language embedded within Scheme. A complete implementation of the interpreter is shown in a 3 page appendix.

microKanren: A Minimal Functional Core for Relational Programming, Hemann & Friedman

[S] An even smaller adaptaion of miniKanren (above) in fewer than 40 lines of Scheme. (via @jackrusher)

miniAdapton, A Minimal Implementation of Incremental Computation in Scheme, Fisher et al

[S] Complete Scheme source code to a layered, Incremental / Self-Adjusting Computation system.

A Real Time Garbage Collector Based on the Lifetimes of Objects, Lieberman & Hewitt

[P] Introduces generational garbage collection based on Baker’s algorithm, including a 3 page pseudo-code appendix of the collector.

Systems

The Ubiquitous File Server in Plan 9, Forsyth

[P] Shows a condensed version of the the 9p protocol used to implement the Plan 9 file system & example systems built on top of it.

A Robust Layered Control System for a Mobile Robot, Brooks

[S] Describes the influential subsumption architecture for mobile robots, and includes complete Lisp code of the described robot’s control system.

Algorithms

In Search of an Understandable Consensus Algorithm, Ongaro & Ousterhout

[P] Describes the Raft consensus algorithm, an alternative to Paxos. No source but has a 1 pager of the member’s state, RPC interfaces & server rules.

Chord - A Scalable P2P Lookup Service for Internet Applications, Stoica et al

[P] Describes a very influential distributed hash table protocol, including pseudo-code for key-location & node joining.

Honorable Mentions

These papers don’t meet some of this list’s requirements but for various reasons I want to mention them anyway.

The Cuneiform Tablets of 2015, Nguyen & Kay

[P] This paper is not really ‘foundational’, but it inspired this list. The authors discuss the problem of the Digital Dark Age and propose a unique solution. It includes the opcodes to a simple abstract machine and a proposed storage mechanism.

Convolutional Neural Networks in APL, Šinkarovs et al

[S] The authors present a complete neural network implementation in 20 lines of APL. Arguably APL is itself much too close to mathematical notation to be considered ‘grokkable’, but given its parsimony seems highly worthy of study.