Algebraic Techniques for Programming

Aims

The goal of this course is to teach students how to understand a variety of algorithmic techniques from the point of view of abstract algebra, lattice theory and category theory. They will be introduced to structured recursion and corecursion, fixed point computations, and an algebraic approach to graph
algorithms via modules over Kleene algebras.

Lectures

This will be a lecture course, divided into three sections of four lectures.

• Data, codata, Recursion and corecursion. Representing (co)data as initial and final algebras of polynomial functors. Understanding generalized folds and unfolds. Sorting algorithms via hylomorphisms. Implementing algorithms with linear state. [4 lectures]
• Lattices, dataflow, and incremental computation. Introduction to lattices and fixed points. Representing dataflow problems as fixed point computations. Incremental algorithms for dataflow problems. Programming with monotonic state. [4 lectures]
• Linear algebra and graph algorithms. Representing graphs as matrices. Introduction to Kleene algebra and modules over semirings. The algebraic path problem. [4 lectures]

Objectives

At the end of the course students should:

• understand the role of the three great recursion schemes in programming
• have a unified perspective on a host of algorithmic techniques
• understand how to apply algebraic techniques to algorithm design

Recommended reading

• The Algebra of Programming, Richard Bird and Oege de Moor
• Graph Algorithms in the Language of Linear Algebra, edited by J. Kepner and J. Gilbert
• Introduction to Lattices and Order, B.A. Davies and H.A. Priestly
• Principles of Program Analysis, Nielsen and Nielsen