Program Design by Calculation

Objectives

  1. Principle of compositionality: learning how to write complex programs by simpler program composition.
  2. Constructive programming: learn how to write functional programs using algebraic combinators.
  3. Program transformation: using the algebra of programming to increase efficiency without sacrificing correction.
  4. Programming architecture: program analysis, comprehension and cataloging: use of algorithmic factorization (hylomorphisms) as a way to understand the architecture of the algorithms and their taxonomy.
  5. Program synthesis: calculation of for-loops from inductive mathematical definitions.
  6. Advanced functional programming: build and reason about functional programs with effects in the form of monads

Program

1.Motivation. Theory and method in programming.Calculation and reasoning about programs.Compositionality.Program combinators.Modularity and reuse.Programming «packages» 2.Functional programming:its motivation and historical background.Composition of functions.Notions of abstraction and isomorphism.Initiation to data structuring.Basic combinators and their structural properties (reflection, fusion, absorption, cancellation and functionality) 3.Algebra of a data type. Exchange law. Introduction to regular inductive data structures. Functor algebras. The cata- ana-hilo triology 4.Polynomial recursion. Case study: sorting algorithms. Parameterization and polymorphism. Inference of polymorphic types 5.Generic programming. Type functors. Introduction to polytypism 6.Functional programming with effects. Monads and their theory. Construction of monadic programs. Examples: error handling, list processing, probabilistic computations, and state computations. Reference to the ‘input / output’ monad

Bibliography

J.N. Oliveira. Program Design by Calculation, 2008 (Chapters 2, 3 and 4). Draft of textbook in preparation, current version: October 2019. Available from http://www4.di.uminho.pt/~jno/ps/pdbc.pdf. Informatics Department, University of Minho. A. Cunha. Cálculo de Programas: notas teórico-práticas. Departamento de Informática, Universidade do Minho, 2005. R. Bird and O. de Moor. Algebra of Programming. Series in Computer Science. Prentice-Hall International, 1997. C. A. R. Hoare, series editor. BGUM 510.5-B

Updated: