Hello, Habr! Today I would like to raise the question of the use of compositions and their role in programming. Those who are faced with functional languages, most likely heard of them, and those who have not encountered, perhaps, learn something new. I hope for an interesting discussion at the end of the article on their application. Escher to attract attention.



Let's start with the concept of the program. From a mathematical point of view, a program is a function. Sometimes this may not seem obvious. If the program is a function, then you should decide what its arguments are and what it returns. In the case of simple utilities like bc, everything is clear: the argument is an expression from stdin , and the result is the result in stdout . In more complex cases, it is also possible to come to the conclusion that the program is a function. Let us consider an example, a DBMS, in this case the program is also a function, with an argument it takes the memory allocated to it in the user space , and returns it, while continuously executing. Maybe a rather non-optimal example, but it is understandable.

If the program is a function, then you should consider what means of obtaining this function may be. It all depends on programming languages, they are such tools. And regardless of whether it is a functional language, procedural, imperative, declarative, etc., they are all characterized by the use of compositions, explicit or implicit. It's time to define the concept of composition. Let two functions be given and , one can construct a function from them applying a function to them : . Such a function F, which takes other functions as an argument, will be called a composition . And ways to build there may be many, each way - composition. Consider a couple of examples of compositions: the composition of branching and the composition of superposition.
')
Composition branching . Let two functions be given and as well as one predicate (the same function, but returning not the element of the set on which it is defined, but the values ​​"true" or "false"). There is such a function which . In this case, it is said that the function is obtained by the branch operation, we denote this operation as then . By applying the composition to the functions, you can get a new function, which is then used.

Composition of superposition . Let it be given function where - -ary function and there is such a function which is defined as . In this case will be considered as a result of a superposition operation. : .

Consider the prototypes of these operations in programming languages. Somewhere they are more pronounced, somewhere less. In the C language, the branch operation is obviously hidden in the control structure :

if(p(X)) f1(X); else f2(X); 

or ternary operator:

 p(X) ? f1(X) : f2(X); 

In the first case, the statement was considered, not expression, but this does not interfere with the presentation as, for example, the entire set of variables in scope. In LISP, the prototype of this composition would look like this:

 (if (p X) (f1 X) (f2 X)) 

And in Haskell, it looks like

 if p X then f1 X else f2 X 

or

 gx | px == True = f1 x | px == False = f2 x 

If we talk about the operation of superposition, it is even less noticeable in many programming languages, but nevertheless, it is omnipresent. The superposition operation in the C language allows us to make the following substitution

 f(f1(X), f2(X), f3(X)); 

On LISP, it would look like

 (f (f1 X) (f2 X) (f3 X)) 

Haskell is like

 f (f1 x) (f2 x) (f3 x) 

Immediately it should be noted that the arity of all the proposed functions must be unified, otherwise the application of the composition mechanism to them may be significantly difficult, i.e. X really is something like .
Obviously, the compositions are deeply “buried” in the syntax of programming languages, implicitly present in them. However, nothing new, as the reader who is well-versed in this matter can truly notice. Edsgar Dijkstra also noticed this in his book “The Discipline of Programming”.

Use of compositions

In connection with the foregoing, many questions arise. In particular, why are compositions not used explicitly? After all, the use of compositions explicitly could bring many advantages. Especially that it will be possible to consider the programming process itself, and therefore - to optimize the development of complex projects. After all, as a programmer is programming now? He does this as a painting artist. In other words, design decisions are made on the basis of his experience, premonition, colleagues' advice, and some personal aesthetic convictions. But this course of thinking can not be laid out just like that in a file with the program. Those. the program is there, but the train of thought that led to it is not. This is the first question. Why do languages ​​have such syntax as they are, why did the creators of the language put such a set of control structures in place? Why is their set dogmatized? What to do if you need to add other control structures.

These questions would help solve the means of applying and generating compositions. Since the solution of any arbitrarily complex task by a person is reduced to analysis / decomposition, and then synthesis, this process can be organically supported by the composition mechanism. After all, the compositions will be the very connecting element that will glue the parts into which the task is broken. Well, a person will have to break the task anyway, this is his prerogative, not the syntactic formulation of the task. Unfortunately, so far no language has been imprisoned under the concept of composition, it has not been noticed.

For a better understanding, consider an example of finding the greatest common divisor (GCD) using compositions. The calculator can find the remainder of the division ( ), implement integer division ( ), calculate the inequality predicate ( ), generate a zero ( ). All functions are defined on the set of natural numbers without zero. Thus, we have the following functions in the proposed algebra = { , , , , }. The reader may notice another feature - , the so-called selector function, which of arguments returns unchanged th, it is necessary since we work with -ary functions. In addition, cycling composition is available, let's call it . We give her definition. Let given -ary functions , and -ary predicate . Iteratively, each function performs the calculation of one of the arguments for the next iteration, so calculates , calculates etc. The iteration process continues until the value of the predicate is “true.” The arguments of the cycling operation are passed in the following order. . Value received at the last iteration will be the value of the function resulting from the composition. Also available is the composition of superposition described earlier. Then the algorithm for computing the gcd can be written as . Schematically it will look like this:


Thus, it becomes possible to formalize the algorithm itself "in the language of mathematics", and therefore it becomes possible to study it by mathematical means, which allows to reduce the share of unreasonable or unconsciously adopted design decisions because of what a person thinks in terms of the programming language in which he writes, instead of thinking about compositions that, in fact, are the basis of various languages.

The very compositional approach to the solution began to be investigated by A.I. Maltsev (Mal'tsev algebras), Academician Glushkov (algorithmic algebras). But they all work at the level of application of compositions, dogmatizing the set of compositions with which work is being conducted. An important improvement in the compositional approach would be the ability to obtain new compositions from existing ones, applying to them some meta-compositions. The topic is interesting, I don’t know that someone touched it, but about it next time. I hope I did not tire you.

The above is the subject of my research. Immediately I will make a remark that the compositional approach is not proposed to be used for trivial calculations, like the same NOD algorithm, or in projects where the share of calculations is negligible. I want to know very much what the community considers. Does the compositional approach have a future? Would you like to use compositions in practice? Do you need tools for this?

PS Suddenly I saw a recent post that also touches on the theme of compositions. I hope they complement each other.
PPS Many thanks to sekrasoft for helping to correct the article.