Duration
24h Th, 24h Pr, 20h Proj.
Number of credits
Lecturer
Language(s) of instruction
French language
Organisation and examination
Teaching in the first semester, review in January
Schedule
Units courses prerequisite and corequisite
Prerequisite or corequisite units are presented within each program
Learning unit contents
General introduction to functional programming. Topics include (in alphabetical order):
- Algebraic Data Types: Numbers, Tuples, Lists, ...
- Equational Reasoning
- Functional approaches to state, error handling, ...
- Functors
- Higher-order functions
- Higher-order programming
- Monads
- Monoids
- Recursion vs. iteration
- Structural recursion
- Type classes
The language Scala is used.
This course content is divided into eight chapters organized into five parts.
Part 1: Introduction to Functional Programming
Chapter 1: Introduction
This chapter introduces the core principles of functional programming, including immutability, pure functions, and higher-order functions. It also discusses functional programming's benefits, such as improved modularity, testability, and concurrency. A fairly complex and fictitious example illustrates the core principles and benefits.
Part 2: Core Principles and Techniques
Chapter 2 Part 1: Higher-Order Programming
This chapter explores the possibilities offered by higher-order functions, which take other functions as arguments and/or return functions as results. You will learn to use higher-order functions to write more expressive, reusable, and adaptable Scala code.
Chapter 2 Part 2: Functional Data Structures
This chapter explores immutable data structures called algebraic data types (ADTs) commonly used in functional programming, such as lists, trees, and maps. You will understand how to work with these structures and the advantages they offer. This chapter explores pattern matching to process these data structures.
Chapter 3: Recursion
This chapter introduces concepts such as structural recursion, complete structural recursion, mixed recursion, non-structural recursion, and continuation passing style to solve problems and characterize solutions. This chapter builds upon the concepts seen in Chapter 2.
Chapter 4: Exception Handling in Functional Programming
In this chapter, we learn how to manage errors in a functional way using the Option and Either ADTs, avoiding traditional exception handling that relies on side effects.
Chapter 5: Non-strict evaluation
This chapter describes the difference between strict and lazy evaluation and how to use laziness effectively in your Scala programs. You will discover how lazy evaluation - where elements are only computed when needed allows for efficient and elegant functional programming in Scala. We will cover call-by-name and call-by-need and use these not only to develop efficient functional programs but also to develop our own LazyList ADT, a useful data structure for representing potentially infinite sequences of elements.
Part 3: A Functional Programming Exercise
This part aims to develop the necessary ADTs for simulating state machines incrementally. This chapter relies on the first five chapters and introduces only a few new concepts of Scala (e.g., type synonyms). The exercise we cover in this chapter is similar to the project's difficulty, allowing students to gauge the required understanding and proficiency in the fundamental chapters.
Part 4: Using mathematics to generalize solutions for types of problems
The goal of Part 4 is to show that concepts from the category (a branch in mathematics) have practical applications in computer science.
Chapter 7: Monoids and Foldable ADTs
This chapter covers monoids, a fundamental algebraic structure with data aggregation and parallelization applications. Monoids also play an important role in Foldable ADTs, an important abstraction for working with a wide range of data structures in a generic and composable way. You will learn how to use fold, foldLeft, foldRight, reduce, ... to perform common operations such as summing elements, finding the maximum, or combining values while remaining independent of the specific underlying data structure. You will see that these operations are built on monoids.
Chapter 8: Functors and Monads
This chapter draws upon category theory to introduce two new abstractions: Functor and Monad. Functor is a fundamental abstraction in functional programming that allows you to apply transformations to values wrapped within a context. You will learn how Functor provides a unified interface for mapping functions over various data structures, enabling you to write generic, reusable code that operates seamlessly across different container types. Monads provide a mechanism for sequencing (or chaining) computations involving effects such as state, error handling, and input/output while maintaining a clean and composable structure.
Part 5: Functional Programming in Distributed Data Engineering
The goal of this part is to show you how and where the principles we covered in class are used in research and industry, as well as give you a taste of how these principles are reused in the masters. The fifth part is not mandatory for this course. You will be invited to participate in a non-obligatory learning activity in which you will be introduced to Apache Spark, an open-source framework for large-scale data processing. Using Scala's functional programming paradigm, you will learn to use Apache Spark's capabilities to perform distributed computations on massive datasets. You will see how Spark's core abstractions, such as Resilient Distributed Datasets (RDDs) and DataFrames, seamlessly integrate with functional programming concepts, enabling you to write expressive, scalable, and fault-tolerant data pipelines.
Learning outcomes of the learning unit
At the end of this course, you will be able to:
- Understand the functional paradigm.
- Write programs in the functional style.
- Use the functional programming paradigm to solve various problems.
- Specify, implement, and use functional data structures and algorithms in a functional style.
- Use and understand type functional programming techniques such as currying and function composition.
- Analyze and reason about functional programs.
- Appreciate the benefits of functional programming.
- Determine when the functional approach is more convenient than the imperative approach.
Prerequisite knowledge and skills
Basic knowledge in programming and mathematics. Object-oriented programming.
Planned learning activities and teaching methods
The course organizes four key learning events, three of which are linked to theory, practice, and project hours.
Theory: For the theory, knowledge will be transmitted based on a lecture supported by slides. You also have access to alternatives based on the same principle of transmission: a reference book and video recordings of the lessons. Small debates or discussions are sporadically organized during the presentations to deepen the understanding of certain aspects. These debates can also be used to introduce a new topic in a chapter.
Practical work: Each session begins with a simple exercise entirely developed by the teaching team. We expect you to follow each of these steps and ask us questions if necessary. Then you will perform training exercises. These exercises are intended to train you in the use of the techniques seen in class. Some practice sessions give you an environment in which to test your solutions. The solutions to these exercises are made available to you after the session.
Project: The project is to design and implement a functional program to solve well-known problems (e.g., semantic tableaux, scheduling algorithms, etc.) that are important in computer science. The assistant and I are here to guide and support you. Unlike the exercises, where solutions are given, you will only be guided. Apart from the courses and the project, there are meta-reflection events. The goal of meta-reflection is to understand where you are in learning the course material. Projects are realized in teams of three students.
Apart from the courses and the project, there are meta-reflection events. The goal of meta-reflection is to understand where you are in learning the course material.
- The first type of activity is the overall feedback on the projects (common errors, observations, etc.). The global feedback also includes statistics about the grades and the session invites you to ask questions or open the discussion.
- The second type of activity is training tests which are auto-evaluated (i.e., by you). These tests (not mandatory) prepare you for the exam. After this question, I share sample solutions and we discuss the errors you want to share. You are invited to discuss and correct any errors made. I explain how the solutions are evaluated and scored during the exam.
Mode of delivery (face to face, distance learning, hybrid learning)
Face-to-face course
Further information:
Face-to-face course
Additional information:
The course is taught in French. The book and course material (including slides) are in English. The tests and exams will be made available in French as well. The course slides will contain a list of translations of the most important concepts.
The English material will facilitate international MSc students in their independent study. These students will also be provided with English versions of tests and exams.
Course materials and recommended or required readings
Platform(s) used for course materials:
- eCampus
- Microsoft Teams
Other site(s) used for course materials
- Scala Standard Library (https://www.scala-lang.org/api/current/)
Further information:
The syllabus is compulsory. Information about course organization, course content, course objectives, and course assessment can be found in this resource.
Slides are a required resource. Each chapter is accompanied by detailed and complete slides. It is possible to study this course using only the slides, but you are encouraged to combine this with class attendance or the lecture recordings. Face-to-face lessons or recordings reexplain or illustrate certain points from different angles.
For the project, consulting the Scala Standard Library is highly recommended.
Exercise materials are highly recommended. The theoretical sessions introduce examples, and these examples correspond to the (types of) exercises that we will approach during the practical work. However, the exercises can introduce new elements. These may include new operators, more elaborate or difficult examples, technical details, or special cases. Solutions will be available after the exercises, but you are strongly encouraged to attend and review those in preparation for the exam. This exercise also prepares you for the realization of your project.
Past exam questions, sample exam questions and project rubrics are highly recommended. All of these resources are made available, in due course, on eCampus. Although these are discussed in class, you will need to consult them to get a concrete idea of the expectations.
The reference book is optional. "Michael Pilquist, Rúnar Bjarnason, and Paul Chiusano, Functional Programming in Scala, 2nd Edition, Manning Publications." This book may be useful for students who wish to learn the material at their own pace, in English, or revisit chapters differently. Copies of this book are available at the library.
Video recordings are optional. The individual chapters are divided into logical parts. A video recording of each part is available on YouTube. Links to YouTube videos are available on eCampus under each chapter. These videos are an alternative to live lessons.
Additional references shared on eCampus are optional. For some chapters, there are links to resources and articles. These are intended to provide additional guidance or (historical) context for those interested.
Exam(s) in session
Any session
- In-person
written exam ( open-ended questions )
Out-of-session test(s)
Further information:
Exam(s) in session
Any session
- In-person
written exam ( open-ended questions )
Written work / report
Out-of-session test(s)
Additional information:
Two tests, a project, and a written exam.
- The first test counts toward 10% of the grade
- The second test counts toward 10% of the grade
- The project counts toward 30% of the grade
- The written exam counts toward 50% of the grade
- The tests and the written exam are replaced by one written exam counting toward 70% of the total. Students whose weighted average for the tests and the exam is less than 10/20 must retake the exam.
- Students who did not obtain at least 10/20 for their project may resubmit a revised version in August.
The final grade will be determined using a weighted average of all evaluations. However, students must attain a minimum grade of 8/20 on each assessment, otherwise, the student's lowest assessment grade will be used as their final grade for the course. During the first semester, the tests and the exam will be combined into one evaluation.
Work placement(s)
Organisational remarks and main changes to the course
All organizational aspects will be communicated through eCampus.
Contacts
- Professor: Christophe Debruyne