Is functional programming considered more "mathematical"? If so, why?

Question

Every now and then, I hear someone saying things like "functional programming languages are more mathematical". Is it so? If so, why and how? Is, for instance, Scheme more mathematical than Java or C? Or Haskell?

I cannot define precisely what is "mathematical", but I believe you can get the feeling.

Thanks!

Impasto

Answer 1

There are two common(*) models of computation: the Lambda Calculus (LC) model and the Turing Machine (TM) model.

Lambda Calculus approaches computation by representing it using a mathematical formalism in which results are produced through the composition of functions over a domain of types. LC is also related to Combinatory Logic, which is considered a more generalized approach to the same topic.

The Turing Machine model approaches computation by representing it as the manipulation of symbols stored on idealized storage using a body of basic operations (like addition, mutation, etc).

These different models of computation are the basis for different families of programming languages. Lambda Calculus has given rise to languages like ML, Scheme, and Haskell. The Turing Model has given rise to C, C++, Pascal, and others. As a generalization, most functional programming languages have a theoretical basis in lambda calculus.

Due to the nature of Lambda Calculus, certain proofs are possible about the behavior of systems built on its principles. In fact, provability (ie correctness) is an important concept in LC, and makes possible certain kinds of reasoning and conclusions about LC systems. LC is also related to (and relies on) type theory and category theory.

By contrast, Turing models rely less on type theory and more on structuring computation as a series of state transitions in the underlying model. Turing Machine models of computation are more difficult to make assertions about and do not lend themselves to the same kinds of mathematical proofs and manipulation that LC-based programs do. However, this does not mean that no such analysis is possible - some important aspects of TM models is used when studying virtualization and static analysis of programs.

Because functional programming relies on careful selection of types and transformation between types, FP can be perceived as more "mathematical".

(*) Other models of computation exist as well, but they are less relevant to this discussion.

Meteoric

It's important to mention that both these models are equivalent. – Garay

Answer 2

Pure functional programming languages are examples of a functional calculus and so in theory programs written in a functional language can be reasoned about in a mathematical sense. Ideally you'd like to be able to 'prove' the program is correct.

In practice such reasoning is very hard except in trivial cases, but it's still possible to some degree. You might be able to prove certain properties of the program, for example you might be able to prove that given all numeric inputs to the program, the output is always constrained within a certain range.

In non-functional languages with mutable state and side effects attempts to reason about a program and 'prove' correctness are all but impossible, at the moment at least. With non-functional programs you can think through the program and convince yourself parts of it are correct, and you can run unit tests that test certain inputs, but it's usually not possible to construct rigorous mathematical proofs about the behaviour of the program.

Shoreline

That's exactly it, the ability to prove the logic stems from mathematics directly. – Seineetmarne

Answer 3

I think one major reason is that pure functional languages have no side effects, i.e. no mutable state, they only map input parameters to result values, which is just what a mathematical function does.

Dudeen

Answer 4

The logic structures of functional programming is heavily based on lambda calculus. While it may not appear to be mathematical based solely on algebraic forms of math, it is written very easily from discrete mathematics.

In comparison to imperative programming, it doesn't prescribe exactly how to do something, but what must be done. This reflects topology.

Seineetmarne

I think This reflects topology. deserves some explanation! – Twelvetone

That's fair! Topology is the study of properties of an object that remain preserved under continuous deformations of the object. It typically concerns the spaces that functions map from and to, but not the functions themselves - it's valid for all possible functions that provide such a map. In functional programming, the spaces mapped to and from are specified but not the algorithms themselves. Imperative specifies the algorithms and you hope that it maps to the right space. – Seineetmarne

Answer 5

The mathematical feel of functional programming languages comes from a few different features. The most obvious is the name; "functional", i.e. using functions, which are fundamental to math. The other significant reason is that functional programming involves defining a collection of things that will always be true, which by their interactions achieve the desired computation -- this is similar to how mathematical proofs are done.

Micromillimeter