Functional Programming

The functional programming is a paradigm of programming which treats calculation like the evaluation of mathematical functions and avoids the mutable state and data. It underlines the application of the functions, contrary to the model of imperative Programmation which underlines changes of state.

It should be noted that a functional language is a computer programming language whose syntax and characteristics encourage the functional programming. The functional language oldest is the Lisp, created in 1958 by Mac Carthy. Lisp gave rise to more recent alternatives such as the Scheme (1975), the Common Lisp (1984). Other recent functional languages include the languages ml (1973), Haskell (1987), OCaml, Erlang, Clean and OZ or CDuce (2003). In the category of languages not ml, one should not forget XSLT and Anubis.

Machine of states and effects edge

Imperative programming

See also: imperative Programming

In imperative programming, one works on the model of the machines in states (cf Finite-state machine, Machine of Turing and Architecture of von Neumann), with a main memory and instructions which modify its state thanks to successive assignments. One can represent a program by a machine of states which represents the successive states of the memory. That requires for the programmer at any moment to know an exact model of the state of the memory which the program modifies.

In order to reduce the difficulty which this task represents, of many techniques intended to reduce the number of variables to be managed are used. One can quote among these techniques the variables known as automatic, whose carried is limited to the procedure in which they were defined and who are désallouées by the compiler at the exit of the procedure, the encapsulation of the data, at the origin of the structured programming, and the directed Programmation object.

It happens however that procedures must update certain variables or storage areas with an aim which is not directly related to their function, but only so that the shared data remain in a state envisaged by the programmer. One gathers these “remote” modifications under the generic term of effects edge. The effects edge, in imperative programming, which are more the rule than the exception, complicate the comprehension of the programs largely and are the source of many difficulties and bug S: indeed, if one forgets to update certain shared data, if the chronological order of the assignments by the various parts of the software is incorrect, or if a storage area were désallouée at the bad time, the program finds itself in an unforeseen state.

Functional programming

The functional programming is freed in a radical way of the effects edge by prohibiting any operation of assignment.

The functional paradigm does not use a machine of states to describe a program, but a fitment of functions which one can see as “block boxes” that one can imbricate the ones in the others. Each box having several parameters in entry but only one exit, it can leave only one possible value for each tuple values presented in entry. Thus, the functions do not introduce effects edge. A program is thus a application, with the mathematical direction, which gives one result for each whole of values in entry. This way of thinking, which is very different from the usual thought in imperative programming is one of the main causes of the difficulty that the programmers trained with the imperative languages have to approach the functional programming. However, it should be noted that it generally does not raise difficulties particular to the beginners who were never exposed to imperative languages. An important advantage of the functions without effect edge is the facility which one has to test them unitairement. In addition, the generalized use of an automatic management of memory via a Ramasse-miettes ( garbage collector in English) simplifies the task of the programmer.

In practice, for reasons of effectiveness, and owing to the fact that certain algorithms are expressed easily with a machine of states, certain functional languages authorize the imperative programming while allowing to specify that certain variables are assignable (or mutable according to the usual denomination), and thus the possibility of introducing effects edge locally. These languages are gathered under the name of impure functional languages .

The languages known as purely functional do not authorize the imperative programming. In fact, they are stripped of effects edge and are protected from the problems raised by the concurrent execution. One can see for example what was made within the framework of the language Erlang.

The implementation of the functional languages makes a sophisticated use of the pile because in order to free itself from the need for storing temporary data in tables they largely call upon the recursivity (made include the call of a function in its own definition). The recursivity can be made more effective using a technique called final Récursion ( tail-recursion in English), which consists to accumulate the intermediate results in a box memory of the pile and to pass it in parameter in the recursive call. This makes it possible to avoid piling up the recursive calls in the pile by replacing them by a simple succession of jumps. The code generated by the compiler is then similar to that generated by a loop in requirement. Certain languages like Design, OCaml and Anubis automatically optimize the recursive calls in this manner.

Referential transparency

The functional languages have like another property the referential Transparence. This term recovers the simple principle according to which the result of the program does not change if one replaces an expression by an expression of value equalizes . This principle is violated in the case of procedures with effects edge since such a procedure, not depending only on its arguments of entry, inevitably does not behave in a way identical to two moments given of the program. The referential transparency is, as we will see it, an extremely useful property.

Let us take an example. In C, if N indicates an aggregate variable containing an entirety to be incremented (thus a box visible memory by all the program), and Inc (K) a function which increases the value of N of the quantity K : int N = 2; int Inc (int K) {N = N + K; return N; }/* incrementing by effect edge * F (Inc (1) + Inc (1));

In this example, the function Inc (I) does not turn over the same value at the time of the two calls: one of the arguments of the function F will be worth 2 + 1 = 3 and the other 3 + 1 = 4 . It thus proves impossible to replace Inc (I) + Inc (I) by 2 * Inc (I) because the value of Inc (I) differs with each call. This behavior is basically different from that of a mathematical function. On an important program scale, that means that the replacement of function by another can require modifications at other places of the program, and that it can prove to be necessary of retester the entirety of the system, because one is not assured that such a replacement did not modify its total behavior. As the complexity of the system increases, the cost of a change increases too. Contrary, the property of referential transparency makes it possible to ensure that the replacement of a function by another equivalent is not likely to modify the total behavior of the program. In other words, they are mathematically equal. This property facilitates software maintenance. It also makes it possible to apply in an automatic way of the evidence of operation. It has finally for other favors appreciably to reduce the importance about execution, this one being ensured by the order of call of the functions; a corollary is that the parallelization of a functional program can be realized in an automatic way.

A greater expressivity

The functional languages employ standard and structures of data high level like the extensible lists. It is thus generally possible to easily carry out operations like the concatenation of lists, or the application of a function to a list - the course of the list being made in a recursive way -, in only one line of code.

A powerful mechanism of the functional languages is the use of the functions of a higher nature . A function is known as of a higher nature when it can take functions like argument (also called callback) and/or turn over a function like result. It is also said that the functions are objects of first class, which means that they are easy to handle as simply as the basic types. They correspond, in mathematics, with the functional calculuses. The operations of derivation and integration are two simple examples. The functions of a higher nature were studied by Alonzo Church and Stephen Kleene in the years 1930, starting from the formalism of the Lambda-calculation which influenced the design of several functional languages, in particular that of Haskell. However the Theory of the Closed Cartesian Categories characterizes the functions in a more modern way using the concept of universal Problème.

Popularity of the functional paradigm

Many are the experienced programmers who think that the functional programming offers advantages without equivalent in requirement. In spite of that, it remains little used apart from the academic world and of the hobbyists. In industrial environment, the languages Erlang (developed by Ericsson for needs for competing programming and requirements of robustness), Common Lisp and Scheme are used. But the development of the functional languages is limited by the deficit out of tools and libraries of fair average quality, and especially by the lack of trained programmers.

Lastly, the functional languages still suffer from a reputation of completely unjustified slowness today: certain compilers Design, like the compilers Stalin or Bigloo, the compilers for Common Lisp, the languages in the line of ml, such as Objectifies Caml or Haskell produces the achievable ones whose average performances are comparable or higher than those produced by the compilers C or C++.

Apart from the universities and specific industrial sectors, XSLT east can be a vector of popularization of the functional paradigm. Dedicated to the treatment XML, it makes it possible a programmer to preserve his imperative languages or objects, while discovering another logic, according to an elegance and a clearness which it cannot obtain in his usual syntaxes.

References