Home » forums » LtU Forum

References for Beginners in PL Theory

I'm an undergrad, and have little exposure to PL theory (or practice). To help remedy this situation I have been, amongst other things, reading LtU but unfortunately, many/most of the discussions here are beyond me.

What texts would you recommend to a beginner in PL theory and practice? What order should they be read in? In what order should the prominent (and not so prominent) topics be addressed?

By Thomas Sutton at 2004-09-23 10:21 | LtU Forum | previous forum topic | next forum topic | other blogs | 6210 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

books to read

Sussman and Abelson, "Structure and Interpretation of Computer Programming"
http://mitpress.mit.edu/sicp/ (full text online!)

Pierce, "Types and Programming Languages".
http://www.cis.upenn.edu/~bcpierce/tapl/

By mrd at Thu, 2004-09-23 15:36 | login or register to post comments

More indications

SICP and "Types and Programming Languages" are very good books. I also liked Theories of Programming Languages (Amazon.com link) by John C. Reynolds. Some of his papers are very good too; Definitional Interpreters for Higher-Order Programming Languages is a classic.

You may want to read something about the lambda calculus sooner or later. There's a short but somewhat dry Introduction to Lambda Calculus by Barendregt & Barendsen. I liked the first part of the lecture notes for a course on Introduction to Functional Programming, by Mike Gordon; it's an introduction to lambda-calculus that's more directly applied to programming. Paulson's Foundations of Functional Programming is good too.

By Andrei Formiga at Thu, 2004-09-23 17:53 | login or register to post comments

Lambda calculus and flood prevention

There's a short but somewhat dry Introduction to Lambda Calculus by Barendregt & Barendsen.

About ten years ago we had very high water levels in the rivers around Nijmegen with thousands of people evacuated from their homes. Erik Barendsen then suggested that he should give a lecture in Lambda Calculus as a way of flood prevention.

Anyway, the version on CiteSeer is out of date. Erik informs me that a more recent version is available.

By Ronny Wichers Schreur at Tue, 2004-09-28 15:33 | login or register to post comments

funny :)

I don't know if this was directed to my comment per se or to the inappropriate use of a term, english being not my native language and all. But I found it very funny, and I'm not being ironic :)

Anyway, what I found lacking in the "Introduction" paper, from a CS pov, were motivating examples to link the theory to its applications. But it is a very good paper and I read it through. And thanks for the link to the updated version.

By Andrei Formiga at Wed, 2004-09-29 12:37 | login or register to post comments

Stuff I've found useful...

Probably one of the best I've gotten hold of is Concepts, Techniques, and Models of Computer Programming, on the parsing front, I've found Parsing Techniques: A Practical Guide to be an excellent intro to the field. Syntax and Semantics of Programming Languages is also a good read. This is in addition to the others posted here.

Honestly, part of it is just that its a huge field and there's so much to learn, a good background in Mathematics can help a lot. Google is your friend, but if you don't know where to start, some of these might be good sources of keywords.

By Matt Estes at Fri, 2004-09-24 04:54 | login or register to post comments

Amazon women, on the moon!

IMO, the best text is John MItchell's Foundations for Programming Languages (MIT Press, 1996). He also has a newer book out, Concepts in Programming Languages (Cambridge Univ Press, 2002), which I haven't seen, but seems to be less technical and more of a survey. (Info is on the same page.)

By Frank Atanassow at Fri, 2004-09-24 14:03 | login or register to post comments

I disagree

I think the Mitchell FoPL book is a really great reference, but it's definitely not an ideal text for an undergrad new to PL. (I haven't seen the Concepts book.)

For self-study, the sequence I'd recommend is something like:

1. Get comfortable with programming in a functional language. Good textbooks are Cousineau and Mauny's The Functional Approach to Programming and Abelson and Sussman's The Structure and Interpretation of Computer Programs. If you use SICP, definitely also learn ML or Haskell -- actually getting comfortable with the behavior of an HM type system will be important later on.

Step 2. Get comfortable with implementing itty-bitty interpreters for functional languages. Good texts here are Friedman, Wand and Haynes's Essentials of Programming Languages and Appel's Compiling with Continuations.

Step 3. At this point, you can look at Benjamin Pierce's Types and Programming Languages. The critical conceptual idea is proving properties by structural induction on the typing or evaluation derivations (which is one step more abstract than an induction on the syntax).

At this point, there's stuff like the Curry Howard isomorphism, category theory, domain theory, and so on, but you can do it in pretty much any order.

The basic pedagogical idea here is to think of PL as a branch of constructive math. When you learn how to program functionally, you get comfortable with using the constructions. When you learn how to implement them, you learn what the structure of the constructions are. Finally, you prove that the constructions are correct. At each stage, you want to minimize the amount of novelty you need to master.

By neelk at Fri, 2004-09-24 15:06 | login or register to post comments

Books

Assuming that the poster is a typical but enthusiastic student with programming experience with one or two imperative languages, I would go for this progression of books:

* a fairly good Principles of Programming Languages / Comparative Languages book, such as Michael L. Scott's Programming Language Pragmatics; these develop a more abstract way of looking at PL's in general. A standard POPL / CL undergrad course is sufficient, too.

* since the beforementioned books tend to downplay functional programming, learn that. I recommend Thompson's Haskell: The Craft of Functional Programming as a guide. Or anticipating the next recommendation, get a ML-based book.

* get serious: Pierce's Types and Programming Languages and Reynold's Theories of Programming Languages (read both in either order).

The point is: get a solid foundation first :)

Or you could do what I did: read everything that comes your way regardless of whether you understand it or not. Eventually, you will. (This will take years.)

By Antti Juhani Kaijanaho at Wed, 2004-09-29 08:23 | login or register to post comments

a few more more good ones

Programming Languages - Application and Interpretation, the latest draft of Shriram Krishnamurthi's new text

Programming Languages and Lambda Calculi, by Matthew Flatt and Matthias Felleisen; lots of operational semantics

Principles of Programming Languages class notes by Mitch Wand; these notes are very approachable and informative. Download them locally as they come out because he tends to remove them and start over every time he teaches the class.

By Dave Herman at Thu, 2004-09-30 04:45 | login or register to post comments