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
[S] Describes the Smalltalk system of communicating objects, and includes an example of the Smalltalk-76 interpreter written in itself in the appendix.
[S] The authors walk the reader thru building a simple Scheme compiler in C and Assembly.
[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.
[S] An even smaller adaptaion of miniKanren (above) in fewer than 40 lines of Scheme. (via @jackrusher)
[S] Complete Scheme source code to a layered, Incremental / Self-Adjusting Computation system.
[P] Introduces generational garbage collection based on Baker’s algorithm, including a 3 page pseudo-code appendix of the collector.
[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.
[S] Describes the influential subsumption architecture for mobile robots, and includes complete Lisp code of the described robot’s control system.
[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.
[P] Describes a very influential distributed hash table protocol, including pseudo-code for key-location & node joining.
These papers don’t meet some of this list’s requirements but for various reasons I want to mention them anyway.
[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.
[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.