Programming Languages - CPSC 604 (Spring 2009)

Course Essentials

News

Apr 2

Info on projects

Mar 26

Assignment 5 is out

Mar 2

Assignment 4 is out

Feb 15

Assignment 3 is out

Feb 3

Assignment 2 is out

Jan 28

Assignment 1 is out

In a nutshell

Study in the design space of programming languages, covering language processing, formalisms to describe semantics of programming languages, important concepts found in current programming languages, and programming paradigms.

Note to a prospective student

Programming languages are an active research area, striving towards ever safer, more efficient, and expressive languages and programming environments. Results from recent programming language research are finding their way to main stream languages, both C# and Java have recently been extended with generics, Java with wildcards, C# with LINQ. C++ is changing signficantly with an addition of constraints to templates. Furthermore, new interesting languages, such as Scala with advanced type systems are being introduced, Spec# combines a theorem prover with a mainstream language, built-in support for representing XML data is being added to several languages. The list goes on and on. For a motivated student, this class is an opportunity to get involved in this exciting research area.

Administrativia

Grading

40% of your course grade will be based on assignments and quizzes, 60% on a research project and/or exams. Participation, or more accurately, lack of it, can influence your grade you achieve otherwise from assignments and on your project or exams, negatively, up to 10%. A grade of 90% or above guarantees an A, 80% or above a B, 70% or above a C, and 60% or above a D.

This grading formula implies that there is no curve; your grade will depend only on how well you do, and not on how well everyone else does. (If everyone does exceptionally badly on some assignment, I may decide the assignment was at fault rather than the students, in which case I'll adjust the grade cutoffs as I deem appropriate. But I won't adjust in the other direction; if everyone gets an A, that's great).

All grade assignments are final—unless there was a mistake made in recording your semester grades or in computing your final grade. If all numbers are correctly recorded and computed, I will not discuss changing the resulting letter grades.

There are situations that may warrant regrading a particular assignment. For example, making addition errors in computing your score, not seeing an answer that you gave, or not understanding an answer that you gave. Requests for regrading of assignments must be made within one week after the graded work has been handed back.

Policies

Academic Integrity Policy: An Aggie does not lie, cheat, or steal or tolerate those who do. The Honor Council Rules and Procedures are available on the web http://www.tamu.edu/aggiehonor.

Americans with Disabilities Act (ADA) Policy: The Americans with Disabilities Act (ADA) is a federal anti-discrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact the Department of Student Life, Services for Students with Disabilities, in Room 126 of the Koldus Building or call 845-1637.

Topics

The primary text for the course is:

Benjamin C. Pierce: Types and Programming Languages

Not all of the book will be covered, and other material is used as well, but this book will be necessary to have.

The course aims to deepen understanding on the concepts and features of programming languages, and provide means to (formally) reason about languages and language features, to the extent to become able to appreciate current research and developments in the area of programming languages. Programming languages are a huge area. Consequently, the course tries to focus on fundamental mechanism rather than broadness. Not everything can be covered: the text focuses on static typing, type systems etc., which will comprise the main body of this course as well.

We start from the lambda calculus as the simplest model of a programming language, and gradually extend it with language features. The basics that are covered include

• Specifying semantics of programming languages
• Necessary proof techniques for programming language research
• Lambda calculus
• Specifying type systems
• Formal study of properties of type systems and languages (such as type safety)

Equipped with this basic skill set, we'll study more ambitious language constructs, such as:

• Subtyping
• Polymorphism and generics
• Constrained generics (bounded quantification)
• Recent advances/questions in programming languages/type systems

A likely class project will be an in-depth study of an interesting topic covered by the last bullet above.

Projects

Information on projects found here.

Schedule and material

Assignments

Exams

Exam is on Thursday, Mar 26th, on normal class hours. Reading for the exam:

• All slides
• All assignments
• From Pierce:
  • Section 1
  • Section 2 if you feel you need that
  • Sections 3, 5, 8
  • Subsections 9.1—9.3
  • Subsections 11.1—11.4, 11.6—11.8
  • Section 13
  • Subsections 15.1—15.6

Resources

LaTeX

LaTeX is the tool to use for type-setting math or math-related text. Packages that I have found useful include amsmath and amssymb for generally more symbols, and math commands; and mathpartir for type-setting inference rules. The former are part of standard LaTeX distributions. The latter you can find here. The file latex_example.tex is an example file that typesets a few inference rules and derivations with the mathpartir package.

Software

Programming assignments will be done in Haskell, here are a few pointers to get you started:

• The "Official" Haskell Web-site
• Haskell Prelude Reference
• A gentle introduction to Haskell Version 98
• The Haskell 98 Report
• Glasgow Haskell Compiler
• Haskell API search enginge

Material useful for specific assignments:

• Parsec parser generator

Using GHC

A few other compilers exist, but we will use the Glasgow Haskell Compiler. An easy way to interact with GHC is to edit your document, say, Foo.hs in your favourite editor (== Emacs, with haskell-mode), and invoke the GHC interpreter in a shell window:

> ghci -fglasgow-exts

The most commonly used commands are

• :l Foo to load the module Foo (from your file Foo.hs)
• :r to re-load the previously loaded module
• :i x to inspect the value, type, ... x
• :q to quit the interpreter

The compiler is invoked, for example as:

> ghci -fglasgow-exts --make

The --make option chases automatically which modules need to be recompiled, so you don't have to write a Makefile yourself. (Also GHC's analysis of what need to be recompiled is more fine grained, thus faster).

GHC and Emacs in linux.cs.tamu.edu

To set up ghc with Emacs, follow the directions below:

1. Create a .emacs file (if you don't have one)
2. Add the following to your .emacs

(load "/home/faculty/jarvi/lib/emacs/haskell-mode/haskell-site-file")

(add-hook 'haskell-mode-hook 'turn-on-haskell-ghci)
(add-hook 'haskell-mode-hook 'turn-on-font-lock)

(add-hook 'haskell-mode-hook
          (function
           (lambda ()
             (setq haskell-program-name "ghci"))))

(setq haskell-ghci-program-args '("-fglasgow-exts"))

1. Launch emacs, start editing some Haskell file, such as a1.hs.
2. C-c l launches the interpreter and loads the current file.