Lambda the Ultimate

A recurring theme in my postings has been Amorphous Computing. For 1 and 3, I'd have Butera's PhD thesis, Paintable Computing. The Amorphous Computing Manifesto has some familiar names, Abelson and Sussman.

Amorphous computing is closely related to biocomputing and in that vein I recently looked for a book for the purpose of understanding the "primitives, means of combination, and means of abstraction" that nature provides. I came across Bionanotechnology. This book is not PL or even CS related, but you can come at it from a perspective of "how do I program this?" Despite many biologically inspired ideas in computer science, biology is an area where it seems many computer scientists are relatively weak (I certainly am.) At any rate, this book is fascinating.

Another recurring theme of mine is exokernels and Xok in particular. Here it is Engler's PhD thesis that I refer to and also falls under 1 and 3 for me. This is the modern analog of Synthesis OS paper, Massalin's PhD thesis and another inspiring paper. This is an operating systems paper but there are direct application of PLT in both directions.

1. Can Programming Be Liberated From the von Neumann Style?
3. Conservative Logic

In the "favourite paper" category: Guy Steele's Growing a Language. Video of the original presentation upon which the paper is based is available here.

My favorites are Tracing the Dynabook: A Study of Technocultural Transformations, a Ph.D. thesis by John Maxwell, and a couple of essays:

The Art of Lisp and Writing, by Richard Gabriel, and History of Thinking, by Chris Crawford.

I was perusing the stacks at my uni last week and found, of all things, Hillis' ph.d disseration on the Connection Machine which goes into a lot of detail on CM Lisp and the problems the CM was meant to tackle.

The Connection Machine story is very interesting in it's own right because of the history and personalities that participated. Plus the subsequent startup and commercilizatioh of the technology in the 80's - 90's time frame, the company being bought and the founders scattering to the four winds.

1) Program Design in the UNIX Environment by Rob Pike and Brian Kernighan.

2) I haven't seen anything 'groundbreaking' for some time... except Go's interfaces, but there is no paper on that (yet).

3) The Plan 9 C Compilers by Ken Thompson.

• The number one most important paper in all computerdom...Characterizing people as non-linear, first-order components in software development
• Joy in Joy, although if you point to the much earlier McCarthy Lisp in Lisp paper instead, I'll forgive you.
• The Algebra of Joy

1) One of your favourite papers of all time:

How Complex Systems Fail by Richard Cook
and since that one is so short as to basically not be a paper, also see:
Why Cryptosystems Fail by Ross Anderson

2) A recent paper you consider ground-breaking in some way:

I'm not in an expert in any field where I could judge "ground-breaking" contributions accurately.

3) A lesser-known paper that you feel ought to be more widely read:

On the Design of Display Processors T.H. Myer, I. E. Sutherland;
Communications of the ACM, Vol 11, No. 6, June 1968 *

* Also known as The Great Wheel of Reincarnation story.

The papers page (see left nav bar) may be a good place to look. Rarely updated these days, it contains links to some of my favorites.

• JMatch: Java plus Pattern Matching. Provides extensible pattern matching like views, extractors and active patterns but improves on them in several ways (edit: JMatch predates extractors and active patterns). The first improvement is that multiple modes can be defined with one formula. For example you can define zs = append(xs,ys) that appends xs to ys and also works backwards in pattern matching (like append in Prolog). The second improvement is that pattern matching can be used as an iteration construct. Foreach takes an arbitrary pattern (element in list being a special case) and iterates over all the ways that this pattern can be instantiated. Integrates switch, foreach, if and let with pattern matching.
• Predicate dispatching: A unified theory of dispatch The way dispatch should be. Unifies conditionals, pattern matching and dispatch in a symmetric whole.
• Flapjax: A Programming Language for Ajax Applications Excellent paper containing among other things many examples of the power of FRP in the browser.
• Sage: Unified Hybrid Checking for First-Class Types, General Refinement Types, and Dynamic "The ultimate type system": unifies types and terms by allowing types to be general predicates. Uses a theorem prover to prove that the program is well typed. Uses a counterexample database to prove that the program isn't well typed. Also shows how you can still do type inference even though type checking is undecidable.

I recently wondered about how to give semantics to functional languages which use random numbers. I stumbled over this paper by Kozen which is about imperative languages but nevertheless very worthwile reading, especially if you enjoyed your functional analysis classes.

1) "Design by Contract: The Lessons of Ariane" (article); by Jean-Marc Jézéquel, IRISA and Bertrand Meyer, ISE (01/1997) :

http://archive.eiffel.com/doc/manuals/technology/contract/ariane/

2) "From Patterns to Components" (Ph.D. dissertation); by Karine Arnout (03/2004) :

http://se.inf.ethz.ch/people/arnout/patterns/

3) "The 'Gang of Four' Companion -- Formal specification of design patterns in LePUS3 and Class-Z" (Technical Report); by Amnon H. Eden, Jonathan Nicholson, Epameinondas Gasparis (12/2007) :

http://www.lepus.org.uk/ref/companion/companion.pdf