Functional Programming Techniques

This is the home page for the "Functional Programming Techniques" course. Here, you will find (in a badly-organised form) all the material, slides, and information needed to attend the course

Lessons:

This is a tentative schedule for the course:

• First lesson: 2020/10/14, 9:30 -> 12:00 This lesson has been cancelled and the course starts on 2020/10/21
• First lesson: 2020/10/21, 9:30 -> 12:00
  • Introduction to the course
  • Some examples about the functional programming paradigm: GCD and towers of Hanoi
• Second lesson: 2020/10/28, 9:30 -> 12:00 (first and second part of the lesson, in italian)
  • First Functional Programming Technique: recursion
  • More details about functional programming techniques: computation as evaluation, ...
• Third lesson: 2020/11/04, 9:30 -> 12:00 (video of the lesson, in italian)
  • More about reduction, evaluation, and related stuff
  • Introduction to currying
  • Some more details on functions and their invocation
• Fourth lesson: 2020/11/11, 9:30 -> 12:00 (first and second part of the lesson, in italian)
  • Introduction to the lambda calculus
• Fifth lesson: 2020/11/18, 9:30 -> 12:00 (video of the lesson, in italian)
  • Lambda calculus, again (typed lambda calculus and combinator calculi)
  • Introduction to Haskell
• Sixth lesson: 2020/11/25, 9:30 -> 12:00 (video of the lesson, in italian)
  • Something more about Haskell
  • Introduction to Algebraic Data Types and Recursive Data Types
• Seventh lesson: 2020/12/02, 9:30 -> 12:00 (first and second part of the lesson, in italian)
  • Advanced use of Haskell data types (parametric data types, ...)
  • Using parametric recursive data types to implement Y!
  • Using parametric data types to encode I/O actions
• Eighth lesson: 2020/12/09, 9:30 -> 12:00 (first and second part of the lesson, in italian)
  • The Haskell I/O Monad
  • Writing complete Haskell programs
  • Example about monads in C++

Documents:

• Introduction to functional programming (in italian!)
• Programming language support for functional programming (in italian!)
• Some basic definitions useful for understanding functional programming concepts (in italian!)
• A short introduction to lambda calculus (in italian!)
• Few notes about Haskell (in italian!)
• Introduction to recursive data types (in italian!)
• More on the fixed point combinators and Y (in italian!)

Examples:

• Example on the GCD:
  • GCD algorithm inplemented iteratively using the euclidean algorithm
  • GCD function inplemented recursively
  • GCD function inplemented according to the functional programming paradigm
  To test this code you will need a main program and a header file describing the software interface of the function
• Example on the towers of Hanoi:
  • simple solution
  • more complex solution, with a more interesting output
  • functional-style solution, in C++. The C version is much less readable, and clearly shows the possible issues with memory leaks.
• Example on closures: a counter implemented without classes (in C++)
• Example on passing multiple arguments without currying
• Examples on currying:
  • Bad currying in C: this example just shows that it is not possible to implement currying in C, because the C language has function pointers, but does not have closures!
  • Currying in C++, using a lambda function (that actually is a closure, not a "simple" function!)
  • Approximating the value of the derivative of a function
  • Approximating the derivative of a function. This example needs a high-order function, returning a function. Notice that this is the curried form of the previous example... Maybe the relationship with the previous example is more visible in this version or this version of the program
• Examples on parameters passing: issues with call-by-value in C++ and a possible workaround
• Haskell examples:
  • Haskell implementation(s) of the greatest common divisor algorithm
  • Haskell implementation(s) of the tail recursive factorial
  • Some possible Haskell implementations of the "Towers of Hanoi" solver: with "move 0 disks" as a recursion base (using definition by cases) and with "move 1 disk" as a recursion base (using definition by cases)
  • Modelling lambda expressions as recursive data types
• Examples about Recursive Data Types:
  • Natural numbers encoded according to Peano, in C++ and in Haskell (without sum and complete)
  • Immutable lists in Haskell: basic data structures and operations; insertion, print and other helpers
  • Immutable lists in C: basic data structures and operations (interface), insertion and print (interface) and test program
    • As a reference, here is the traditional mutable list implementation
  • Generic immutable lists in Haskell: basic data structures and operations
• Implementing the Y combinator in Haskell: simple implementation, that has some issues with some versions of ghci when typing the definition on the REPL, and more advanced version, which works correctly even with the ghci REPL. Notice that the first version is correct, and should theoretically work... It probably triggers a ghci bug.
• Examples of complete Haskell programs (with I/O): gcd with the bind operator and in do notation
• Source files for the example about monads in C++ showed during the last lesson

Ideas about Possible Projects for the Exam

Some projects are simpler than others; if you decide to work on a project, please contact me first. Do not be afraid of asking questions.

• Implement beta reduction for lambda expressions in Haskell. Based on a representation of lambda expressions in Haskell, write a function that reduces an expression to a normal form (if possible) using the reduction order you prefer. Then, write a program using this function.
• Write an Haskell program to convert lambda expressions to SK calculus.
• Investigate the usage of functional programming in real-time systems and write a report about this (useful starting points: a paper about this topic, the Erlang programming language and an example about using functional programming techniques to perform schedulability analysis)
• Describe the implementation of the Y combinator in your favourite programming language
• Write (and discuss) some example about monads in C++

Links:

Here is the home of the ghc compiler (also provides the ghci interactive REPL).

For students interested in embedded/real-time systems: the Secure L4 microkernel uses a Haskell model of the microkernel to prove its correctness (and perform formal analysis on the microkernel).