Author : Kenta Inoue

What is a functional language?

Although it is difficult to clearly define a functional language, this article considers the following.

While procedural languages are mainly programmed by combining statements and instructions, functional languages are mainly written by combining expressions and functions.

Now, to compare the differences between procedural and functional languages, let's see a program that computes the least common multiple of integers n1 and n2.

Procedural language written in "statements"

First, we will look at java, a procedural language.

public class GCD {
            public static void main(String[] args) {
                final int n1 = 15;
                final int n2 = 10;
        
                int n = n1;
                int m = n2;
                int k;
        
                System.out.println(n); // n == 15
                while (m > 0){
                    k = m;
                    m = n % m;
                    n = k;
                }   
                System.out.println(n); // n == 5
            }
        }

The program is made by combining statements such as assignment and while statements. In addition, because the value of a variable changes due to assignment, the same instruction statement may produce different output, as in the above System.out.println(n) output result is 15 before the while statement and 5 after. (We will explain this in more detail later.)

In contrast, we see the case in a functional language.

Functional language written in "expressions"

The program to find the least common multiple in the functional language Haskell is shown as follows.

n1 :: Int
        n1 = 15
        
        n2 :: Int
        n2 = 10
        
        euclid :: Int -> Int -> Int
        euclid n m =
            if m == 0
            then n
            else euclid m $ n `mod` m -- euclid m (n `mod` n)
        
        main :: IO ()
        main = print $ euclid n1 n2 -- print (euclid n1 n2)

In functional languages, there is no such thing as a while statement, but rather a combination of expressions and functions. In the example above, euclid and print in the main function are functions, and euclid n1 n2 and print $ euclid n1 n2 are expressions. Even with such a combination of functions and expressions, the same program can be written as in a procedural language, i.e., it is guaranteed to be Turing-complete, and the program-writing capability remains the same.

Reference permeability and side effects

Writing only expressions, as in Haskell, means that variables are not rewritten as in assignment statements. This means that all variable values and functions are defined only at the time of declaration and cannot be rewritten later in an immutable declaration. This specification is reference-transparent and has no side-effects, as follows The specification is reference-transparent, meaning that the same arguments passed to the same function will always return the same result, and side-effects, meaning that other external variables or state can be rewritten within the function.

So, to summarize briefly

• reference-transparent：Not affected by outside influences.
• No side-effects：No external influence.

That is to say. A function that satisfies both of these is called a pure function, and a functional language in which (almost) all functions are pure functions, such as Haskell, is called a pure functional language.

At first glance, a pure functional language would seem incapable of performing these operations, since programs that include external inputs and outputs are, in principle, not reference-transparent and will contain side effects. However, if it is possible to separate the pure part from the part where these inputs and outputs occur, it can be called a pure functional language. In fact, this is achieved by utilizing monads and the like. (That is what I mean by almost all functions being pure.)

Focus on reference transparency

Scala, which is also sometimes called a functional language, is not a pure functional language due to its object-oriented aspect, but it is one of the languages that is highly aware of referential transparency: it is either mutable or immutable, which means that it cannot be changed afterwards. In fact, there are two types of variable definitions, mutable var and immutable val, and libraries are also separated into mutable and immutable.

Programs in languages that satisfy referential transparency have the following characteristics.

Characteristics of languages that satisfy referential transparency

Characteristics of programs that satisfy referential transparency, such as Haskell, include the following.

Easy to test and fix bugs.

In the case of a program that satisfies referential transparency, since the value of a variable or the execution of a function does not change depending on the context, only a single test can be completed, and when an error occurs, only its definition needs to be checked, making bug correction relatively easy. For programs that do not satisfy referential transparency, their output may depend on the context, so when a bug occurs, it may be necessary to check not only the definition but also the context before and after it, which requires more time and effort.

Easy to perform parallel processing.

In a program that satisfies referential transparency, each function always returns the same value for the same input, regardless of the order of execution. Therefore, if the input values are the same, it is guaranteed that the result will not change even if parallel processing is performed. In non-reference-transparent languages, the return value may vary depending on the order of program execution, and some programs are not suitable for parallel processing.

Need to consider the compatibility with external input/output.

When there are inputs and outputs such as external databases, functions that read no longer satisfy referential transparency, and functions that rewrite no longer satisfy purity in principle because of side effects that affect the outside world. Therefore, the question becomes how to handle such functions. In the case of the pure functional language Haskell, a mechanism called a monad is used to separate functions that are not transparent to references such as external input/output and functions with side effects from pure functions for internal processing, allowing programming while maintaining the purity of internal processing. This mechanism called Monad will be explained in detail in another article.

Refer to how to write functional languages.

As we saw in the previous example, one feature of the pure functional language Haskell was its guaranteed referential transparency. That is, it consists only of functions whose return values are always the same if the inputs are the same. This has the above advantages and makes it possible to create referentially transparent programs to some extent even in a procedural language.

Be aware of reference transparency.

In general, writing an assignment statement itself can cause side effects. Therefore, let's try to write the java example as shown in the previous section without using assignment statements.

public class GCD {
            public static void main(String[] args) {
                final int n1 = 15;
                final int n2 = 10;
        
                System.out.println(euclid(n1,n2));
            }
        
            public static int euclid(int n, int m) {
                int k;
                while (m != 0){
                    k = m;
                    m = n % m;
                    n = k;
                }
                return n;
            }
        
            public static int euclid2(int n, int m) {
                if (m == 0) {
                    return n;
                } else {
                    return euclid2(m,(n % m));
                }
            }
        
            public static int euclid3(int n, int m) {
                return (m == 0) ? n : euclid3(m,(n % m));
            }
        }

Let's isolate the euclid function from the original program; the first simply isolates it and changes the values of the arguments n,m and the internal variable k. The second isolates it and changes the values of the arguments n,m and the internal variable k. Basically, if you try to write a loop statement, it will be rewritten, and internally there will be side effects. In other words, the loop statement is considered to have a side effect, which is why repeating the same instruction causes changes and brings meaning to the statement. However, euclid itself does not depend on or rewrite external variables, making euclid a pure function that is reference transparent.

In functional languages, recursive calls are used instead of loops, and euclid2 is aware of this. In this function, there are no side effects because there are no assignments to variables, and the appearance is similar to a program in Haskell. However, to be more precise, an if statement is not an expression but a statement, so euclid3, which is written as an expression using the ternary operator, is the most functional-like description. However, there is no need to be so particular about making it look like a functional language. In practical use, it is enough to make the first euclid function transparent by reference.

Other features of functional languages.

Other features include higher-order functions, i.e., the ability to take function arguments, return a function as the return value, and take type arguments. However, this is not a feature of functional languages, but rather a feature of the specification of each language that is independent of the language type, so it is not specifically explained in this article. (Certainly, higher-order functions can be written in most functional languages and are often used.)

Summary

The concept of functional languages adopted by languages such as Scala was explained, as well as what functional languages are in the first place and their characteristics.