blucz.com

Papers

Reading papers seems time consuming, especially at first, but there's no substitute for getting the information straight from the researchers that created it.

This is a list of papers that I've found particularly valuable, sorted by category.

If you like this, you should also check out Great Works in Programming Languages.

General Wisdom

  • Typeful Programming (Luca Cardelli)

    In this paper, Cardelli flaunts the typical classification of programming languages in order to draw a distinction between typeful programming and everything else. He argues that the value of typeful programming transcends the paradigm of the language in question.

  • Growing A Language (Guy Steele)

    The only paper on this list that is suitable for non-technical readers. It's a quick read, and not very heavy. Highly recommended.

  • Good Ideas, Through the Looking Glass (Wirth)

    A retrospective look at many successes and failures of the research community across several decades. Not very heavy. Worth reading for perspective.

  • The Next 700 Programming Languages (P.J. Landin)

    In this paper, P.J. Landin introduces a programming language called ISWIM that was, to my knowledge, never implemented. ISWIM introduced the idea of building imperative languages with a functional core, an idea that has become the foundation of decades of functional programming langauge design. ISWIM is often cited as a major influence for ML, Miranda, and Haskell.

  • Hints on Programming Language Design (C.A.R. Hoare)

    The paper is somewhat quaint and quite old, but still worth a read. It focuses on the human factors side of programming language design. Very accessible, light on theory.

  • What Every Programmer Should Know About Memory (Ulrich Drepper)

    A long and comprehensive survey of CPU and memory architecture. Should be required reading for anyone writing software.

Programming Languages

  • Scalable Component Abstractions (Odersky, Zenger)

    This paper caused me to totally rethink my approach towards software engineering and object-oriented design. Not only are the objectives in this paper attainable with minor extensions to existing object-oriented languages, the system is also capable of efficiently encoding System F<:. Herein lies our best hope for first class access to functional and object oriented programming methodology within the same language.

  • Self: The Power of Simplicity (Ungar, Smith)

    A description of the design rationale behind the Self programming language. Self is a highly regular prototype-based object-oriented langauge. Many of the fruits of this research effort ended up deployed in Sun's HotSpot virtual machine. Unfortunately, the language has not enjoyed similar success. Elements of Self's approach live on in Javascript and Io.

  • Design Principles Behind Smalltalk (Danial H. H. Ingalls)

    A description of the design rationale behind the Smalltalk programming langauge. Smalltalk was as much a social project as it was a technical one. The description of how technical decisions resulted from social objectives is especially interesting.

  • The Definition of Standard ML (Milner, Harper, Tofte, MacQueen)

    One of the most concise, clear, and formally justifiable language specs out there. It's not meant to be a good reference for ML programmers, but it's excellent reference material for someone writing a language specification.

  • Implementing General Purpose Dependently Typed Programming Languages (Brady)

    Dependent types are one of the next big things on the horizon in programming language design. Though theoretically simple, incorporating them into general purpose languages is an immense task. Edwin Brady is leading the charge with the Idris language.

Type Systems

  • Principal type-schemes for functional programs (Damas, Milner)

    This is the paper that made type inference practical for everyday use. It describes Algorithm W, an efficient algorithm for computing principle type assignments for terms in System F. Extensions of this algorithm are currently used in most functional languages.

  • Type Inference with Deferral (Michal Moskal)

    From the Nemerle project, a type inference algorithm based on constraint solving that can cope with object-oriented style method overloads. This paper doesn't get great play in the theoretical community because it fails to produce principle types, however in practice it seems to work well for Nemerle.

  • Objects to Unify Type Classes and GADTs (Oliveira, Sulzmann)

    A valiant attempt at unifying functional and object-oriented systems within a single theretical framework. Somewhat modest in its goals as it doesn't attempt to address subtyping. There's some very neat stuff here, and it's more accessible than most type theory papers out there. Recommended.

  • A Nominal Theory of Objects with Dependent Types (Odersky et al)

    Think of this as a more formal version of "Scalable Component Abstractions". Introduces the vObj calculus, the theoretical framework behind GJ and Scala, in formal terms.

  • Implicit Parameters: Dynamic Scoping with Static Types (Lewis, Shields, Meijer, Launchbury)

    Dynamic scoping has always been a touchy concept. Recently it's been seeing wide adoption under different names, like "type classes" and "implicits". This paper lays out a type-safe framework for dynamic scoping in staticly typed languages.

Compiler Implementation

  • An Incremental Approach to Compiler Construction (Ghuloum)

    Compilers are complex software, and there is much precedent in how they are implemented. This is a walkthrough of the implementation of a simple scheme compiler, suitable for beginning compiler writers.

  • A Nanopass Framework for Compiler Education (Sarkar, Waddell, Dybvig)

    This paper takes a stab at the meta-problem of teaching students how to write compilers. In doing so, the authors reformulate some of the difficult to explain portions of compiler engineering in simpler ways.

  • Compiling With Continuations (Andrew W. Appel)

    Actually a book. Should be required reading for any serious engineer working in a strict functional language. Describes the internals of the SML/NJ optimizing compiler in detail.

Language Runtimes, GC's etc

  • Cheney On the M.T.A. (Henry Baker)

    A neat implementation technique that builds a capable garbage collector out of very simple building blocks. Not very heavy or dense. Suitable for readers without a strong theoretical background.

  • Optimizing Dynamically-Typed Object-Oriented Languages with Polymorphic Inline Caches (Ungar et. all)

    It's hard to believe that this paper is from the early 90s. One of the most important contributions of the Self profject. Now this technology underlies most fast Javascript virtual machines as well as Microsoft's DLR and Java's invokedynamic.

  • List Processing in Real Time on a Serial Computer (Baker)

    This paper may not represent the state of the art for real-time collectors, but it is a good introduction to a valid technique, explained with Henry Baker's typical clarity.

  • Software Transactional Memory (Shavit, Touitou)

    Describes a scheme for safe obstruction-free memory sharing that is simple to use. This paper is early, and doesn't address many of the more challenging problems (for example, STM with dynamically sized data structures), but it is still worth a detailed read.

Textbooks

  • Types and Programming Languages (Benjamin C. Pierce)

    This might be the greatest type theory textbook out there. It's approachable enough to be useful for people without type theory experience without sacrificing completeness. Highly recommended.

  • Advanced topics in Types and Programming Languages (Benjamin C. Pierce)

    A graduate-level supplement to Types and programming languages edited by Benjamin C. Pierce. The chapters are written by various prominent type theory researchers and cover theoretical and practical topics including dependent types, substructural types, and the design concerns that motivated the ML module system.

  • Design Concepts in Programming Languages (Turbak, Gifford, Sheldon)

    When "Types and Programming Languages" doesn't quite go deep enough, this is a great alternative for broad coverage on PLT topics. It is much less approachable, and based around scheme, which isn't ideal, but it is very comprehensive.

  • Concepts, Techniques, and Models of Computer Programming (Van Roy, Haridi)

    This is meant as an intro programming book, in the same spirit as the venerable SICP. However this book is built arount Oz, an impressive multi-paradigm language. Oz's pervasive support for different programming methodoligies makes it a great platform for explaining a variety of less-commonly-explored paradigms like data-flow programming and logic programming. Even if intro programming is a decade behind you, there's still much to be learned here.

  • Practical Foundations for Programming Languages (Robert Harper)

    Robert Harper has been a pillar of the PLT community for three decades. This book is a work in progress. When finished, it should be an excellent replacement for "Types and Programming Languages". The upside is that you can download the PDF for free. If you're just starting out with PLT, this is the easiest starting point.

Reference Material

Three well written documents about intel x86 cpus. Mirrored here in case this page stops hosting them.