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.

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

- Towers of Hanoi, again: a purely functional solution, in C++ and then in C
- 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

- Functional programming technique: recursion
- 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

- 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)

- 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

- Immutable lists in C:
basic data structures and operations
(interface),
insertion and print
(interface) and
test program
- Example of complete Haskell program: without do notation and with do notation

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++

- 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