CMPSC 461: Programming Language Concepts: Fall 2010


[This page is only a "brochure" for the course. To access course materials, visit Angel.]

Coordinates

This class meets at 075 Willard, on MWF 10:10-11:00 am. The official prerequisites are CMPSC 221 and CMPSC 360. Exemptions can be made, but I urge you to speak to me beforehand if you are seeking one.

Course description

This course exposes you to the principles of programming languages. Here we will: (a) try to understand the internals of several established programming languages, as well as the deep theory behind them; and (b) build several mini-languages ourselves. This means that as you study theoretical principles in this course, you will also be implementing them in your homework assignments. At the end of the course, you will hopefully to able to choose between a fairly wide variety of programming idioms and languages for your next programming project. You will also have built a fairly sophisticated scripting language.

We will use several different programming languages in the course (including Haskell, Ocaml, Scala, and Prolog), but the primary language used for implementation of new languages will be Scheme (in a version known as Racket).

Textbooks

  • Programming Languages: Applications and Implementation. By Shriram Krishnamurthi. (Required). The book is available online, free of cost, at http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/. You can also buy a bound copy of the book for a fairly low price. I encourage you to consider this option, as the author gets paid for his efforts this way.

  • The Little Schemer (4th Edition). By Friedman and Felleisen. (Optional).

  • How to Design Programs. By Felleisen, Findler, Fisler, Flatt, and Krishnamurthi. (Optional). Online text, available at http://www.htdp.org.

We will follow the required text closely.

Programming environments

We will use the Dr. Racket programming environment. Please go to http://racket-lang.org/ and download the current version of Racket. Now open the Dr.Racket programming environment. To install the dialect of Scheme of interest, open Dr. Racket, choose the Pretty Big Language level from the menu in the bottom left of the IDE, type "(require (planet plai/plai:1:3))" in the Definitions window, and click Run. This automatically installs the language for the text. (You will see some warnings; don't mind them.)

Now restart DrRacket. The language will be visible from the language chooser at the bottom-left. Choose the PLAI Scheme language.

Systems for programming in other languages will be introduced in class.

Assignments, examinations, and grading policies

  • Homework assignments: 50%

  • Two in-class midterms: 25%

  • Final (weighted towards later topics): 25%

Late homework and plagiarism policy

There will be no extensions for homework assignments under any circumstances. Late homework will not be accepted, so plan ahead. Plagiarism in any form guarantees a grade less than or equal to C, and may result in an F.

ANGEL

All course materials (including homework assignments and slides) will be posted on ANGEL (http://cms.psu.edu).

Office hours and communication policies

My office hours are Tuesday 2:00-3:00pm, at 343E IST, and by appointment. I am also available for discussion right after class. All emails regarding the course should be sent through Angel; I strongly urge you not to send direct email to me. I will respond to email sent using Angel within 3 working days.

Teaching assistant

The TA for this course is Shad Kirmani (sxk5292@psu.edu). Please email him on Angel if you have questions. He will email you his office hours.

Schedule (updated as semester progresses)

  • First day: Introduction. Syntax and abstract syntax trees. Assignment 0: writing a calculator in your favorite language.

  • Week 1: Syntax in Backus-Naur form. Ambiguous and unambiguous grammars. Why syntax is less important than semantics. Scheme for dummies: recursive programs manipulating lists and trees. Assignment 1: grammars and simple Scheme programming.

  • Week 2: Writing a calculator in Scheme. From a calculator to a functional programming language: introducing scoping and substitutions. Assignment 2: building a simple interpreter using Scheme.

  • Week 3: Scoping and substitutions (continued). Adding support for functions. Lazy vs. eager evaluation. Assignment 3: extending your calculator with scoping and functions.

  • Week 4: Higher-order functional programming. Currying, memoization, etc. Midterm 1.

  • Week 5: Implementation issues in functional programming: closures and recursion.

  • Week 6: Introduction to Haskell and programming with laziness. Assignment 4: Programming with laziness and adding closures and laziness to your mini-language.

  • Week 7: Imperative programming: introducing the store. How to extend the calculator with imperative updates.

  • Week 8: Variables and implicit store updates. Parameter passing. Implementing parameter passing. Assignment 5: Extending your calculator with imperative features (a.k.a. completing your scripting language)

  • Week 9: Automatic memory management and garbage collection. Midterm 2.

  • Week 10: Continuations and scripting languages

  • Week 10-11: Types and program correctness. Introducing the Ocaml language. Building a type checker.

  • Week 12: Type inference. Polymorphic types. Assignment 6: Building a type-checker and playing with the Ocaml type system.

  • Week 13: From type checking to program verification. From type inference to Prolog and programming by searching

  • Week 14-15: Introduction to objects. The Scala language. Inheritance and subtyping. Assignment 7: Concepts in object-oriented programming.

  • Week 15-16: Combining functional and object-oriented programming in Scala