Total Functional Programming is pure functional programming with a guarantee that no expression will undefined at run time.
Some operations have an undefined result, for example:
There are a surprising number of operations one can perform in a piece of code that are actually partial.
In most popular functional programming systems today, it is possible to have a run time error when you divide by zero or get the head of an empty list, or a program that runs forever if you have endless recursion.
Total functional programming eliminates this possibility.
The benefit of total functional programming is that eliminating errors and non-termination can greatly simplify program analysis and optimization, for both humans and programs.
Strictly speaking the domain of division includes only non-zero denominators but we cannot always tell at compile time whether the value of expression may be zero; so, we expand the range of division to allow any number as the denominator for practicality.
Consider the function f(a,b,c) = a/(b - c). This function is undefined when b == c even if b and c were non-zero on function entry. Thus this is a partial function.
Having a type system or static analysis that can encode the concept that this function must not be called when b == c is impractical today; even requiring a parameter to be non-zero complicates matters greatly.
Rather than make everyone actually deal with partial functions by checking the inputs or results of partial functions, programming languages generally will either:
Two different kinds of partial programs seem to be the most commonly discussed:
There are some functions that could fit in either category, depending on implementation.
For example, an implementation of division that doesn't check for zero in the denominator could run forever adding zero to the denominator.
For partial functions in the first category, we can easily convert them into total functions by making the return value capture the partial result. For division we can return either a quotient result or a division by zero marker. The person doing the division must check whether it was successful before continuing too far.
Partial functions that may never return, however, are a different beast. Proving that they are total is impossible to do in general in the presence of general recursion so one must restrict recursion in some way to prevent these.
Total functional programming is probably unpopular because dealing with every possible partial function explicitly is a nuisance and not being able to recurse freely can cause some code contortions to make things fit a limited recursion capability.
One side of total functions is getting rid of functions that never return. Normally in strict languages we don't worry about this very much because when you find one you just fix it. So what's the big deal?
Well, one of the benefits of total functional programming is that expressions can be evaluated in any order, or even in parallel, as long the data dependencies between them are respected.
Consider:
f(x) = let y = f(x-1) in (if x = 0 then 0 else y*y)
In this case if the compiler decides to calculate y first, as an eager language typically would, the function will loop forever. In a lazy language you would typically be okay - calculation of y is deferred until it is needed, which it is not when x = 0.
In a total functional programming system, this kind of recursion is not allowed because it is impossible to prove for any recursive function that it will never run forever.
The Charity programming language restricts recursion by strictly separating infinite and finite data structures, and only providing a "fold" over finite data structures, and not allowing the user to write recursive functions themselves. To recurse you must either "fold" or "map" over a data structure.
Thus in Charity the only partial function issues to deal with are division by zero, out of memory, stuff like that.
One open question I have about Charity is whether you can pass a function to itself. My guess is NO but I haven't confirmed that.
One common issue with total functional style is that you must handle all possible errors, even when you know there is no error but cannot explain this to the system.
Let's say you define division so that it requires you to check whether or not the division was successful (not a division by zero). Even in an expression like x/2 you may still have to check for division by zero.
The same goes for the head of an empty list. Maybe you are running head [1,2,3] or somesuch. You know there will be success and yet you must handle failure.
So when you do know - what to do? Should you propagate this impossibility of failure up the call chain even though it appears impossible?
In many popular languages they throw an exception or error of some sort in these cases, and basically this means the programmer's assumption of non-error was violated.
It seems there is a trade-off here. On the one hand you can assume success to avoid superfluous error checking at compile time but allow runtime failures. Or you can forbid runtime errors but have superfluous compile/check time errors.
It may be that two operators/methods are needed - one that assumes success and one that you must check the result of. It may be possible one day with static analysis to validate uses of the "assumed success" operator/method. Adding extra operators comes with a big cost, too, in the learning curve of the code and the language.
One of the thoughts that might come up in the study of total functional programming is that total functions are in fact the normal state of functions and partial functions are the exception.
However, I am thinking this is not really the case. Many arithmetic functions only accept numbers, for example. Division by zero is undefined, making division a partial function.
Here's another perspective: functions are very often partial functions. However, if with static checking we can prove that no invocation of a function is undefined, we can treat the functions "as if" they are total. This is what is actually meant by "total functional programming."
When someone says a function is total, generally they really mean that the particular system they are using is able to enforce the domain of the function prior to running it.
The only functions that are total "as written" are the ones that can accept any object, such as the identity function or a constructor for a general data structure (like a list).