Map, Filter, Reduce in Fortran 2018

Milan Curcic
May 22, 2019 · 11 min read
Photo by Nik Shuliahin on Unsplash

Also on milancurcic.com.

While not a purely functional language, Fortran allows the programmer to express themselves functionally. John Backus, the original creator of FORTRAN at IBM in 1956, argued for functional programming in his 1977 Turing award lecture. Map, filter, and reduce are the core tools of a functional programmer — they allow you to solve problems by chaining recursive functions instead of piling do-loops and if-blocks one on top of another. Map applies a function element-wise to an arbitrary array. Filter applies a function to an array and returns only those elements that meet the criteria defined in the function. Reduce, often also called fold, applies a reduction operation to an array and returns a scalar result.

Fortran 2018 now offers (almost) out-of-the-box support for map, filter, and reduce patterns. This article explains how.

Map

Let’s start with map. This higher-order function applies a function for each element in array and returns the resulting array. Given function and array , the typical syntax is . This expression returns an array of same size as . On first look, Fortran doesn’t have anything like in its standard library. However, Fortran has had similar functionality built into the language since the Fortran 90 standard — elemental procedures.

Elemental procedures allow you to define a procedure that can operate both on a scalars and arrays at the same time. A minimal, though not terribly useful example, is:

then returns . However, the attribute makes this function surprisingly powerful. Without any modifications to the code, you can apply to an array — returns . Further, you can apply to an array of any rank. Fortran supports up to 15-dimensional arrays. I’ve never used more than 5 dimensions myself but I’m sure there are application domains that make good use many-dimensional arrays.

However, originally came with a restriction — you couldn’t make a procedure both elemental and recursive. If you wanted to apply a recursive function to an array, you had to resort to a do-loop. This is why I made available as part of functional-fortran. Say you have a recursive function, an ubiquitous textbook example being the Fibonacci function:

Prior to Fortran 2018, you had to specify the attribute if the function was to be used recursively. However, if you tried to make this function both and , you’d get scolded by the compiler soon enough. Here’s the output from gfortran-8.2.1:

In his human-readable rendering of the updates to the Fortran standard, John Reid writes:

The restriction against elemental recursion was intended to make elemental procedures easier to implement and optimise, but recursion has become normal so it is not needed.

This means that Fortran 2018 finally drops the restriction for recursive procedures also being elemental. However, we can’t compile our programs with the ISO standard, so until the compiler developers implement these features, we still have to resort to a home-cooked :

That’s it, the whole function. We loop over all elements of , and apply function to each, all wrapped in an array comprehension. The result array is a so-called automatic array — it assumes the size of and will by default be allocated on the stack. For the above to work though, we still need to define an interface for :

Now that we have the recursive function we want to apply () and , we can use it as advertised. For example, yields as the result. To get all Fibonacci numbers, say, from 1 to 30, you’d do .

Once you map a function to all elements of an array, what else would you do but filter the results?

Filter

Filter asks for a function that returns a logical (Fortran word for a Boolean) True or False given an input value. Common example of a function used to demonstrate filtering numbers are or :

Let’s define a higher-order function to get even numbers out of an array of integers so that we can just do . Like map, filter can be constructed with existing Fortran building blocks.

Since Fortran 95, we’ve had the function in the standard library. GNU Fortran documentation for reads:

PACK — Pack an array into an array of rank one

Description: Stores the elements of ARRAY in an array of rank one.

It sounds like this is meant to unroll (or flatten, if you come from the numpy world) a multi-dimensional array into a one-dimensional array. Keep reading though:

The beginning of the resulting array is made up of elements whose MASK equals . Afterwards, positions are filled with elements taken from VECTOR.

OK, there are a few more elements to the syntax of here, namely the arguments and optional . To understand what these do, we need to look at the complete syntax for :

The square brackets here indicate optional syntax. The docs go on to describe the arguments:

Shall be an array of any type.

Shall be an array of type and of the same size as ARRAY. Alternatively, it may be a scalar.

(Optional) shall be an array of the same type as and of rank one. If present, the number of elements in shall be equal to or greater than the number of true elements in . If is scalar, the number of elements in shall be equal to or greater than the number of elements in .

It turns out that does the very same thing as , except that instead of the filtering function, you pass a logical array that says which elements of the original input array to return. Great! This means that the filter could be defined as a syntactic-sugar kind of wrapper around :

We declare as an allocatable array since we don’t know its size ahead of time. However, we don’t need to allocate it explicitly, as we can use automatic allocation on assignment, a neat feature of Fortran 2003. Note that as an allocatable array, the result will be allocated on the heap, which is likely to cause a performance hit relative to automatic arrays that typically go on the stack.

As before, to use as an input argument, you need to define its interface first (just the interface, no body!):

Having covered and , we can now combine them to map a recursive function over all elements of an array, then filter the results by applying the filtering function:

This snippet takes an integer array , computes a Fibonacci number for each element, and then filters out only even numbers out of the lot. It yields as the result.

Reduce

We’ve mapped a function to the input array and filtered the results. The last step is to apply a reduction operation on the array to get to a scalar result. Reduction (or folding) recursively applies a binary operation to all elements of the array, in or out of order, until it exhausts the array and reaches the final scalar result. Common examples of Fortran functions that perform reduction on arrays are , , , or .

Admittedly, reduction is tad more difficult to get your head around compared to map or filter. Guido van Rossum argued against reduce in Python because it’s difficult to reason about reduction unless the operation is an extremely simple one, such as addition and multiplication. In those cases, he argued for including and functions in the standard library, whereas any reduction more complex than that would be more clearly expressed with list comprehensions. Should you reduce or not in your code? Totally up to you — try it out and see if you like it. Let’s see how we can use it in Fortran today.

The Fortran 2018 reduce

Fortunately for functional Fortranners, Fortran 2018 brings a new reduction intrinsic (a Fortran word for a built-in, or a standard library function), . There are two forms to this function (Reid, 2018):

The input array can be of any type and rank. The second argument is a pure function with two arguments and a result of same type as . If 2nd form is used, indicates the one dimension along which to perform the reduction, and the result is an array of rank reduced by one relative to the input array. a logical array which will filter the input array, much like in the built-in function . is a fall-back value that the result will take if the input sequence is empty. Finally, if is , the reduction is applied left-to-right. Otherwise, the will compiler will assume that the operation is commutative and will evaluate the reduction in the most optimal way it can find.

The built-in reduce function looks quite useful and flexible, however, it’s a recent addition to the language, and as of May 2019, stable release of gfortran (9.1) doesn’t support it. Until it does, we need to roll our own implementation. Note that the parallel reduction is supported and ready to use with gfortran and OpenCoarrays, and works well in practice.

Implementing your own reduce function

Let’s implement a custom high-order function that will allow us to do the following:

where is a function to add two integer scalars. First argument is the function that we’ll use as a reduction operation, second argument is the input array, and third argument is the starting value (I’ll get to this in a bit). This single line will compute a sum of all even Fibonacci numbers from 1 to 30.

applies a binary function or operator to elements of an array, recursively. Here’s the code for a left-to-right reduction (a so-called left-fold):

where is an interface of a function that takes two integers and returns an integer result:

and is the starting value to use when applying the reduction to the first element of , and also the value of the result should the input array be empty. Intrinsic function could then be written as , while the function could be written as . Note that the argument can be made optional — Python’s does so, for example.

Alternatively, you can also apply reduction to the array elements right-to-left, also called a right-fold:

Left- versus right-fold defines the associativity of the operation . For example, left-fold will evaluate the sum of as , whereas the right-fold will evaluate it as . While the order is irrelevant in this particular case, it will matter for reductions of floating-point arrays, or if applying a non-commutative function.

If you put all the pieces together, you can now write:

and the result is 1089154.

For another example of a common reduction operation, a Fortran programmer often uses intrinsics and to test if any or all values of a Boolean array are True, respectively. If you think about these in the context of , these could be written as and , respectively. If you get creative, you can do other cool stuff too, such as reverse or sort arrays.

Finally, should you use it in production? In his paper on universality of recursive reduction, Graham Hutton (1999) wrote:

Programs written using fold can be less readable than programs written using explicit recursion, but can be constructed in a systematic manner, and are better suited to transformation and proof.

Thus, while using recursive reduction likely leads to more expressive and cleaner code that is a composition of small building blocks, it can also be less readable and more difficult to reason about, merely due to it being recursive and not iterative. Try to recurse in your head — it’s not easy!

Functional patterns, and recursion in general, may come with a performance hit in Fortran. This is simply due to the fact that these patterns haven’t been used much in legacy Fortran historically, so they haven’t ranked highly on the priority list for compiler developers. The usual recommendations hold:

  • Use the patterns that are most intuitive to you. There’s no point in writing smart code if you won’t understand what it does when you look at it a year later.
  • Profile your code before using functional patterns in production. They may be less computationally efficient than the imperative implementation, and this may vary wildly between compiler vendors.

Summary

Although it’s not immediately obvious, Fortran 2018 now provides (almost) complete out-of-the-box support for map-filter-reduce patterns:

  • Map: Use functions that are defined on scalars, but can operate element-wise on arrays of any rank. Prior to Fortran 2018, there was a restriction on functions being recursive. This restriction is now lifted, and I can’t think of a good reason to cook up your own implementation of . If you write your functions as , what you’d write in some other language as in Fortran 2018 is just . Beauty!
  • Filter: Use the built-in , together with an array comprehension, e.g. , or use the function from the functional-fortran library if array comprehension is too verbose for you.
  • Reduce: Fortran 2018 brings (serial) and (parallel) to its standard library. Until your compiler supports , use a custom implementation of reduce from this article, or use one of the fold implementations from functional-fortran.

References

Modern Fortran

Modern Fortran: Building Efficient Parallel Applications