Generic programming: fundamental concepts in C++ template metaprogramming

Procedural programming has a few general and important constructs: conditional, loop, recursion.

In Functional programming, loop is not allowed because variable is not mutable. To loop, is to alter counter variables. In Functional programming, recursion is used to accumulate or iterate, in recursion the rule 'immutable variable' is not violated.

A programming construct is a fundamental concept of programming, it's a logical unit. A program is a hierarchical structure of programming constructs. There are 4 basic constructs: sequential, conditional, loop, function (lambda). What a program does is side effect of a program executing these constructs.

1. Sequential construct:
do A
do B
do C

2. What's a conditional construct?

if (condition) then
do A
else
do B
end if

This construct is allowed in both procedural and functional programming.

3. What's a loop? there are 2 kinds of loops based on its result (not side effect), infinite loop, finite loop. Often a loop can be decomposed into sequential and conditional constructs. For example a infinite loop

condition = true
while(condition) then
do A
do B
end while

a finite loop
condition = true
while(condition) then
do A
if(result=do B) condition = false // note that the value of condition is altered
end while

In functional programming, variable value is immutable once defined, to rewrite the above example with recursion, we need the help of a function construct.

4. define a function or a lambda

return_type function(argument_type)
function body
end function

bool do_b()
bool result = do B
return result
end do_b

void do_a_b()
do A
bool result = do_b
if(!result)
do_a_b
end do_a_b

As you can see, no variable value is ever changed after the point of definition (declaration and initialization), a key characteristic of functional programming.

C++ template provides powerful means to do functional programming, interestingly by design it has the same 'immutable variable' requirement. Let's see how we again transform the above example into C++ templates

bool do_B(){
}

template
class do_a_b{

do_a_b(){
do_A;
bool result = do_B;
do_a_b();
}

};

template
class do_a_b{
};

In summary, conditional is implemented with partial specialization, and loop is implemented with recursion. Why bother doing this? Functional programming as a form of generic programming, provides a higher level of concept correctness through programming logic.

References:
http://en.wikipedia.org/wiki/Tail_recursion