What is meant by the statement that functional programs are "more tractable mathematically"?

Question

What is meant by the statement that functional programs are "more tractable mathematically"?

Answer 1

It means that you can look at a piece of code and trace the flow of the program more easily.

Since a functional program operates not through a sequential ordering of statements, it simply returns the results of other function calls, and so you can trace one call to another more easily.

Also, proving correctness mathematically is much easier with functional programs.

Ok, so looking at the code might not be easier, but it would be easier to reason about what the code does. Well easier might not be the right word.

Answer 2

You can state conditions to be true or false or that variables have specific values, etc. at certain points in the execution of the code. For example, if you have an immutable object, you can state that its contents never changes. Then you can pass it to a method, and know that you can continue using it after the method returns and its contents will be the same as it was before you called the method.

Answer 3

Wikipedia's definition of functional programming begins with:

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data.

In other words, it's possible to mathematically prove things about functional programs that would be (nearly) impossible to prove about imperative programs.

Answer 4

All programs are ultimately one big number (presented in binary, of course.) Functional programs are easier to convert into that number than object-oriented programs (all other things being equal,) hence more mathematically tractable.

Answer 5

It means that you can more easily prove a program correct (e.g., through mathematical induction). Programs that are stateful (like most programs written in object-oriented languages) are extremely difficult to model through equations, hence it's difficult to reason about them through equations and mathematical theorems.

This may sound like theoretical mumbo-jumbo, but has important applications. Software that people depend their lives on (air traffic control, missile guidance systems, etc...) need to be proven correct, because traditional testing simply cannot cover all possible situations.

Answer 6

It means that you can more easily apply mathematical techniques to understand programs written in a functional language or style. For example, you can use the substitution model of evaluation to figure what this Erlang program evaluates to:

% function definitions
accumulate(F, Init, []) -> Init;
accumulate(F, Init, [H | T]) -> F(H, accumulate(F, Init, T).
Add = fun(x, y) -> x + y end.

% expression to evaluate
accumulate(Add, 0, [3, 2, 4]).

Using the substitution model, the last line is equivalent to each of the following:

Add(3, accumulate(Add, 0, [2, 4]).
3 + accumulate(Add, 0, [2, 4]).
3 + Add(2, accumulate(Add, 0, [4])).
3 + (2 + accumulate(Add, 0, [4])).
3 + (2 + Add(4, accumulate(Add, 0, [])).
3 + (2 + (4 + accumulate(Add, 0, []))).
3 + (2 + (4 + 0)).

Substituting variables with values like this works when you use a functional style, because once a variable has been assigned, its value will always be the same. This reflects the way variables are use in mathematics: every occurrence of a variable (in the same scope) always stands for the same value. In contrast, the value of i is different at different times when you execute the following C code:

int i;
for (i = 0; i < 10; i++) {
    ;
}

Answer 7

It's hard to guess what the original author meant, but one thing that distinguishes a pure functional language is that you can always substitute equals for equals and apply algebraic laws. This means that you can calculate with programs in much the same way that you calculuate with formulas in high-school algebra.

There are two good reasons to do this:

• You calculate a complicated fragment of code into something equivalent but simpler.

• You write a simple piece of code that "obviously has no faults", but it turns out to be inefficient. So you calculate an equivalent version that runs like a bat out of hell.

The past master of the second technique is Oxford professor Richard Bird. Some of his stuff, like his Sudoku solver or his implementation of Burrows-Wheeler compression (bzip2) is absolutely amazing. Read his papers!

Answer 8

In mathematics y=f(x) always gives you the same value y for a given x. ALWAYS, it doesn't matter if there's a moon eclipse, or Saturn is not aligned with Mars.

In mathematics, functions does not have side effects. That means that if you resolve function f(x), and then resolve function g(x), the first function does not have any influence on the second one at all. If g(2) is defined such that it will give you back a 4, nothing in the world can make g(2) suddenly give you back an 8, it's just not possible.

The value of a function only depends on the values of it's parameters.

But with typical programs, that rule is broken almost all the time; it's very common for many functions to have side effects. Imperative and Object Oriented languages strongly encourage that kind of programming.

With pure functional languages, that kind of problems are easier to avoid. In a functional language a function has the same property of a mathematical function, called "referential transparency", which means that you can replace a call to a function with it's know value, and the program will continue to compute correctly; if the value of a function with a given parameter is already known, it is not necessary that the function executes it's body since a function cannot have side effects.

This is useful for proving the correctness of a function, and also very helpful for optimization.

The following Wikipedia article may be of interest:

Referential transparency (computer science)