Serveur © IRCAM - CENTRE POMPIDOU 1996-2005.
Tous droits réservés pour tous pays. All rights reserved.

Le système de traitement de signaux digitaux « junior »

Jean-Luc Delâtre

Rapport Ircam 24/80, 1980
Copyright © Ircam - Centre Georges-Pompidou 1980

I. But du système

On cherche à définir un logiciel commode et efficace permettant de se livrer à des manipulations complexes sur des signaux digitaux représentant la codification discrète de phénomènes continus, notamment dans le but de synthétiser la parole et la musique. Ces applications se ramènent à la transcription d'un flôt d'informations en entrée tel que texte, chaîne de phonèmes ou partition, en une ou plusieurs séquences d'échantillons qui expriment la réalisation physique du sens que l'on attache à ces informations.

Nous allons exposer comment, à partir de considérations générales relatives à la représentation discrète des phénoménes continus, il se dégage un ensemble de conditions qui fixent les grandes lignes de l'architecture d'un tel système. Dans le cadre ainsi défini nous examinerons ensuite l'incidence des contraintes imposées par la mise en oeuvre sur ordinateur, ces contraintes déterminant elles aussi une partie des caractéristiques finales. Enfin, la notion de transcription d'un flot d'informations en un autre amènera à choisir des moyens de commande qui facilitent l'analyse syntaxique des informations d'entrée, considérées comme un langage défini par une grammaire LL(1).

Cette analyse aboutit à la définition d'un langage par lequel il est possible de déclancher et de contrôler la production de flots d'échantillons en se référant au contenu d'un ou plusieurs flots d'informations en entrée, aussi bien qu'à l'écoulement d'un temps courant exprimé par rapport à une origine arbitraire 0, ou à des critères propres aux étapes intermédiaires des calculs.

II. Considérations préliminaires.

Première approche du problème.

Dans l'univers des signaux digitaux la dimension temporelle est en fait non continue et son « grain » minimum correspond à l'inverse de la fréquence d'échantillonnage, c'est a dire à la durée de la « tenue » d'une valeur échantillonnée. Rien n'est définissable qui ne soit localisé sur l'axe du temps (tout au moins quand à son effet final) par un repère exprimé en multiples de ce grain minimum, c'est pourquoi ce grain a été pris comme unité temporelle, comme « pas » élémentaire, dans le logiciel que nous allons décrire.

Supposons donc, sans à priori quand à la nature des travaux que nous désirons effectuer, que nous voulions exprimer l'évolution des valeurs d'un ensemble de variables le long d'une échelle de temps discrète. Il suffira pour chaque variable de spécifier à chaque pas l'expression qui décrit sa valeur, cette expression pourra faire référence aux valeurs d'autres variables, soit telles qu'elles étaient au pas précédent, soit telles qu'elles doivent être au présent pas. Ce dernier cas implique un ordre d'élaboration des valeurs qui n'introduise pas de cercle vicieux, certaines variables devant contenir en quelque sorte des résultats intermédiaires qui concourent à l'élaboration d'autres valeurs, elles ne peuvent elles-mêmes être définies par rapport au résultat auquel elles participent.

Bien que l'on puisse imaginer que l'expression qui décrit la valeur que doit prendre une variable varie arbitrairement à chaque pas, faisons l'hypothèse que pour des durées notables, l'expression qui décrit le contenu de telle ou telle variable soit la même. Les fluctuations éventuelles de la valeur résultante découleront donc des changements de valeurs des opérandes référencées dans l'expression et non pas de l'altération de l'expression elle-même.

Deux conséquences importantes apparaissent :

Dans le but de description que nous nous sommes assigné il n'est nécessaire que de spécifier à quels instants l'expression qui définit la valeur d'une variable doit changer et non plus de spécifier une expression à chaque pas.
On voit clairement que, durant un laps de temps pendant lequel on ne modifie aucune définition, si les valeurs de certaines variables doivent changer que la définition des valeurs de certaines variables font référence (explicitement ou implicitement) au temps courant, ou, que certaines expressions contiennent des références à des valeurs prises au pas antérieur. En effet, si toutes les expressions ne se référent qu'à des valeurs de variables telles qu'elles doivent être au présent pas, certaines variables (au moins une) qui apparaissent comme les « feuilles » des arborescences formées par les expressions, ne peuvent, sans introduire de cercle vicieux, être définies que comme étant des constantes, leurs valeurs déterminant celles de toutes les autres, toutes les valeurs de toutes les variables doivent être stables pour la durée de la période de stabilité des définitions. De plus, si les changements de valeur des variables doivent pouvoir se poursuivre pour des durées indéterminées, c'est que le graphe formé par les arcs « variable définie -> variable référencée » contient des cycles. En effet, si ce graphe était uniquement composé d'arborescences, après que le nombre de pas nécessaire à la propagation des valeurs des « feuilles » vers les « racines » se soit écoulé les valeurs des variables demeureraient stables.

Méthode générale qui se dégage.

Une même expression qui définit la valeur d'une variable devant donc être évaluée au cours de plusieurs pas successifs elle apparaît tout naturellement comme une sous-routine répétitive, chaque itération étant associée à l'écoulement d'une unité temporelle élémentaire. D'autre part, la définition du contenu d'une variable étant susceptible de changer, on voit que cette redéfinition consiste à lier une sous-routine itérative à une variable. Ce qui s'exprimera dans le langage que nous nous proposons de mettre en oeuvre par une instruction d'affectation de la forme

<variable>:=<expression>

L'usage de <expression> signifie non pas seulement que la variable apparaissant à gauche du signe ':=' reçoit la valeur que dénote à ce pas l'expression apparaissant à droite, mais également qu'elle recevra désormais à chaque « pas » la valeur correspondante.

Structure résultante du programme.

Afin de décrire l'évolution des valeurs de notre ensemble de variables il nous suffit donc de noter le long de l'axe du temps l'occurrence d'affectations de ce genre.

La succession des valeurs de chaque variable dépend donc d'une part de la valeur initiale (que l'on pourra supposer non significative) et de la nature et de la répartition dans le temps des affectations qui définissent son contenu. Nous pouvons alors par le choix de ces affectations et, tenant compte des interactions entre les définitions des différentes variables, construire n'importe quelle « trajectoire » possible du système représenté par l'ensemble des variables en jeu. Une telle « trajectoire » étant obtenue en calculant successivement pour chaque « pas » les valeurs prises par les variables.

Pour ce faire il suffit au cours d'un même pas de calculer les divers résultats intermédiaires dans l'ordre dans lequel ils sont nécessaires et de recommencer pour le pas suivant. La forme du programme est donc une simple boucle formée d'appels aux sous-routines de calcul, chaque sous-routine pouvant être conçue comme un processus indépendant.

Mise en oeuvre du choix de l'instant d'exécution des affectations.

Au cours d'un tel calcul l'échelonnement dans le temps des affectations se traduira par le choix de l'instant où s'effectuera la liaison entre chaque variable concernée et la sous-routine qui doit élaborer à chaque pas la valeur du contenu de la variable. C'est à dire que chaque choix se fait grâce à l'examen des valeurs de certaines variables, telles qu'elles étaient au pas précédent ou telles qu'elles doivent être au présent pas.

La procédure qui décide de la prise d'effet de chaque redéfinition de variable peut donc être vue elle aussi comme une sous-routine répétitive qui, au lieu de délivrer une valeur à chaque pas teste si l'instant de prise d'effet d'une redéfinition particulière est atteint et si oui effectue la liaison correspondante entre la variable redéfinie et sa nouvelle valeur.

III. Contraintes techniques.

On s'aperçoit cependant qu'une telle description, si elle est conceptuellement bien représentative de l'effet désiré, implique un usage excessif des ressources de calcul. D'autant plus qu'il est intuitivement évident qu'il n'est pas besoin de tester si un instant est atteint longtemps avant que cela soit plausible, en particulier si sa position dans le temps est exactement connue.

Nous allons donc être amenés à définir un mécanisme qui puisse nous permettre de garder toute la généralité qui découle des concepts précédemment exposés mais qui également minimise l'usage des ressources de calcul.

Notion de calcul redondant.

Comme nous l'avons dit il n'est pas besoin d'exécuter une action quelconque quand son résultat est implicitement déjà connu, ce qui peut se résumer à une seule condition :

le dit résultat a déjà été élaboré une fois et les valeurs ayant servi à cette élaboration n'ont pas changé.

En effet, si il apparaît, par exemple, que la comparaison du temps courant à une limite constante est une action pour laquelle au moins une valeur servant à l'élaboration est toujours changeante, il s'agit là d'une fonction à effet de « seuil » qui délivre une valeur duale oui/non qui elle ne change pas tant que le seuil n'est pas franchi. Si, pour n'importe quelle fonction à effet de seuil, il est possible de prédire que le seuil n'a pas été franchi, le résultat issu de cette fonction sera inchangé en dépit des fluctuations des valeurs qui servent à son élaboration.

Détection des valeurs stables.

Donc pour toute action élémentaire nous allons essayer de déterminer si son résultat sera inchangé au prochain pas, et si oui, pour quel nombre de pas consécutifs, afin de nous abstenir de le recalculer inutilement. Dans ce but il nous sera nécessaire de connaître toutes les valeurs qui concourent à son élaboration et notamment, pour chacune de celles-ci, au cas où elle serait stable, la durée en nombre de pas de cette stabilité et, si la fonction examinée est à effet de seuil, le type de progression des arguments qui induisent l'effet de seuil. Nous nous limiterons à la reconnaissance de progressions arithmétiques simples.

Un résultat qui ne dérive pas immédiatement d'un effet de seuil est stable pour un nombre de pas égal à la durée de stabilité de son opérande le moins stable.

Un résultat qui dérive d'un effet de seuil est stable pour la durée estimée nécessaire à ce que le franchissement devienne plausible, et qui se calcule de manière ad hoc selon la nature de l'effet de seuil, par exemple la durée de stabilité de la comparaison d'une progression arithmétique et d'un autre type de valeur est égale :

si le seuil est déjà franchi, au minimum de la durée de stabilité de la définition de la progression arithmétique et de la durée de stabilité de la variable définissant le seuil.
si le seuil n'est pas encore franchi, au minimum de la durée définie ci-dessus et du nombre de pas nécessaire pour atteindre le seuil.

Stratégie d'économie.

Toute instance de sous-routine dont le résultat est connu jusqu'à un certain instant est extraite de la boucle d'appel des sous-routines et mise dans une file d'attente jusqu'à cet instant. Une routine de service se chargeant de réintroduire dans la boucle au moment opportun les sous-routines ainsi suspendues.

Cette gestion des stabilisations de valeurs sera effectuée grâce à des liens qui identifient dans chaque sous-routine élémentaire quels sont les opérandes de celle-ci et quels sont les usages du résultat. Pour que cette technique soit réellement efficace il est exclu d'avoir à tester les conditions de stabilité à chaque calcul c'est pourquoi on procédera à l'envers, c'est à dire que seules certaines routines auront l'initiative de ces tests de stabilité et propageront cette information vers celles qui font usage de leur résultat.

Ayant cette structure à notre disposition nous nous apercevons qu'une autre amélioration est possible : si tous les usages d'un résultat sont suspendus il est inutile de le calculer pendant la période correspondant à la durée minimum de suspension en vigueur parmi ses usages.

Cas particulier des boucles de rétroaction.

On notera que selon ce mécanisme les groupes de sous-routines formant des boucles de rétroaction ne seront jamais suspendus, même si tous leurs usages le sont. Il n'a pas été jugé utile d'essayer, de remédier à cela car suspendre le calcul de ces boucles poserait le problème de la détermination des valeurs de reprise et entrainerait des calculs plus couteux que la simple continuation du déroulement de la boucle. Cependant les cas les plus simples tels que rampes et oscillateurs à pas fixe peuvent donner lieu à suspension, pourvu qu'ils soient décrits comme sous-routines élémentaires ou comme fonctions du temps courant, auquel cas le calcul des valeurs de reprise, qui se ramène à une simple multiplication, sera traité de facon ad hoc.

Purge des ressources en fin d'utilisation.

D'autre part ces mêmes liens serviront également à déterminer l'obsolescence des sous-routines et à permettre la libération des ressources mémoire associées à celles qui, du fait des redéfinitions de contenus de variables, n'auront plus aucun usage.

Si l'impossibilité de suspendre des structures circulaires est sans grand inconvénient il n'en va pas de même en ce qui concerne leur cessation d'usage, mais ce problème sera traité de façon légèrement différente par une technique de récupération (« garbage collection »), selon la méthode suivante :

chaque instance de sous-routine possède un indicateur « d'utilité »
cet indicateur est positionné à + quand une nouvelle instance est créee
quand il s'avère plausible que certaines sous-routines sont devenues inutiles, i.e. après que pour la première fois une instance de sous-routine soit devenue obsoléte du fait des redéfinitions de contenus de variables, tous les indicateurs d'utilité (qui à ce moment valent +) sont basculés à -, et, les sous-routines qui communiquent des résultats à l'utilisateur étant considérées comme toujours utiles, on positionne leurs indicateurs à + et à partir d'elles on marque comme utiles tous leurs opérandes ainsi que les opérandes de leurs opérandes, et ainsi de suite...
afin de ne pas distraire entièrement les ressources de calcul pour cette opération, elle est exécutée pas à pas et un certain nombre de pas est exécuté à chaque cycle de calcul, qui dépend du nombre de redéfinitions de variables ayant eu lieu. On essaye de cette façon d'équilibrer le rapport entre les ressources de calcul ainsi consommées et celles que l'on espère économiser en détectant et éliminant des boucles de rétroaction désormais inutiles.
quand on a parcouru de façon exhaustive les arborescences d'opérandes ayant pour racines les sous-routines qui communiquent les résultats finaux, on est certain que toutes les instances de sous-routines réellement utiles ont été marquées et on purge toutes les instances qui ont conservé l' indicateur -. Cette opération doit s'effectuer en une seule passe car l'exécution de boucles de rétroactions partiellement détruites ne manquerait pas de provoquer des erreurs. Cependant, toutes les instances concernées étant par définition non suspensibles (les instances de sous-routines non impliquées dans des boucles sont purgées au fur et à mesure) elles résident dans la boucle des sous-routines actives, et donc, cette opération de purge ne sera pas notablement plus longue que l'exécution d'un cycle de calcul.
après la purge ci-dessus, toutes les instances de sous-routines ont leur indicateur d'utilité positionné à +, on les bascule tous à - et on recommence un nouveau cycle de purge.

IV. Caractéristiques générales de la mise en oeuvre.

La définition d'un programme se compose de deux parties successives. D'abord, une série de déclarations de variables qui spécifie combien de variables on désire utiliser et quels noms on leur donne, ainsi que le type de valeurs qu'elles peuvent contenir.

Ensuite une série d'instructions décrivant l'évolution du contenu de ces variables, qui seront exécutées l'une après l'autre dès le début de l'exécution du programme, jusqu'à la dernière ou jusqu'à ce que l'une de ces instructions suspende sa propre exécution et celle des instructions qui la suivent en faisant dépendre son déroulement d'une condition qui ne soit pas remplie au départ et qui puisse l'être par la suite.

Afin de pouvoir décrire de façon précise et non ambigue les constructions syntaxiques utilisées nous utiliseront la convention suivante, variante de ce qui est appellé notation BNF (Backus-Naur Form).

les noms en minuscules désignent des constructions composées de un ou plusieurs symboles.
les séquences de caractères comprises entre apostrophes sont les mots et symboles du langage décrit tels qu'ils doivent apparaître dans le texte d'un programme.
la définition de chaque construction est précisée en écrivant à gauche du nom de la construction, le signe '=' suivi des différents formats qu'elle peut avoir, ceux-ci étant séparés par le signe ' | ' et cette liste des différents formats étant terminée par un point.
chacun de ces formats possibles consiste en une suite de symboles primitifs du langage ou de mots qui désignent des constructions constituant des éléments du format décrit. Un tel format peut être vide, c'est à dire ne comprendre aucun symbole, auquel cas on le fera figurer en dernier dans la liste dans laquelle il apparaît, liste qui se terminera donc par '| .'
afin d'abréger l'expression de certaines alternatives simples on notera l'occurrence optionnelle d'une séquence de symboles en l'entourant de crochets i.e. '[ mot1 mot2 ... ']' et l'occurrence répétitive (zéro, une ou plusieurs occurrences de la même séquence) en l'entourant d'accolades i.e. '{' séquence '}' pour ou « séquence » ou « séquence séquence... ».

Selon notre convention un programme est donc décrit par :

programme = 'PROGRAM' { déclaration ';' } { instruction separ }. 
separ = ','  | ';'.

Les déclarations permettent non seulement de définir des variables mais aussi des expressions et fonctions plus complexes que celles permises par l'usage des opérateurs habituels (+, -,*, /) et auxquelles on pourra se référer en plusieurs endroits dans les instructions subséquentes sans avoir à en réécrire le détail.

Les instructions consistent soit en des instructions d'affectation telles que celles que nous avons évoquées plus haut soit en des constructions plus complexes qui permettent d'exprimer les conditions de prise d'effet de ces affectations relativement au temps, aux valeurs atteintes par certaines variables, etc...

V. Déclaration des variables.

En ce qui concerne la première mise en oeuvre du langage les variables pourront être de quatre types différents :

le type 'INT' peut contenir des entiers compris entre -32768 et +32767
le type 'LONG INT' peut contenir des entiers compris entre -2147483648 et +2147483647
le type 'FRAC' peut contenir des fractions positives comprises entre 0 et 1 - (1/65536), le dénominateur étant toujours 65536.
le type 'LONG FRAC' peut contenir des fractions comprises entre -327GB et +2147483647/65536, le dénominateur étant toujours 65536.

Ce choix correspond aux caractéristiques de la machine sur laquelle doit être réalisée cette première mise en oeuvre (un ordinateur PDP-11/34 de la firme Digital Equipment Corporation) mais n'est en aucune façon essentiel quand aux propriétés attendues du système. On pourrait envisager d'autres types de variables tels que nombres en virgule flottante, caractères, chaînes de caractères, etc...

Par contre ces variables sont réparties en deux catégories significatives, les variables échantillonnées qui correspondent exactement à la notion de variable telle que nous l'avons définie et les variables non échantillonnées qui, devant servir à l'élaboration de résultats intermédiaires et n'étant pas censées transmettre une valeur d'un pas à l'autre, ne sont pas soumises à la gestion usages/opérandes, et pour lesquelles l'instruction d'affectation retrouve son sens habituel d'altération immédiate et unique de la valeur.

Une déclaration de variables est de la forme :

declvar = [ 'SAMPL'] [ 'LONG' ] typevar ident { ',' ident }.
typevar = 'INT' | 'FRAC'.
ident = lettre [ a [ a [ a [ a [ a [ a [ a [ a [ a ] ]]]]]]]].
lettre = 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I'
	|'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R'
	|'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z' .
a = lettre | chiffre.
chiffre = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7'
	| '8' | '9' .

La séquence d'au plus 10 lettres et/ou chiffres qui forme le nom d'une variable doit être composée de caractères contigus. Le mot-clé 'SAMPL' identifie les variables échantillonnées.

VI. Déclaration de fonctions et de procédures.

On peut également déclarer des fonctions, qui constitueront le moyen par lequel la valeur d'une expression sera recalculée au cours d'un pas avant d'être affectée à une variable échantillonnée, mais aussi des procédures, qui, sans délivrer de valeur, seront exécutées de la même façon à chaque pas et dont l'utilité résidera dans les effets de bord qu'elles produiront, tels que d'écrire à chaque pas une valeur résultat sur un support externe, fichier disque ou autre, ou de redéfinir des variables échantillonnées.

Enfin, ces fonctions et procédures échantillonnées pouvant nécessiter des calculs intermédiaires non triviaux, il est possible de rassembler, découper, et en un mot, de structurer, ces calculs intermédiaires sous forme de fonctions et procédures non échantillonnées qui, de même que les variables non échantillonnés, auront une signification classique n'impliquant pas l'itération implicite de leur exécution mais simplement une action immédiate et unique à leur point et instant d'invocation.

Le format de ces déclarations de procédures et fonctions est le suivant :

procédure = [ 'SAMPL' ] 'PROC' ident arguments ';'
	    corpsproc.
arguments = '(' declvar { ';' declvar } ')' |.
corpsproc = 'EXTERNAL' | { declaration } corpsbloc 'END'.
déclaration = declvar | procédure | fonction.
fonction = [ 'SAMPL' ] [ 'LONG' ] typevar 'FUNC' ident
	   arguments ';' corpsfunc.
corpsfunc = 'EXTERNAL' | { déclaration } specvaleur 'END'.

Avec la restriction supplémentaire qu'à l'intérieur d'une fonction ou procédure non échantillonnée on ne peut déclarer de variable échantillonnée.

En effet, tandis qu'une fonction ou procédure échantillonnée présente une rémanence d'un pas de calcul à l'autre, qui lui permet donc de détenir les informations qui constituent les références à des variables échantillonnées, une fonction ou procédure non échantillonnée peut terminer son exécution à tout moment et donc ne garantit pas la persistance des données qui lui sont propres.

On constate que les fonctions et procédures peuvent être imbriquées. Dans ce cas les déclarations de variables, fonctions et procédures propres à une fonction ou procédure ne sont effectives que depuis leur point de déclaration jusqu'au symbole 'END' qui marque la fin de la fonction ou procédure. Cette étendue constitue la portée d'une déclaration. La portée des déclarations contenues dans l'entête du programme s'étend jusqu'à la fin du programme.

D'autre part si certaines de ces déclarations locales définissent des symboles déjà utilisés dans les déclarations de l'entête du programme ou de procédures ou fonctions qui englobent le contexte où elles apparaissent, les déclarations locales prennent le pas, pour l'étendue de leur propre portée, sur les déclarations antérieures.

VII. Exécution conditionnelle des calculs.

Moyens de contrôle désirables.

D'après les desideratas que nous avons formulés nous avons besoin d'exprimer, au minimum, à quel instant nous voulons changer la définition d'une variable échantillonnée, c'est à dire y attacher une nouvelle sous-routine. Ce qui pourrait se ramener à une construction de la forme :

<condition> <affectation>

Cette construction constituant à elle seule une procédure échantillonnée qui à partir de son lancement testerait à chaque pas la condition voulue, et, si elle est remplie, exécuterait l'instruction d'affectation.

Cependant l'utilisation d'une méthode aussi primitive serait extrêmement mal commode, et, nous basant sur le genre de travaux que nous avons en vue, nous allons définir un système de contrôle des calculs beaucoup plus riche.

Notre but principal se ramène, ainsi que nous l'avons dit, à une transcription d'informations initialement sous forme de texte ou, plus généralement, sous forme d'une séquence de signes. Il apparaît que ce qui permet le plus aisément de décrire une telle séquence de signes, et les transformations que l'on désire y apporter, est une grammaire décrivant les constructions sémantiques possibles au moyen de ces signes.

Nous avons ici même un exemple de ce que peut être la notation d'une grammaire dans ce que nous avons appelé notation BNF, et dont nous nous servons pour décrire les caractéristiques de notre système. Nous voyons que chaque construction est décrite en énumérant les diverses formes qu'elle peut revêtir.

Nous désirons, d'une part pouvoir reconnaître chaque construction sans ambiguité quand elle se présente, d'autre part y attacher une signification, c'est à dire, en ce qui concerne notre projet, en déduire une série de valeurs ou d'actions sur des valeurs déjà existantes.

Reconnaissance des constructions.

Les signes élémentaires de notre flot d'entrée sont appelés symboles terminaux. Pour chaque alternative qui apparaît dans la définition d'une règle (à droite du signe '=') le ou les symboles terminaux qui peuvent constituer le premier symbole de l'alternative constituent l'ensemble des symboles directeurs de cette alternative. Si une grammaire est telle que pour chaque règle les ensembles de symboles directeurs de chaque alternative sont disjoints (aucun symbole terminal ne figure dans plus d'un ensemble), alors cette grammaire est dite LL(1).

Pour permettre la reconnaissance aisée des constructions nous vérifierons que les grammaires que nous utilisons sont LL(1), et au besoin nous les modifieront en subdivisant certaines règles et/ou en introduisant des règles auxiliaires afin de remplir cette condition. En effet, partant de la règle qui définit ce que doit être le flot d'entrée (règle-cible ou « goal symbol »), pour toute grammaire LL(1), il suffit d'examiner le symbole de tête du flot d'entrée pour pouvoir choisir quelle alternative appliquer et ainsi trouver l'enchaînement des règles successives, sans ambiguité et sans retour en arrière.

Actions qui accompagnent l'analyse du flot d'entrée.

Notre méthode d'analyse étant strictement déterministe, dès que nous avons identifié quelle règle s'applique nous pouvons effectuer toutes les manipulations qui sont désirables dans le cas qui vient d'être reconnu. En particulier, puisque c'est là notre but ultime, déclancher la production de séquences d'échantillons dont les caractéristiques seront choisies d'après le contenu du flot d'entrée.

Ceci s'exprimera en mentionnant parmi les symboles qui décrivent les règles de la grammaire, des actions telles que des affectations, des appels de procédures ou de fonctions ou des actions composites plus complexes (que nous allons définir plus loin). Ces actions étant implicitement exécutées au moment où, dans l'alternative où elles figurent, toutes les actions d'analyse et/ou sémantiques situées à leur gauche ont été accomplies.

Contrôle du déroulement des calculs intermédiaires.

Comme nous voulons en fait, non seulement analyser le flot d'entrée, mais aussi contrôler l'exécution des calculs selon d'autres critères, qui porteront sur des valeurs intermédiaires, nous allons mettre en oeuvre la méthode de contrôle ci-dessus de sorte qu'elle s'étende naturellement au cas de ces décisions intermédiaires.

Pour cela, la reconnaissance d'un symbole terminal s'effectuera au moyen d'une comparaison entre le contenu de la variable qui reçoit le symbole de tête du flot d'entrée et les valeurs possibles de ce symbole, suivie, au cas ou le symbole de tête est reconnu, de la lecture du symbole suivant. Cette décomposition de l'opération de reconnaissance d'un symbole terminal en deux primitives (comparaison et lecture) permet de généraliser la sémantique de la primitive de comparaison en la faisant porter, non seulement sur les signes du flot d'entrée, mais aussi sur toute valeur intermédiaire, et en étendant les comparaisons possibles aux opérateurs d'ordre ("<",">", "<=", ">=").

De même que la comparaison du symbole de tête du flot d'entrée aux symboles directeurs des diverses alternatives de la rêgle en cours permet de choisir quelle alternative appliquer, la comparaison de certaines valeurs intermédiaires permettra de décider quelle sera la prochaine action à exécuter parmi plusieurs actions concurrentes. Cette construction est analogue à la construction "(COND...)" du langage LlSP.

Elle se traduit par :

IF <condition 1> <action 1>
IF <condition 2> <action 2>
		...
IF <condition n> <action n>

De plus, cette construction est, du point de vue sémantique, strictement équivalente à une règle de grammaire, en ce sens que si aucune des conditions posées n'est satisfaite, la construction elle-même a la signification d'une condition fausse. Une telle construction, délimitée par les mots-clés 'DO' et 'END', peut donc être utilisée en tant que condition composite partout où l'on peut user d'une expression conditionnelle. De même si une telle construction constitue le corps d'une procédure ou fonction non échantillonnée la référence au nom de cette procédure ou fonction a le sens d'une référence à la règle dont les alternatives correspondent chacune à l'une des conditions de 1 à n.

C'est par ce moyen que s'exprime la correspondance bijective entre les règles d'une grammaire LL(1) et les procédures et paragraphes de notre langage de commande.

Appliquant la démarche inverse de celle qui nous a mené d'une grammaire à une structure de contrôle, nous pouvons également considérer que les structures de contrôle ci-dessus, présentes dans un programme, définissent une grammaire décrivant le langage constitué par les « trajectoires » que ce programme peut suivre au cours de toutes ses exécutions possibles. Ce point de vue est cohérent sous réserve qu'à chaque choix parmi plusieurs actions les conditions concurrentes soient mutuellement exclusives, ce qui correspond à la condition LL(1) pour une grammaire.

VIII. Définitions complémentaires.

Nous pouvons donner maintenant la syntaxe exacte de la partie exécutable des fonctions et procédures.

corpsbloc = alternative | instructions.
alternatives = clause { clause } [ finalter ].
clause = 'IF' conjonction instructions.
conjonction = condition { '&' condition }.
finalter = 'DONE' | 'ELSE' 'DONE' | 'ELSE' instructions.

Le mot-clé 'THEN' peut apparaître entre « conjonction » et « instructions », de même qu'à la place d'une virgule car il n'est pas significatif. La conjonction de plusieurs conditions est vraie si toutes les conditions sont vraies. Soit C1, C2... Cn les conjonctions qui apparaissent dans les alternatives A1, A2, An, on nomme Cx la conjonction non (C1) & non (C2)... & non (Cn). La construction « ELSE instructions » signifie « IF Cx instructions », tandis que « ELSE DONE » ou « DONE » signifient « IF Cx <rien> ». Si l'une de ces trois constructions est utilisée pour terminer une série d'alternatives, la règle ainsi définie est toujours applicable. C'est à dire qu'en tant que condition composite elle est toujours vraie, donc il est recommandé de ne pas l'utiliser de cette façon, ce qui n'aurait aucun sens et irait à l'encontre de la règle d'exclusion mutuelle des conditions concurrentes.

En fait, dans la mise en oeuvre actuelle, cette règle d'exclusion mutuelle n'est ni vérifiée ni même requise pour le bon fonctionnement du choix des alternatives. Les conditions sont testées dans l'ordre dans lequel elles apparaissent dans le texte du programme et acquièrent donc un sens légèrement diffèrent : Cn <= Cn & non (Cn-1) & ... & non (C1). Il appartient à l'utilisateur de vérifier lui-même la condition d'exclusion au cas où elle est significative.

condition = expression opcomp expression | paragraphe
	   | appelproc.
opcomp = '=' | '#' | '<>' | '>' | '<' | '<=' | '>='.
paragraphe = 'DO' alternative 'END'
appelproc = nomproc  [ arguments ].
nomproc = ident.
arguments ='(' expression {',' expression } ')'.

Les opérateurs de comparaison '#' et '<>', ont le sens de « non égal ». Le format des appels de procédures non échantillonnées et des déclanchements de procédures échantillonnées est le même, mais seul l'appel de procédures non échantillonnées constitue une condition significative, et, de plus, sous réserve que la partie exécutable de la procédure appelée soit une série d'alternatives. Une procédure non échantillonnée contenant des instructions inconditionnelles est équivalente à une règle toujours applicable.

expression = terme { addop terme }.
addop = '+' | '-'.
terme = fact { mulop fact }.
mulop = '*' | '/'.
fact = étiquette ':' fact | '-' fact | const | appelfunc
	| 'TIME' | nomvar | '(' specvaleur ')'.
appelfunc = nomfunc [ arguments ].
étiquette = ident.
nomvar = ident.
nomfunc = ident.
specvaleur = valternatives | valtexte.
valtexte = instructions expression instructions.
valternatives =  'IF' vclause { 'IF' vclause }
		[ 'ELSE' valtexte ].
vclause = conjonction valtexte | valcond instructions.
valcond = condition '&' valcond
	| expression { '&' condition }.

Les diverses interprétations d'un identificateur « ident » (nomproc, étiquette, nomfvar, nomfunc) sont différenciées d'après les déclarations antérieures. TIME est une fonction sans arguments prédéfinie, dont la valeur est le temps courant exprimé en nombre de pas écoulés depuis le début de l'exécution du programme. Les parties d'expression étiquettées peuvent être utilisées comme des fonctions sans arguments, ce qui évite d'en réécrire le détail.

On voit apparaître une des incidences les plus bizarres de notre choix de structure de contrôle. Une fonction non échantillonnée est, aussi bien qu'une procédure, l'équivalent d'une règle, pourvu que sa partie exécutable soit constituée d'alternatives. Donc une telle fonction peut à la fois renvoyer une valeur et constituer la condition qui détermine le choix de l'alternative qui correspond à cette même valeur. Ceci s'exprime par la définition de « valcond ».

Dans tous les cas où une série d'alternatives n'est pas terminée par une clause 'ELSE' ou 'DONE', une des alternatives doit être obligatoirement satisfaite, sinon le processus pour lequel cette condition de non satisfaction apparaît cesse de se dérouler. C'est par ce mécanisme que s'effectue la gestion de l'entrelacement des calculs. En effet la signification intuitive de cette condition est claire, c'est seulement si l'une des alternatives spécifiées est applicable que l'on désire continuer les calculs mentionnés dans les instructions suivantes. De deux choses l'une : ou bien les conditions testées sont stables vis-à-vis du déroulement des processus concurrents et le processus actuel doit être définitivement arrêté, ou bien les processus concurrents sont susceptibles de modifier ces conditions et il faut donc leur donner la possibilité de le faire en leur laissant l'usage des ressources de calcul.

On voit donc qu'une procédure, une fois lancée au cours d'un cycle de calculs, se déroule à l'intérieur de ce même cycle jusqu'à ce qu'elle rencontre une condition qui détermine, pour elle, la fin de ce cycle. Cette fin de cycle peut être spécifiée explicitement au moyen de l'instruction 'RESUME' qui passe le contrôle au prochain processus dans la boucle d'appels.

instructions = { instruction }.
instruction = étiquette ':' instruction | paragraphe
	| appelproc | ident ':=' expression
	| 'RESUME' | 'EXIT'.

L'appel d'une procédure échantillonnée crée le processus correspondant qui, à partir de cet instant, va se dérouler à chaque cycle de calcul jusqu'à ce que s'établisse sa condition d'arrêt. Le processus appelant ne perd pas le contrôle au moment de l'appel. L'appel d'une procédure non échantillonnée est tout à fait classique, le processus en cours continue son déroulement au sein de la procédure appelée. L'instruction EXIT permet de provoquer l'arrêt définitif du processus en cours.

Une instruction étiquettée peut être utilisée comme une procédure non échantillonnée sans arguments, ce qui évite d'en réécrire le détail. C'est également par ce moyen que l'on peut spécifier l'itération de certaines séquences d'instructions par l'appel d'un paragraphe à l'intérieur de lui-même. Cependant, dans cette première mise en oeuvre du langage, les paragraphes récursifs ne sont pas autorisés. C'est à dire que les appels exprimant l'itération devront être strictement récursifs à droite, i.e. qu'il ne devra pas y avoir d'instructions exécutables comprises entre le point d'appel et la fin du paragraphe appelé. En effet une récursion à droite est équivalente à une itération, et, ce qui apparaît comme un appel peut être transformé en un branchement sans altérer la sémantique du texte.

IX. Conclusion.

Le système décrit ci-dessus est en cours d'installation sur un ordinateur PDP- 11/34. Tout au long de ce processus d'installation des problèmes soit techniques, soit tenant à la sémantique des objets manipulés, sont apparus et leur solution a contribué à clarifier les concepts mis en jeu dans le traitement pas à pas des signaux digitaux. Il est de même espéré que l'utilisation de ce logiciel, de part les possibilités entièrement nouvelles qu'il offre, permettra de mieux comprendre et maîtriser les techniques de synthèse des signaux complexes.