CS 320 - Concepts of Programming Languages

Spring, 2018

Instructor and Lecture

Times and Locations


Instructor:Wayne Snyder

      Email: waysnyder at gmail dot com

      Office: MCS 290

      Office Hours for CS Advising: W 4-6 (for general CS advising)

     Office Hours for CS 320: M 4-6, 7:30 - 9pm, T 4-6pm

     
      Tutoring Hours in Rich Hall: T 7:30-10:30pm

      Cell Phone: 617-966-(210+41) (text in an emergency; in general, email vastly preferred, but if you call, leave a message!);

    


Lectures:

      A1: M, W 2:30 - 3:45pm (CAS B12)
      B1: M, W 6:00 - 7:15pm (CAS B12)

Discussion/Labs:

     A2: W 9:05 - 9:55am (KCB 102)
     A3: W 10:10 - 11:00pm (KCB 102)
     A4: W 11:15 - 12:05pm (KCB 107)
     A5: W 12:20 - 1:10pm (KCB 102)

     B2: W 11:15 - 12:05am (KCB 107)
     B3: W 12:20 - 1:10pm (CAS 204B)
     B4: W 1:25 - 2:15pm (CAS 204B)
     B5: W 2:30 - 3:20pm (CAS 220)

Teaching Fellows:

     Mark Lemay (lemay at bu dot edu)
         Office hours: Th 2 - 4pm in Ugrad Lab

     Cheng Zhang (czhang03 at bu dot edu)
         Office hours: F 2 - 4pm in Ugrad Lab

Useful Links

  • Piazza
  • Syllabus
  • YouTube Channell: YT
  • Github: HTML
  • Programming Environments for Haskell:
  • Haskell.org (Haskell download and resources): HTML
  • Hoogle (Haskell search engine): HTML
  • Book: Learn you a Haskell for Great Good: HTML
  • Book: Real World Haskell: HTML
  • Hutton's PPT Slides based on book are on this site: HTML
  • PDF Slides by Ralf Lammel based on slides by Hutton: PDF
  • Haskell Cheat Sheet (nice summary of all of Haskell): PDF
Lecture
Date
Lecture & Readings/Videos
Assignments and Practice Problems
1 W 1/23

Administrative matters; Overall Plan for the course; Motivation: Why learn functional Programming?

Lecture Slides: PDF

Here is my channel where I will post lecture videos: YT

2 M 1/28

Bare-Bones Haskell: Constructing data expressions, functions on data expressions, expressions as trees, rewrite semantics;

Reading: Hutton Chapters 1 & 2; also you could look at section 8.2 on data declarations (just for the basic idea; ignore anything you don't understand).

Lecture Slides: PDF

Also, make sure you remember recursive tree traversals, particularly preorder and postorder; here is my CS 112 lecture on this: PDF

Here is a video talk-through of the last couple of slides from Lecture 2, which I did not finish in section A1: HTML

Practice Problems on data and function definitions and computation by matching and rewriting: HTML
3 W 1/30

Function definition by pattern matching; polymorphic types.

Reading: Hutton, Ch. 3.1 - 3.7

Lecture Slides: PDF

 

HW01 Solution: PDF

Video walkthrough of HW 1 analytical part (with hints!):HTML

4 M 2/4

Polymorphic data and functions; type checking; function definitions; modules

Reading: Hutton, Ch. 3.8 - end, 4.1 - 4.4

Lecture Notes: PDF

Practice Problems 2 A Alternate (using build-in syntax for Integers, tuples, and lists) HTML

Practice Problems 2 B Alternate (using build-in syntax for Integers, tuples, and lists) HTML

5 W 2/6

Functions as first-class values; map and filter;lambda expressions; functions manipulating functions; modules.

Reading: Hutton, Finish chapter 4. On modules, read HTML up to right before the section on Data.List.

Lecture Notes: PDF

 

Solution for HW 2, analytical part: PDF

Typo fix in problem One a4 uploaded 2/10 11am.

Here is a short video with some hints: HTML

6 M 2/11 Basic Haskell: Haskell built-in list and tuple types; Case expressions; Beta-reduction for lambda expressions and let expressions; HO programming continued: Curried functions; (if time) Function composition with currying.

Reading: Hutton Ch. 4 & 7

Lecture Slides: PDF

Practice Problems 3: HTML
7 W 2/13

Curried functions, HO programming paradigms concluded: foldr; Type classes.

Reading: Hutton 5 & 15.1-15.5

Lecture Slides: PDF

HW 3 out, due 2/19
M 2/18 President's Day: Holiday  
8 T 2/19 Virtual Monday!

Type classes Continued.

Reading: Hutton, reread Ch. 3 and then read 8.1 - 8.5, and also section 12.1 (on Functors)

This section from "Learn you a ...." is also worth reading on the basic type classes: HTML

Also the beginning of this section, about the Functor type class, is very good: HTML

The first part of this, Functors with Pictures, is very good: HTML

Lecture Slides: PDF

 

9 W 2/20 Type classes concluded.

Reading: Same as last time. Reread it!

Lecture Slides: PDF

HW 4 Solution: PDF, due 2/25

M 2/25

Review for Midterm

Reading: Hutton, Ch.8.

Midterm Study Guide: HTML
W 2/27 Midterm 1

Midterm A: PDF

Midterm B: PDF

Midterm C: PDF

Midterm D: PDF

 
10 M 3/4

Monads: the Maybe Monad

Lecture Slides: PDF

MonadLectureCode1: HS

MonadLectureCode2: HS

Video walk throughs of these two files have been uploaded to the YT channel linked at the top of this page, as well as a brief summary of my lecture.

Required Readings:

  1. Functors and Monads (ignore anything about Applicatives) in pictures:HTML
  2. Hutton, Ch. 12.3 (pp.164 - 166);
  3. Learn you a Haskell, A Fistful of Monads, ignore anything about "Applicatives" and you can skip the long example in the section "Walk the Line";

Optional readings (if you are interested):

  1. Dan Piponi's blog post "You could have invented monads": HTML
  2. Dan Piponi's blog post on the Trivial Monad: HTML
  3. Phillip Wadler's paper on monads: PDF
  4. Hutton's paper on monadic parsing in Haskell: PDF
  5. This is one of the better tutorials, very detailed, emphasizing the syntax: HTML
  6. A short blog post on the Monad Laws: HTML; here is a short but essential article on the monad laws, relating it to do expressions: HTML

Here are some videos on monads:

  • Hutton on monads: HTML
  • Our own instructor Abbas Attarwala on monads: HTML
  • Brian Beckman at Microsoft on monads: HTML

Even more optionally, here are some informative links about monads:

  • The Monad Tutorial Fallacy: HTML
  • The Monad Tutorials Timeline: HTML

11 W 3/6

Monads continued; the Ok Monad; the List Monad; List Comprehensions

Lecture Slides: PDF

MonadLectureCode3: HS

Video walk throughs of this file, and a two-part summary of my lecture have been uploaded to the YT channel.

HW 6, Analytical Part Solution (goes with week 7 code assignment): PDF

Video with hints on the homework has been uploaded to YT channel.

Examples and easy test cases for coding assignment: HS

3/11 - 3/15 Spring Break!
Response to Survey: PDF
12 M 3/18 The State Monad

Lecture Slides: PDF

13 W 3/20

Implementing a functional language: Syntax, Context-Free Grammars, Parse Trees, Derivations; Parsing and Abstract Syntax Trees.

Lecture Slides: PDF

Reading on Context-Free Grammars: PDF

Another reading: HTML

Complete BNF for Haskell (see section 9.5): HTML

Solution to Analytical HW for Week 8: PDF
14 M 3/25

Parsing and Grammars

Example code from lecture: HS

Lambda Calculus 1

Reading: Introduction to the Lambda Calculus: PDF

 
15 W 3/27

Lambda Calculus 2: Confluence and Evaluation order

Haskell: Lazy evaluation and infinite data structures

Lecture Notes: PDF

Reading: Hutton, 12.1 - 12.5

Examples/Easy Test Cases for Lambda Parser: HS

Examples/Easy Test Cases for Lambda Calculus Implementation: HS

16 M 4/1

Infinite Lists; Lazy evaluation in Haskell concluded.

Reading: Finish chapter 15 in Hutton, then read this more precise exposition: HTML

Lecture Notes: PDF

17 W 4/3

Conclusions on lazy evaluation in Haskell; foldl vs foldl'
Dynamic vs lexical scope for lambda expressions.

Read section 7.4 in Hutton on foldl.

Here is a rather complete introduction to lazy vs strict evaluation: HTML

Reading on scope (from stack overflow, with nice code examples): HTML

Lecture Notes: PDF

Solution to last analytical hw: PDF

Easy test cases for parser for last coding homework: HS
18 M 4/8 Implementing imperative features: assignments, loops, and mutable state.  
19 W 4/10 Review for Midterm 2; Discussion of final project.

Midterm 2 Study Guide and Practice Problems HTML

Semester Project Writeup in on gitHub!

M 4/15 Tax Day: Holiday!
W 4/17 Midterm 2
20 M 4/22 Comments on the Project: general overview and static type checking

Lecture Slides: PDF

 
21 W 4/24 Comments on Project: Testing
22 M 4/29 Advanced topics: Dependent Types  
22 W 5/1 Conclusions and course evaluations.  
F 5/3 Final Project Due