Module 1: Functional Programming and Immutability

In this module, we rely on a pure functional language such as Haskell, in which there is no (internal) mutable state. Haskell is a lazy language by default, and the opportunity arises to discuss different evaluation orders.

Week 2: Lists and Higher-Order Functions

List construction and deconstruction, map and fold, anonymous functions, other higher-order functions. (“A” level.)

Week 3: Algebraic Data Types

Sum and product types, parametric polymorphism; specific algebraic data types, such as natural numbers, lists (viewed in this way), and trees; units of measurement. (“A” level.)

Week 4: Algebraic Data Types (cont.)

• Algebraic data types (continued):
• sum, product, arity, recursion, type parameters
• nonrecursive, e.g. finite enumerations, option
• sublinear, e.g. natural numbers
• linear, e.g. lists
• nonlinear, e.g. trees
• separation of concerns
• data
• structure
• content
• behavior
• traversal
• processing
• examples: Bool, Option, Nat, List, Tree
• handout
• Presentation: Perl

Week 5: Recursion Patterns and Performance Considerations

Notions from category theory for systematically describing recursive patterns, fold/catamorphism, unfold/anamorphism, fold+map/paramorphism; first on lists, then generalized to trees and other algebraic data types. Tail recursion, evaluation order, lazy versus strict evaluation. Scalability. (“C” and “A” levels.)
• Project 1 discussion
• Recursion patterns
• example: prime numbers handout

Week 6: Recursion Patterns and Performance Considerations (cont.)

• Recursion patterns
• map, filter
• fold/catamorphism: length, filter, map as fold
• lengthCata = foldr ((+) . (const 1)) 0
• mapCata f = foldr ((:) . f) []
• mapAccumL/R: as fold
• mapAsMapAccumR = snd . mapAccumR (\_ x -> (undefined, f x)) undefined
• cat+count as MapAccumL
• unfold/anamorphism: zip, iterate, map as unfold
• iterateAna f = unfoldr (\x -> Just(x, f x))
• mapAna f = unfoldr (\xs -> case xs of [] -> Nothing ; (x:ys) -> Just(f x, ys))
• paramorphism: tails, dropWhile
• hylomorphism: cata o ana
• foldr versus foldl
• examples: Nat (including factorial), BTree, ATree
• Presentation: Erlang
• Test 1: take-home

Week 7: Recursion Patterns and Performance Considerations (cont.)

• Test 1 discussion
• Discussion of tree examples, trees in Haskell, and uniform operations on structured types

Module 2: Programming Language Implementation and Tools

Starting with this module, we switch to F#, a hybrid functional language with mutable state. F# includes fslex and fsyacc, robust tools for lexical and syntax analysis.

Week 8: Overview

• Project 1b discussion
• Representing programs, abstract syntax trees as algebraic data types, evaluating expressions, interpreting simple imperative and functional programs. (“A” level.)
• Compilation toolchain phases overview
• source code (string stored in file)
• lexical analysis
• sequence of tokens
• parsing
• abstract syntax tree
• optimization
• transformed abstract syntax tree
• code generation
• machine code or byte code
• alternative: direct interpretation of abstract syntax trees
• Expressions examplesJava and Scala
• Presentation: Objective-C
• Presentation: Go

Week 9: Interpreters, Lexical and Syntax Analysis

• Project 1b discussion
• Tokens, scanning, regular expressions, scanner generators, fslex; parsing, grammars and productions, parser generators, fsyacc. (“C” and “A” levels.)
• Regular languages
• example: valid identifiers in Java
• Context-free languages
• example: infix arithmetic expressions
• fslex/fsyacc example
• Presentation: Python
• Presentation: Ruby

Week 12: Interpreters (cont.)

• Project 1b catamorphism recap
• Project 2a discussion/Q&A
• Code generation
• Concepts, .NET CodeDom, Dynamic Language Runtime. (“C” and “A” levels.)

Module 3: Concurrent and Parallel Programming

In this module, we study established concurrent and parallel programming paradigms in the context of F#, which makes the entire .NET runtime library available to us. Then, we explore several emerging concurrent and parallel programming paradigms in the context of F#.

Week 13: Shared Memory and Threads, Synchronization and Confinement

• Test 2 discussion
• Project 2a discussion
• Concurrency
• Mutual exclusion, locking, liveness versus safety, starvation and deadlock, fairness, thread-local storage. (“A” level.)
• independent activities versus communicating activities
• thread synchronization primitives in .NET
• Presentation: C++
• Presentation: PHP

• The actor model, the “share nothing” approach, communication among actors, actors in F#; importance of user-mode threading libraries. (“A” level.)  Software-Transactional Memory: Optimistic concurrency, cost of copying, probability of retry, advantages for sparsely modified data structures. (“C” level.) Functional Data Structures: Functional implementations of familiar data structures, evaluation order considerations, amortization. (“C” level.)
• .NET parallel extensions including Parallel-LINQ (PLINQ) and the Task Parallel Library. (“A” level.) Discussion of MPI and OpenMP (“K” level.)
• Example: matrix multiplication in F# using different paradigms
• Presentation: CoffeeScript
• Test 3: take-home