👩🏼‍💼 🌖 😪 Automated recursive computing 😊 👆🏿 👼🏼

1. Introduction

The impact of subroutines (English subroutine) on programming without exaggeration is enormous. Introduced at the dawn of programming, they do not lose their relevance to this day. Without them, practical programming is simply impossible to imagine. Although from a formal point of view, they are not so necessary, because Pure theory is more interested in the properties of the algorithm than in its size.

In the theory of automata, the concept of nested automata, on the basis of which the practice of automaton subprograms (AMP) would be based, is rarely discussed. A similar (nested) hierarchical organization of automata, if considered, is very superficial. One of the reasons for this relationship may be the complexity of implementing a nested hierarchy at the hardware level [1, 2].

Programming is more flexible and provides more features than the practice of designing digital circuits. We have to make sure of this, considering further the software implementation of nested automata, and then the concept of automaton recursive algorithms.

For all the particular problems of forming a nested automaton model, its formal definition does not cause any problems. But, on the other hand, the choice of building a model hierarchy will certainly have a significant impact on its software implementation.

2. Automated recursive algorithms

In the previous article [3], only a formal definition of the control model of automatic programs (AP) was given without considering its implementation and specific examples of use. The possibility of implementing recursive algorithms was also mentioned. Next, using the factorial calculation example, firstly, we will consider the software implementation of the mechanisms for creating automatic routines within the framework of the object automaton C ++ paradigm, and secondly, since we will consider a recursive algorithm, we will essentially define a general principle for implementing any such algorithms in the framework of automatic programming.

Using recursive functions in an API can be quite simple. This demonstrates the code for listing 1 of the object machine program. Here the FSimpleFactorial automaton class is not a process, but an automaton routine, because contains the final state “00” (for more details on subprograms see [3]). At the level of behavior, the created automaton object corresponds to an automaton with one unconditional transition from the initial state “f0” to the final state “00” and a call to this transition within the framework of action y1 of the usual factorial factorial function (factorial (...)).

Listing 1. Calling the factorial function from the AMS

#include "lfsaappl.h"

class FSimpleFactorial : public LFsaAppl
{
public:
    double dF{1};		//	 
    FSimpleFactorial(int n);
    virtual ~FSimpleFactorial() {};
private:
    int nN{0};
    void y1();
    double factorial(int n);
};

#include "stdafx.h"
#include "FSimpleFactorial.h"

LArc TT_SimpleFactorial[] = {
    LArc("f0", "00", "--",	"y1"),		//
    LArc()
};
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
FSimpleFactorial::FSimpleFactorial(int n)
    :LFsaAppl(TT_SimpleFactorial, "FSimpleFactorial")
{
    nN = n;
}
//
void FSimpleFactorial::y1() { dF = factorial(nN); }

double FSimpleFactorial::factorial(int n)
{
    if (n == 0) return 1;
    else return n*factorial(n-1);
}

Since the FSimpleFactorial object is a nested automaton (subroutine), there must be a “wrapper” for it - the process that calls it. His example is a process spawned from an object named FTskSimple, whose code is shown in Listing 2.

Listing 2. The process for creating a nested automaton

#include "lfsaappl.h"

class FTskSimple : public LFsaAppl
{
public:
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTskSimple(nameFsa); }
    bool FCreationOfLinksForVariables();
    FTskSimple(string strNam);
    virtual ~FTskSimple();

    CVar    *pVarF;
    CVar    *pVarN;
    CVar    *pVarStart;

    LFsaAppl *pFCall{nullptr};
protected:
    int x1();
    void y1(); void y2(); void y3();
};

#include "stdafx.h"
#include "FTskSimple.h"
#include "FSimpleFactorial.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
LArc TT_Task[] = {
    LArc("st", "t1", "--",	"y1"),	//
    LArc("t1", "t2", "x1",	"y3"),	//
    LArc("t2", "t1", "--",	"y2"),	//
    };

FTskSimple::FTskSimple(string strNam)
    :LFsaAppl(TT_Task, strNam)
{
}

FTskSimple::~FTskSimple() { if (pFCall) delete pFCall; }

bool FTskSimple::FCreationOfLinksForVariables() {
    pVarF = CreateLocVar("dF", CLocVar::vtDouble, "factorial value");
    pVarN = CreateLocVar("nN", CLocVar::vtInteger, "input value");
    pVarStart = CreateLocVar("bStart", CLocVar::vtBool, "start?");
    return true;
}

int FTskSimple::x1() { return pVarStart->GetDataSrc(); }

void FTskSimple::y1()
{
    // reset flag start
    pVarStart->SetDataSrc(this, 0.0);
    // creating and calling a subroutine
    pFCall = new FSimpleFactorial(pVarN->GetDataSrc());
}
void FTskSimple::y2()
{
    // display factorial value
    pVarF->SetDataSrc(this, static_cast<FSimpleFactorial*>(pFCall)->dF);
}

void FTskSimple::y3()
{
    // reset flag start
    pVarStart->SetDataSrc(this, 0.0);
    static_cast<FSimpleFactorial*>(pFCall)->nN = pVarN->GetDataSrc();
    // creating and calling a subroutine
    pFCall->FCall(this);
}

This process at the transition from the initial state "st" to the state "t1" creates an object of type FSimpleFactorial, which will be the basis for creating a nested automaton (in the usual sense, calling a subprogram). Further, based on the current state of the local variable of the Boolean type bStart (see also the predicate code x1), it causes a transition from the state “t1” to “t2”. On this transition, the action of y1, firstly, resets the value of this local variable (to prevent false restart) and, secondly, calls the FCall procedure, which creates a nested automaton.

The interpreter of the automata of the VKPA environment organizes the transition to the initial state “f0” of the embedded automaton and the states of the latter become the current states of the process. The transition of the nested automaton to the final state “00” returns the calculation to the previous level of nesting, and in our case, to the completion of the transition of the top level automaton to the state t2. Then the process, on an unconditional transition from the state “t2” to the state “t1”, performs the action y2, which sets the result of calculating the factorial of the local variable of the process dF.

Note, and it is very important that the result of a nested automaton will be available only after completion of its work and transition to the next state of a top-level automaton. It will be possible to get it (result) through a pointer to an object of a nested automaton.

And everything would be fine if it weren't for the recursive function runtime. In comparison with the usual subroutine, due to nesting, as a rule, it is much larger and therefore can violate the conditional atomicity of the actions of automatic processes, the total execution time of which should fit into the value of a discrete clock cycle.

In our case, the calculation of the factorial is quite small and up to the maximum value of a double result for n = 170 fits into 1 microsecond. To calculate large values, one needs to switch to long arithmetic (see, for example, [4, 5]). At the same time, factorial computation time will increase even more and will almost guaranteed to go beyond the discrete clock cycle, affecting the speed of the remaining network machines operating in the non-preemptive multitasking mode and the reactivity of the response of the application as a whole, which will manifest itself in its “brakes”.

You can keep within a discrete clock cycle and get rid of the “brakes” defect by expanding the calculation into steps. For these purposes, it is convenient to translate the usual factorial algorithm into automatic form. True, due to the interpretation mode of automata, the calculation time will increase, but the temporal properties of the application will return to normal.

Listing 3 shows the calculation of the factorial in its usual form and in the form prepared for subsequent conversion to an automaton form. The latter explicitly represents atomic steps that are hidden in the source code of the program. In this case, we are talking about operators of the form y = f (...), where f is an ordinary or recursive program function. Such a record masks the operating time of the function and creates a false impression of the “instantaneous” assignment of the value of the variable y. In reality, there is neither one nor the other.

Listing 3. Software functions for calculating factorial

int factorial(int n)
{
    if (n == 0) return 1;
    else return n*factorial(n-1);
}

double Factorial(int n)
{
    double dF = 1;
    if (n == 0)
        return dF;
    else {
        double dPrev = Factorial(n-1);
        double dF = n*dPrev;
        return dF;
    }
}

In the framework of the concept of automatic programming, atomic actions (methods) of software automatic objects are considered conditionally instantaneous. And if only the total operating time of actions fits into a single cycle of discrete time of automaton space, then the software implementation corresponds to its formal model.

Remark 1. The total real time of operation of actions on one or another discrete clock cycle can vary quite strongly. In case of exceeding the cycle time, the VKPA environment tries to compensate for it at subsequent cycles of the automaton space operation, reducing, if possible, the discrete time of subsequent cycles.

In fig. Figure 1 shows a block diagram that includes markup that reflects the states of an equivalent finite state machine and the names of its predicates and actions. The automaton model itself in the form of a graph of the automaton is shown in Fig. 2.

Fig. 1. Block diagram of the recursive algorithm factorial

Fig. 2. An automaton model of a recursive factorial algorithm

The code for the automatic routine for calculating the factorial is shown in Listing 4. The comments in the transition table (TP) reflect the time of calculating the factorial in ms and the number of discrete steps spent on the calculation procedure for n = 170. And if the calculation time depends on the speed of the computing platform and / or on the type of project (debug / release), then the number of discrete steps (clock cycles) is determined only by the properties of the algorithm and can serve as an objective assessment of the speed of the algorithm, regardless of the form of its presentation and implementation.

In the case of an automaton model, the number of discrete ticks can be calculated quite simply and, having collected certain statistics, derive an analytical formula for the speed of the algorithm. In the meantime, such estimates are very approximate and are based on conclusions, often obtained as a result of rather complex reasoning.

Listing 4. Automated factorial routine

#include "lfsaappl.h"

class FFactRec : public LFsaAppl
{
public:
    FFactRec(int n);
    virtual ~FFactRec() { if (pFFactRec) delete pFFactRec; };
    int nN;		//	n
    double dF;	//	n!
private:
	int x1();
    void y1(); void y2(); void y3();
protected:
    void CallFactorial();
    double  PrevFactorial();
    FFactRec *pFFactRec{nullptr};
};

#include "stdafx.h"
#include "FFactRec.h"

#define QT_NO_DEBUG_OUTPUT

extern LArc TT_FactRec[];
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
//	   
FFactRec::FFactRec(int n)
    :LFsaAppl(TT_FactRec, "FFactRec")
{
    nN=n; dF=1;
}

LArc TT_FactRec[] = {
//        Debug    Release     Steps
//msec: 120-129   98-101        340
    LArc("f1", "00", "x1",	"y3"),	//
    LArc("f1", "f2", "^x1",	"y1"),	//
    LArc("f2", "00", "--",	"y2"),	//
    LArc()
};

int FFactRec::x1() { return nN==0; }
//   
void FFactRec::y1() { CallFactorial(); }
//	1.      
//	2.    
void FFactRec::y2() { dF = PrevFactorial()*nN; }
// 0!
void FFactRec::y3() { dF = 1; }
//   (  )
void FFactRec::CallFactorial()	{
    //	     
    pFFactRec = new FFactRec(nN-1);
    pFFactRec->FCall(this);
};
//    
double  FFactRec::PrevFactorial()	{ return pFFactRec->dF; };

3. Conclusions

I admit, due to the specifics of the tasks to be solved, I actually did not have to use, and develop recursive algorithms in real projects, except for training purposes and for testing the kernel for the implementation of nesting. Automated routines - almost constantly and in large numbers. Among them, the subroutines called inertial are especially interesting (for more details, see [3]). But they are supposed to devote a separate article to their consideration.

Recursive algorithms are an important part of program theory [6]. Without the implementation of routines and recursion, it is difficult to imagine an efficient and convenient computational model from all points of view. And to implement recursion, given the possibilities of object programming (see examples of the article), after creating a model of subprograms, it is not so difficult. You can, of course, using certain methods of converting recursion into a regular form, bypassing it using the same cycles. But it is preferable not to get rid of it stupidly, but to have direct mechanisms for its implementation. Of course, it will be slower, of course, more expensive in terms of resources (expenses of the same stack memory), but with the existing hardware capabilities this will not be so critical.

But recursive algorithms are also interesting as tests for evaluating the capabilities, universality, and effectiveness of algorithmic models. In this sense, the automaton model not only implements recursion quite effectively, but also adds “automaton chips” as a bonus - the ability to control the internal state of the recursive algorithm, count steps to evaluate performance, control the execution time of the algorithm, etc. etc.

Fighting recursion is pointless enough. It must be able to use. I’ll quote with which I completely agree: “At first glance, recursion may seem complicated. But in some cases, the recursive method is incredibly effective if everything is done correctly. However, it is sometimes better to use loops. Understanding both methods and the ability to use them effectively will help you in your work and will be an advantage in the interview ”[7]. I can only add on my own that automatic models of recursive algorithms make it possible, using the "automatic properties" of a computational model, to understand recursion, debug and refine such an algorithm much faster.

And the last one. Nevertheless, I would like to get an answer to the question - how are things going with coroutine recursion? I already asked it, but I haven’t received an answer ... After all, it’s one thing to create a million coroutine (see [8] for examples) and another to implement a recursive algorithm that has a nesting level that is not the same but high enough. And, it seems, the answer to this question interests not only me alone ... [9]

Literature

1. .., .. . I, . ., 1981, 2, 135-144. [ ], : mi.mathnet.ru/at5725 . . . ( 10.03.2020).
2. .., .. . II, . ., 1981, 3, 112-121. [ ], : mi.mathnet.ru/at5743 . . . ( 10.03.2020).
3. . [ ], : habr.com/ru/post/484588 . . . ( 10.03.2020).
4. . [ ], : habr.com/ru/post/255761 . . . ( 10.03.2020).
5. C++. [ ], : habr.com/ru/post/172285 . . . ( 10.03.2020).
6. . . : . . – .: , 1983. – 256 .
7. , ? Python. Ethan Jarrell. Recursion vs. Looping in Python [ ], : nuancesprog.ru/p/3325 . . . ( 15.03.2020).
8. Your first coroutine with Kotlin. [ ], : kotlinlang.org/docs/tutorials/coroutines/coroutines-basic-jvm.html . . . ( 18.03.2020).
9. . CyberForum.ru. [ ], : www.cyberforum.ru/unity/thread2479923.html . . . ( 18.03.2020).

Automated recursive computing

1. Introduction

2. Automated recursive algorithms

3. Conclusions

More articles: