Cours Coroutines en Lua langage en PDF


Télécharger Cours Coroutines en Lua langage en PDF

★★★★★★★★★★3.5 étoiles sur 5 basé sur 1 votes.
Votez ce document:

Télécharger aussi :


Cours coroutines en Lua langage avec exemples [Eng]

...

Introduction

Le concept de coroutine est l'une des propositions les plus anciennes pour une abstraction de contrôle général. Il est attribué à Conway [Conway, 1963], qui a décrit les coroutines comme des sous-programmes qui agissent comme le programme maître, et a implémenté cette construction pour simplifier la coopération entre les analyseurs lexicaux et syntaxiques dans un Compilateur COBOL. La thèse de doctorat de Marlin [Marlin, 1980], largement reconnue comme une référence pour ce mécanisme, reprend les caractéristiques fondamentales d'une coroutine comme suit:

 € "Les valeurs de données locales à une routine persistent entre des appels successifs â €";

«L'exécution d'un coroutine est suspendue lorsque le contrôle quitte la zone, mais continue là où elle s'est arrêtée lorsque le contrôle rentre dans la coroutine à un stade ultérieur».

La pertinence du concept de coroutine pour exprimer plusieurs comportements de contrôle utiles a été perçue et explorée pendant quelques années dans un certain nombre de contextes, tels que la programmation concurrente, la simulation, le traitement de texte, l'intelligence artificielle et divers types de structures de données manipulation [Marlin, 1980, Pauli et Soffa, 1980]. Cependant, la commodité de fournir à un programmeur cette puissante abstraction de contrôle a été négligée par les concepteurs de langage à usage général. avec de rares exceptions comme Simaula [Birtwistle et al., 1976], BCPL [Moody et Richards, 1980], Modula-2 [Wirth, 1985] et Icon [Griswold et Griswold, 1996].

L'absence d'installations coroutines dans les langues dominantes peut être partiellement attribuée à l'absence d'une vision uniforme de ce concept, qui n'a jamais été défini avec précision. En outre, la plupart des descriptions de corotines trouvées dans la littérature, la thèse de Marlin inclus, sont toujours basées sur Simula, une mise en œuvre vraiment complexe de coroutines qui a contribué à l'idée fausse commune que les coroutines sont un â € ¢ Å "awkwardâ €? Construire, difficile à gérer et à comprendre.

Après une période d'oubli, nous pouvons maintenant observer un regain d'intérêt pour certaines formes de coroutines, notamment dans deux groupes différents. Le premier groupe correspond aux développeurs d'applications multitâches, qui étudient les avantages de la gestion coopérative des tâches comme alternative aux environnements multithread [Adya et al., 2002, Behren et al., 2003]. Dans ce scénario, les constructions simultanées qui prennent en charge le multitâche coopératif sont généralement fournies par des bibliothèques ou des ressources système telles que les fibres de Windows [Richter, 1997]. Il convient de noter que, bien que la description des mécanismes de concurrence utilisés dans ces travaux ne soit qu'une description de l'abstention coroutine, le terme coroutine n'est même pas mentionné.

Une autre résurgence des coroutines actuellement observée est dans le contexte des langages de script, notamment Lua, Python et Perl. Python [Schemenauer et al., 2001] a récemment incorporé une forme restreinte de coroutines qui permet le développement d'itérateurs simples, ou de générateurs, mais qui ne sont pas assez puissants pour implémenter des caractéristiques intéressantes qui peuvent être écrites avec de vraies coroutines, incluant multitâche au niveau de l'utilisateur. Un mécanisme similaire est proposé pour Perl [Conway, 2000]. Une approche différente a été suivie par les concepteurs de Lua, qui ont décidé d'une implémentation complète des coroutines.

Le but de ce travail est de présenter et de discuter les installations de Coroutine fournies par Lua. La section 2 donne une brève introduction au langage et décrit ses installations coraperines, fournissant une sémantique opérationnelle pour ce mécanisme. La section 3 illustre le pouvoir expressif des coroutines asymétriques de Lua en montrant quelques exemples pertinents de leur utilisation. La section 4 traite des coroutines dans d'autres langues. La section 5 présente nos conclusions.

  1. Lua Coroutines

Lua [Ierusalimschy et al., 1996, Figueiredo et al., 1996] est un langage de script léger qui prend en charge la programmation procédurale générale avec des facilités de description de données. Il est dynamiquement typé, étendu lexicalement, interprété à partir de bytecodes, et possède une gestion mémoire automatique avec garbage collection. Lua a été conçu à l'origine et est généralement utilisé, en tant que langage d'extension, intégré dans un programme hôte.

Lua a été conçu dès le départ pour être facilement intégré avec les logiciels écrits en C, C ++ et autres langages conventionnels. Lua est implémentée comme une petite bibliothèque de fonctions C, écrite en ANSI C, et compilée virtuellement non modifiée dans toutes les formes de plata disponibles actuellement. Avec l'interpréteur Lua, cette bibliothèque fournit un ensemble de fonctions (l'API C) qui permet au programme hôte de communiquer avec l'environnement Lua. Grâce à cette API, un programme hôte peut, par exemple, lire et écrire des variables Lua et appeler des fonctions Lua. En plus d'autoriser le code Lua à étendre une application hôte, l'API permet également l'extension de Lua elle-même en fournissant des fonctionnalités pour enregistrer les fonctions C appelées par Lua. Dans ce sens, Lua peut être considéré comme un cadre de langage pour construire des langages spécifiques à un domaine.

Lua met en œuvre le concept de coroutines asymétriques, souvent désignées comme semi-symétriques ou semi-corépondantes [Marlin, 1980, Dahl et al., 1972]. Les installations de coroutine asymétriques sont appelées parce qu'elles impliquent deux types d'opérations de transfert de contrôle: l'une pour (ré) invoquer une coroutine et l'autre pour la suspendre, cette dernière renvoyant le contrôle à l'invocateur de coroutine. Une coroutine asymétrique peut être considérée comme subordonnée

nate à son appelant, la relation entre eux étant similaire à celle entre une routine appelée et une routine d'appel. Une discipline de contrôle différente est mise en œuvre par des installations de coroutine symétriques, qui fournissent une seule opération de transfert pour passer le contrôle à la coroutine indiquée. Parce que les coroutines symétriques sont capables de passer le contrôle entre elles, on dit qu'elles fonctionnent au même niveau hiérarchique. Les arguments suivants justifient pourquoi Lua offre des coroutines asymétriques, au lieu de fournir des fonctions symétriques ou les deux mécanismes.

Il a été soutenu que les coroutines symétriques et asymétriques n'ont pas de puissance équivalente, et que les installations coroutines à usage général devraient fournir les deux construits [Marlin, 1980, Pauli et Soffa, 1980]. Cependant, il est facile de démontrer que les coré-dines symétriques peuvent être exprimées par des structures asymétriques (voir l'annexe A). Par conséquent, aucune puissance expressive n'est perdue si seules des coroutines asymétriques sont fournies. (En fait, la mise en œuvre de coroutines asymétriques sur des installations symétriques est tout aussi simple). Imposer les deux abstractions ne fait que compliquer la sémantique du langage. Dans Simula, par exemple, l'introduction de semicoroutines a conduit à des problèmes dans la compréhension des détails du séquençage de la corotine, et plusieurs tentatives pour décrire la sémantique des corolles Simula se sont révélées incohérentes [Marlin, 1980].

Puisque la puissance expressive n'est pas un problème, la préservation de deux des principales caractéristiques du Lua, la simplicité et la portabilité, constitue la raison principale de la mise en place de facilités asymétriques. La plupart des programmeurs ont déjà été exposés au concept de thread qui, comme une coroutine, représente une ligne d'exécution qui peut être interrompue et reprise plus tard au point où elle a été suspendue. Néanmoins, les mécanismes coroutines sont souvent décrits comme difficiles à comprendre. En fait, gérer de manière explicite le séquençage entre des coroutines symétriques n'est pas une tâche facile et nécessite un effort considérable de la part du programmeur. Même les programmeurs expérimentés peuvent avoir des difficultés à comprendre le flux de contrôle d'un programme qui emploie un nombre modéré de coroutines symétriques. D'autre part, les coroutines asymétriques se comportent vraiment comme des routines, en ce sens que le contrôle est toujours transféré à leurs appelants. Puisque même les programmeurs débutants sont familiers avec le concept d'une routine, le séquençage de contrôle avec des coroutines asymétriques semble beaucoup plus simple à gérer et à comprendre, en plus de permettre le développement de programmes plus structurés. Un argument similaire est utilisé dans les propositions de continuations partielles qui, comme les coroutines asymétriques, peuvent être composées comme des fonctions régulières [Danvy et Filinski, 1990, Queinnec et Serpette, 1991, Hieb et al., 1994].



L'autre motivation pour mettre en œuvre des coroutines asymétriques était la nécessité de préserver la facilité d'intégration de Lua avec son langage hôte (C) et sa portabilité. Lua et le code C peuvent librement s'appeler l'un l'autre; par conséquent, une application peut créer une chaîne d'appels de fonctions imbriquées dans laquelle les langues sont entrelacées. L'implémentation d'une fonctionnalité symétrique dans ce scénario impose la préservation de l'état C lorsqu'un sous-programme Lua est suspendu. Cette préservation n'est possible que si une installation de coroutine est également prévue pour C; mais une implémentation portable de coroutines pour C ne peut pas être écrite. D'un autre côté, nous n'avons pas besoin d'installations coraperines en C pour supporter les coroutines asymétriques de Lua; tout ce qui est nécessaire est une restriction qu'un coroutine ne peut pas céder tant qu'il y a une fonction C dans cette pile coroutine.

2.1. Lua Coroutine Equipements

Lua coroutine installations fournissent trois opérations de base:,, et. Comme

Dans la plupart des bibliothèques Lua, ces fonctions sont regroupées dans une table globale (table).

La fonction crée une nouvelle coroutine et attribue une

empiler pour son exécution. Il reçoit comme argument une fonction qui représente le corps principal de la coroutine et renvoie une référence coroutine. Créer une coroutine ne démarre pas son exécution; une nouvelle coroutine commence en état suspendu avec son point de continuation défini sur la première instruction dans son corps principal. Assez souvent, l'argument de

Les coroutines de Lua sont des valeurs de première classe; ils peuvent être stockés dans des variables, passés en arguments et renvoyés en tant que résultats. Il n'y a pas d'opération explicite pour supprimer une coroutine Lua; Comme toute autre valeur de Lua, les coroutines sont éliminées par la récupération de place.

Fonction (ré) active une coroutine, et reçoit comme requis

premier argument la référence coroutine. Une fois repris, un coroutine commence à s'exécuter à son point de continuation et s'exécute jusqu'à ce qu'il se bloque ou se termine. Dans les deux cas, le contrôle est renvoyé au point d'invocation de la coroutine.

Une coroutine se suspend en appelant la fonction; dans ce cas, le

l'état d'exécution de coroutine est enregistré et l'appel correspondant à re

tourne immédiatement. En implémentant une coroutine en tant que pile séparée, Lua permet aux appels de se produire même depuis l'intérieur des fonctions Lua imbriquées (c'est-à-dire, directement ou indiciellement appelées par la fonction principale coroutine). La prochaine fois que la coroutine est reprise, son exécution continuera à partir du point exact où elle a été suspendue.

Un coroutine se termine lorsque sa fonction principale revient; dans ce cas, la coroutine est censée être morte et ne peut plus être reprise. Une coroutine se termine également si une erreur se produit pendant son exécution. Quand une coroutine se termine normalement,

renvoie plus les valeurs renvoyées par la fonction principale coroutine. En cas d'erreur,

renvoie plus un message d'erreur.

Comme, la fonction auxiliaire crée une nouvelle

coroutine, mais au lieu de renvoyer la référence coroutine, elle renvoie une fonction qui reprend le coroutine. Tous les arguments passés à cette fonction sont des arguments supplémentaires

. La fonction renvoie également toutes les valeurs renvoyées par, sauf l'état code. Contrairement à, la fonction n'attrape pas les erreurs; toute erreur qui se produit à l'intérieur d'une coroutine est propagée à son appelant. Une implémentation simple de la fonction en utilisant les fonctions de base et est illustré ensuite:

Lua fournit une installation très pratique pour permettre à une coroutine et à son appelant d'échanger des données. Comme nous le verrons plus loin, cette fonctionnalité est très utile pour la mise en œuvre de générateurs, une abstraction de contrôle qui produit une séquence de valeurs, chacune à la fois. Pour illustrer cette fonctionnalité, considérons la coroutine créée par le code suivant:

 La première fois qu'un Coroutine est activé, tous les arguments supplémentaires reçus par l'invocation corre-spondent sont transmis à la fonction principale Coroutine. Si, par exemple, notre exemple de coroutine est activé en appelant la fonction coroutine recevra la valeur 20 in. Quand une coroutine se suspend, tout

Les éléments passés à la fonction sont renvoyés à son appelant. Dans notre exemple, la coroutine

La valeur de résultat 22 () est reçue par l'affectation.

Quand une coroutine est réactivée, tous les arguments supplémentaires sont renvoyés par le cor répondre à l'appel à la fonction. Poursuivant notre exemple, si nous réactivons le

coroutine en appelant la variable locale coroutine aura la valeur 23 ().

Enfin, quand un coroutine se termine, toutes les valeurs renvoyées par sa fonction principale vont à son dernier point d'invocation. Dans ce cas, la valeur de résultat 46 () est reçue par le affectation.

2.2. Une sémantique opérationnelle pour les Coroutines asymétriques Lua

Afin de clarifier les détails des coroutines asymétriques de Lua, nous développons maintenant une sémantique opératoire pour ce mécanisme. Cette sémantique opérationnelle est partiellement basée sur la sémantique pour les sous-populations fournies dans [Hieb et al., 1994]. Nous commençons par le même langage de base, une variante appel-par-valeur du -calcul étendu avec des affectations. L'ensemble des expressions dans ce langage de base () est en fait un sous-ensemble d'expressions Lua: constantes (c), variables (x), définitions de fonctions, appels de fonctions et affectations:

 Les expressions qui indiquent des valeurs () sont des constantes et des fonctions:

 Un magasin, mappant les variables aux valeurs, est inclus dans la définition du langage principal pour permettre les effets de bord:

Les règles d'évaluation () et de réécriture suivantes définissent une sémantique d'ordre ap plicative de gauche à droite pour évaluer le langage de base.

La règle 1 stipule que l'évaluation d'une variable remplit le contexte avec sa valeur associée dans. La Règle 2 décrit l'évaluation des applications; dans ce cas, -substitution est supposé afin de garantir qu'une nouvelle variable est insérée dans le magasin. Dans la règle 3, qui décrit la sémantique des affectations, on suppose que la variable existe déjà dans le magasin (c'est-à-dire qu'elle a été précédemment introduite par une abstraction).

Afin d'incorporer des coroutines asymétriques dans le langage, nous étendons l'ensemble des expressions avec des étiquettes, des expressions étiquetées et des opérateurs de coroutine:

 Parce que les étiquettes sont utilisées pour référencer les coroutines, nous les incluons dans l'ensemble des expressions qui indiquent des valeurs et étendons la définition du magasin, en permettant les mappages des étiquettes aux valeurs:

 Enfin, la définition des contextes d'évaluation doit intégrer les nouvelles expressions:

Nous pouvons maintenant développer des règles de réécriture qui décrivent la sémantique des coroutines Lua. Deux types de contextes d'évaluation sont utilisés: full contexts () et subcontexts (). UNE

le sous-contexte est un contexte d'évaluation qui ne contient pas de contextes étiquetés (). Il

correspond à une coroutine active la plus interne (c'est-à-dire, une coroutine dans laquelle il n'y a pas de coroutine imbriquée).

La règle 4 décrit l'action de créer une coroutine. Il crée une nouvelle étiquette pour représenter le coroutine et étend le magasin avec un mappage de cette étiquette à la fonction principale coroutine.



La règle 5 montre que l'opération produit une expression étiquetée,

correspond à une suite de coroutine obtenue du magasin. Cette continuation est

invoqué avec l'argument supplémentaire passé à. Afin d'éviter que la coroutine soit

réactivé, son libellé est mappé à une valeur non valide, représentée par.

La règle 6 décrit l'action de suspendre un coroutine. L'évaluation de l'expression de rendement doit se produire dans un sous-contexte étiqueté (), résultant de l'évaluation de l'expression de reprise qui a appelé la coroutine; cela garantit qu'un coroutine retourne le contrôle à son point d'appel correspondant. La suite de la coroutine suspendue est enregistrée dans le magasin. Cette continuation est représentée par une fonction dont le corps principal est

créé à partir du sous-contexte correspondant. L'argument passé à devient le

valeur de résultat obtenue en reprenant la coroutine.

La dernière règle définit la sémantique de la terminaison coroutine et montre que la valeur retournée par le corps principal coroutine devient la valeur de résultat obtenue par la dernière activation de la coroutine.

  1. Programmation avec Corayines Asymétriques Lua

Les coroutines asymétriques de Lua sont une construction expressive qui permet la mise en œuvre de plusieurs paradigmes de contrôle. En mettant en œuvre cette abstraction, Lua est capable de fournir des fonctionnalités pratiques pour un large éventail d'applications, tout en préservant son économie distinctive des concepts. Cette section décrit l'utilisation de coroutines asymétriques Lua pour implémenter deux fonctionnalités utiles: les générateurs et le multitâche coopératif.

3.1. Lua Coroutines en tant que générateurs

Un générateur est une abstraction de contrôle qui produit une séquence de valeurs, renvoyant une nouvelle valeur à son appelant pour chaque invocation. Une utilisation typique des générateurs consiste à implémenter des itérateurs, une abstraction de contrôle connexe qui permet de traverser une structure de données indépendamment de sa mise en œuvre interne [Liskov et al., 1977]. Outre la possibilité de conserver l'état, la possibilité d'échanger des données lors du transfert de contrôle fait des routines Lua une installation très pratique pour implémenter des itérateurs.

Pour illustrer ce type d'utilisation, le code suivant implémente un exemple classique: un itérateur qui parcourt un arbre binaire en pré-commande. Les nœuds d'arbres sont représentés par Lua

tables contenant trois champs:, et

...

Un exemple d'utilisation de l'itérateur binaire, la fusion de deux arbres, est montré

au dessous de. La fonction reçoit deux arbres binaires en tant qu'arguments. Il commence par créer

itérateurs pour les deux arbres (et) et la collecte de leurs plus petits éléments (et

). La boucle imprime la plus petite valeur et réinvite l'itérateur correspondant

pour obtenir son prochain élément, continuer jusqu'à ce que les éléments des deux arbres soient épuisés.

 Les générateurs sont également une construction pratique pour la programmation orientée vers les buts, comme implémentée, par exemple, pour résoudre des requêtes de type Prolog [Clocksin et Mellish, 1981] et pour faire des problèmes d'appariement de modèles. Dans ce scénario, un problème ou un objectif est soit un objectif primitif, soit une disjonction de solutions alternatives ou de sous-objectifs. Ces sous-objectifs sont, à leur tour, des conjonctions d'objectifs qui doivent être satisfaits successivement, chacun d'entre eux contribuant partiellement au résultat final. Dans les problèmes d'appariement de modèles, par exemple, les littéraux de chaînes sont des objectifs primitifs, les modèles alternatifs sont des disjonctions de sous-objectifs et les séquences de modèles sont des conjonctions de buts. Le processus d'unification dans Prolog est un exemple de but primitif, une relation Prolog est une disjonction et les règles Prolog sont des conjonctions de buts. La résolution d'un objectif implique généralement la mise en œuvre d'un mécanisme de retour en arrière qui essaie successivement chaque solution alternative jusqu'à ce qu'un résultat adéquat soit trouvé.

Les coroutines asymétriques Lua utilisées comme générateurs simplifient la mise en œuvre de ce type de comportement de contrôle, en évitant le code de réservation complexe nécessaire à la gestion des points de retour arrière explicites. Envelopper un but dans une coroutine Lua permet à un backtracker, implémenté comme une simple construction en boucle, de réessayer successivement (reprendre) un but jusqu'à ce qu'un résultat adéquat soit trouvé. Un objectif primitif peut être défini comme une fonction qui donne à chaque invocation l'un de ses résultats positifs. Une disjonction peut être mise en œuvre par une fonction qui invoque séquentiellement ses objectifs alternatifs. Une conjonction de deux sous-objectifs peut être définie comme une fonction qui itère sur le premier sous-objectif, en invoquant la seconde pour chaque résultat produit. Il vaut la peine de noter que, encore une fois, la possibilité de céder de l'intérieur des appels imbriqués est essentielle pour cette mise en œuvre concise et directe.

3.2. Multitâche au niveau de l'utilisateur

La pertinence des coroutines en tant que construction simultanée a été perçue par Wirth, qui les a introduites dans Modula-2 [Wirth, 1985] comme une installation de base pour soutenir le développement de programmes concurrents. En raison principalement de l'introduction du concept de threads, et de son adoption dans les langages traditionnels modernes, cette utilisation appropriée des corotines est, malheureusement, actuellement ignorée.

Un langage avec coroutines ne nécessite pas de constructions simultanées supplémentaires pour fournir des fonctionnalités multitâches: tout comme un thread, un coroutine représente une unité d'exécution qui a ses données privées et sa pile de contrôle, tout en partageant des données globales et d'autres ressources avec d'autres coroutines. Cependant, alors que le concept de thread est typiquement associé au multitâche préemptif, les coroutines fournissent un autre modèle de concurrence qui est essentiellement coopératif. Un logiciel doit explicitement demander à être suspendu pour permettre l'exécution d'un autre logiciel.

Le développement d'applications multithread correctes est largement reconnu comme une tâche complexe. Dans certains contextes, comme les systèmes d'exploitation et les applications en temps réel, où des réponses rapides sont essentielles, la planification préemptive des tâches est inévitable; dans ce cas, les programmeurs ayant une expertise considérable sont responsables de la mise en œuvre de stratégies de synchronisation adéquates. Les exigences de synchronisation de la plupart des applications concurrentes, cependant, ne sont pas critiques. De plus, les développeurs d'applications ont généralement peu ou pas d'expérience en programmation simultanée. Dans ce scénario, la facilité de développement est un problème pertinent, et un environnement multitâche coopératif, qui élimine les conflits dus aux conditions de course et minimise le besoin de synchronisation, semble beaucoup plus approprié.



225