🏍️ 👨🏻‍⚖️ 🧜🏾 Informatique récursive automatisée 🚂 🤲🏻 ☮️

1. Introduction

L'impact des sous-programmes (sous-programme anglais) sur la programmation sans exagération est énorme. Introduits à l'aube de la programmation, ils ne perdent pas leur pertinence à ce jour. Sans eux, une programmation pratique est tout simplement impossible à imaginer. Bien que d'un point de vue formel, ils ne sont pas si nécessaires, car La théorie pure s'intéresse plus aux propriétés de l'algorithme qu'à sa taille.

Dans la théorie des automates, le concept d'automates imbriqués, sur la base duquel la pratique des sous-programmes d'automates (AMP) serait basée, est rarement discuté. Une organisation hiérarchique similaire (imbriquée) des automates, si elle est considérée, est très superficielle. L'une des raisons de cette relation peut être la complexité de l'implémentation d'une hiérarchie imbriquée au niveau matériel [1, 2].

La programmation est plus flexible et offre plus de fonctionnalités que la pratique de conception de circuits numériques. Nous devons nous en assurer, compte tenu de la mise en œuvre logicielle des automates imbriqués, puis du concept d'algorithmes récursifs d'automates.

Pour tous les problèmes particuliers de formation d'un modèle d'automate imbriqué, sa définition formelle ne pose aucun problème. Mais, d'autre part, le choix de construire une hiérarchie de modèle aura certainement un impact significatif sur sa mise en œuvre logicielle.

2. Algorithmes récursifs automatisés

Dans l'article précédent [3], seule une définition formelle du modèle de contrôle des programmes automatiques (AP) était donnée sans tenir compte de sa mise en œuvre et des exemples spécifiques d'utilisation. La possibilité de mettre en œuvre des algorithmes récursifs a également été évoquée. Ensuite, en utilisant l'exemple de calcul factoriel, d'une part, nous considérerons l'implémentation logicielle des mécanismes de création de routines automatiques dans le cadre du paradigme C ++ de l'automate objet, et d'autre part, puisque nous considérerons un algorithme récursif, nous définirons essentiellement un principe général pour la mise en œuvre d'une telle algorithmes dans le cadre de la programmation automatique.

L'utilisation de fonctions récursives dans une API peut être assez simple. Cela illustre le code pour répertorier 1 du programme machine objet. Ici, la classe d'automate FSimpleFactorial n'est pas un processus, mais une routine d'automate, car contient l'état final "00" (pour plus de détails sur les sous-programmes, voir [3]). Au niveau du comportement, l'objet automate créé correspond à un automate avec une transition inconditionnelle de l'état initial "f0" à l'état final "00" et un appel à cette transition dans le cadre de l'action y1 de la fonction factorielle factorielle habituelle (factorielle (...)).

Listing 1. Appel de la fonction factorielle depuis l'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);
}

Étant donné que l'objet FSimpleFactorial est un automate imbriqué (sous-programme), il doit y avoir un «wrapper» pour lui - le processus qui l'appelle. Son exemple est un processus généré à partir d'un objet nommé FTskSimple, dont le code est affiché dans le listing 2.

Listing 2. Le processus de création d'un automate imbriqué

#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);
}

Ce processus à la transition de l'état initial "st" à l'état "t1" crée un objet de type FSimpleFactorial, qui servira de base à la création d'un automate imbriqué (au sens habituel, appeler un sous-programme). De plus, sur la base de l'état actuel de la variable locale de type booléen bStart (voir aussi le code de prédicat x1), il provoque une transition de l'état "t1" à "t2". Sur cette transition, l'action de y1, d'une part, réinitialise la valeur de cette variable locale (pour éviter un faux redémarrage) et, d'autre part, appelle la procédure FCall, qui crée un automate imbriqué.

L'interpréteur des automates de l'environnement VKPA organise la transition vers l'état initial "f0" de l'automate embarqué et les états de ce dernier deviennent les états actuels du processus. La transition de l'automate imbriqué à l'état final "00" ramène le calcul au niveau d'imbrication précédent, et dans notre cas, à l'achèvement de la transition de l'automate de niveau supérieur à l'état t2. Ensuite, le processus, lors d'une transition inconditionnelle de l'état "t2" à l'état "t1", effectue l'action y2, qui fixe le résultat du calcul de la factorielle de la variable locale du processus dF.

Remarque, et il est très important que le résultat d'un automate imbriqué ne soit disponible qu'après l'achèvement de son travail et la transition vers l'état suivant d'un automate de niveau supérieur. Il sera possible de l'obtenir (résultat) via un pointeur vers un objet d'un automate imbriqué.

Et tout irait bien sans le runtime de la fonction récursive. En comparaison avec le sous-programme habituel, en raison de l'imbrication, en règle générale, il est beaucoup plus grand et peut donc violer l'atomicité conditionnelle des actions des processus automatiques, dont le temps d'exécution total devrait correspondre à la valeur d'un cycle d'horloge discret.

Dans notre cas, le calcul de la factorielle est assez petit et jusqu'à la valeur maximale d'un double résultat pour n = 170 s'inscrit dans 1 microseconde. Pour calculer de grandes valeurs, il faut passer à l'arithmétique longue (voir, par exemple, [4, 5]). Dans le même temps, le temps de calcul factoriel augmentera encore plus et sera presque garanti d'aller au-delà du cycle d'horloge discret, affectant la vitesse des autres machines du réseau fonctionnant en mode multitâche non préemptif et la réactivité de la réponse de l'application dans son ensemble, qui se manifestera dans ses `` freins ''.

Vous pouvez rester dans un cycle d'horloge discret et vous débarrasser du défaut «freins» en étendant le calcul en étapes. À ces fins, il est commode de traduire l'algorithme factoriel habituel en forme automatique. Certes, en raison du mode d'interprétation des automates, le temps de calcul augmentera, mais les propriétés temporelles de l'application reviendront à la normale.

Le listing 3 montre le calcul de la factorielle sous sa forme habituelle et sous la forme préparée pour une conversion ultérieure en une forme automate. Ce dernier représente explicitement les étapes atomiques qui sont cachées dans le code source du programme. Dans ce cas, nous parlons d'opérateurs de la forme y = f (...), où f est une fonction de programme ordinaire ou récursive. Un tel enregistrement masque le temps de fonctionnement de la fonction et crée une fausse impression de l'affectation «instantanée» de la valeur de la variable y. En réalité, il n'y a ni l'un ni l'autre.

Listing 3. Fonctions logicielles de calcul factoriel

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;
    }
}

Dans le cadre du concept de programmation automatique, les actions (méthodes) atomiques des objets automatiques logiciels sont considérées conditionnellement instantanées. Et si seul le temps total de fonctionnement des actions s'inscrit dans un seul cycle de temps discret de l'espace automate, alors l'implémentation logicielle correspond à son modèle formel.

Remarque 1. Le temps réel total de fonctionnement des actions sur l'un ou l'autre cycle d'horloge discret peut varier assez fortement. En cas de dépassement du temps de cycle, l'environnement VKPA essaie de le compenser lors des cycles suivants du fonctionnement spatial de l'automate, réduisant, si possible, le temps discret des cycles suivants.

En figue. La figure 1 montre un schéma de principe qui inclut un balisage qui reflète les états d'une machine à états finis équivalente et les noms de ses prédicats et actions. Le modèle d'automate lui-même sous la forme d'un graphique de l'automate est illustré à la Fig. 2.

Fig. 1. Schéma fonctionnel de l'algorithme récursif factoriel

Fig. 2. Un modèle d'automate d'un algorithme factoriel récursif

Le code de la routine automatique de calcul de la factorielle est indiqué dans le listing 4. Les commentaires dans la table de transition (TP) reflètent le temps de calcul de la factorielle en ms et le nombre d'étapes discrètes consacrées à la procédure de calcul pour n = 170. Et si le temps de calcul dépend de la vitesse de la plateforme informatique et / ou du type de projet (débogage / release), alors le nombre d'étapes discrètes (cycles d'horloge) est déterminé uniquement par les propriétés de l'algorithme et peut servir d'évaluation objective de la vitesse de l'algorithme, quelle que soit la forme de sa présentation et de sa mise en œuvre.

Dans le cas d'un modèle d'automate, le nombre de ticks discrets peut être calculé assez simplement et, après avoir collecté certaines statistiques, dériver une formule analytique pour la vitesse de l'algorithme. Dans l'intervalle, ces estimations sont très approximatives et reposent sur des conclusions, souvent obtenues à la suite d'un raisonnement assez complexe.

Listing 4. Routine factorielle automatisée

#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

J'avoue qu'en raison des spécificités des tâches à résoudre, je n'ai en fait pas eu à utiliser et développer des algorithmes récursifs dans des projets réels, sauf à des fins de formation et pour tester le noyau pour l'implémentation de l'imbrication. Routines automatisées - presque constamment et en grand nombre. Parmi eux, les sous-programmes appelés inertiels sont particulièrement intéressants (pour plus de détails, voir [3]). Mais ils sont censés consacrer un article séparé à leur examen.

Les algorithmes récursifs sont une partie importante de la théorie des programmes [6]. Sans implémentation de routines et de récursivité, il est difficile d'imaginer un modèle de calcul efficace et pratique à tous points de vue. Et pour mettre en œuvre la récursivité, compte tenu des possibilités de programmation objet (voir exemples de l'article), après avoir créé un modèle de sous-programmes, ce n'est pas si difficile. Vous pouvez, bien sûr, utiliser certaines méthodes de conversion de la récursivité en une forme régulière, en la contournant en utilisant les mêmes cycles. Mais il est préférable de ne pas s'en débarrasser bêtement, mais d'avoir des mécanismes directs pour sa mise en œuvre. Bien sûr, cela sera plus lent, bien sûr, plus cher en termes de ressources (dépenses de la même mémoire de pile), mais avec les capacités matérielles existantes, cela ne sera pas si critique.

Mais les algorithmes récursifs sont également intéressants en tant que tests pour évaluer les capacités, l'universalité et l'efficacité des modèles algorithmiques. En ce sens, le modèle d'automate implémente non seulement la récursivité assez efficacement, mais ajoute également des «puces d'automate» en bonus - la possibilité de contrôler l'état interne de l'algorithme récursif, de compter les étapes pour évaluer les performances, de contrôler le temps d'exécution de l'algorithme, etc. etc.

Combattre la récursivité est assez inutile. Il doit pouvoir utiliser. Je citerai avec quoi je suis tout à fait d’accord: «À première vue, la récursivité peut sembler compliquée. Mais dans certains cas, la méthode récursive est incroyablement efficace si tout est fait correctement. Cependant, il est parfois préférable d'utiliser des boucles. La compréhension des deux méthodes et la capacité de les utiliser efficacement vous aideront dans votre travail et seront un avantage lors de l'entretien »[7]. Je peux seulement ajouter par moi-même que les modèles automatiques d'algorithmes récursifs permettent, en utilisant les "propriétés automatiques" d'un modèle de calcul, de comprendre la récursivité, de déboguer et d'affiner un tel algorithme beaucoup plus rapidement.

Et la dernière. Néanmoins, je voudrais obtenir une réponse à la question - comment ça se passe avec la récursion coroutine? Je l'ai déjà demandé, mais je n'ai pas reçu de réponse ... Après tout, c'est une chose de créer un million de coroutines (voir [8] pour des exemples) et une autre d'implémenter un algorithme récursif qui a un niveau d'imbrication qui n'est pas le même mais assez élevé. Et, semble-t-il, la réponse à cette question ne m'intéresse pas seulement ... [9]

Littérature

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).

Informatique récursive automatisée

1. Introduction

2. Algorithmes récursifs automatisés

3. Conclusions

More articles: