What makes mathematica a "functional programming language"?

According to the website of mathematica itself, mathematica is a "functional progrmaming language".

I am trying to understand what "functional programming" is. I don't think I have ever worked with "functional programming" before (though I'm not sure, since I don't quite know what it is). I've been taught programming mainly in terms of object oriented programming.

But here are some reasons why I don't see why mathematica is a functional programming language:

1. 
   

   I just read that functional programming languages have "immutable variables" much as variables in mathematics are immutable. However, the variables in mathematica can be changed arbitrarily

   
   
   


2. 
   

   I just read that in functional programming languages, the programmer "gives up control over the order of execution". However, in mathematica, we can control this order, to perfect detail, by changing the order of the expressions.

   
   


3. 
   

   "non-functional languages" like C++ also contain functions. If we made a C++ program that consisted only of one object, and simply wrote the program on the basis of functions, how would mathematica be fundamentally different from this?

   
   

Answer

On the Wolfram web site there is a description of the Wolfram Language (WL) entitled Notes for Programming Language Experts. At time of writing, it lists 47 attributes of WL including Functional. It also lists a number of other programming paradigms such as Symbolic, Declarative, Procedural, Concatenative, and Query Capable. (It also lists Object-Oriented, but only as a contrast to WL's "symbolic alternative to traditional object-oriented programming").

This characterization emphasizes that WL is a multi-paradigm language. The native paradigm is based upon pattern-based transformations of expressions. As we will see, this can ably simulate the Functional paradigm.

What is Functional Programming?

The accepted view as to what constitutes functional programming has evolved over time and is somewhat contentious. However, I think it is safe to say that there is one functional programming feature upon which all commentators would agree: the use of higher order functions.

Higher Order Functions

A function is "higher order" if it takes one or more other functions as arguments. Let us look at an example. We will start with a list of numbers:

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

If we want to apply the function f to those numbers, we could write:

{f[1], f[2], f[3], f[4], f[5], f[6], f[7], f[8], f[9], f[10]}

but this is repetitive and tedious. We would like a way, in some sense, to "multiply together" the list and the function f. That is, we wish to treat f like a value in some kind of combining operation with the list value. In Wolfram Language, that operation is called Map:

Map[f, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}]
(* {f[1], f[2], f[3], f[4], f[5], f[6], f[7], f[8], f[9], f[10]} *)

which can also be written as:

f /@ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

/@ looks like an arithmetic operator that is being applied to a function value and a list value. Since at least one argument is a function, /@ is a higher order function.

But there is another, "more pure", way to perform mappings like this. We can convert f from a function that operates upon single values to one that operates upon a list:

g = Map[f];


g[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}]
(* {f[1], f[2], f[3], f[4], f[5], f[6], f[7], f[8], f[9], f[10]} *)

Here we have used the so-called operator form or curried form of Map. This is kind of function transformation sometimes called "lifting", in that the type of a function's input argument has been lifted from one domain to another.

It is possible to perform "function arithmetic" and never mention any function arguments. Consider the following function definition which determines whether the lengths of the strings in a list are all odd:

allOddLength = Apply[And] @* Map[OddQ @* StringLength];

allOddLength[{"one", "is", "even"}]
(* False *)


allOddLength[{"all", "are", "odd"}]
(* True *)

Note how allOddLength is defined purely by means of function algebra. In the functional world this is often termed purely functional. Unfortunately this label conflicts with the WL jargon term pure function. Take care to distinguish between the two senses of "pure".

We can see from these examples that code in the functional style is easily expressed in WL. On this basis, I think it is safe to say that WL has good support for functional programming.

Other Functional Programming Features

We noted earlier that the exact definition of functional programming is contentious. Paul Hudak wrote an excellent survey paper on Conception, evolution, and application of functional programming languages. In it, he proposes five distinguishing features of modern functional programming languages:

1. Higher Order Functions



2. Non Strict Semantics (Lazy Evaluating)


3. Data Abstraction


4. Equations and Pattern Matching


5. Formal Semantics

Today, the term "purely functional" may imply any or all of these features, depending upon vintage and nature of the context within which the term is used.

WL, as Mathematica, was born in the 1980's where "functional" was still popularly equated with the higher-order function feature which we have discussed at length. Nevertheless, let us look at the other features (but only briefly as each topic could easily balloon into a further wall of text).

Non Strict Semantics (Lazy Evaluating)

WL offers many constructions that permit lazy evaluation of expressions, but they require manual intervention by the programmer. They are not implicit and pervasive as they are, say, in Haskell. For an introduction to evaluation control in WL, see Non-Standard Evaluation. For an example of its use in a quasi-functional style, see Functional style using lazy lists?

Data Abstraction

WL's symbolic nature and use of expressions and transformations allows for very strong data abstraction capabilities. For example, here are three distinct implementations of a lookup table:

lt1[keys_, values_][key_] := First@Pick[values, keys, key]
lt2[keys_, values_] := AssociationThread[keys, values]
lt3[keys_, values_] := With[{rules = MapThread[Rule, {keys, values}]}, # /. rules &]

They all present the same interface but their distinctive data representations and operation algorithms are hidden from callers. It is true that this kind of abstraction is idiomatic rather than a built-in concept, but I would argue that the distinction is largely moot.

Hudak's paper regards strong-typing to be part of the data abstraction feature. In this regard, WL is lacking. Except for the small language subset that can be compiled, there is no built-in provision for strong typing (at least in the present version 11).

Equations and Pattern Matching

This, of course, is the bread and butter of WL. There is a conceptual disconnect between the notion of equational reasoning as described in the paper between equation solving in WL. Equational reasoning is meant to be implicit and pervasive where as WL's equation solving is essentially a particular set of run-time library functions. Nevertheless, I would score WL well in this category on the strength of its pattern-matching alone.

Formal Semantics

This is an area where WL is sorely lacking. The idiomatic nature of WL is simultaneously a strength and weakness. The strength is that it allows considerable notational flexibility. The weakness is that the semantics are sometimes ill-defined.

Conclusion

Even though it is idiomatic, WL's support for higher-level functions is very strong. On this basis alone, I believe that WL qualifies as supporting the functional programming paradigm.

If we consider the wider criteria that modern commentators often include in their definitions of functional programming, then WL still fares well for many of those features.