Fun and Functional Programming

Fun and Functionality

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

The core feature of mathematical functions is the property of being a ✨functional✨ relation, i.e. a mapping from an input to a unique output. This is where the name “function programming” comes from — however, it doesn’t mean that the language functions properly…

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.

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

1. The global variable x is 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.

2. 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.

3. if without else.

   In functional programming every if ends with an else, because the if-else expression must evaluate to a value.

4. 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.

5. 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 a subset of the programming language so that we don’t break functionality.

Execution and Evalution

A mathematical function does not execute any code — it just knows the answer — Bartosz Milewski, Category Theory for Programmers

As Bartosz says in his book Category Theory for Programmers, mathematical functions aren’t executed, rather they are evaluated. Evaluation means turning an expression, or a block of code, into a final value through a sequence of evaluation rules. Evaluation rules say what the value of a certain kind of expression is, they give “meaning” to words.

For example the expression 1 + 2 evaluates to the value through the following steps. But first, a word on notation: code, like 1 + 2, is used to denote expressions whereas the more mathematical looking denotes values.

1. The expression is an arithmetic add expression of syntactic shape a + b.
2. To evaluate the expression, we first need to evaluate the sub-expressions 1 and 2:
   • evaluating the sub-expression 1 results in the value
   • evaluating 2 results in the value
3. Now that we know the values of the sub-expressions, we can derive the value of 1 + 2, which is

The distinction between code expressions and values is important to keep in mind when analyzing functional programs.

Every piece of syntax/code has a similar procedure for determining its value. …Well almost every — for instance a function definition isn’t an expression, but an equation assigning functions to names. This is how in the pure functional programming language Haskell everything is laid out.

In Gleam, we can’t just return a function definition from a function, as its not a value.

This code doesn’t compile because a named function (the fn add(a, b)) must be at module-level, i.e. outside any other functions.

Similarly imports must be made at the module-level.

Instead, we can define add at module-level and return that from f.

But surely there is a way to write the function add inside f, right?

Well, there is, and we call that construction an anonymous function (in programming language terminology), a lambda-function, or a lambda-abstraction (in mathematical terminology).

fn(x) { x }

fn(x) {
    let y = x
    y + x
}

fn(x) {
    fn(y) { x + y }
}

fn(x) {
    fn(y) { x + y }
}

To tie things up, we were discussing how to return the function add from f, and here it is using a lambda-abstraction:

Immutability

Contrary to popular belief about functional programming, many functional languages actually do support statefulness¹ and mutation of variables² in a small context. Some languages, such as Clojure, go as far as allowing a global kind of mutation, but that breaks functionality, which is the core principle of functional programming.

Gleam doesn’t have any statefulness or global mutation.

Basic Types and Type Checking

So far we have been using Gleam without using its strong type system. The reason why we can write “untyped” code is that Gleam can infer the type of most expressions we write, and we haven’t written anything out of the ordinary so far — let’s do that now.

The following code attempts to compute 5 + True, but Gleam refuses to compile the code due to a type error.

*Argh*, now the compiler is yelling at me about an unused function

warning: Unused private function
  ┌─ /app/main/src/main.gleam:1:1
  │
1 │ fn f() {
  │ ^^^^^^ This private function is never used

Hint: You can safely remove it.

…no wait, that’s not the solution — well it is a solution…

The compiler also produced the following type mismatch error, which may be more productive to investigate:

error: Type mismatch
  ┌─ /app/main/src/main.gleam:2:7
  │
2 │   5 + True
  │       ^^^^

The + operator expects arguments of this type:

    Int

But this argument has this type:

    Bool

What Gleam is trying to tell us is that using the + operator expects Integer expressions on either side, and True is a Boolean expression rather than an Int. This error simply means that we are trying to call the binary (i.e. takes two arguments) + function with values which have the wrong type. There is no convincing Gleam that True is an Int, Gleam doesn’t have implicit coercions, or convincing it that + takes Bool on the right as Gleam doesn’t have function overloading as we learned earlier.

*Sigh*, I guess the solution is to remove the function…

Instead of implicit coercions (and to avoid having to remove the function), we can use an explicit coercion (i.e. a regular function call) to to_int. To do this, we need to add import gleam/bool on the first lines of the file.

This produces the expected result of 6 (and a deprecation warning about the function we just used — in Gleam stdlib 0.52.0 bool.to_int is removed, so we’ll stick with 0.51.0 for a while):

warning: Deprecated value used
  ┌─ /app/main/src/main.gleam:5:11
  │
5 │   5 + bool.to_int(True)
  │           ^^^^^^^ This value has been deprecated

It was deprecated with this message: Please use a case expression to get
the behaviour you desire

   Compiled in 0.63s
    Running main.main
6

The return type of the function can be made explicit by adding an arrow -> followed by the type of the function’s body expression, in this case Int.

import gleam/bool

pub fn f() -> Int {
    5 + bool.to_int(True)
}

The type signature of f itself can be written as f: fn() -> Int in Gleam syntax or

in mathematical notation.

Let’s define a function g which takes a boolean parameter and returns an integer.

import gleam/bool

pub fn g(b: Bool) -> Int {
    5 + bool.to_int(b)
}

The function has the type signature g: fn(Bool) -> Int which can be written mathematically with or without parentheses:

Gleam even has enough information to infer the function’s type without us writing Bool or Int:

Assigning Functions to Variables

In Gleam, functions are just ordinary data. We can assign functions to variables just like we can assign the value 5.

Let-bindings also allow us to specify the type of a variable using a colon between the variable name and equals sign.

Function Signatures — How Functions Sign Their Name

Official documentation.

So far we’ve mostly looked at functions from the functionality perspective — trying to answer “what does this function do”. In (typed) functional programming it is often useful to abstract a function to its signature. A function’s signature is a description of the type(s) that it takes as arguments and the type that it outputs. For instance, a function with the type signature maps a value of type to a value of type . In Gleam, the type signature is written as fn(Int) -> Bool.

A common practice when developing functional programs is to first determine a function’s signature and worry about the implementation later. It is in fact so common, that there’s an entire development methodology called type-driven development that takes it above and beyond. In Gleam, stump functions can be defined by using the todo keyword. The interior functionality of todo is a bit strange, but its return type is guaranteed to be the one required by the type checker in that specific situation. Reaching a todo at runtime causes a panic.

Multi-Parameter Function Types and Currying

The signature of functions with arity greater than one, i.e. which have multiple parameters, is usually written using parentheses with all the parameter types separated by commas.

For example, a function plus which takes two integer arguments would have the following type.

In Gleam, this translates to the type signature: fn(Int, Int) -> Int.

In Gleam, we can partially apply functions, i.e. pre-fill an argument to a function call, by using an underscore in place of the other argument. For example, to partially apply the value a = 2 in the call plus, we write plus(2, _). This returns us a function which takes in the missing b as an argument.

Notice that only one argument can be left out using an underscore.

This concept of partially applying functions one argument at a time is called currying (named after the mathematician Haskell Curry).

Gleam’s authors don’t like currying. curry2 along with others were recently removed.

The function plus_alt in the example has the signature fn(Int) -> fn(Int) -> Int. This can be expressed mathematically with

and is often used to mean exactly the same thing as . To read chains of arrows, you can add parentheses associating to the right like so:

Crucially, this is not the same as

which belongs in the very interesting set of higher-order functions, whereas plus_alt does not.

Higher-order Functions

Functions that take other functions as arguments are referred to as higher-order functions. They are a key feature of functional programming languages, adopted even in many not-so-functional programming languages (such as C++). The usage of higher-order functions often leans heavily on generics, which will be discussed later.

We will learn about generics in the Generics chapter.

Below is a simple higher-order function which uses concrete types (instead of generics) that takes in a function f: fn(Int) -> Int and a value Int and returns the result of the function applied to the value.

Like apply_int, list.map takes in a function Int -> Int and applies it to each integer in the list.

Common higher-order functions

Here is a table of some common higher-order functions which exists in almost every functional programming language. The most commonly used higher-order functions are often implemented by the language’s standard library.

The notation [a] is Haskell syntax for Gleam’s List(a).

warning: Todo found
  ┌─ /app/main/src/main.gleam:2:3
  │
2 │   todo
  │   ^^^^ This code is incomplete

This code will crash if it is run. Be sure to finish it before
running your program.

Hint: I think its type is `fn(a) -> fn(b) -> c`.

Summary

In this chapter we covered the basics of functional programming (except for recursion). You learned what types of functions look like. You learned that in functional programming functions are like mathematical functions. You learned how to construct functions without names and how to use them with higher-order functions.

Finally you hopefully learned that you can do a little bit of maths in Gleam, at least construct functions between types to show their equivalence.

Footnotes