CS4400 Programming Languages

Fall 2020

Parts of this syllabus are subject to change as the semester progresses.

Time and Place

We meet on Tuesdays and Fridays, 9:50-11:30am in Mugar 201 and on Zoom. Zoom links for each lecture are available on Canvas. The first class is on Friday, 9/11.

People

Role Name Email Office hours Location
Instructor Ferdinand Vesely f.vesely@northeastern Tue/Thu 3-4:30pm Zoom/Teams
TAs Jack Gelinas gelinas.j@northeastern Wed, 1:45-4:30pm Zoom
Divya Venkatesh payyadivenkatesh.d@northeastern Mon/Thu 12:30-2pm Zoom

Note: We use waiting rooms in Zoom to deal with queues.

Course Description

The overarching idea of (this version of) this course is to study constructs and fundamental concepts of programming languages, while getting familiar and exploring topics in functional programming using the language Haskell. We will be discussing concepts both formally and informally, as well as implement interpreters and other language-related tools in Haskell. These implementations will motivate exploring various approaches, idioms and concepts in functional programming.

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.

Prerequisities

The formal prerequisites of CS4400 are CS3000 (or CS4800) and CS3500. 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. Some basics of logic or discrete math might come in handy too.

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. This list currently concentrates on aspects of programming languages, but topics covered will include useful functional programming concepts supported by Haskell.

  1. Intro to Programming Languages. Haskell basics

  2. Abstract syntax. BNF. Parsing

  3. Basic interpreters. Arithmetic

  4. Names and bindings. Substitution

  5. Environments. Basic procedures and functions

  6. Functions as values. Lambda calculus. Reduction

  7. Recursion. Fixpoint combinators. The Y combinator

  8. Strict vs. lazy evaluation. Call by name, call by value, call by need

  9. Imperative programming. Assignment. Stores. Loops

  10. Types & type systems. Simply-Typed Lambda Calculus

  11. Polymorphism. Type inference

  12. Classes and objects. Dynamic dispatch

  13. Continuations. Exceptions. Coroutines

  14. Non-determinism. Logic programming

  15. Reasoning about programs

  16. Concurrency. Process algebras. Bisimulation

  17. Advanced type systems. Dependent types. Curry-Howard correspondence

Schedule

Date Topic Materials
09/11 Overview & Quick Intro to Haskell Slides   Lec01.hs   Wat (video)
09/15 Abstract Syntax & (Algebraic) Datatypes Notes   Lec02.hs
09/18 Intro to interpreters, evaluating SAE, polymorphic types Notes    Lec03.hs
09/22 JSON example & Haskell corner Lec04.hs   Foo.hs
09/25 Bindings, substitution, scope & Maybe Lec05.hs
09/29 Equational reasoning, maps & environments Notes   Lec06.hs
10/02 Procedural abstraction & function definitions Lec07b.hs   Maps.hs
10/06 Functions as values; Abstracting ‘case … of’ Lec08a.hs

Assignments

You can expect homework assignments to be handed out roughly every week and there will be around 10 assignments in total this semester. Some of them will be individual work, for others you will be expected to work in pairs. They will be mostly programming assignments. Tentatively, assignments will be handed out on Fridays and be due on the following Thursday. Submission will be via

Assignment Date Set Date Due
Assignment 1 9/15 9/19 PDF
Assignment 2 9/20 9/24 PDF   SimpleTests.hs
Assignment 3 9/25 10/1 PDF   Pack
Assignment 4 10/2 10/8 PDF   Pack
Assignment 5 10/9 10/15 PDF   Pack
Assignment 6 10/18 10/24 PDF   Pack

Haskell

We use Haskell both as a topic of study and for implementing our examples. Haskell is a programming language that is statically typed, purely functional, and lazy.1 I expect that a majority of you does not have 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.

Haskell in a browser. The quickest way to start using Haskell is to simply run it in your browser. There is a handful of online IDEs, for example https://repl.it/languages/haskell. Note, that when you click Run, it will throw an error at you about a variable main not being in scope. You can ignore that error for now – it still loads your definitions. If you want to avoid that error, instead of clicking Run, type :l main.hs in the interactive area and press enter. Then you can reload the same file after you edit it by typing :r.

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 (currently mostly NeoVim) and running the compiler, REPL, or other tools in a terminal. However, there are plugin-based alternatives, e.g.,

Last time I checked, the Atom option had issues due to a deprecated dependency (ghc-mod) – it complained, but seemed usable.

If you are an Emacs user, you’re out of luck… Just kidding, there is, of course a Haskell mode and a whole lot of other goodies.

There’s also spacemacs.

See also https://wiki.haskell.org/IDEs.

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

In general, there is no required reading for this course and I may provide lecture notes or annotated slides where applicable. However, there are other sources that we might use to replace or supplement those. I will draw your attention to them where appropriate.

Books

Check Northeastern’s library. A good portion of these books is available to us online. Some of these items have abbreviations – I will use these when referring to supplementary reading.

Other

I will keep extending this list.

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 on Piazza by going to https://piazza.com/northeastern/fall2020/cs4400. You will need an access code which will be provided in class or via email.

Note: The Piazza forum is meant for discussion related to the topics of this course and to exchange knowledge. While I welcome debates about the course structure, the whys and why nots, or other general topics, I reserve the right to change the visibility of posts if I think they do not contribute to the learning aims of this course. You are most welcome to talk to me about any topic directly – after class, in office hours, or in an ad-hoc/scheduled meeting.

Grades

This is a tentative breakdown of how the final grade will be determined:

The mapping of percentages to letter grades is as follows:

Cutoff

  

93%

  

90%

  

86%

  

83%

  

80%

  

76%

  

73%

  

70%

  

66%

  

63%

  

60%

  

else

Letter grade

  

A

  

A-

  

B+

  

B

  

B-

  

C+

  

C

  

C-

  

D+

  

D

  

D-

  

F

Late Policy

You are allowed to turn your work in after the deadline, with a penalty of 4% of your grade per hour. For example, submitting 10 minutes late reduces your grade by 4%, submitting 5 hours and 1 minute late reduces your grade by 24%. Submitting more than 25 hours late will result in a zero. This will be automatically determined by the Handins server. You can submit as many times as you wish. We thus recommend submitting even a partial solution well before the deadline. That way if something goes wrong, you’ll get at least partial credit (and feedback).

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.


  1. Do not despair if these words currently mean nothing to you in this context. We will make sense of them during the course.↩︎