List of academic papers on programming – Part 1
Finger Trees: A Simple General-purpose Data Structure by Ralf Hinze and Ross Paterson
We present 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece. Representations achieving these bounds have appeared previously, but 2-3 finger trees are much simpler, as are the operations on them. Further, by defining the split operation in a general form, we obtain a general purpose data structure that can serve as a sequence, priority queue, search tree, priority search queue and more.
Growing a Language by Guy L. Steele JR.
I think you know what a man is. A woman is more or less like a man, but not of the same sex.
Next, I shall say that a person is a woman or a man (young or old).
To keep things short, when I say “he” I mean “he or she,” and when I say “his” I mean “his or her.”
Singularity: Rethinking the Software Stack by Galen C. Hunt and James R. Larus
Operating systems form the foundation of almost every software stack, so inadequacies in present systems have a pervasive impact. This paper describes the efforts of the Singularity project to re-examine these design choices in light of advances in programming languages and verification tools.
Traits: Composable Units of Behaviour by Nathanael Scharli, Stephane Ducasse, Oscar Nierstrasz, and Andrew P. Black
Despite the undisputed prominence of inheritance as the fundamental reuse mechanism in object-oriented programming languages, the main variants – single inheritance, multiple inheritance, and mixin inheritance – all suffer from conceptual and practical problems. In the first part of this paper, we identify and illustrate these problems. We then present traits, a simple compositional model
for structuring object-oriented programs.
Engineering a Sort Function by Jon L. Bentley and M. Douglas McIlroy
We recount the history of a new qsort function for a C library. Our function is clearer, faster and more robust than existing sorts. It chooses partitioning elements by a new sampling scheme; it partitions by a novel solution to Dijkstra’s Dutch National Flag problem; and it swaps efficiently. Its behavior was assessed with timing and debugging testbeds, and with a program to certify performance. The design techniques apply in domains beyond sorting.
Definitional Interpreters for Higher-Order Programming Languages by John C. Reynolds
Higher-order programming languages (i.e., languages in which procedures or labels can occur as values) are usually defined by interpreters that are themselves written in a programming language based on the lambda calculus (i.e., an applicative language such as pure LISP).
