CS 4400/5400 Programming Languages

Time and Place

We meet on Tuesdays, 6-9:15pm in Hurtig Hall 129. The first class is on Tue 9/10.

People

Course Description

In CS 4400/5400, we will study concepts underlying programming language constructs, their design and their meaning. We will do this by specifying and implementing small example languages in the functional programming language Haskell, as well as looking at examples from real programming languages.

Registrar’s description for 4400: Introduces a systematic approach to understanding the behavior of programming languages. Covers interpreters; static and dynamic scope; environments; binding and assignment; functions and recursion; parameter-passing and method dispatch; objects, classes, inheritance, and polymorphism; type rules and type checking; and concurrency.

Registrar’s description for 5400: Studies the basic components of programming languages, specification of syntax and semantics, and description and implementation of programming language features. Discusses examples from a variety of languages.

Prerequisities

The formal prerequisites of CS4400 are CS3000 (or CS4800) and CS3500. For CS5400 it is CS5010. Knowing at least basics of functional programming will make your life easier, but is not required as we will cover the necessary essentials. You might also find it helpful to brush up on material from CS2500.

Topics

This is a rough and tentative list of topics that we will aim to cover this semester. It will be adapted into a schedule once the course gets started and as it progresses. I strongly recommend to check the online version of this syllabus frequently to get a better idea what are the next steps in this course.

1. Introduction to Programming Languages. Introducing Haskell
2. Abstract syntax. BNF. Basic interpreters. Big- vs. small-step
3. Names. Binding. Scope.
4. Lambda calculus. Substitution. Reduction
5. Functions. Environments. Closures. De Bruijn indices
6. Recursion. Fixpoint combinators. The Y combinator
7. Functions as values. Higher-order functions
8. Strict vs. lazy evaluation. Call by name, call by value, call by need
9. Assignment. Stores. Loops
10. Wear formal today: “Pen and paper semantics”. Operational. Denotational. Inductive definitions
11. Types & type systems. Type safety. Type inference
12. Data Types. Product. Sum. Pattern Matching
13. Monads. Monadic programming. Type classes
14. Classes and objects. Dynamic dispatch
15. Continuations. Exceptions. Coroutines
16. Concurrency. Process algebras. Bisimulation
17. Logic programming
18. Advanced type systems. Dependent types. Curry-Howard correspondence

Schedule

Assignments

Haskell

We use Haskell as a language for implementing our example interpreters. Haskell is a programming language that is statically typed, purely functional, and lazy.¹ I will assume that a majority of you does not have a previous experience with it. Thus, this course will contain an introduction to programming in Haskell and you can expect to pick up some techniques specific to functional programming along the way. Apart from being an implementation language for our interpreters, Haskell is an interesting language to study, so we will use it to exemplify some languages features.

The main implementation of Haskell is GHC: the Glasgow Haskell Compiler. It comes with a compiler, ghc, as well as an interactive REPL, ghci.

Installation. There are several ways to install Haskell. Generally, the easiest way across major operating systems is to install the Haskell Platform. Its website contains installation instructions for Windows, macOS, and various Linux distributions.

IDEs. My personal preference is to use a combination of Vim (or another text editor) and running the compiler or REPL in a terminal. However, there are plugin-based alternatives, e.g.,

• IntelliJ IDEA with the IntelliJ-Haskell plugin, or
• Atom with the ide-haskell plugin and other plugins (such as ide-haskell-repl).

The Atom option has currently some issues due to a deprecated dependency (ghc-mod) – it will complain, but seems usable. Of course, there is also a Haskell mode for Emacs users.

Examples. To give you a quick taste of what programming in Haskell looks like, here are a few basic versions of factorial:

-- This is a one-line comment

{- This is
   a comment
   spread across
   multiple lines -}

-- Variant 1: pattern matching
-- type signatures are (mostly) optional in Haskell, but not in this course :)
fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n - 1)

-- Variant 2: conditional
fact' :: Int -> Int
fact' n = if n <= 1 then 1 else n * fact' (n - 1)

-- Variant 3: guards
fact'' :: Int -> Int
fact'' n | n <= 1    = 1
         | otherwise = n * fact'' (n - 1)

Here is a simple “Hello World”:

main :: IO () -- think of IO () as a type of computations with side-effects
main = do
  putStrLn "Hello World!"

And here is an interactive “Hello World”:

main :: IO ()
main = do -- do-blocks allow us to perform sequential computations
  putStrLn "What is your name?"
  name <- getLine
  let message = "Hello, "
  putStrLn (message ++ name)

Resources

• no required reading
• will provide lecture notes / annotated slides
• (potentially) useful books:
  • Haskell:
    • Learn You a Haskell for Great Good! by Miran Lipovaca (available online)
    • Programming in Haskell by Graham Hutton
  • Essentials of Programming Languages by Daniel P. Friedman and Mitchell Wand – closest to what we will be doing, but with examples in Scheme
  • Types and Programming Languages by Benjamin C. Pierce – oriented towards type systems
  • Programming Languages: Application and Interpretation by Shriram Krishnamurthi (available online)

Forum

The primary forum for this class is on Piazza, which you can use to ask questions and exchange wisdom while completing assignments. I will also use Piazza to broadcast announcements to the class, so you will be expected to check it at least every few days. Participate actively and use it as a first place to post questions related to assignments, programming, debugging, exams, etc. Please use the forum to post questions and answers that may be useful to others. Bottom line: unless you have a private problem, post to Piazza before writing me/the TA an email.

Please register for Piazza by going to http://piazza.com/northeastern/fall2019/cs44005400 and registering as a student.

Exams

There will be one midterm and one final. All exams will be closed book and closed notes, and computers are not allowed nor is any access to the Internet via any device. The exams will cover material from lectures, readings, and the projects.

Grades

The final grade is determined as follows:

• 60% assignments (12% per assignment)
• 15% midterm
• 20% final
• 5% participation

The mapping of percentages to letter grades is as follows:

Late Policy

For the homework assignments, we will use flexible slip dates. Each student is given an automatic extension of 4 calendar days for the semester. You can use the extension on any assignment during the semester in increments of a day². For instance, you can hand in one assignment 4 days late, or one assignment 2 days late and two assignments 1 day late. This should let you schedule due dates around the due dates for other courses. After you have used up your slip time, any assignment handed in late will be marked off 20% per day. Assignments more than 2 days late (beyond the use of slip days) will not be accepted. Extensions will not be granted.

Cheating Policy

It’s ok to ask your peers about the concepts, algorithms, or approaches needed to do the assignments. We encourage you to do so; both giving and taking advice will help you to learn. However, what you turn in must be your own, or for projects, your group’s own work. Looking at or copying code or homework solutions from other people or the Web is strictly prohibited. In particular, looking at other solutions (e.g., from other groups or students who previously took the course) is a direct violation. Projects must be entirely the work of the students turning them in, i.e. you and your group members. If you have any questions about using a particular resource, ask the course staff or post a question to the class forum.

All students are subject to the Northeastern University’s Academic Integrity Policy. Per Khoury College policy, all cases of suspected plagiarism or other academic dishonesty must be referred to the Office of Student Conduct and Conflict Resolution (OSCCR). This may result is deferred suspension, suspension, or expulsion from the university.

Accommodations for Students with Disabilities

If you have a disability-related need for reasonable academic accommodations in this course and have not yet met with a Disability Specialist, please visit www.northeastern.edu/drc and follow the outlined procedure to request services. If the Disability Resource Center has formally approved you for an academic accommodation in this class, please present the instructor with your “Professor Notification Letter” at your earliest convenience, so that we can address your specific needs as early as possible.