7 ms·

Great Works in Programming Languages

184 points by timf 13y ago

csense 13y ago
The most recent paper in the first section was written in 1978. The majority of the ones in the first two sections were written before I was born; only three were written in the 1990's. The only one from the 21st century (published in 2000) is in the least-prestigious third section. Does it take time for good ideas to accumulate the recognition needed to be included in this list? Or was all the low-hanging fruit quickly picked in the early days of the computer age, and only hard problems remain on which little progress has been made? Haven't any new ideas been introduced by the innovations of modern languages like Python, Lisp, Haskell and Ruby? Or even C++, Java and JavaScript? Or is language implementation, almost without exception, a series of engineering refinements that happen in a decades-long process after theoretical foundations are first published?
- ernesth 13y ago
  > Haven't any new ideas been introduced by the innovations of modern languages like Python, Lisp, Haskell and Ruby? Or even C++, Java and JavaScript? Those modern languages are all older than 2000. Some of the papers cited in this list are indeed related to Haskell, Lisp (do you really consider lisp modern?). And Compiling works that will have a lasting impact needs some time to reflect on the importance of new works. This list is essentially centered on logic in programming languages (lambda calculus, types theory, semantics, monads), hence the absence of python, ruby, javascript: those languages picked a lot from this theory but did not bring much novel material.
- exDM69 13y ago
  > Or was all the low-hanging fruit quickly picked in the early days of the computer age, and only hard problems remain on which little progress has been made? Yes, most of the ground breaking theories were researched and documented decades ago. And some of that stuff has yet to make itself to mainstream programming languages (e.g. type inference). > Haven't any new ideas been introduced by the innovations of modern languages like Python, Lisp, Haskell and Ruby? Or even C++, Java and JavaScript? Apart from Lisp and Haskell, the "modern" languages you mention are rather boring when it comes to programming language design and there isn't too much research behind them. There has been a lot of practical work and research in garbage collection, run time systems, compiler back ends, just in time compilation and virtual machines. But when it comes to language design, the mainstream programming languages are really conservative.
  - jfb 13y ago
    Too, Lisp was described for the first time in 1958. See "Pretty Great Works", #8.
- arethuza 13y ago
  The relationships between theoretical innovations and practical innovations is particularly indistinct in Computer Science. A language like JavaScript might be interesting because it is simple and ubiquitous and embedded in a powerful application platform - but that does not mean it is of much interest from a theoretical CS perspective.
  - csense 13y ago
    > that does not mean it is of much interest from a theoretical CS perspective JavaScript theoretically uninteresting? Are you kidding? What about its unusual prototypical inheritance? JSON-style literals? Its notation for anonymous functions? The approach modern JS frameworks take to single-threaded asynchronous execution? IMHO, JS is not the best language for getting work done [1], but it has lots of innovations which are worthy of study. [1] If you need to do Web frontend stuff, obviously JavaScript is the only game in town, unless you're into Flash, Java applets, or compilers with JS backends.
    - arethuza 13y ago
      "Interesting" and even "practically useful" do not imply "theoretically interesting from an academic perspective". Of course, the measure for academics is "can I get something published on the topic somewhere respectable" - it (mostly) doesn't have much to do with whether something is cool or useful.
    - octo_t 13y ago
      It can certainly be interesting, but most of the interesting research being done is related to the intersection of languages and security. There do exist formalisations, but they are derivative works based on the GREAT papers. Notation is for the most part boring. The way you write function literals has no effect on the semantics of the language. The prototype inheritance is also boring, the small step semantics being two inference rules[1]. JSON-style literals are what. A way of writing a POD. Who cares. It is boring. Asynchronous execution is also boring. It was novel in the 1960s, it is not novel now. [1] - http://www.doc.ic.ac.uk/research/technicalreports/2008/DTR08-13.pdf http://www.doc.ic.ac.uk/research/technicalreports/2008/DTR08...
boothead 13y ago
Does this count? http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html http://james-iry.blogspot.com/2009/05/brief-incomplete-and-m... It's a masterpiece!
- tehwalrus 13y ago
  That is wonderful. As a physicist whose first language was FORTRAN, I particularly like "It is a syntax error to write FORTRAN while not wearing a blue tie."
angersock 13y ago
You know what'd be even better? A public vault of this articles so we can all learn easily instead of having to go through journal publishers. EDIT: Why thank you, Lazyweb!
- YAYERKA 13y ago
  ## The greatest of the great C. A. R. Hoare. An axiomatic basis for computer programming. http://sunnyday.mit.edu/16.355/Hoare-CACM-69.pdf http://sunnyday.mit.edu/16.355/Hoare-CACM-69.pdf Peter J. Landin. The next 700 programming languages. http://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf http://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf Robin Milner. A theory of type polymorphism in programming. http://courses.engr.illinois.edu/cs421/sp2012/project/milner-polymorphism.pdf http://courses.engr.illinois.edu/cs421/sp2012/project/milner... Gordon Plotkin. Call-by-name, call-by-value, and the λ-calculus. http://homepages.inf.ed.ac.uk/gdp/publications/cbn_cbv_lambda.pdf http://homepages.inf.ed.ac.uk/gdp/publications/cbn_cbv_lambd... John C. Reynolds. Towards a theory of type structure. http://www.cs.cmu.edu/~crary/819-f09/Reynolds74.pdf http://www.cs.cmu.edu/~crary/819-f09/Reynolds74.pdf
  - angersock 13y ago
    <3
- lambda 13y ago
  Greatest of the great: C. A. R. Hoare. An axiomatic basis for computer programming: http://sigpl.or.kr/school/2005w/slides/2_17_1.pdf http://sigpl.or.kr/school/2005w/slides/2_17_1.pdf Peter J. Landin. The next 700 programming languages: http://www.thecorememory.com/Next_700.pdf http://www.thecorememory.com/Next_700.pdf Robin Milner. A theory of type polymorphism in programming: http://courses.engr.illinois.edu/cs421/sp2012/project/milner-polymorphism.pdf http://courses.engr.illinois.edu/cs421/sp2012/project/milner... Gordon Plotkin. Call-by-name, call-by-value, and the λ-calculus : http://www.sciencedirect.com/science/article/pii/0304397575900171 http://www.sciencedirect.com/science/article/pii/03043975759... (PDF link at upper right of page) John C. Reynolds. Towards a theory of type structure: http://repository.cmu.edu/cgi/viewcontent.cgi?article=2289&context=compsci&sei-redir=1 http://repository.cmu.edu/cgi/viewcontent.cgi?article=2289&c... Pretty great works: Luca Cardelli. A semantics of multiple inheritance: http://lucacardelli.name/Papers/Inheritance.pdf http://lucacardelli.name/Papers/Inheritance.pdf Luis Damas and Robin Milner. Principal type schemes for functional programs: http://web.cs.wpi.edu/~cs4536/c12/milner-damas_principal_types.pdf http://web.cs.wpi.edu/~cs4536/c12/milner-damas_principal_typ... Edsger W. Dijkstra. Recursive programming: http://oai.cwi.nl/oai/asset/9253/9253A.pdf http://oai.cwi.nl/oai/asset/9253/9253A.pdf Edsger W. Dijkstra. Go to statement considered harmful: http://www.massey.ac.nz/~kahawick/159331/Goto-Harmful-Dijkstra.pdf http://www.massey.ac.nz/~kahawick/159331/Goto-Harmful-Dijkst... William A. Howard. The formulas-as-types notion of construction: http://www.cs.cmu.edu/~crary/819-f09/Howard80.pdf http://www.cs.cmu.edu/~crary/819-f09/Howard80.pdf Robert Kowalski. Predicate logic as programming language: http://65.99.230.10:81/collect/computer/index/assoc/HASH0183.dir/doc.pdf http://65.99.230.10:81/collect/computer/index/assoc/HASH0183... Peter J. Landin. The mechanical evaluation of expressions: http://ropas.snu.ac.kr/lib/dock/La1964.pdf http://ropas.snu.ac.kr/lib/dock/La1964.pdf John McCarthy. Recursive functions of symbolic expressions and their computation by machine: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.8833&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111... Eugenio Moggi. Computational lambda-calculus and monads: http://pdf.aminer.org/000/267/711/lazy_lambda_calculus_theories_models_and_local_structure_characterization_extended.pdf http://pdf.aminer.org/000/267/711/lazy_lambda_calculus_theor... Greg Morrisett, David Walker, Karl Crary, and Neal Glew. From System-F to typed assembly language: http://staff.ustc.edu.cn/~xyfeng/reading/p527-morrisett.pdf http://staff.ustc.edu.cn/~xyfeng/reading/p527-morrisett.pdf George C. Necula. Proof-carrying code: http://www.utdallas.edu/~kxh060100/Papers/necula96.pdf http://www.utdallas.edu/~kxh060100/Papers/necula96.pdf Gordon D. Plotkin. LCF considered as a programming language: http://www.sciencedirect.com/science/article/pii/0304397577900445 http://www.sciencedirect.com/science/article/pii/03043975779... Gordon D. Plotkin. A structural approach to operational semantics: https://www.alice.virginia.edu/~weimer/2006-655/reading/plotkin81structural.pdf https://www.alice.virginia.edu/~weimer/2006-655/reading/plot... Guy Lewis Steele Jr. RABBIT: A compiler for SCHEME ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-474.pdf OK, I think the first two sections are plenty. You can search for the rest yourself on Google Scholar (I found most of these as the first hit on Google Scholar, one or two took looking through a few hits or doing a Google search as well)
kenko 13y ago
When I saw this was hosted at upenn.edu, I was certain it was a Kenneth Goldsmith project.
- adregan 13y ago
  I too was expecting something very different. Something nice and uncreative.
jph 13y ago
Great reading list! How about "The Semantic Web" by Tim Berners-Lee?
- angersock 13y ago
  Oh, the one by the Web Developer?
Locke1689 13y ago
Ugh, if you look at the bottom of the pretty great works you will see Guy Steele's master's thesis where he defined the Scheme programming language and its compiler. I know when I was writing my thesis I was pretty disgusted that he ruined it for all of us mere mortals. ;)
- quantumet 13y ago
  I think Claude Shannon's (of information theory fame) master's thesis beats out all others in the field of computer science. "A Symbolic Analysis of Relay and Switching Circuits", 1938, proves that you can use electrical switches to do boolean algebra! He basically invented the digital computer, as a master's thesis.
  - sp332 13y ago
    Not to diminish Shannon's genius at all, but he wasn't the first to make logic circuits. http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams/1183541145 http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?vi... On page 917 you can see Charles Sanders Pierce and Alan Marquand made some in the 1880's.
trippy_biscuits 13y ago
More of Plotkin's publications: http://homepages.inf.ed.ac.uk/gdp/publications/ http://homepages.inf.ed.ac.uk/gdp/publications/
mixedbit 13y ago
'Can Programming Be Liberated from the von. Neumann Style?' by John Backus is another great work very worth studying: 'Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor—the von Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs.' Thankfully, 30+ years later these problems are widely fixed ;) http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf http://www.thocp.net/biographies/papers/backus_turingaward_l...
exDM69 13y ago
I'm a bit surprised not to see any papers by Simon Peyton-Jones (of Haskell fame) on the list. I guess most of the papers on this list were old classics and many of the authors have already passed away or retired. SPJ is one of the most relevant programming language researchers of the past 20 years, but maybe his work is "too new" for this list. Reading his books and papers taught sparked the interest in programming languages in me.
- marshray 13y ago
  I think it lacks the property of being "a paper", but I'll happily nominate The Implementation of Functional Programming Languages Simon Peyton Jones, Prentice Hall 1987 http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/ http://research.microsoft.com/en-us/um/people/simonpj/papers...
  - exDM69 13y ago
    That book is great. I wrote a toy compiler loosely based on parts of that book. Here's a newer book that covers similar subjects: "Implementing functional languages: a tutorial" http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/ http://research.microsoft.com/en-us/um/people/simonpj/papers...
- dscrd 13y ago
  Perhaps it's still questionable whether his work will have any actual effect on the industry as a whole, as opposed to just academia.
  - wbsun 13y ago
    Good point!
  - octo_t 13y ago
    Are you serious? SPJ's work has been incredibly instrumental in bringing functional features (such as LINQ) to C# See: http://www.infoq.com/interviews/simon-peyton-jones-about-mainstream-programming-languages http://www.infoq.com/interviews/simon-peyton-jones-about-mai... http://research.microsoft.com/en-us/um/people/simonpj/papers/haskell-retrospective/ecoop-july09.pdf http://research.microsoft.com/en-us/um/people/simonpj/papers...
swah 13y ago
If anyone doesn't know, Benjamin Pierce is the author of a highly regarded book, Types and Programming Languages. (I'm yet to study it, its advanced supposedly...)
- octo_t 13y ago
  I was looking for Featherweight Java[1] on that list before I decided it would have been vein for him to include a paper by himself on the list. [1] http://web.eecs.umich.edu/~bchandra/courses/papers/Igarashi_FJ.pdf http://web.eecs.umich.edu/~bchandra/courses/papers/Igarashi_...
zwieback 13y ago
Since the list is a lot about typing I wanted to see Liskov-Wing "A Behavioral Notion of Subtyping" in there. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=213162B5E8875E6BDB3D104B452F036B?doi=10.1.1.39.1223&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=213... I found that pretty interesting and it caused a lot of discussion.
deleted 13y ago
[deleted]
tel 13y ago
Only one paper by Filinski? I've been picking through 'Declarative Continuations and Categorical Duality' where he shows the duality between values and continuations by generalizing lambda calculus to a symmetric version. It's incredible beautiful.
papsosouid 13y ago
>Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348-375, August 1978 It is in the top 5 and yet none of the go developers will acknowledge that it exists.
6ren 13y ago
My second remark is that our intellectual powers are rather geared to master static relations and that our powers to visualize processes evolving in time are relatively poorly developed. For that reason we should do (as wise programmers aware of our limitations) our utmost to shorten the conceptual gap between the static program and the dynamic process, to make the correspondence between the program (spread out in text space) and the process (spread out in time) as trivial as possible. From Dijkstra's "Go To Statement Considered Harmful"

184 points by timf 13y ago

The most recent paper in the first section was written in 1978. The majority of the ones in the first two sections were written before I was born; only three were written in the 1990's. The only one from the 21st century (published in 2000) is in the least-prestigious third section. Does it take time for good ideas to accumulate the recognition needed to be included in this list? Or was all the low-hanging fruit quickly picked in the early days of the computer age, and only hard problems remain on which little progress has been made? Haven't any new ideas been introduced by the innovations of modern languages like Python, Lisp, Haskell and Ruby? Or even C++, Java and JavaScript? Or is language implementation, almost without exception, a series of engineering refinements that happen in a decades-long process after theoretical foundations are first published?

ernesth 13y ago
> Haven't any new ideas been introduced by the innovations of modern languages like Python, Lisp, Haskell and Ruby? Or even C++, Java and JavaScript? Those modern languages are all older than 2000. Some of the papers cited in this list are indeed related to Haskell, Lisp (do you really consider lisp modern?). And Compiling works that will have a lasting impact needs some time to reflect on the importance of new works. This list is essentially centered on logic in programming languages (lambda calculus, types theory, semantics, monads), hence the absence of python, ruby, javascript: those languages picked a lot from this theory but did not bring much novel material.
exDM69 13y ago
> Or was all the low-hanging fruit quickly picked in the early days of the computer age, and only hard problems remain on which little progress has been made? Yes, most of the ground breaking theories were researched and documented decades ago. And some of that stuff has yet to make itself to mainstream programming languages (e.g. type inference). > Haven't any new ideas been introduced by the innovations of modern languages like Python, Lisp, Haskell and Ruby? Or even C++, Java and JavaScript? Apart from Lisp and Haskell, the "modern" languages you mention are rather boring when it comes to programming language design and there isn't too much research behind them. There has been a lot of practical work and research in garbage collection, run time systems, compiler back ends, just in time compilation and virtual machines. But when it comes to language design, the mainstream programming languages are really conservative.
- jfb 13y ago
  Too, Lisp was described for the first time in 1958. See "Pretty Great Works", #8.
arethuza 13y ago
The relationships between theoretical innovations and practical innovations is particularly indistinct in Computer Science. A language like JavaScript might be interesting because it is simple and ubiquitous and embedded in a powerful application platform - but that does not mean it is of much interest from a theoretical CS perspective.
- csense 13y ago
  > that does not mean it is of much interest from a theoretical CS perspective JavaScript theoretically uninteresting? Are you kidding? What about its unusual prototypical inheritance? JSON-style literals? Its notation for anonymous functions? The approach modern JS frameworks take to single-threaded asynchronous execution? IMHO, JS is not the best language for getting work done [1], but it has lots of innovations which are worthy of study. [1] If you need to do Web frontend stuff, obviously JavaScript is the only game in town, unless you're into Flash, Java applets, or compilers with JS backends.
  - arethuza 13y ago
    "Interesting" and even "practically useful" do not imply "theoretically interesting from an academic perspective". Of course, the measure for academics is "can I get something published on the topic somewhere respectable" - it (mostly) doesn't have much to do with whether something is cool or useful.
  - octo_t 13y ago
    It can certainly be interesting, but most of the interesting research being done is related to the intersection of languages and security. There do exist formalisations, but they are derivative works based on the GREAT papers. Notation is for the most part boring. The way you write function literals has no effect on the semantics of the language. The prototype inheritance is also boring, the small step semantics being two inference rules[1]. JSON-style literals are what. A way of writing a POD. Who cares. It is boring. Asynchronous execution is also boring. It was novel in the 1960s, it is not novel now. [1] - http://www.doc.ic.ac.uk/research/technicalreports/2008/DTR08-13.pdf http://www.doc.ic.ac.uk/research/technicalreports/2008/DTR08...

boothead 13y ago

Does this count? http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html http://james-iry.blogspot.com/2009/05/brief-incomplete-and-m... It's a masterpiece!

tehwalrus 13y ago
That is wonderful. As a physicist whose first language was FORTRAN, I particularly like "It is a syntax error to write FORTRAN while not wearing a blue tie."

angersock 13y ago

You know what'd be even better? A public vault of this articles so we can all learn easily instead of having to go through journal publishers. EDIT: Why thank you, Lazyweb!

YAYERKA 13y ago
## The greatest of the great C. A. R. Hoare. An axiomatic basis for computer programming. http://sunnyday.mit.edu/16.355/Hoare-CACM-69.pdf http://sunnyday.mit.edu/16.355/Hoare-CACM-69.pdf Peter J. Landin. The next 700 programming languages. http://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf http://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf Robin Milner. A theory of type polymorphism in programming. http://courses.engr.illinois.edu/cs421/sp2012/project/milner-polymorphism.pdf http://courses.engr.illinois.edu/cs421/sp2012/project/milner... Gordon Plotkin. Call-by-name, call-by-value, and the λ-calculus. http://homepages.inf.ed.ac.uk/gdp/publications/cbn_cbv_lambda.pdf http://homepages.inf.ed.ac.uk/gdp/publications/cbn_cbv_lambd... John C. Reynolds. Towards a theory of type structure. http://www.cs.cmu.edu/~crary/819-f09/Reynolds74.pdf http://www.cs.cmu.edu/~crary/819-f09/Reynolds74.pdf
- angersock 13y ago
  <3
lambda 13y ago
Greatest of the great: C. A. R. Hoare. An axiomatic basis for computer programming: http://sigpl.or.kr/school/2005w/slides/2_17_1.pdf http://sigpl.or.kr/school/2005w/slides/2_17_1.pdf Peter J. Landin. The next 700 programming languages: http://www.thecorememory.com/Next_700.pdf http://www.thecorememory.com/Next_700.pdf Robin Milner. A theory of type polymorphism in programming: http://courses.engr.illinois.edu/cs421/sp2012/project/milner-polymorphism.pdf http://courses.engr.illinois.edu/cs421/sp2012/project/milner... Gordon Plotkin. Call-by-name, call-by-value, and the λ-calculus : http://www.sciencedirect.com/science/article/pii/0304397575900171 http://www.sciencedirect.com/science/article/pii/03043975759... (PDF link at upper right of page) John C. Reynolds. Towards a theory of type structure: http://repository.cmu.edu/cgi/viewcontent.cgi?article=2289&context=compsci&sei-redir=1 http://repository.cmu.edu/cgi/viewcontent.cgi?article=2289&c... Pretty great works: Luca Cardelli. A semantics of multiple inheritance: http://lucacardelli.name/Papers/Inheritance.pdf http://lucacardelli.name/Papers/Inheritance.pdf Luis Damas and Robin Milner. Principal type schemes for functional programs: http://web.cs.wpi.edu/~cs4536/c12/milner-damas_principal_types.pdf http://web.cs.wpi.edu/~cs4536/c12/milner-damas_principal_typ... Edsger W. Dijkstra. Recursive programming: http://oai.cwi.nl/oai/asset/9253/9253A.pdf http://oai.cwi.nl/oai/asset/9253/9253A.pdf Edsger W. Dijkstra. Go to statement considered harmful: http://www.massey.ac.nz/~kahawick/159331/Goto-Harmful-Dijkstra.pdf http://www.massey.ac.nz/~kahawick/159331/Goto-Harmful-Dijkst... William A. Howard. The formulas-as-types notion of construction: http://www.cs.cmu.edu/~crary/819-f09/Howard80.pdf http://www.cs.cmu.edu/~crary/819-f09/Howard80.pdf Robert Kowalski. Predicate logic as programming language: http://65.99.230.10:81/collect/computer/index/assoc/HASH0183.dir/doc.pdf http://65.99.230.10:81/collect/computer/index/assoc/HASH0183... Peter J. Landin. The mechanical evaluation of expressions: http://ropas.snu.ac.kr/lib/dock/La1964.pdf http://ropas.snu.ac.kr/lib/dock/La1964.pdf John McCarthy. Recursive functions of symbolic expressions and their computation by machine: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.8833&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111... Eugenio Moggi. Computational lambda-calculus and monads: http://pdf.aminer.org/000/267/711/lazy_lambda_calculus_theories_models_and_local_structure_characterization_extended.pdf http://pdf.aminer.org/000/267/711/lazy_lambda_calculus_theor... Greg Morrisett, David Walker, Karl Crary, and Neal Glew. From System-F to typed assembly language: http://staff.ustc.edu.cn/~xyfeng/reading/p527-morrisett.pdf http://staff.ustc.edu.cn/~xyfeng/reading/p527-morrisett.pdf George C. Necula. Proof-carrying code: http://www.utdallas.edu/~kxh060100/Papers/necula96.pdf http://www.utdallas.edu/~kxh060100/Papers/necula96.pdf Gordon D. Plotkin. LCF considered as a programming language: http://www.sciencedirect.com/science/article/pii/0304397577900445 http://www.sciencedirect.com/science/article/pii/03043975779... Gordon D. Plotkin. A structural approach to operational semantics: https://www.alice.virginia.edu/~weimer/2006-655/reading/plotkin81structural.pdf https://www.alice.virginia.edu/~weimer/2006-655/reading/plot... Guy Lewis Steele Jr. RABBIT: A compiler for SCHEME ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-474.pdf OK, I think the first two sections are plenty. You can search for the rest yourself on Google Scholar (I found most of these as the first hit on Google Scholar, one or two took looking through a few hits or doing a Google search as well)

kenko 13y ago

When I saw this was hosted at upenn.edu, I was certain it was a Kenneth Goldsmith project.

adregan 13y ago
I too was expecting something very different. Something nice and uncreative.

jph 13y ago

Great reading list! How about "The Semantic Web" by Tim Berners-Lee?

angersock 13y ago
Oh, the one by the Web Developer?

Locke1689 13y ago

Ugh, if you look at the bottom of the pretty great works you will see Guy Steele's master's thesis where he defined the Scheme programming language and its compiler. I know when I was writing my thesis I was pretty disgusted that he ruined it for all of us mere mortals. ;)

quantumet 13y ago
I think Claude Shannon's (of information theory fame) master's thesis beats out all others in the field of computer science. "A Symbolic Analysis of Relay and Switching Circuits", 1938, proves that you can use electrical switches to do boolean algebra! He basically invented the digital computer, as a master's thesis.
- sp332 13y ago
  Not to diminish Shannon's genius at all, but he wasn't the first to make logic circuits. http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams/1183541145 http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?vi... On page 917 you can see Charles Sanders Pierce and Alan Marquand made some in the 1880's.

trippy_biscuits 13y ago

More of Plotkin's publications: http://homepages.inf.ed.ac.uk/gdp/publications/ http://homepages.inf.ed.ac.uk/gdp/publications/

mixedbit 13y ago

'Can Programming Be Liberated from the von. Neumann Style?' by John Backus is another great work very worth studying: 'Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor—the von Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs.' Thankfully, 30+ years later these problems are widely fixed ;) http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf http://www.thocp.net/biographies/papers/backus_turingaward_l...

exDM69 13y ago

I'm a bit surprised not to see any papers by Simon Peyton-Jones (of Haskell fame) on the list. I guess most of the papers on this list were old classics and many of the authors have already passed away or retired. SPJ is one of the most relevant programming language researchers of the past 20 years, but maybe his work is "too new" for this list. Reading his books and papers taught sparked the interest in programming languages in me.

marshray 13y ago
I think it lacks the property of being "a paper", but I'll happily nominate The Implementation of Functional Programming Languages Simon Peyton Jones, Prentice Hall 1987 http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/ http://research.microsoft.com/en-us/um/people/simonpj/papers...
- exDM69 13y ago
  That book is great. I wrote a toy compiler loosely based on parts of that book. Here's a newer book that covers similar subjects: "Implementing functional languages: a tutorial" http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/ http://research.microsoft.com/en-us/um/people/simonpj/papers...
dscrd 13y ago
Perhaps it's still questionable whether his work will have any actual effect on the industry as a whole, as opposed to just academia.
- wbsun 13y ago
  Good point!
- octo_t 13y ago
  Are you serious? SPJ's work has been incredibly instrumental in bringing functional features (such as LINQ) to C# See: http://www.infoq.com/interviews/simon-peyton-jones-about-mainstream-programming-languages http://www.infoq.com/interviews/simon-peyton-jones-about-mai... http://research.microsoft.com/en-us/um/people/simonpj/papers/haskell-retrospective/ecoop-july09.pdf http://research.microsoft.com/en-us/um/people/simonpj/papers...

swah 13y ago

If anyone doesn't know, Benjamin Pierce is the author of a highly regarded book, Types and Programming Languages. (I'm yet to study it, its advanced supposedly...)

octo_t 13y ago
I was looking for Featherweight Java[1] on that list before I decided it would have been vein for him to include a paper by himself on the list. [1] http://web.eecs.umich.edu/~bchandra/courses/papers/Igarashi_FJ.pdf http://web.eecs.umich.edu/~bchandra/courses/papers/Igarashi_...

zwieback 13y ago

Since the list is a lot about typing I wanted to see Liskov-Wing "A Behavioral Notion of Subtyping" in there. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=213162B5E8875E6BDB3D104B452F036B?doi=10.1.1.39.1223&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=213... I found that pretty interesting and it caused a lot of discussion.

deleted 13y ago

[deleted]

tel 13y ago

Only one paper by Filinski? I've been picking through 'Declarative Continuations and Categorical Duality' where he shows the duality between values and continuations by generalizing lambda calculus to a symmetric version. It's incredible beautiful.

papsosouid 13y ago

>Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348-375, August 1978 It is in the top 5 and yet none of the go developers will acknowledge that it exists.

6ren 13y ago

My second remark is that our intellectual powers are rather geared to master static relations and that our powers to visualize processes evolving in time are relatively poorly developed. For that reason we should do (as wise programmers aware of our limitations) our utmost to shorten the conceptual gap between the static program and the dynamic process, to make the correspondence between the program (spread out in text space) and the process (spread out in time) as trivial as possible. From Dijkstra's "Go To Statement Considered Harmful"