The Concept of Referential Transparency

Referential transparency (translator's note: also called substitution transparency) is a made-up term for describing the ability to safely replace pure functions with their expression. An example will demonstrate this clearly.

In algebra, when you have the following formula:

y = x + 10

And it's stated that:

x = 3

You can substitute x back into the equation to get:

y = 3 + 10

Notice that the equation remains true. We can make similar substitutions with pure functions.

Here's a function in Elm that wraps an incoming string in single quotes:

quote str =
    "'" ++ str ++ "'"

And here's code that uses it:

findError key =
    "Unable to find " ++ (quote key)

In this example, findError will create an error message if the search for key was unsuccessful.

As long as the quote function is pure, we can simply move the function call in findError together with the body of the quote function (which is, in essence, an expression):

findError key =
   "Unable to find " ++ ("'" ++ key ++ "'")

This is what I call reverse refactoring (translator's note: inlining) (I use this term fairly broadly) — a process that can be used by programmers or programs (such as compilers or testing tools) to analyze code more meaningfully.

This can be especially useful when analyzing recursive functions.

Order of Operations in Functional Programming

Most programs are single-threaded, meaning one and only one piece of code executes at a given moment. Even if you have a multithreaded program, most threads are blocked waiting for I/O operations to complete, such as loading a file, waiting for a network response, and so on.

This is one reason why we tend to think in terms of step-by-step instructions when we write code:

1. Get the bread
2. Put two slices in the toaster
3. Select maximum toasting
4. Push the lever down
5. Wait for the toast to pop up
6. Take out the toast
7. Get the butter
8. Take a butter knife
9. Spread butter on the toast

In this example there are two independent operations: using the butter and making the toast. They only become interdependent at step nine.

We could carry out steps seven and eight in parallel with steps one through six, since they are independent of each other.

But as soon as we do that, everything becomes much more complicated:

Thread 1
--------
1. Get the bread
2. Put two slices in the toaster
3. Select maximum toasting
4. Push the lever down
5. Wait for the toast to pop up
6. Take out the toastThread 2
--------
1. Get the butter
2. Take a butter knife
3. Wait for thread 1 to finish
4. Spread butter on the toast

What happens to the second thread if the first one fails? What's the mechanism by which the two threads interact? Which thread does the toast actually belong to: the first, the second, or both?

It's easiest not to think about these structural complications and just let our program run on a single thread.

However, when it's important for us to squeeze every last bit of performance out of the program, we have to put in a titanic effort to write multithreaded code for it.

Either way, there are two main problems with multithreading. First, multithreaded applications are hard to write, analyze, test, and debug.

Second, languages like JavaScript don't support multithreading (translator's note: this article was written back in 2016, and now we have some hope in the form of Napa.js), and some of the ones that do support it do it poorly.

But what if the order didn't matter and everything could run in parallel?

Even though it sounds crazy, the idea isn't as chaotic as it might seem at first. Let's take a look at the following Elm code, which illustrates this:

buildMessage message value =
    let
        upperMessage =
            String.toUpper message        quotedValue =
            "'" ++ value ++ "'"    in
        upperMessage ++ ": " ++ quotedValue

Here buildMessage takes message and value, then converts message to uppercase, wraps value in quotes, and concatenates these strings, separating them with a colon.

Notice that upperMessage and quotedValue are independent of each other. How do we know this?

There are only two conditions for independence to hold. First, both functions must be pure. This matters because, when executed, they must not affect each other.

If they weren't pure, we could never say for sure whether they're independent. In that case, we'd be forced to rely on whatever order they happened to run in on their own. That's how imperative programming languages work.

Second, here's the other condition: the result of one function's execution is not the input value of the other. If that weren't the case, we'd have to wait for the first function to finish before the second one could run.

In this light, upperMessage and quotedValue are both pure functions, and neither one requires the result of the other.

Consequently, these functions can be called in ANY ORDER.

The compiler can determine the order of execution without any involvement from the programmer. This is only possible in a pure functional language, because it's very difficult, if possible at all, to determine the consequences of side effects.

The order of code execution in a pure functional programming language can be determined by the compiler on its own.

This is extremely efficient, given that processors aren't getting faster. Instead, processing is adding more and more cores. This means that code can run in parallel at the hardware level.

Unfortunately, with imperative languages we can't take full advantage of the power of these cores, except at a very coarse level. And even that requires radically changing the architecture of our programs.

With a pure functional programming language, we have the potential to automatically take advantage of processor cores at a fine-grained level without changing a single line of code.

Type Annotations

In statically typed programming languages, declaring types is a built-in capability. Here's a Java code example to illustrate:

public static String quote(String str) {
    return "'" + str + "'";
}

Notice how typing is built right into the function definition itself. Things get even murkier when generic data types come into play:

private final Map getPerson(Map people, Integer personId) {
   // ...
}

Here the types are marked in bold to highlight them, but they still keep cluttering the function definition. You have to read carefully to find the variable names.

In dynamically typed languages, this isn't a problem. In JavaScript we can write code like this:

var getPerson = function(people, personId) {
    // ...
};

It's much easier to read code without all that distracting type information. The only trouble is that we lose type safety. We could just as easily pass the parameters in reverse order, meaning a Number for people and an Object for personId.

We won't catch the error until the whole application crashes, and that could happen after several months of diligent work in production. This wouldn't happen in Java, since the code there would simply refuse to compile.

But what if we could get the best of both worlds? The syntactic simplicity of JavaScript together with the safety of Java.

Indeed, we can. Here's a function in Elm with a type annotation (translator's note: type signature):

add : Int -> Int -> Int
add x y =
    x + y

Notice that the type information sits on a separate line. This separation draws a line between these two worlds.

You're probably thinking right now that there's a typo in this annotation. I remember thinking exactly that the first time I saw it. I thought the first -> should have been a comma. But there's no typo here.

This will make a lot more sense once you see the annotation with the implied parentheses in place:

add : Int -> (Int -> Int)

This says that add is a function that takes a single parameter of type Int, and then returns a function that takes a single parameter of type Int and returns an Int.

Here's another type annotation with the parentheses spelled out:

doSomething : String -> (Int -> (String -> String))
doSomething prefix value suffix =
    prefix ++ (toString value) ++ suffix

This says that doSomething is a function that takes a single parameter of type String and returns a function that takes a single parameter of type Int and returns a function that takes a single parameter of type String and returns a String.

Notice that everything takes a single parameter. That's because all functions in Elm are automatically curried.

Since the parentheses are always implied on the right-hand side of the expression, they aren't required. So we can just write:

doSomething : String -> Int -> String -> String

Parentheses matter when we pass a function in as an input parameter. Without them, the type annotation would be ambiguous. For example:

takes2Params : Int -> Int -> String
takes2Params num1 num2 =
    -- do something

and this is quite different from:

takes1Param : (Int -> Int) -> String
takes1Param f =
    -- do something

takes2Params is a function that requires two parameters, an Int and another Int. Whereas takes1Param requires a single input parameter that is itself a function taking an Int and returning another Int.

Here's the type annotation for map:

map : (a -> b) -> List a -> List b
map f list =
    // ...

Here the parentheses are needed because f is a function of type (a -> b), that is, a function that takes a single parameter of type a and returns something of type b.

Here a can be any type. When a type name starts with a capital letter, it means it's an explicitly specified type, such as String. If the type name is lowercase, it can be any type. Here a could be String, or it could be Int.

If you see (a -> a), it means that the incoming and outgoing types MUST be the same. It doesn't matter which type exactly, as long as they match each other.

But in the case of map we have (a -> b). This means that although the function CAN return different types, it can also return the same type.

But once type a is defined, it has to carry through the rest of the annotation (translator's note: signature). For example, if a is Int and b is String, then the annotation would look like:

(Int -> String) -> List Int -> List String

Here every occurrence of a is replaced with Int, and every occurrence of b with String.

The type List Int means a list containing Int values, and List String means a list containing String values. If you've used generics in Java or other languages, this concept should feel familiar.