# Functional Programming and Scientific Computing

I apologize if this is a vague question, but here goes:

Over the past few years, functional programming has received a lot of attention in the Software Engineering community. Many have started using languages such as Scala and Haskell and claimed success over other programming languages and paradigms. My question is: as high performance computing / scientific computing experts, should we be interested in functional programming? Should we be participating in this mini-revolution?

What are the pros and cons of functional programming in the SciComp domain of work?

• Why purposely put yourself in a straight jacket? Side effects is a tool; it is essential for real world applications. If you want cpu and memory efficiency, functional programming languages wouldn't be on my radar. Programs that need automated verification/correctness checking (eg, for use in a nuke facility?), then ok there might be a case. Nov 8, 2013 at 19:01
• "Side effects" is a bit of a misnomer. There are effects, and then there are side-effects: we want to write to files and plot graphs and print results; we do not want to work with objects and variables whose state changes in ways we don't understand or are unaware of. The FP approach helps us avoid the latter, which is a GOOD thing. Feb 13, 2020 at 1:21

## 9 Answers

I've only done a little bit of functional programming, so take this answer with a grain of salt.

## Pros:

• Functional programming looks very mathematical; it's a nice paradigm for expressing some mathematical concepts
• There are good libraries available for things like formal verification of programs and theorem proving, so it's possible to write programs that reason about programs -- this aspect is good for reproducibility
• You can do functional programming in Python and C++ via lambda expressions; you can also do functional programming in Julia and Mathematica
• Not many people use it, so you can be a pioneer. Much like there were early adopters of MATLAB, Python, R, and now Julia, there need to be early adopters of functional programming for it to catch on

## Cons:

• Languages that are typically thought of as functional programming languages, like Haskell, OCaml (and other ML dialects), and Lisp are generally thought of as slow relative to languages used for performance-critical scientific computing. OCaml is, at best, around half as fast as C.
• These languages lack library infrastructure compared to languages commonly used in computational science (Fortran, C, C++, Python); if you want to solve a PDE, it's way easier to do it in a language more commonly used in computational science than one that is not.
• There isn't as much of a computational science community using functional programming languages as there is using procedural languages, which means you won't get a whole lot of help learning it or debugging it, and people are probably going to give you crap for using it (whether or not you deserve it)
• The style of functional programming is different than the style used in procedural programming, which is typically taught in introductory computer science classes and in "MATLAB for Scientists and Engineers"-type classes

I think many of the objections in the "Cons" section could be overcome. As is a common point of discussion on this Stack Exchange site, developer time is more important than execution time. Even if functional programming languages are slow, if performance-critical portions can be delegated to a faster procedural language and if productivity gains can be demonstrated through rapid application development, then they might be worth using. It's worth noting here that programs implemented in pure Python, pure MATLAB, and pure R are considerably slower than implementations of these same programs in C, C++, or Fortran. Languages like Python, MATLAB, and R are popular precisely because they trade execution speed for productivity, and even then, Python and MATLAB both have facilities for implementing interfaces to compiled code in C or C++ so that performance-critical code can be implemented to execute quickly. Most languages have a foreign function interface to C, which would be enough to interface with most libraries of interest to computational scientists.

### Should you be interested in functional programming?

That all depends on what you think is cool. If you're the type of person who is willing to buck convention and you're willing to go through the slog of evangelizing to people about the virtues of whatever it is you want to do with functional programming, I'd say go for it. I would love to see people do cool things with functional programming in computational science, if for no other reason than to prove all of the naysayers wrong (and there will be a lot of naysayers). If you're not the type of person who wants to deal with a bunch of people asking you, "Why in hell are you using a functional programming language instead of (insert their favorite procedural programming language here)?", then I wouldn't bother.

There's been some use of functional programming languages for simulation-intensive work. The quantitative trading firm Jane Street uses OCaml for financial modeling and execution of its trading strategies. OCaml was also used in FFTW for generating some C code used in the library. Liszt is a domain-specific language developed at Stanford and implemented in Scala that is used for solving PDEs. Functional programming is definitely used in industry (not necessarily in computational science); it remains to be seen whether it will take off in computational science.

• I would like to contribute to add a Pro and a Con. Pro :: code flexibility: since everything is a function, you can always just call that function by another function; this is extremely powerful. Con :: code readability: functional programming codes are really hard to read; even for (most of) the people who have written them. It now even takes me a while to understand some old codes that I have written to solve some generic PDE problems with B-splines in Mathematica 6 months ago; I always pull that code out when I want to scare some colleagues ;-).
– seb
Nov 9, 2013 at 5:53
• Only addition that I would add is: Con :: memory consumption. A lot of copying has to be done to eliminate side effects. Dec 15, 2013 at 18:42
• @StefanSmith: (i) I know it's sometimes used in research (for instance, Maxima is a Lisp-based CAS); beyond that, I don't know off the top of my head. (ii) No idea. Much of my answer was based on anecdotal evidence gleaned from conversations I've had over the past few years. May 19, 2014 at 18:33
• @seb, it sounds like you're describing properties of Lisp-like functional languages that don't apply nearly as well to Haskell-like functional languages. Apr 13, 2016 at 23:19
• Big up vote for the comment by @MatthewEmmett . Copying can be very expensive for high performance computations. Aug 7, 2016 at 20:38

I have maybe a unique perspective on this because I am a HPC practitioner with a scientific computation background as well as a functional programming language user. I don't want to equate HPC with scientific computation, but there is considerable intersection, and so that is the point of view I take in answering this.

Functional languages are unlikely to be adopted in HPC for now primarily because HPC users and customers genuinely care about achieving as close to peak performance as possible. It is true that when code is written in a functional way it naturally exposes parallelism that can be exploited, but in HPC that is not enough. Parallelism is only one piece of the puzzle in achieving high performance, you must also take into account a wide range of micro-architectural details and doing this generally requires very fine-grained control over the execution of code, that control is not available in any functional languages that I know of.

That said, I have high hopes this may change. I have noticed a trend that researchers are starting to realize that a lot of these micro-architectural optimizations can be automated (to an extent). This has bred a zoo of source-to-source compiler technology where a user inputs a "specification" of the computation they want to have happen, and the compiler outputs C or Fortran code which realizes that computation with the optimizations and parallelism necessary to efficiently use the target architecture. Incidentally this is what functional languages are well adapted to doing: modeling and analyzing programming languages. It is no accident that the first major adopters of functional languages were compiler developers. With a few notable exceptions I have not seen this actually take hold yet, but the ideas are there, and functional languages are the ideal tool for realizing those ideas.

I would like to add one aspect to the other two answers. Ecosystem aside, functional programming provides a great opportunity for parallel execution such as multithreading or distributed computing. Its inherent immutability properties make it suitable for parallelism, which is generally a real pain in the *bleep* when it comes to imperative languages.

Since the improvement in hardware performance in recent years has been focused on adding cores to the processors instead of pushing higher frequencies, parallel computation is getting a lot more popular (I bet you all know this).

Another thing that Geoff mentions is that developer time is often more important than execution time. I work for a company that builds a computationally intensive SaaS and we did an initial performance test when starting out, pitting C++ vs Java. We found that C++ provided approximately a 50% cut in execution time over Java (this was for computational geometry and the figures will most likely vary depending on the application), but we went with Java anyway because of the importance of developer time and hoped that optimizations and future hardware performance improvements would help us make it on the market. I can say with confidence that had we chosen otherwise, we would not still be in business.

Ok, but Java is not a functional programming language, so what does it have to do with anything, you might ask. Well, later on as we employed more proponents of the functional paradigm and stumbled on the need for paralellization, we progressively migrated parts of our system over to Scala, which combines the positive aspects of functional programming with the power of the imperative and merges well with Java. It has helped us tremendously when increasing the performance of our system with minimal headache and will probably continue to reap benefits from further performance increases in the hardware business when more cores are crammed into the processors of tomorrow.

Note that I totally agree with the cons mentioned in the other answers, but I thought that the facilitation of parallel execution is such a powerful pro that it could not go unmentioned.

Geoff has already given a good overview of the reasons to which I have little add other than emphasize one of his points: ecosystem. Whether you're advocating functional programming or any other paradigm, one of the important questions you have to address is that there is an incredible amount of software every else can build upon that you have to re-write. Examples are MPI, PETSc or Trilinos for linear algebra, or any of the finite element libraries -- all written in C or C++. There is a huge amount of inertia in the system, maybe not because everyone thinks that C/C++ is in fact the best language to write computational software in, but because a lot of people have spent years of their lives creating something that is useful to a lot of people.

I think most computational people will agree that there is a lot of value in trying new programming languages and evaluating their suitability for this problem. But it's going to be a difficult and lonely time because you will not be able to produce results that are competitive with what everyone else is doing. It may also yield you a reputation as someone who started the next move to a different programming paradigm. Hey, it only took C++ about 15 years to replace Fortran!

• And C++ is, at best, only half way to actually replacing Fortran in this space. We see new codes in Fortran all the time, and plenty of legacy one to boot! Nov 11, 2013 at 2:22
• C++ (unlike Fortran) is too complicated to both learn and use. New open source scientific codes are still being written in Fortran. Notable in my area (Earth Sciences) are PFlotran, SPECFEM3D, GeoFEM etc. Ditto for almost all new codes in Atmospheric sciences. IMHO C++ hasn't even replaced what it was supposed to replace (C). Nov 11, 2013 at 16:05
• You should give Fortran a try Wolfgang, it's a great language, easy to learn/write in and the speed will not disappoint you. Nov 17, 2013 at 5:02
• I don't care about speed (well, I do a little, but it's not the overarching consideration it is for others). What matters to me is how long it takes me to program a complex algorithm, and Fortran loses out on this front because the language is so simple. No standard library to speak of, no templates to allow for generic code, half-assed object orientation. Fortran is simply not my language and, frankly, it shouldn't be for almost all other scientific computing people either. Nov 17, 2013 at 16:21
• @StefanSmith: Yes. It may be a defensible idea in scientific computing (where I would still argue that it is outdated and unproductive). It is certainly not defensible as far as the education of students is concerned -- because the majority of our students leave academia and in industry practically nobody uses Fortran. May 27, 2014 at 22:39

The quick summary is that

1. Numerical computing uses mutability/side-effects to achieve most of its speedups and reduce allocations (many functional programming structures have immutable data)
2. Lazy evaluation can be rough to use with numerical codes.
3. Either you are developing a package where dropping down to the lowest levels for performance really matters (C/Fortran or now Julia) (in these you can also edit the assembler code as necessary), or you are writing a script which uses these fast libraries so you mostly tend to care about development time (and so you choose Julia/MATLAB/Python/R). Functional languages tend to sit in a weird middle ground which is helpful in other disciplines, but not as helpful here.
4. Most of the numerical algorithms for differential equations, optimization, numerical linear algebra, etc. are written/developed/proved in terms of convergence, i.e. you have approximation $x_n$ and you want to get $x_{n+1}$. The natural style to implement these algorithms is a loop. (There are some algorithms written recursively like some multigrid algorithms, but these are much more rare.)

These facts together make functional programming not seem necessary to most users.

• +1, but one addition to point 3: I think that functional features in high level languages are quite useful, and many of the advantages of functional languages mentioned in other answers (e.g. easy parallelization) tend to apply to this scenario. Feb 8, 2017 at 12:08

I think it is interesting to note that the use of functional programming in Computational Science is not new. For example, this paper from 1990 showed how to improve the performance of numerical programs written in Lisp (possibly the earliest functional programming language) using partial evaluation. This work was part of a tool chain used in a 1992 paper by G J Sussman (of SICP fame) and J Wisdom which provided numerical evidence of the chaotic behavior of the Solar System. More details about the hardware and software involved in that computation can be found here.

Here are my arguments for why functional programming can, and should be utilized for computational science. The benefits are vast, and the cons are quickly going away. In my mind there's only one con:

Con: lack of language support in C / C++ / Fortran

At least in C++, this con is vanishing - as C++14/17 has added powerful facilities to support functional programming. You might need to write some library / support code yourself, but the language will be your friend. As an example, here is a (warning: plug) library that does immutable multi-dimensional arrays in C++: https://github.com/jzrake/ndarray-v2.

Also, here is a link to a good book on functional programming in C++, although it's not focused on science applications.

Here is my summary of what I believe are the pro's:

Pros:

• Correctness
• Understandability
• Performance

In terms of correctness, functional programs are manifestly well-posed: they force you to properly define the minimal state of your physics variables, and the function that advances that state forward in time:

int main()
{
auto state = initial_condition();

while (should_continue(state))
{
state = advance(state);
side_effects(state);
}
return 0;
}


Solving a partial differential equation (or ODE) is perfect for functional programming; you're just applying a pure function (advance) to the current solution to generate the next one.

In my experience, physics simulation software is by and large, burdened by poor state management. Usually, each stage of the algorithm operates on some piece of a shared (effectively global) state. This makes it difficult, or even impossible, to ensure the correct order of operations, leaving the software vulnerable to bugs that can manifest as seg-faults, or worse, error terms that do not crash your code but silently compromise the integrity of its science output. Attempting to manage shared state in a physics simulation also inhibits multi-threading - which is a problem for the future, as supercomputers are moving toward higher core counts, and scaling with MPI often tops out at ~100k tasks. In contrast, functional programming makes shared-memory parallelism trivial, because of immutability.

Performance is also improved in functional programming due to the lazy evaluation of algorithms (in C++, this means generating many types at compile time - often one for each application of a function). But it reduces the overhead of memory accesses and allocations, as well as eliminating virtual dispatch - allowing the compiler to optimize an entire algorithm by seeing at once all the function objects comprising it. In practice, you'll experiment with different arrangements of the evaluation points (where the algorithm result is cached to a memory buffer) to optimize use of CPU vs. memory allocations. This is rather easy due to the high locality (see the example below) of the algorithm stages compared to what you'll typically see in a module or class-based code.

Functional programs are easier to understand insofar as they trivialize the physics state. That is not to say their syntax is readily understandable by all of your colleagues! Authors should be careful to use well-named functions, and researchers in general should get accustomed to seeing algorithms expressed functionally rather than procedurally. I'll admit that the absence of control structures can be off-putting to some, but I don't think that should stop us from going into the future able to do better quality science on computers.

Below is a sample advance function, adapted from a finite-volume code using the ndarray-v2 package. Note the to_shared operators - these are the evaluation points I was alluding to earlier.

auto advance(const solution_state_t& state)
{
auto dt = determine_time_step_size(state);
auto du = state.u
| divide(state.vertices | volume_from_vertices)
| nd::map(recover_primitive)
| extrapolate_boundary_on_axis(0)
| nd::to_shared()
| compute_intercell_flux(0)
| nd::to_shared()
| nd::difference_on_axis(0)
| nd::multiply(-dt * mara::make_area(1.0));

return solution_state_t {
state.time + dt,
state.iteration + 1,
state.vertices,
state.u + du | nd::to_shared() };
}


R is a functional language & also a statistics (& now Machine learning) language and actually the number 1 language for statistics. It's not a HPC language though: it's not used for traditional "number crunching" like physics simulations etc. But it can be made to run on massive clusters (e.g. via MPI) for massive statistics simulations (MCMC) of machine learning.

Mathematica is also a functional language but it's core domain is symbolic computing rather than numerical computing.

In Julia you can also program in a functional style (next to procedural & their flavor of OO (multi-dispatch)) but it's not pure (the base data structures are all mutable (except for tuples), although there are some libraries with immutable functional data structures. More importantly, it's much slower than the procedural style so it's not used much.

I wouldn't call Scala a functional language but rather a object-functional hybrid. You can use many functional concepts in Scala. Scala is important for Cloud computing because of Spark (https://spark.apache.org/).

Note that modern Fortran has actually some elements of functional programming: it has strict pointer semantics (unlike C), you can have pure (no side effect) functions (& mark it as such) and you can have immutability. It even has smart indexing where you can specify conditions for matrix indices. This is query like and normally only found in high level language like R of LINQ in C# or via higher order filter functions in functional languages. So Fortran isn't so bad at all, it even has some pretty modern features (e.g. co-arrays) not found in many languages. In fact in future versions of Fortran I'd rather see more functional features added rather than OO-features (which is now usually the case) because OO in Fortran is really awkward and ugly.

The Pros are the "tools" built into each functional language: It is so easy to filter data, it is so easy to iterate over data and it is so much easier to come up with a clear and concise solution to your problems.

The only Con is, that you have to get your head around this new kind of thinking: It could take some time to learn what you have to know. Others in the SciComp domain don't really use those languages, which means you can't get that much support :(

If you are interested in functional-scientific-languages, I developed one https://ac1235.github.io