Scientific math with functional languages?

Question

Are there any serious scientific math libraries made with functional programming languages? From the very nature of functional languages one would think that they are particularly suitable for math, but yet the well-known algorithms seem to be procedural.

For instance, the classic Numerical Recipes series is written pretty much in procedural way. LAPACK is almost de facto standard in many fields, but it's in Fortran and thus procedural or maybe OO, but definitely not functional.

Has anyone been able to transfer these kinds of well-known procedural algorithms to functional style?

Update: it seems to be so that functional languages are being used in symbolic calculations, e.g. in Mathematica. But, is there something inherently incompatible with numeric calculations and functional algorithms? Or is it just so that because imperative algorithms happened to be invented first, nobody has bothered to come up with functional equivalents?

Flagpole

phys.uu.nl/DU/num_recipes/lisp.1ed/senac/readme.htm – Kimberlykimberlyn

@jeffamaphone: Link has died. Fortunately there's a copy in the WayBack Machine: Numerical Recipes in Common Lisp. – Deboer

@Joonas_Pulakka: I'd say the reason why functional languages are more popular for symbolic calculations is because these calculations have a high degree of complexity, as opposed to traditional linear algebra which are really basic operations but involve large quantities of data. Functional languages are good at expressing complicated algorithms clearly, whereas imperative algorithms tend to quickly become unmaintainable as it grows complex. – Deboer

Answer 1

There's a Haskell library for numerical stuff in hackageDB: hmatrix. It draws from LAPACK, BLAS and GSL (GNU Scientific Library).

But you should keep in mind that imperative algorithms can be readily transferred into purely-functional languages using monads (more specifically, state transformers). In fact, any efficient, in-place implementation must generally use such a mechanism to provide mutable variables in purely-functional languages.

As for following a functional style, it isn't possible in many cases. For many problems, there aren't any (efficient) functional approaches known. Of course, you can get such algorithms to work in Haskell for example, but they won't look much different than if they were written in Matlab, Fortran or C.

EDIT:

It's both an apparent incompatibility, as well as an issue of which came first:

1. Efficient numerical algorithms usually require mutable data. While this is possible in a purely-functional setting, it is not as straightforward as in imperative languages. But the two computational models are perfectly equivalent.
2. The underlying machine (e.g. instruction set) has always been and still is imperative, with very few exceptions (!). Imperatively-coded algorithms are easier to analyze and optimize given the way the real machine is modeled.
3. While the underlying mathematics allow relatively easy derivations for functional solutions, you won't get an efficient algorithm (just as in the case of deriving imperative solutions directly from mathematics). Since most effort has been and still is directed towards imperative solutions, functional counterparts are simply unknown. By functional counterparts I mean code that properly expresses functional intent and style.
4. There's quite a lot of imperative code that can be reused. Much of it can be transcribed into a functional language using state transformers, though it would still look imperative.

I actually think a purely-functional language like Haskell could be beneficial for coding algorithms: one could unify the mathematical description, the algorithm itself and some sort of type-oriented proof (i.e. using the Curry-Howard isomorphism) in the same chunk of code.

Incontestable

Thanks, interesting! Is it something inherent with functional approach that it's not possible to solve math problems well with them, or is it just that the first good solutions happened to be imperative, and then nobody has bothered to come up with functional ones? – Flagpole

Answer 2

I'd use LAPACK as a black box from a functional language rather than trying to rewrite it. LAPACK has been tested, fine-tuned, optimized, etc. for decades by some extremely smart people. I wouldn't touch it.

Serafina

So would I. I was just curious about the reason for all major libraries seem to be imperative. Is it just because of historic reasons, or is there some inherent "incompatibility with math" in functional languages? – Flagpole

I wouldn't say there's an incompatibility between math and functional programming. Quite the opposite. When I use Mathematica, I write in a functional style without thinking about it. But with LAPACK in particular, they want very low-level control of the computer to squeeze out every bit of performance. – Serafina

Answer 3

In the spirit of the excellent Structure and Interpretation of Computer Programs, there is also Structure and Interpretation of Classical Mechanics. This book uses Scheme to clarify a lot of loose mathematical notations used in the variational approach to mechanics.

A cornerstone of the book is the scmutils package, which includes a functional approach to many computational tasks such as integration and minimization.

Iosep

Answer 4

Excellent question!

I have been one of the few pioneers of this field for several years now and we are only recently reaching the point where it is possible to get Fortran-like performance and Python-like brevity at the same time for a wide range of problems. Having examined all of the available functional languages and their implementations in great detail, I decided to focus my efforts on the statically-typed impure functional languages: the open source OCaml programming language and Microsoft's F# programming language for .NET.

My book OCaml for Scientists covers scientific computing with the OCaml programming language using Linux or Mac OS X. My book F# for Scientists covers scientific computing with Microsoft's F# programming language using Windows and Visual Studio. My company also sells F# for Numerics and F# for Visualization libraries that are written entirely in F# and make extensive use of functional programming both internally to improve brevity, clarity and maintainability and also externally to make the library easier to use. For example, first-class functions allow you to plot graphs really easily, e.g. ploting the sine function:

Plot([Function sin], (-5., 5.))

F# for Visualization will even attempt to visualize any value of any type so you can give it a matrix of arbitrary-precision rationals and it will display the result as typeset mathematics.

We have had great success writing code for scientific computing in a functional style in both the OCaml and F# languages. In particular, F# makes it easy to write high performance parallel code that is generic without any performance penalty for abstraction. So you can implement QR decomposition that works for matrices of any type (single precision, double precision, complex or even symbolic!) and even beat the performance of vendor-tuned libraries like the Intel MKL!

Finally, I should note that Mathematica went some way to blazing this trail long before I did. However, their solution was to combine a huge standard library of numerical and symbolic functions written in C with a conventional imperative style and provide a rather rudimentary functional programming language to call those functions. The main disadvantage of their approach is that general code written in Mathematica (i.e. where the time is not spent mostly in their standard library) is around 1,000x slower than C.

Cryptic

How have things changed in 5 years and living in an era of 'Big Data'? – Analytic

Answer 5

Several computer-algebra-systems (e.g. Maxima) utilize LISP-based languages internally to represent symbolic computations/syntax trees.

Examples of mathematical, functional languages:

http://en.wikipedia.org/wiki/J_(programming_language)

http://en.wikipedia.org/wiki/K_(programming_language)

Anyway, there are several mathematical problems and algorithms that can't be formulated well or efficient in functional style. An efficient implementation will always be imperative. Ex: Sieve of Eratosthenes

Wavelength

Sieve of Eratosthenes isn't that bad in Haskell, though not as efficient as it could be sieve (n:ns) = (n:) . sieve $ filter ((/= 0) . flip rem n) ns, primes = sieve [2..] – Inharmonic

Answer 6

i believe that mathematica utilizes its own functional language.

Gallows

utilize... is that like "use"? – Landaulet

lol, yes it is a monday and i did not get much sleep last night – Gallows

You should look at Guy Steele's talk "growing a language". Besides being a hilarious and insightful talk, you will look at your language use in a whole different light. ;) – Koblas

Answer 7

Define "serious". Remember that functional languages (other than LISP) are pretty new — Backes' original papers were only in the late 70's, and production engineering functional languages are quite new. The well-known and well-accepted numerical packages are all based on algorithms and codes starting in the late 60's and early 70's — BLAS was first published in 1979. Since, for production use, people tend to gravitate toward well-know and trusted packages, there's a major drive to the old FORTRAN codes.

But there are certainly people doing numeric processing with functional languages. As pointed out in another answer, Mathematica is increasingly a function numerical language and increasingly implemented in itself.

Tribulation

Mathematica is also more oriented towards mathematicians, while fortran, and for example, matlab, towards engineers (analitic vs. numerical). There are counterexamples of course, but this can be applied as a rough rule. – Gadolinium

Well, I used "serious" as a synonym for well-known/widespread/etc. Anyway, the fact that most well-known algorithms are imperative can at least partly be explained with history - the first useful algorithms were imperative, and everybody was happy with them, so why bother re-inventing functional counterparts? I was wondering if there's something inherent in functional languages that makes them less useful with math related algorithms. – Flagpole

I suspect the historical reason is the dominant one. The notion that functional languages have inherent inefficiencies that make them unsuited for numerical problems is urban legend, just as the notion that C wasn't suited for numerical programs versus FORTRAN was 20 years ago. There's probably a PhD or two just in making the translation and demonstrating it, though. – Tribulation