Module 1: Functional Programming and ImmutabilityIn 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 FunctionsList construction and deconstruction, map and fold, anonymous functions, other higher-order functions. (“A” level.) Week 3: Algebraic Data TypesSum 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
- examples: Bool, Option, Nat, List, Tree
- handout
- Presentation: Perl
Week 5: Recursion Patterns and Performance ConsiderationsNotions 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 MarchModule 2: Programming Language Implementation and ToolsStarting 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.)- Examples: Java and Scala
- F# development
- Parsing
- Code generation
- Concepts, .NET CodeDom, Dynamic Language Runtime. (“C” and “A” levels.)
- Test 2: take-home
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 ProgrammingIn 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.)
- 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 ParadigmsIn this last module, we discuss two other important paradigms, logic programming and scripting. Finals Week: Logic Programming and ScriptingOrganizational 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.) |