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

For the previous edition of the course, check the old website: year 2020/2021.

Lessons:

This the current schedule for the course:

• First lesson: 2022/11/02, White room, 9:00 -> 11:00
  • Introduction to the course
  • Some examples about the functional programming paradigm:
    • The GCD, implemented iteratively using the euclidean algorithm, or recursively
    • The towers of Hanoi
• Second lesson: 2022/11/09, Yellow room, 9:00 -> 11:00
  • Towers of Hanoi, again: a purely functional solution, in C++ and then in C
    • Something more about functional programming in C and C++
  • Looking at the essence of the functional programming paradigm
• Third lesson: 2022/11/16, PC room, 9:00 -> 11:00
  • Functional programming technique: recursion
    • Something about recursion and stack usage
  • Functional programming technique: currying
• Fourth lesson: 2022/11/23, PC room, 9:00 -> 11:00
  • Something more on functions and their invocation
  • Functional programming technique: closures
• Fifth lesson: 2022/11/30, White room, 9:00 -> 11:00
  • Introduction to the lambda calculus
• Sixth lesson: 2022/12/07, White room, 9:00 -> 11:00
  • Lambda calculus and recursion: fixed point combinators
  • Combinatory calculi
  • Typed lambda calculus
  • Experiments with the lambda calculus; using lambda calculus as a programming language
• Seventh lesson: 2022/12/16, White room, 10:00 -> 12:00
  • Some examples with Haskell
  • Advanced data types in Haskell
• Eighth lesson: 2022/12/21, White room, 9:00 -> 11:00
  • Recursive data types
  • Recursive types in Haskell
  • Lists as recursive data types; Haskell lists; immutable lists vs "traditional" lists
  • Type of the Y combinator in Haskell
• Nineth lesson: 2023/01/11, 9:00 -> 11:00
  • The Y combinator in Haskell, again
  • Introduction to Haskell's monadic side effects
• Eighth lesson: 2023/01/18, 9:00 -> 11:00

Documents:

• Some basic definitions useful for understanding functional programming concepts (in italian or in english)
• Short introduction to functional programming (in italian or in english)
• A small and incomplete introduction to lambda calculus (in italian or in english)
• A small and incomplete introduction to Haskell (in italian or in english)
• Introduction to recursive data types (in italian or in english)
• More on the fixed point combinators and Y (italian version)

Examples:

• A gcd() function implementing the Greatest Common Divisor (o test this code you will need a main program and a header file describing the software interface of the function)
  • Euclidean algorithm inplemented iteratively
  • GCD function inplemented recursively
  • GCD function inplemented according to the functional programming paradigm
• A program solving the problem of 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 (try compiling with "-fanalyzer=address).
• Diverging computation in C. Try compiling with -O0 and with -O2
• Example of lambda expressions (expressions evaluating to a function) in C++.
• Simple examples on currying in C++:
  • Example on passing 2 arguments through a pair
  • Curryified version of such a function
  • 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!
• A more "interesting" example on (maybe) currying:
  • Function computing the derivative of a mathematical function in a point x
  • Function generating the derivative of a mathematical function
  • See the relationship between the compute_derivative() function and the derivative() function? Maybe this version of the code can help in understanding...
• Endless loop because of parameters passing by value in C++
• Same example emulating parameters passing by name through closures as parameters
• 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
  • Generic immutable lists in Haskell: basic data structures and operations
• Examples about lists in other languages:
  • 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
• Example of complete Haskell program: without do notation and with do notation

• 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:

• Example of lambda calculus reducer (there are many others around... Try searching on google). It also provides some useful extensions, such as a global environment; try:

  2 = \f.\x.f (f x)

  3 = \f.\x.f (f (f x))

  add = \m.\n.\f.\x.(n f)((m f) x)

  add 2 3

  or simply try

  (\m.\n.\f.\x.(n f)((m f) x)) (\f.\x.f (f (f x))) (\f.\x.f (f x))

• Some examples about using the lambda calculus as a general-purpose language:
  • A virtual CPU implemented with lambda calculus (this shows the expressive power of the lambda calculus)
  • Lambda calculus can even be used to implement a C compiler!
  • Some tools for programming with lambda calculus
• A very small lambda calculus interpreter (based on a binary encoding of the lambda calculus)
• Something more about lambda calculus and combinatory calculi (including some simple interpreters/reducers)
• Interpreter for a language based on the lambda calculus
• Home of the Glasgow Haskell Compiler