CS4400 Programming Languages

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

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

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

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.¹ 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.,

• Visual Studio Code – based on my limited experience with it, VSCode has/had decent Haskell support and it seems fun to use,
• IntelliJ IDEA with the IntelliJ-Haskell plugin, or
• Atom with the ide-haskell plugin and other plugins (such as ide-haskell-repl).

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.

• Haskell:
  • Programming in Haskell by Graham Hutton
  • Get Programming with Haskell by Will Kurt seems pretty good
  • Haskell Programming from first principles by Christopher Allen and Julie Moronuki is new and seems interesting
  • Learn You a Haskell for Great Good! by Miran Lipovaca (available online) – I liked this one when I read it, but it is somewhat problematic, so watch out.
• Programming lanugages:
  • [EOPL] Essentials of Programming Languages by Daniel P. Friedman and Mitchell Wand (some editions with Christopher T. Haynes) – closest to what we will be doing, but with examples written in Scheme
  • [TAPL] Types and Programming Languages by Benjamin C. Pierce – THE textbook on types and type systems. It has a good chapter on Lambda Calculus and other chapters will be relevant when we look at type systems.
  • Programming Languages: Application and Interpretation by Shriram Krishnamurthi (available online)

Other

I will keep extending this list.

• Try Haskell! – a nice online tutorial to get you started with Haskell
• What I Wish I Knew When Learning Haskell – excellent comprehensive resource about various topics pertaining to Haskell and functional programming
• Hackage: The Haskell Package Repository
• Eli’s version of this course – Eli Barzilay’s excellent version of CS4400 and a source of inspiration for the topics in this version

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:

• 60% assignments
• 35% other (in-class quizzes)
• 5% karma

The mapping of percentages to letter grades is as follows:

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.