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.
List construction and deconstruction, map and fold, anonymous functions, other higher-order functions. (“A” level.)
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.)
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.)
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.
Representing programs, abstract syntax trees as algebraic data types, evaluating expressions, interpreting simple imperative and functional programs. (“A” level.)
Tokens, scanning, regular expressions, scanner generators, fslex; parsing, grammars and productions, parser generators, fsyacc. (“C” and “A” levels.)
Concepts, .NET CodeDom, Dynamic Language Runtime. (“C” and “A” levels.)
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#.
Runnable tasks, worker threads, thread creation and cancellation. (“A” level.)
Mutual exclusion, locking, liveness versus safety, deadlock, fairness, thread-local storage. (“A” level.)
.NET parallel extensions including Parallel-LINQ (PLINQ) and the Task Parallel Library. (“A” level.) Discussion of MPI and OpenMP (“K” level.)
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.)
In this last module, we discuss two other important paradigms, logic programming and scripting.
Rules, queries, backtracking, Prolog. (“A” level.)