Programmation basée sur le flux

En programmation informatique , la programmation par flux ( FBP ) est un paradigme de programmation qui définit les applications comme des réseaux de processus de type boîte noire , qui échangent des données via des connexions prédéfinies par transmission de messages , les connexions étant spécifiées en externe aux processus. Ces processus de type boîte noire peuvent être reconnectés à l'infini pour former différentes applications sans avoir à être modifiés en interne. La FBP est donc naturellement orientée composants .

FBP est une forme particulière de programmation de flux de données basée sur des tampons délimités, des paquets d'informations avec des durées de vie définies, des ports nommés et une définition distincte des connexions.

La programmation basée sur les flux définit les applications à l'aide de la métaphore d'une « usine de données ». Elle considère une application non pas comme un processus unique et séquentiel, qui démarre à un moment donné et effectue ensuite une tâche à la fois jusqu'à ce qu'elle soit terminée, mais comme un réseau de processus asynchrones communiquant au moyen de flux de blocs de données structurés, appelés « paquets d'informations » (IP). Dans cette perspective, l'accent est mis sur les données de l'application et les transformations qui leur sont appliquées pour produire les résultats souhaités. Le réseau est défini en dehors des processus, comme une liste de connexions interprétée par un logiciel, généralement appelé « planificateur ».

Les processus communiquent au moyen de connexions à capacité fixe. Une connexion est attachée à un processus au moyen d'un port , dont le nom a été convenu entre le code du processus et la définition du réseau. Plusieurs processus peuvent exécuter le même morceau de code. À tout moment, une adresse IP donnée ne peut être « détenue » que par un seul processus, ou être en transit entre deux processus. Les ports peuvent être simples ou de type tableau, comme par exemple pour le port d'entrée du composant Collate décrit ci-dessous. C'est la combinaison de ports avec des processus asynchrones qui permet à de nombreuses fonctions primitives de traitement de données de longue durée, telles que Trier, Fusionner, Résumer, etc., d'être prises en charge sous la forme de boîtes noires logicielles .

Étant donné que les processus FBP peuvent continuer à s'exécuter tant qu'ils disposent de données sur lesquelles travailler et d'un endroit où placer leur sortie, les applications FBP s'exécutent généralement en moins de temps que les programmes conventionnels et utilisent de manière optimale tous les processeurs d'une machine, sans qu'aucune programmation spéciale ne soit requise pour y parvenir.

La définition du réseau est généralement schématique et convertie en une liste de connexions dans un langage ou une notation de niveau inférieur. FBP est souvent un langage de programmation visuel à ce niveau. Les définitions de réseau plus complexes ont une structure hiérarchique, construites à partir de sous-réseaux avec des connexions « collantes ». De nombreux autres langages/environnements d'exécution basés sur les flux sont construits autour de langages de programmation plus traditionnels, l' exemple le plus notable RaftLib qui utilise des opérateurs de type iostream C++ pour spécifier le graphe de flux.

FBP a beaucoup en commun avec le langage Linda dans la mesure où il s'agit, selon la terminologie de Gelernter et Carriero, d'un « langage de coordination » : il est essentiellement indépendant du langage. En effet, étant donné un ordonnanceur écrit dans un langage de niveau suffisamment bas, des composants écrits dans des langages différents peuvent être liés entre eux dans un même réseau. FBP se prête ainsi au concept de langages spécifiques à un domaine ou « mini-langages ».

FBP présente un « couplage de données », décrit dans l'article sur le couplage comme le type de couplage le plus lâche entre les composants. Le concept de couplage lâche est à son tour lié à celui des architectures orientées services , et FBP répond à un certain nombre de critères pour une telle architecture, bien qu'à un niveau plus fin que la plupart des exemples de cette architecture.

Le FBP promeut un style de spécifications fonctionnel de haut niveau qui simplifie le raisonnement sur le comportement du système. Un exemple de cela est le modèle de flux de données distribué pour spécifier et analyser de manière constructive la sémantique des protocoles multipartites distribués.

La programmation basée sur les flux a été inventée par J. Paul Morrison au début des années 1970 et initialement implémentée dans un logiciel pour une banque canadienne. À ses débuts, FBP a été fortement influencé par certains langages de simulation IBM de l'époque, en particulier GPSS , mais ses racines remontent à l'article fondateur de Conway sur ce qu'il a appelé les coroutines .

Le FBP a subi plusieurs changements de nom au fil des ans : la mise en œuvre originale s'appelait AMPS (Advanced Modular Processing System). Une grande application au Canada a été mise en service en 1975 et, en 2013, elle est utilisée en production en continu, quotidiennement, depuis près de 40 ans. IBM considérant que les idées derrière le FBP « ressemblaient trop à une loi de la nature » pour être brevetables, ils ont plutôt placé les concepts de base du FBP dans le domaine public, au moyen d'un bulletin de divulgation technique , « Data Responsive Modular, Interleaved Task Programming System », en 1971. Un article décrivant ses concepts et l'expérience de son utilisation a été publié en 1978 dans l' IBM Research IBM Systems Journal sous le nom de DSLM. Une deuxième mise en œuvre a été réalisée dans le cadre d'un projet conjoint d'IBM Canada et d'IBM Japon, sous le nom de « Data Flow Development Manager » (DFDM), et a été brièvement commercialisée au Japon à la fin des années 80 sous le nom de « Data Flow Programming Manager ».

Généralement, ces concepts étaient appelés chez IBM « Flux de données », mais ce terme était considéré comme trop général et finalement le nom « Programmation basée sur le flux » a été adopté.

Du début des années 80 à 1993, J. Paul Morrison et l'architecte d'IBM Wayne Stevens ont affiné et promu les concepts à la base de FBP. Stevens a écrit plusieurs articles décrivant et soutenant le concept FBP, et a inclus des éléments à ce sujet dans plusieurs de ses livres. . En 1994, Morrison a publié un livre décrivant FBP et fournissant des preuves empiriques que FBP a conduit à des temps de développement réduits.

Le diagramme suivant montre les principales entités d'un diagramme FBP (en dehors des paquets d'information). Un tel diagramme peut être converti directement en une liste de connexions, qui peut ensuite être exécutée par un moteur approprié (logiciel ou matériel).

A, B et C sont des processus exécutant des composants de code. O1, O2 et les deux IN sont des ports reliant les connexions M et N à leurs processus respectifs. Il est permis aux processus B et C d'exécuter le même code, donc chaque processus doit avoir son propre ensemble de stockage de travail, de blocs de contrôle, etc. Qu'ils partagent ou non du code, B et C sont libres d'utiliser les mêmes noms de port, car les noms de port n'ont de sens que dans les composants qui les référencent (et au niveau du réseau, bien sûr).

M et N sont ce que l'on appelle souvent des « tampons délimités » et ont une capacité fixe en termes de nombre d'adresses IP qu'ils peuvent contenir à tout moment.

Le concept de ports permet d'utiliser le même composant à plusieurs endroits du réseau. En combinaison avec une capacité de paramétrage, appelée paquets d'informations initiales (IIP), les ports offrent à FBP une capacité de réutilisation des composants, faisant de FBP une architecture basée sur des composants . FBP présente ainsi ce que Raoul de Campo et Nate Edwards d' IBM Research ont appelé la modularité configurable .

Les paquets d'informations ou IP sont alloués dans ce que l'on pourrait appeler un « espace IP » (tout comme les tuples de Linda sont alloués dans un « espace tuple ») et ont une durée de vie bien définie jusqu'à ce qu'ils soient éliminés et que leur espace soit récupéré - dans FBP, cela doit être une action explicite de la part d'un processus propriétaire. Les IP qui circulent sur une connexion donnée (en fait, ce sont leurs « handles » qui circulent) constituent un « flux », qui est généré et consommé de manière asynchrone - ce concept présente donc des similitudes avec le concept de lazy cons décrit dans l'article de 1976 de Friedman et Wise.

Les IP sont généralement des blocs de données structurés. Certaines IP peuvent toutefois ne contenir aucune donnée réelle, mais être utilisées simplement comme signaux. Les « IP entre crochets » en sont un exemple. Elles peuvent être utilisées pour regrouper des IP de données en modèles séquentiels au sein d'un flux, appelés « sous-flux ». Les sous-flux peuvent à leur tour être imbriqués. Les IP peuvent également être enchaînées pour former des « arbres IP », qui circulent sur le réseau sous forme d'objets uniques.

Le système de connexions et de processus décrit ci-dessus peut être « ramifié » jusqu'à n'importe quelle taille. Au cours du développement d'une application, des processus de surveillance peuvent être ajoutés entre des paires de processus, des processus peuvent être « éclatés » en sous-réseaux ou des simulations de processus peuvent être remplacées par la logique de processus réelle. FBP se prête donc au prototypage rapide .

Il s'agit en réalité d'une image de chaîne de montage du traitement des données : les IP qui circulent dans un réseau de processus peuvent être considérées comme des widgets qui se déplacent d'une station à l'autre dans une chaîne de montage. Les « machines » peuvent facilement être reconnectées, mises hors ligne pour être réparées, remplacées, etc. Curieusement, cette image est très similaire à celle des équipements d'enregistrement des unités qui étaient utilisés pour traiter les données avant l'arrivée des ordinateurs, à ceci près que les jeux de cartes devaient être transportés à la main d'une machine à l'autre.

Les implémentations de FBP peuvent être non préemptives ou préemptives - les implémentations antérieures avaient tendance à être non préemptives (mainframe et langage C), tandis que la dernière implémentation Java (voir ci-dessous) utilise la classe Java Thread et est préemptive.

Les composants FBP forment souvent des paires complémentaires. Cet exemple utilise deux de ces paires. Le problème décrit semble très simple tel qu'il est décrit en mots, mais il est en fait étonnamment difficile à résoudre en utilisant la logique procédurale conventionnelle. La tâche, appelée le « problème du télégramme », décrit à l'origine par Peter Naur , consiste à écrire un programme qui accepte des lignes de texte et génère des lignes de sortie contenant autant de mots que possible, où le nombre de caractères de chaque ligne ne dépasse pas une certaine longueur. Les mots ne peuvent pas être divisés et nous supposons qu'aucun mot n'est plus long que la taille des lignes de sortie. Cela est analogue au problème de retour à la ligne des mots dans les éditeurs de texte.

Dans la logique conventionnelle, le programmeur découvre rapidement que ni les structures d'entrée ni les structures de sortie ne peuvent être utilisées pour piloter la hiérarchie des appels du flux de contrôle . Dans FBP, en revanche, la description du problème elle-même suggère une solution :

• Les « mots » sont mentionnés explicitement dans la description du problème, il est donc raisonnable pour le concepteur de traiter les mots comme des paquets d'informations (IP)
• Dans FBP, il n'y a pas de hiérarchie d'appel unique, donc le programmeur n'est pas tenté de forcer un sous-modèle de la solution à être le niveau supérieur.

Voici la solution la plus naturelle dans FBP (il n'y a pas de solution « correcte » unique dans FBP, mais cela semble être une solution naturelle) :

où DC et RC signifient respectivement « DeCompose » et « ReCompose ».

Comme mentionné ci-dessus, les paquets d'informations initiaux (IIP) peuvent être utilisés pour spécifier des informations paramétriques telles que la longueur d'enregistrement de sortie souhaitée (requise par les deux composants les plus à droite) ou les noms de fichiers. Les IIP sont des blocs de données associés à un port dans la définition du réseau qui deviennent des IP « normales » lorsqu'une « réception » est émise pour le port concerné.

Ce type de programme implique de transmettre un fichier de « détails » (modifications, ajouts et suppressions) à un « fichier maître » et de produire (au moins) un fichier maître mis à jour et un ou plusieurs rapports. Les programmes de mise à jour sont généralement assez difficiles à coder en utilisant un code procédural synchrone, car deux flux d'entrée (parfois plus) doivent être synchronisés, même s'il peut y avoir des fichiers maîtres sans détails correspondants, ou vice versa.

Dans FBP, un composant réutilisable (Collate), basé sur l' idée d'enregistrement unitaire d'un Collator, facilite grandement l'écriture de ce type d'application car Collate fusionne les deux flux et insère des adresses IP entre crochets pour indiquer les niveaux de regroupement, simplifiant ainsi considérablement la logique en aval. Supposons qu'un flux (« masters » dans ce cas) se compose d'adresses IP avec des valeurs de clé de 1, 2 et 3, et que les adresses IP du deuxième flux (« details ») ont des valeurs de clé de 11, 12, 21, 31, 32, 33 et 41, où le premier chiffre correspond aux valeurs de clé principale. En utilisant des caractères entre crochets pour représenter les adresses IP « entre crochets », le flux de sortie collationné sera le suivant :

( m1 d11 d12 ) ( m2 d21 ) ( m3 d31 d32 d33 ) (d41) 

Comme il n'y avait pas de maître avec une valeur de 4, le dernier groupe est constitué d'un seul détail (plus des parenthèses).

La structure du flux ci-dessus peut être décrite succinctement à l'aide d'une notation de type BNF telle que

{ ( [m] d* ) }* 

Collate est une boîte noire réutilisable qui a seulement besoin de savoir où se trouvent les champs de contrôle dans ses adresses IP entrantes (même cela n'est pas strictement nécessaire car les processus de transformation peuvent être insérés en amont pour placer les champs de contrôle dans des emplacements standard), et peut en fait être généralisée à n'importe quel nombre de flux d'entrée et à n'importe quelle profondeur d'imbrication des crochets. Collate utilise un port de type tableau pour l'entrée, ce qui permet un nombre variable de flux d'entrée.

La programmation basée sur les flux prend en charge le multiplexage des processus de manière très naturelle. Étant donné que les composants sont en lecture seule, n'importe quel nombre d'instances d'un composant donné (« processus ») peuvent s'exécuter de manière asynchrone les unes avec les autres.

Lorsque les ordinateurs étaient généralement dotés d'un seul processeur, cela était utile lorsque de nombreuses E/S étaient effectuées. Aujourd'hui, les machines sont généralement dotées de plusieurs processeurs, cela commence à devenir utile également lorsque les processus sont gourmands en ressources CPU. Le diagramme de cette section montre un processus unique « Load Balancer » distribuant des données entre trois processus, respectivement étiquetés S1, S2 et S3, qui sont des instances d'un seul composant, qui à leur tour alimentent un seul processus selon le principe du « premier arrivé, premier servi ».

Dans ce schéma général, les requêtes (transactions) provenant des utilisateurs entrent dans le diagramme en haut à gauche et les réponses sont renvoyées en bas à gauche. Les « back-ends » (sur le côté droit) communiquent avec les systèmes d'autres sites, par exemple en utilisant CORBA , MQSeries , etc. Les connexions croisées représentent les requêtes qui n'ont pas besoin d'aller aux back-ends, ou les requêtes qui doivent parcourir le réseau plusieurs fois avant d'être renvoyées à l'utilisateur.

Étant donné que différentes demandes peuvent utiliser différents back-ends et peuvent nécessiter des durées de traitement différentes pour les back-ends (s'ils sont utilisés), des dispositions doivent être prises pour relier les données renvoyées aux transactions de demande appropriées, par exemple les tables de hachage ou les caches.

Le diagramme ci-dessus est schématique dans le sens où l'application finale peut contenir beaucoup plus de processus : des processus peuvent être insérés entre d'autres processus pour gérer les caches, afficher le trafic de connexion, surveiller le débit, etc. Les blocs du diagramme peuvent également représenter des « sous-réseaux » - de petits réseaux avec une ou plusieurs connexions ouvertes.

Cette méthodologie suppose qu'un programme doit être structuré comme une hiérarchie procédurale unique de sous-routines. Son point de départ est de décrire l'application comme un ensemble de « lignes principales », basées sur les structures de données d'entrée et de sortie. L'une de ces « lignes principales » est alors choisie pour piloter l'ensemble du programme, et les autres doivent être « inversées » pour les transformer en sous-routines (d'où le nom « inversion Jackson »). Cela entraîne parfois ce que l'on appelle un « conflit », nécessitant la division du programme en plusieurs programmes ou coroutines. Lors de l'utilisation de FBP, ce processus d'inversion n'est pas nécessaire, car chaque composant FBP peut être considéré comme une « ligne principale » distincte.

FBP et JSP partagent le concept de traitement d'un programme (ou de certains composants) comme un analyseur d'un flux d'entrée.

Dans les travaux ultérieurs de Jackson, Jackson System Development (JSD), les idées ont été développées plus avant.

Dans JSD, la conception est maintenue comme une conception de réseau jusqu'à l'étape finale d'implémentation. Le modèle est ensuite transformé en un ensemble de processus séquentiels en fonction du nombre de processeurs disponibles. Jackson discute de la possibilité d'exécuter directement le modèle de réseau qui existe avant cette étape, dans la section 1.3 de son livre (italiques ajoutées) :

La spécification produite à la fin de l'étape de synchronisation du système est, en principe, capable d'une exécution directe. L'environnement nécessaire contiendrait un processeur pour chaque processus, un périphérique équivalent à un tampon illimité pour chaque flux de données et des périphériques d'entrée et de sortie où le système est connecté au monde réel. Un tel environnement pourrait, bien entendu, être fourni par un logiciel approprié exécuté sur une machine suffisamment puissante. Parfois, une telle exécution directe de la spécification sera possible et peut même constituer un choix raisonnable.

FBP a été reconnu par MA Jackson comme une approche qui suit sa méthode de « décomposition de programme en processus séquentiels communiquant par un mécanisme de type coroutine »

WB Ackerman définit un langage applicatif comme un langage qui effectue tout son traitement au moyen d'opérateurs appliqués à des valeurs. Le premier langage applicatif connu était LISP.

Un composant FBP peut être considéré comme une fonction transformant son ou ses flux d'entrée en son ou ses flux de sortie. Ces fonctions sont ensuite combinées pour réaliser des transformations plus complexes, comme illustré ici :

Si nous étiquetons les flux, comme indiqué, avec des lettres minuscules, le diagramme ci-dessus peut être représenté succinctement comme suit :

c = G(F(a),F(b)); 

Tout comme dans la notation fonctionnelle, F peut être utilisé deux fois car il ne fonctionne qu'avec des valeurs et n'a donc aucun effet secondaire, dans FBP, deux instances d'un composant donné peuvent être exécutées simultanément et les composants FBP ne doivent donc pas non plus avoir d'effet secondaire. La notation fonctionnelle pourrait clairement être utilisée pour représenter au moins une partie d'un réseau FBP.

La question se pose alors de savoir si les composants FBP peuvent eux-mêmes être exprimés à l'aide d'une notation fonctionnelle. WH Burge a montré comment les expressions de flux peuvent être développées à l'aide d'un style de programmation récursif et applicatif, mais ce travail a été réalisé en termes de (flux de) valeurs atomiques. Dans FBP, il est nécessaire de pouvoir décrire et traiter des blocs de données structurés (IP FBP).

De plus, la plupart des systèmes applicatifs supposent que toutes les données sont disponibles en mémoire en même temps, alors que les applications FBP doivent être capables de traiter des flux de données de longue durée tout en utilisant des ressources limitées. Friedman et Wise ont suggéré un moyen de le faire en ajoutant le concept de « lazy cons » au travail de Burge. Cela a supprimé l'exigence que les deux arguments de « cons » soient disponibles au même instant. « Lazy cons » ne construit pas réellement un flux tant que ses deux arguments ne sont pas réalisés - avant cela, il enregistre simplement une « promesse » de le faire. Cela permet à un flux d'être réalisé dynamiquement depuis le début, mais avec un back-end non réalisé. La fin du flux reste non réalisée jusqu'à la toute fin du processus, tandis que le début est une séquence d'éléments de plus en plus longue.

De nombreux concepts de FBP semblent avoir été découverts indépendamment dans différents systèmes au fil des ans. Linda, mentionné ci-dessus, en fait partie. La différence entre les deux techniques est illustrée par la technique d'équilibrage de charge « école de piranhas » de Linda : dans FBP, cela nécessite un composant « équilibreur de charge » supplémentaire qui oriente les requêtes vers le composant d'une liste qui a le plus petit nombre d'adresses IP en attente de traitement. Il est clair que FBP et Linda sont étroitement liés, et l'un pourrait facilement être utilisé pour simuler l'autre.

Un objet en OOP peut être décrit comme une unité semi-autonome comprenant à la fois des informations et un comportement. Les objets communiquent au moyen d'« appels de méthodes », qui sont essentiellement des appels de sous-routines, effectués indirectement via la classe à laquelle appartient l'objet récepteur. Les données internes de l'objet ne sont accessibles qu'au moyen d'appels de méthodes, il s'agit donc d'une forme de masquage d'informations ou « d'encapsulation ». L'encapsulation, cependant, est antérieure à la POO - David Parnas a écrit l'un des articles fondateurs à ce sujet au début des années 70 - et est un concept de base en informatique. L'encapsulation est l'essence même d'un composant FBP, qui peut être considéré comme une boîte noire , effectuant une conversion de ses données d'entrée en données de sortie. Dans FBP, une partie de la spécification d'un composant concerne les formats de données et les structures de flux qu'il peut accepter, et ceux qu'il va générer. Cela constitue une forme de conception par contrat . De plus, les données d'une IP ne sont accessibles directement que par le processus actuellement propriétaire. L'encapsulation peut également être mise en œuvre au niveau du réseau, en faisant en sorte que les processus externes protègent les processus internes.

Un article de C. Ellis et S. Gibbs fait la distinction entre les objets actifs et les objets passifs. Les objets passifs comprennent des informations et un comportement, comme indiqué ci-dessus, mais ils ne peuvent pas déterminer le moment de ce comportement. Les objets actifs, en revanche, peuvent le faire. Dans leur article, Ellis et Gibbs affirment que les objets actifs ont beaucoup plus de potentiel pour le développement de systèmes maintenables que les objets passifs. Une application FBP peut être considérée comme une combinaison de ces deux types d'objets, où les processus FBP correspondraient aux objets actifs, tandis que les IP correspondraient aux objets passifs.

FBP considère l'acteur de Carl Hewitt comme un processus asynchrone avec 2 ports : un pour les messages d'entrée et un pour les signaux de contrôle. Un signal de contrôle est émis par l'acteur lui-même après chaque tour d'exécution. Le but de ce signal est d'éviter l'exécution parallèle du corps de l'acteur et ainsi de permettre d'accéder aux champs de l'objet acteur sans synchronisation.