Notation polonaise inverse
La notation polonaise inverse (NPI) (en anglais RPN pour Reverse Polish Notation), également connue sous le nom de notation post-fixée, permet d'écrire de façon non ambiguë les formules arithmétiques sans utiliser de parenthèses. Dérivée de la notation polonaise présentée en 1924 par le mathématicien polonais Jan Łukasiewicz, elle s’en différencie par l’ordre des termes, les opérandes y étant présentés avant les opérateurs et non l’inverse.
![](http://up.wiki.x.io/wikipedia/commons/thumb/5/53/CPT-RPN-example1.svg/220px-CPT-RPN-example1.svg.png)
Par exemple, sur une calculatrice, l’expression peut s'écrire en NPI sous la forme 10 Enter 5 + 3 x, ou encore sous la forme 3 Enter 10 Enter 5 + x.
Histoire
modifierDérivée de la notation polonaise utilisée pour la première fois en 1924 par le mathématicien polonais Jan Łukasiewicz[1], la NPI a été inventée par le philosophe et informaticien australien Charles Leonard Hamblin (en) dans le milieu des années 1950, pour permettre les calculs sans faire référence à une quelconque adresse mémoire[2].
Un des premiers ordinateurs conçu, le Zuse 4 utilisait une pile, et une arithmétique de type NPI dès 1945, avant même que le concept soit formalisé[3]. Puis d'autres ordinateurs comme le English Electric KDF9 ou le Burroughs B5000 en ont appliqué le principe dès 1963[3].
Mais la NPI se développera réellement sur les calculatrices, comme moyen de saisie interactif d'expression arithmétiques. Le premier calculateur électronique utilisant cette notation est la Friden (en) EC-132 en 1964[4],[5].
C'est à la fin des années 1960, qu'elle a été diffusée dans le public comme interface utilisateur avec les calculatrices de bureau de Hewlett-Packard (HP-9100), puis avec la calculatrice scientifique HP-35 en 1972[1].
Implications pratiques
modifier- l’écriture est raccourcie grâce à la suppression des parenthèses ;
- un résultat intermédiaire peut être réutilisé. Par exemple dans le calcul de on voit rapidement que l'expression est utilisée deux fois. On peut la dupliquer dans la pile, ce qui donne :
- 3 Enter π * 4 / DUP SIN SWAP / avec DUP et SWAP des opérateurs de pile pour dupliquer et intervertir.
- les calculs intermédiaires sont gérés sous forme de pile.
- parce qu'elle permet de voir les résultats intermédiaires, elle permet de détecter plus facilement les erreurs et donc un débogage plus rapide ; à l’époque des premiers circuits intégrés, cela en diminuait la complexité (gestion d'une pile et d'opérateurs de pile).
- ni l'opérateur, ni les parenthèses ne servant de séparateur, il faut en fournir entre deux opérandes successifs. Une espace devrait pouvoir suffire dans la majorité des cas ; sur une calculatrice, il s'agit de la touche Enter.
Quelques utilisations réelles de la NPI
modifier- Le langage de programmation Forth
- Le langage de programmation RPL (Hewlett Packard)
- Le langage de programmation RPL/2[6]
- Les calculatrices scientifiques Hewlett-Packard, dont les HP-35, HP-41, HP-28, HP-48, HP-15C, HP-35s, HP-12c, etc.
- Le langage de description de pages PostScript
- Le programme calc[7], intégré dans Emacs
- Le tableur d’Unix, le programme dc
- L’écriture d’interprètes[réf. nécessaire]
- Le langage de description de format de bibliographie pour LaTeX et BibTex .bst[8],[9].
- La création de graphiques complexes dans rrdtools[10].
- Le langage WarpScript, créé par Warp10 pour faciliter le traitement des Géo-Time Series (GTS)[11].
Notes et références
modifier- (en) What is RPN?, sur le site hpmuseum.org, consulté le 19 mai 2013
- (en) Biographie de C.L.Hanblin, sur le site vukutu
- Charles Eric LaForest, « Second-Generation Stack Computer Architecture »
- (en) Robert King, « The Evolution of Today's Calculator. », The International Calculator Collector, no 15 & 16, hiver-printemps 1997
- ACONIT, « 1964, naissance de la Friden EC 130, un bijou électronique », sur Echosciences Grenoble, Recherche, industrie, informatique,
- Joël Bertrand, « Site officiel du langage RPL/2 ®, langage de programmation fonctionnel impur dédié au calcul scientifique », (consulté le )
- calc, sur le site gnu.org
- Bibliography style (.bst) files, lire en particulier la section 16
- Notons que le package BibLaTeX de LaTeX propose une syntaxe plus simple que celle de bst pour modifier les styles.
- Page de manuel de rrdgraph
- (en) « WarpScript, a language designed for analytics of time-series data », sur Warp10 (consulté le )