Fun and Functional Programming

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. We will use the convention that text formatted as code, e.g. 1 + 2, is used to denote expressions whereas mathematical looking text, e.g. , denotes values.

1. The expression is an arithmetic add expression with two subexpressions 1 and 2.
2. To evaluate the expression, we first need to evaluate the subexpressions:
   • evaluating the subexpression 1 results in the value
   • evaluating 2 results in the value
3. Now that we know the values of the subexpressions, 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 top-level names are defined in as well as in the pure functional programming language Haskell.

Declarations vs. Statements vs. Expressions

Most programming languages have three categories of code: declarations, statements and expressions. A declaration defines a name for an object that’s at the top-level of the file (or module). For example, functions are often declared starting with a keyword such as def, function or fn followed by the name of the function. In (and in Haskell), no such keyword is used — instead, everything at top-level is a declaration or an import statement.

num : Int
num = 0

square : Int -> Int
square = fun x : Int, x * x

The above code declares two names num and square to represent different expressions. An expressions is a piece of code that we can imagine evaluating to a value. For example, x * x is certainly an expression. A declaration, however, is not an expression, but the name of a declaration is an expression. In functional languages we can write function expressions like fun x : Int, x * x.

Declarations are like mathematical equalities: one can replace equals by equals in functional languages without changing the semantics, i.e. the meaning, of the code.

Fun("x", Int, Mul(Var("x"), Var("x")))

Immutability

Contrary to popular belief about functional programming, many functional languages actually do support statefulness¹ and mutation of variables² in a local context. Some languages, such as Clojure, go as far as allowing mutation of certain kinds of global variables, but that breaks functionality — not all functions in Clojure are therefore mathematical functions.

doesn’t have mutation. Instead of mutating variables, we can shadow them.

On line 5, we shadow the variable x with a new variable.

Basic Types and Type Checking

When writing let expressions (i.e. variable assignments) in , the system infers the type of the right-hand-side term. Type inference works recursively by checking the types of subterms using pre-defined inference rules. If the types don’t match any rule, a type error is raised.

The following example attempts to compute 5 + true, which ‘s type checker refuses.

And to be clear, the point of type checking is that it always happens before evaluation, which means that it can eliminate entire classes of runtime errors.

As an example of a “type error” which happens at runtime rather than beforehand, we have Python’s legendary TypeError.

Trying to run the above code produces the following error message:

Traceback (most recent call last):
  File "/app/src/main.py", line 1, in <module>
    [] + 1
    ~~~^~~
TypeError: can only concatenate list (not "int") to list

We can see the difference more clearly by examining how conditionals affect type checking.

Try removing + true in the else-branch to see what happens.

In the example, infers 3 < 5 to be a boolean, but fails to infer the type of the entire if-then-else term. Compare this with Python, where no “type error” is raised in a similar situation.

Try changing the condition to evaluate to False.

Dynamic and Static Typing

Programming languages like Python, where types are compared at runtime, are commonly called “dynamically typed” languages. Some languages are neither dynamically nor statically typed, for example x86 assembly language has no concept of types. Many languages, like Python, Java and Rust, have both dynamic and static typing capabilities, i.e. a runtime value can carry type information, but the language still provides some means of static type checking.

Assigning Functions to Variables

• functions as “first-class citizens”

In , 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

A function is declared in mathematical notation as follows

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 .

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.

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.

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

The function plus_alt in the example has the signature . 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

plus_alt : Int -> Int -> Int
plus_alt = fun x : Int, fun y : Int, x + y

not_plus_alt : (Int, Int) -> Int
not_plus_alt = fun x : (Int, Int), fst x

also_not_plus_alt : Int -> (Int, Int)
also_not_plus_alt = fun x : Int, (x, x)

Composing Functions

Composing is the process of taking two functions and combining the into one. In mathematics it’s denoted using the symbol, but in , as it’s easier to write ASCII, the composition operator is the period ..

When talking about sets, like in the above definition, one can during this course substitute “type” for the word “set”³.

Composition is baked into for technical reasons, i.e. it’s a primitive operator, but it’s no escape hatch for the type checker. The type checker ensures that the composition is legal, i.e. the types match. For example composing g : Char -> Bool after f : String -> Int would have to be rejected as Int and Char are different types.

If you change Int to Char or vice versa, the code type checks but panics when evaluated as g and f are only declared but not defined.

This gets us to one of the core principles of (functional) programming: abstraction i.e. implementation hiding. The main function has type String -> Bool, not String -> Int -> Bool or whatever else. If a user would only ever see the name and signature of the main function, they would have no way to identify the “intermediate” type that f and g use to communicate — assuming they don’t know of f and g in the first place.

As the developer of a library, we have the power to choose which types are seen and which are hidden to the outside world.

does not have visibility rules for controlling this, however most programming languages do.

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 in the chapter about polymorphism.

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

trace and ? are useful ways to debug and inspect code in . trace takes an integer literal which says how many steps to reduce. ? is shorthand for trace 99999999.

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. Such is the case also for .

Footnotes