Introduction to Functional Programming

Overview

In this part, we cover the basics of functional programming. You should be confident in programming at least one language, but no prior functional programming experience is required.

The language of choice for this part is , a custom-made functional programming language. The next chapter, STLC++ Tooling, covers running locally and using the web-based playground.

After the tooling chapter, you will dive into functional programming forming both practical and theoretical understanding on the way. You will learn how functional programs are type checked and evaluated. You will work with recursion and learn recursive problem solving techniques. You will also learn foundational mathematical concepts that will be essential later on during the course.

After this part, you should be comfortable implementing small functional programs in . You can structure your code with types and abstractions, and debug programs when they don’t behave as expected.

Internal Prerequisites

The following diagram highlights the dependencies between the chapters in this part.

A solid arrow from chapter to a chapter means that is a strict prerequisite to . A strict prerequisite in this context means that uses terminology and concepts introduced in .
A dotted arrow from to indicates a weak prerequisite. A prerequisite is weak if it contains useful and related concepts, but not strictly necessary to understand .

You can find the index of a chapter from its URL.

Dependency Graph of Part 1

Even if the chapters don’t have dependencies between them, it’s still recommended to go through them in the numerical order.

Chapters 5 and 6 are more theoretical and contain quiz exercises worth 40 points. However, they cover essential mathematical concepts and even a couple of proofs that will be more relevant once we start working on our own programming language in a later part

Fun and Functionality

In functional programming, functions as we are familiar with in programming, are given a stronger meaning. Functional programming works with mathematical functions — which, believe us, are fun!

The core feature of functions in functional programming languages is the property of being a mathematical function Functions in mathematics are ✨functional✨ relations, i.e. they relate every input to at most one output. Functions also relate each input to at least one output. Those functional relations that do not have this property are not total functions, but are called partial functions. A function is therefore a mapping from an input to a unique output.

This gets us roughly to how functional programming languages are characterized: a language where functions are mathematical functions.

Notice that according to this definition, a programming language is functional only if it is also pure and all functions are be total. This sets a really high bar a function and rules out most functional programming languages. The exact definition of what counts as a functional language is not worth arguing over, it’s just a matter of preference.

Functional programming traces its theoretical roots back to Alonzo Church’s work on the lambda calculus in the 1930s. The first practical implementation of functional programming ideas in an actual programming language was in Lisp, in late 1950s. Functional programming today is closely related to the mathematical fields of type theory and category theory.

Let’s start learning about functional programming by first seeing the “least functional” program the author could come up with.

No files opened Select a file to edit

Try running the example a couple of times to see the different results.

This code breaks many of the constraints in functional programming. Here are the key takeaways why the code example is “unfunctional”:

The global variable x and the state of the random number generated rng are mutated inside the main function.

This is not possible in functional programming, because functions have to be “self-contained”, i.e. they cannot change anything defined outside.
The call to rng.nextInt is not functional because the function maps the argument (number 2) to either 0 or 1 depending on the state of the random number generator.

In functional programming calling a function twice is guaranteed to produce the same result. The value returned by rng.nextInt(2) inside the if statement can be a different value from the previous call. This breaks referential transparency, i.e. being able to “replace equals by equals”, which makes functional programs much easier to reason about.
if without else.

In functional programming every if ends with an else, because the if-else expression must evaluate to a value.
Raising an exception with throw new Exception("Fatal error"); stops the execution of the main function early.

Functional programming doesn’t have a way to return early. Stopping early is usually only possible with a “panic” function provided by the language.
Calling print("Everything is fine ${x}"); has the side effect of writing text into the output stream of the program.

In computer science it is usually convenient to be able to manipulate the state of the computer, by reading input, producing output, sending packets, etc. Even mutating global variables in a single program is a side effect. Functional programming languages that prohibit side effects are called “pure”, and all mathematical functions are pure in this sense.

Functional programming is not only restricted to functional programming languages, in fact most programming languages support writing functional code. This is why functional programming is often called a programming paradigm, roughly meaning a high-level programming pattern or philosophy. The key is to restrict ourselves to using only a subset of the programming language where functions are as “mathematical” as possible.

Loading Exercise...

Overview

Internal Prerequisites

Fun and Functionality

Further Reading