In the study [4], the amount of software development work was measured as a function of the number of machine instructions in 11 major software projects. It turned out that the dependence has the form of a power function with exponent 1.5. Articles [5, 6] described a mathematical model of the process of software development as a process of editing program code. Based on this model, a su cient condition was formulated, in which the development speed will not decrease with the growth of the project size. In this paper, the weakened version (theorem 2) of this su cient condition is proved. This theorem is proposed as a formal form of The OpenClosed Principle in the part of \Software entities (classes, modules, functions, etc.) should be ... closed for modi cation."
In the study [
Articles [
In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
with the growth of the project size. This example can be easily reproduced in
any programming language. Based on the model, in [
In this paper, the weakened version of this su cient condition is proposed
(see Theorem 2). Theorem 2 explains formally one part of The Open-Closed
Principle [
Formal Model of the Software Development Process
In section, there are key results of the articles [
The Set of Operations Let L be a formal language over the alphabet : The set of all words over the alphabet design as ; and the words themselves are symbols of the Greek alphabet ; ; ; length of the word design as j j: Remember, that is a semigroup. In other words, 8 ; 2 : 2 :
De nition 1 (Delete Symbol). Let's say that the word 0 is obtained by removing the symbol a 2 from the word = a , where ; 2 , and one of words or can be empty if and only if 0 can be written in the form 0 = : De nition 2 (Add symbol). Let's say that the word 0 is obtained by adding the symbol a 2 to the word = ; where ; 2 , and one of words or can be empty if and only if 0 can be written in the form 0 = a : Example 1. Consider the alphabet of C++. The word: void f() {
int } void f() { } is obtained by adding the character int to the word And, conversely, the second word can be obtained from the rst by removing the character int.
We want to introduce a formal de nition of the software development process over the language L: In the framework of this process, the same words from can appear. To distinguish between them we will not consider the words themselves, but the pairs ( ; n); where 2 ; n 2 N and denote such pairs ; and call the word the word ; if it is necessary.
Here and in the following text, we assume that the set of natural numbers N contains 0.
Let
S = f 1; 2; : : : ; ng; is a set of pairs ( i; ni); where i 2 ni are pairwise distinct.
Let's de ne four types of operations on the set of pairs S: ; ni 2 N; i 2 N; i 2 (1; 2; : : : ; n); all the 1. Let's say that the set of pairs S0 is obtained from S by adding to S the pair ( ; k); where 2 ; j j = 1; k 2 N; if and only if
S0 = S [ f( ; k)g; ( ; k) 2= S; and @( ; t) 2 S : k = t: 2. Let's say that the set of pairs S0 is obtained from S by deleting the pair ( ; k); where 2 ; k 2 N; if and only if
S0 = S n f( ; k)g; ( ; k) 2 S: 3. Let's say that the set of pairs S0 is obtained from S by replacing the pair ( ; k); where 2 ; k 2 N, by ( 0; k); where the word 0 was obtained from the word by adding the character a 2 in the sense of De nition 3, if and only if
S0 = S n f( ; k)g [ f( 0; k)g; ( ; k) 2 S: 4. Let's say that the set of pairs S0 is obtained from S by replacing the pair ( ; k); where 2 ; k 2 N, by ( 0; k); where the word 0 was obtained from the word by deleting the character a 2 in the sense of De nition 2, if and only if
S0 = S n f( ; k)g [ f( 0; k)g; ( ; k) 2 S: Remark 1. 8 2 there exists a sequence of operations the result of which is the pair ( ; n); for some n 2 N: Proof. Let 2 : Suppose that = a1a2 : : : an; where n > 0: Then we take the following set of operations: Using the operation of type 1, we add the pair (a1; n). Then, for each symbol ai; i > 1, with the help of an operation of type 3, we replace the pair (a1a2 : : : ai 1; n) by a pair (a1a2 : : : ai 1ai; n): Remark 2 (Existence of a set of operations.). Let S is an arbitrary set of pairs. Then there is a sequence of operations, the result of which is a given set of pairs. Proof. It is carried out by induction on the number of pairs in the set S and applying the previous remark to each pair. 2.2
De nition of the Software Development Process Let L^ be a subset of words of the programming language L over some alphabet : The subset L^ symbolizes the restrictions imposed by programmers on the language used in connection with the chosen programming methodology for example, procedural, object-oriented, etc. or the coding standards adopted in the development process, for example, the prohibition on the use of global variables.
S = f iji 2 (1; 2; : : : ; n)g; where n 2 N; i 2 ; is some set of pairs. S is called a program in the language L if and only if 8 i : i 2 L^: De nition 4 (The Software Development Process). The sequence of sets of pairs:
P0 c!1 P1 c!2 P2 c!1 : : : where P0 = ?; Pi (i > 0) are sets of pairs, and Pi is obtained from Pi 1 by using operation ci of one of the above types, while for all operations of type 1 all the added pairs have the form ( ; k); where 2 , k is a step number at which the operation was performed, is called the software development process P r: De nition 5. Let's say that the program P is obtained using the software development process P r; if 9i > 0 : Pi = P:
All further reasoning will be carried out on the assumption that there is some process of developing Pr: Remark 3. By de nition of the software development process, either pair ( ; k) does not exist, which was created in the software development process, either there is only one, for any k 2 N: Let's de ne for convenience the sequence of sets of removed pairs as: 1. D0 = ?; 2. Di = Di 1 [ f g; if was removed on the step i from the set Pi 1 by using operation of type 2, Di = Di 1 otherwise.
Proposition 1. 8n 2 N : Pn \ Dn = ?: The proof is by induction by virtue of constructing the set of pairs Pn: 2.3
Speed of the Software Development Process
Fi : (
N) ! N; i 2 1; 2; :::; n : on the set
N { the Cartesian product of the sets and N 1. F0( N) = 0: 2. Suppose that all functions Fj ; j i were already de ned. Let 2 N be some pair. Then { Fi( ) = 1; if the pair = ( ; i) was adding to Pi by operation of type 1 at step i: { Fi( ) = Fi 1( 0)+1; if the pair = ( ; k) was obtained from 0 = ( 0; k) by operation of type 3 or 4 at step i: { Fi( ) = Fi 1( ) + 1; if the pair = ( ; k) was removed at step i from the set Pi 1 by operation of type 2.
{ Fi( ) = Fi 1( ); otherwise.
De nition 6. Let 2 N: Then the complexity of writing the pair the step n in the software development process P r is called Fn( ): on It follows from the de nition of functions Fi; i 2 N; and proposition 2. De nition 7. Let 2 N: Then the asymptotic complexity of writing the pair in the software development process P r is called lim Fi( ): i!1 De nition 8. Let F : N ! R+ is some function from N to R+; where R+ = fx 2 R; x 0g: Let's say that software development process P r has speed not better, than F up to constant, if and only if 9k 2 N 8n > k jPnj
F (n) n: Here and below, jPnj denotes the cardinality of the set Pn: De nition 9. Let F : N ! R+ is some function from N to R+; where R+ = fx 2 R; x 0g: Let's say that software development process P r has speed not worse, than F up to constant, if and only if 9k 2 N 8n > k jPnj
F (n) n: De nition 10. Let F : N ! R+ is some function from N to R+: Let's say that the software development process P r has speed F up to constant if and only if 9C1 > 0; C2 > 0 9k 2 N 8n > k C1 F (n) n jPnj
C2 F (n) n: 2.4
The Su cient Condition for the Constant Speed of the Software Development Process
Corollary 1. By Proposition 4, the speed of any software development process can not be better than n:
Proposition 6. Suppose that 9C > 0; C 2 N 8n 2 N 8 2 Pn [ Dn : Fn( ) < C: jPn [ Dnj
n: n C n c n c jPn [ Dnj
n: jPn [ Dnj = jPnj + jDnj; (1 + C1)jPnj; n C(1 + C1)
jPnj: n C(1 + C1) jPnj n:
that is consequently, by the assumption of the theorem
jPnj + jDnj jPnj + C1 jPnj = (1 + C1)jPnj: Proof. The upper limit follows from propositions 1 and 4. The restriction from below follows directly from the condition and the proposition 5. Theorem 1 (The Su cient Condition for The Constant Speed of The Software Development Process). - Under the assumptions of Proposition 6, suppose that 9C1 > 0 9k1 2 N 8n k1 jDnj C1 jPnj: Then the software development process P r has a constant speed.
n: We get The Weakened Version of the Su The theorem 1 requires that the assimptotic complexity of writing each word of the program is bounded by some positive integer constant C: This requirement can be weakened.
Before we formulate a new su cient condition, we introduce several notation. Let P r be some software development process, C > 0; C 2 N; be some positive integer constant. Then 8n 2 N the set of all pairs in Pn; that were obtained no more than for C operations. By the assumption of the theorem 8n 2 N : n > k Or, the set of all pairs in Pn; that were obtained more than for C operations. Remark 4. By de nition of sets GnC and BnC ; n 2 N Theorem 2 (The Su cient Condition for The Constant Speed of The Software Development Process). In the notation of this section, suppose that 9C > 0; C 2 N 9C1 > 0 9k 2 N 8n > k
C1 ( X
Fn( ))
X Fn( ) + X Fn( ) 2GnC 2BnC 2Dn Then the software development process P r has a constant speed.
8n 2 N X 2Pn[Dn
GnC = f j 2 Pn : Fn( ) Cg BnC = f j 2 Pn : Fn( ) > Cg 8k 2 N GkC [ BkC = Pk; 8k 2 N GkC \ BkC = ;: X Fn( ) + X Fn( ) + X Fn( ) = n: 2GnC 2BnC 2Dn X Fn( ) + C1 2GnC
X Fn( ) 2GnC n: (1 + C1) ( X
Fn( ))
n:
By remark 4 jGnC j + jBnC j = jPnj follows that
By de nition 10 we get that the speed F of the software development process P r equals F (n) = 1: Remark 5. Theorem 1 is a special case of Theorem 2 Proof. Indeed, if in the conditions of Theorem 2 we take the process of the software development P R; for which the complexity of all words is less than some C > 0; C 2 N; then BnC = ; and by remark 4 GnC = Pn: We obtain the statement of theorem 1. 4 4.1
Practical Using
The Open-Closed Principle
The Open-Closed Principle (OCP) was rst described by Bertrand Meyer in [
\Software entities (classes, modules, functions, etc.) should be open for extension, but closed for modi cation."
OCP is one of ve principles for which Robert C. Martin o ered the acronym SOLID. It is believed that a program that has a \good" design must meet SOLID. However, till now in the community of programmers, there is no unanimous opinion concerning the obligatory observance of SOLID. For instance, Joel Spolsky, author of a popular blog and several books about programming, one of the developers of Visual Basic For Applications, in the 38th issue of Stack Over ow podcast said:
\Last week I was listening to a podcast on Hanselminutes, with Robert Martin talking about the SOLID principles . . . they all sounded to me like extremely bureaucratic programming that came from the mind of somebody that has not written a lot of code, frankly."
Nevertheless, SOLID and, in particular, OCP has a number of interesting consequences that require an answer to the question of the appropriateness of using SOLID.
For example, the following programming language constructions: { multiple-choice operator switch, { enumeration type enum, { chain of nested operators if-else-if as a rule, lead to violation of OCP.
Indeed, each of these constructions has a nite set of options. If the set of options is not exhaustive, then there is a possibility that in the future it will be necessary to modify such operator to add the missing option, which is a violation of OCP. In practice, one has to deal with situations where the entire set of options is unknown beforehand or changes in time. 4.2
The Open-Closed Principle and the Su In our opinion, the reasons for the ambiguous assessment of SOLID are the following: { The vagueness of the term \good" design. Everyone puts their meaning in the term \good" design. Therefore, it is di cult to establish a causal relationship between SOLID and own understanding of \good" design. { It is believed that SOLID are the principles of object-oriented programming.
So, for other methodologies, they are not applicable. { Martin claims that "It should be clear that no signi cant program can be 100% closed. . . . Since closure cannot be complete, it must be strategic. That is, the designer must choose the kinds of changes against which to close his design. This takes a certain amount of prescience derived from experience. The experienced designer knows the users and the industry well enough to judge the probability of di erent kinds of changes."
The su cient condition (theorem 2) allows one to answer some of these questions about OCP. Before proceeding to the answers, we note that OCP consists of two parts: 1. \Open For Extension". In this article, we will not touch Extension in any way. This is a topic for a separate article. 2. \Closed For Modi cation". Our further reasoning will only be about closure.
So, in OCP it is asserted that software entities should not be modi ed, but
not all, only those that are \strategically" important for the program being
created. In our model, the absence of modi cations of any word of the program
means, in accordance with the proposition 2, that the asymptotic complexity of
writing this word converges to some constant. In OCP, nothing is said about
the fact that the asymptotic complexity of writing any word should be limited
to some general constant. In [
However, there is another practice for \good" code [
In this case, the \strategic" closure in Theorem 2 is replaced by the requirement 9C > 0; C 2 N 9C1 > 0 9k 2 N 8n > k
C1 ( X Fn( ))
X Fn( ) +
Note also that in the case of Theorem 2, the complexity of all deleted words is taken into account. In OCP, nothing is said about this, so the following situation is possible: instead of editing, the entity is completely deleted, and instead of it, a new entity is created that takes into account the necessary changes. OCP is not broken, but the change is actually done.
Instead of a \good" design, Theorem 2 proposes a completely understandable result with obvious bene ts: the development speed will not fall as the size of the project grows.
In addition, Theorem 2 is valid for any programming language and is not tied to any software development methodology. 5
Conclusion
In this article, we have obtained a weakened su cient condition for the constant
speed of the software development process compared to the su cient condition
in the article [