ACM 20 Most Influential Papers on Programming Languages [tarball]

http://dl.getdropbox.com/u/2083231/acm_pldi_20_best_papers.tar.gz

by mahmud • 17 years ago

83 15 17 years ago

dl.getdropbox.com

mahmud5• 17 years ago

These are actually 18 of the papers that I could find in the "free" web, away from the ACM/IEEE pay wall. I got them all from the authors' websites and collected them for my own reading. I share them with you here for the love of learning, they're a treasure. I hope I don't annoy anybody for doing this.

Here is the original ACM announcement:

http://www.cs.utexas.edu/users/mckinley/20-years.html

And these are the papers in the tarball:

A Data Locality Optimizing Algorithm.pdf

A Safe Approximate Algorithm for Interprocedural Pointer

Aliasing.pdf

An Evaluation of Staged Run-Time Optimizations in DyC.pdf

An Implementation of Lazy Code Motion for SUIF.pdf

Analysis of Pointers and Structures.pdf

Balanced Scheduling- Instruction Scheduling When Memory Latency is Uncertain.pdf

Complete Removal of Redundant Expressions.pdf

Global Register Allocation at Link Time.pdf

How To Read Floating Point Numbers Accurately.pdf

Improving Register Allocation for Subscripted Variables.pdf

Interprocedural Constant Propagation.pdf

Interprocedural Slicing Using Dependence Graphs.pdf

Lazy Code Motion.pdf

On-The-Fly Detection of Access Anomalies.pdf

Soft Typing.pdf

Software Pipelining-- An Effective Scheduling Technique for VLIW Machines.pdf

The Design and Implementation of a Certifying Compiler.pdf

tlrobinson• 17 years ago

Neat, thanks.

In general if you link directly to something that's not a webpage you should indicate what it is in the title.

mahmud5• 17 years ago

fixed! thanks.

P.S. big fan of your work :-)

pbiggar• 17 years ago

Title is wrong. These are only the most influential papers published at PLDI, I think.

juvenn• 17 years ago

Awe, Thanks

pkrumins• 17 years ago

You have not included 'Aliasing.pdf' and 'An Evaluation of Staged Run-Time Optimizations in DyC.pdf' in the tarball.

Can you include them as well?

mahmud5• 17 years ago

These are actually 18 of the papers that I could find in the "free" web

Let's hunt those two down HNers! But please, do NOT repost from the ACM, IEEE, Elsevier or other pay services.

Email it to me and I will add to the collection.

tsally• 17 years ago

I hope I don't annoy anybody for doing this.

Quite the contrary. :)

zitterbewegung• 17 years ago

What about a paper on lisp like "A basis for a mathematical theory of computation "?

mahmud5• 17 years ago

Indulge yourself:

http://library.readscheme.org/

The must reads are Keny Dybvig's thesis, "Three Implementations of Scheme". The original lambda papers can wait until you read the Orbit paper, an optimizing compiler for T by Kranz, Rees et al.

The Lisp implementation bibliography pretty much runs through PL research like a vein. Some of the stuff you must read for Lisp are typically in "books"; Christian Quinnec's Lisp in Small Pieces is the most important work, but you will need a good foundation in denotational semantics (you can get by with the one chapter in the little book by Nielson and Nielson, "Semantics with Applications: A Formal Introduction".

Somewhere in there you will brush against various compilation methods and IRs for the lambda calculus, most importantly continuation passing style. Most semantics text introduce lambda calculus and its three rules, but none go in depth into this like the tall green book by Andrew Appel, "Compiling with Continuations", a good chunk of which can be read in Appel's other papers. Appel's work is MLish in nature, but don't let that stop you; most optimizing Lisp compilers are MLish down underneath anyway. CMUCL does very good type inference but gets short of implementing a full Hindley-Milner. Felleisen et al's "The Essence of Compiling with Continuations" might also come handy, though it's heavy on the theory. Andrew Kennedy continues the saga with "Compiling with Continuations Continued", this time CPS gives way to A-Normal Form, another IR. He describes the techniques used by a compiler targeting .NET.

Most compiling "meat" can be found in the bits-and-bytes type papers. Wilson's GC bibliography "Uniprocessor Garbage Collection Techniques" is a must, it should have been called "What Every Programmer Should Know About Garbage Collection". Not to be confused with Richard Jones' "the Garbage Collection Bibliography". Boehm's "Garbage Collection in an Uncooperative Environment" is sheer hacking bravado, perhaps second only to "Pointer Swizzling at Page Fault Time", which should introduce you to memory management for disk-based heaps (i.e. object stores) among other things.

Your start in hacking runtimes will probably be David Gudeman's "Representing Type Information in Dynamically Typed Languages"; this is where you learn how stuff looks inside the computer when you no longer need to malloc and free. A previous hacking of a Pascal dialect prepared me for this wonderful paper.

Implementations of runtimes are documented by Appel, for SML/NJ, Robert MacLaclahn's "Design of CMU Common Lisp" (also perhaps Scott Fahlman's CMU report on CMUCL's precursor, "Internal Design of Spice Lisp", but that confused the crap out of me as I don't know the machine architecture they're talking about.) You will also enjoy the Smalltalk research starting with L. Peter Deutsch's first optimizing Smalltalk compiler, documented in "Efficient Implementation of Smalltalk-80", follow the Smalltalk lineage btw, all they way up to David Ungar's "The Design and Evaluation of a High Performance Smalltalk System" making sure NOT to ignore Self and its literature, also spearheaded by Ungar (Start your Smalltalk hacking career with Timothy Budd's "A Little Smalltalk", should take you about a weekend and will absolutely prepare you for dynamic languages; a similar system is described by Griswold and Griswold, compiler, intermediate representation and VM, but that one is for ICON.)

Dynamic type inference and type-checking (TYPEP and SUBTYPEP, CLASS-OF, INSTANCE-OF, etc) you can learn a good chunk of how CLOS should look like to the runtime system from Justin Graver's "Type-Checking and Type-Inference for Object Oriented Programming Languages". He scratches the surface, and you should supplement this with a selection from Smalltalk and Self, though neither will prepare you for multiple-dispatch, for that peer into Stanley Lippman's "Inside the C++ Object System".

I have deliberately avoided "classics" on Lisp, compiler construction, optimization, and other stuff. None of the books and papers I have recommended are as popular as SICP, PAIP, or AMOP. Or even the popular PL books, like EoPL, van Roy and Haridi, both of which you should read by the way, but they're stuff that you need to read and understand to be able to implement a practical Lisp implementation, or at least satisfy your curiosity.

onreact-com2• 17 years ago

Ask HN: Are numbered lists in headlines OK again?

onreact-com2• 17 years ago

Does downvoting mean yes or no in this case?

gloob• 17 years ago

In this case, I suspect that downvoting means that people think you're being snarky about something that is blatantly awesome. Dunno though, as I wasn't one of them.

g__• 17 years ago

Another nice collection:

http://www.reddit.com/r/programming/comments/9220o/ask_progg...

mahmud5• 17 years ago

Shame on you. I was just going to bed!

Thanks :-)

ACM 20 Most Influential Papers on Programming Languages [tarball]

Related Stories