Weekly Schedule (Actual)

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
    • ad-hoc recursion
    • 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

SPRING BREAK: No class on Mon 5 March

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 examples: Java 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 10: Interpreters (cont.)

    Week 11: Interpreters (cont.)

    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
    • Runnable tasks, worker threads, thread creation and cancellation. (“A” level.)
    • Mutual exclusion, locking, liveness versus safety, starvation and deadlock, fairness, thread-local storage. (“A” level.)
      • deadlock example
      • independent activities versus communicating activities
      • thread synchronization primitives in .NET
    • Presentation: C++
    • Presentation: PHP

    Week 14: Task Parallelism versus Data Parallelism, 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.)
    • .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

    Module 4: Other Programming Paradigms

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

    Finals Week: Logic Programming and Scripting

    Organizational matters
    • pair effort questionnaire
    • end-of-semester celebration
    • test Q&A
    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.)
    Comments