Weekly Schedule (Target)

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
    • 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

Module 2: Programming 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 6: Abstract Syntax Trees and Interpreters

Representing programs, abstract syntax trees as algebraic data types, evaluating expressions, interpreting simple imperative and functional programs. (“A” level.)
  • Test 1 discussion
  • Discussion of tree examples, trees in Haskell, and uniform operations on structured types
  • Presentation: C++
  • Presentation: Objective-C

Week 7: Lexical and Syntax Analysis

Tokens, scanning, regular expressions, scanner generators, fslex; parsing, grammars and productions, parser generators, fsyacc. (“C” and “A” levels.)

    Week 8: Code Generation

    Concepts, .NET CodeDom, Dynamic Language Runtime. (“C” and “A” levels.)
    • Presentation: Python
    • Presentation: Go

    Week 9: Putting Everything Together

    • Presentation: Ruby

    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 10: Shared Memory and Threads

    Runnable tasks, worker threads, thread creation and cancellation. (“A” level.) 
    • Test 2

    Week 11: Synchronization and Confinement

    Mutual exclusion, locking, liveness versus safety, deadlock, fairness, thread-local storage. (“A” level.)
    • Presentation: Clojure

    Week 12: Task Parallelism versus Data Parallelism

    .NET parallel extensions including Parallel-LINQ (PLINQ) and the Task Parallel Library. (“A” level.) Discussion of MPI and OpenMP (“K” level.)
    • Presentation: Fantom

    Week 13: Actors and Emerging Paradigms

    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.)
    • Presentation: PHP

    Module 4: Other Programming Paradigms

    In this last module, we discuss two other important paradigms, logic programming and scripting.

    Week 14: Logic Programming and Scripting

    Rules, queries, backtracking, Prolog. (“A” level.)

    The use and limitations of scripting languages, tradeoff between performance and productivity, JavaScript, the efficient V8 JavaScript engine. (“C” and “A” levels.)
    • Presentation: CoffeeScript