Lecturer: 穆信成 Shin-Cheng Mu

Bird-Meertens style functional program derivation.

• Handouts.
• Slides.
• Assignment #1, with solutions to in-class exercises, and full solutions.
• Assignment #2, with solutions to in-class exercises, and full solutions.
• Exercise for Day 3.
• Supplementary Haskell code.

Functional programming.

• Prelude: Maximum Segment Sum
• Preliminaries
  • Functions
  • Data Structures
• The Expand/Reduce Transformation
  • Example: Sum of Squares
  • Proving Properties by Induction
  • Accumulating parameters
  • Tupling

• Folds
  • The Fold-Fusion Theorem
  • More Useful Functions as Folds
  • Finally, Solving Maximum Segment Sum!
  • Folds on Trees
• Unfolds
  • Unfold on Lists
  • Folds v.s. Unfolds
• Hylomorphism
  • A Museum of Sorting Algorithms
  • Hylomorphism and Recursion
• Wrapping Up

• The Guarded Command Language
  • Assignments and Selection
  • Repetition
• Procedural Program Derivation
  • Taking Conjuncts as Invariants
  • Replacing Constants by Variables
  • Strengthening the Invariant
  • Tail Invariants
• Maximum Segment Sum, Procedually
• Wrapping Up

Grading: Class Participation 10%, Homework 40%, Final (2008/07/11) 50%.

Some suggested reading:

• R. S. Bird, Introduction to Functional Programming using Haskell.
• R. S. Bird and O. de Moor, Algebra of Programming. Only the functional part.
• Some papers from H. Zantema on list segment problems.
• A. Kaldewaij, Programming: the Derivation of Algorithms.
• E. W. Dijkstra, A Discipline of Programming, for more interesting examples and exercises.