Notation polonaise inversée

La notation polonaise inversée ( RPN ), également connue sous le nom de notation Łukasiewicz inversée , notation postfixée polonaise ou simplement notation postfixée , est une notation mathématique dans laquelle les opérateurs suivent leurs opérandes , contrairement à la notation préfixée ou polonaise (PN), dans laquelle les opérateurs précèdent leurs opérandes. La notation n'a pas besoin de parenthèses tant que chaque opérateur possède un nombre fixe d'opérandes .

Le terme notation postfixée décrit le schéma général des mathématiques et de l'informatique, tandis que le terme notation polonaise inversée fait généralement référence spécifiquement à la méthode utilisée pour saisir des calculs dans des calculatrices matérielles ou logicielles, qui ont souvent des effets secondaires et des implications supplémentaires en fonction de l'implémentation réelle impliquant une pile . La description « polonaise » fait référence à la nationalité du logicien Jan Łukasiewicz , qui a inventé la notation polonaise en 1924.

Le premier ordinateur à utiliser la notation postfixée, bien qu'elle soit restée longtemps essentiellement inconnue en dehors de l'Allemagne, fut le Z3 de Konrad Zuse en 1941 ainsi que son Z4 en 1945. Le schéma polonais inversé fut à nouveau proposé en 1954 par Arthur Burks , Don Warren et Jesse Wright et fut réinventé indépendamment par Friedrich L. Bauer et Edsger W. Dijkstra au début des années 1960 pour réduire l'accès à la mémoire de l'ordinateur et utiliser la pile pour évaluer les expressions . Les algorithmes et la notation de ce schéma furent étendus par le philosophe et informaticien Charles L. Hamblin au milieu des années 1950.

Au cours des années 1970 et 1980, Hewlett-Packard a utilisé RPN dans toutes ses calculatrices de bureau et portables, et a continué à l'utiliser dans certains modèles jusqu'aux années 2020. En informatique , la notation polonaise inversée est utilisée dans les langages de programmation orientés pile tels que Forth , dc , Factor , STOIC , PostScript , RPL et Joy .

En notation polonaise inversée, les opérateurs suivent leurs opérandes . Par exemple, pour additionner 3 et 4, l'expression est 3 4 + plutôt que 3 + 4. L'expression de notation conventionnelle 3 − 4 + 5 devient 3 4 − 5 + en notation polonaise inversée : 4 est d'abord soustrait de 3, puis 5 lui est ajouté.

Le concept de pile , une construction dernier entré/premier sorti, fait partie intégrante de l'évaluation de gauche à droite de RPN. Dans l'exemple 3 4 − , le 3 est d'abord placé sur la pile, puis le 4 ; le 4 est maintenant au-dessus et le 3 en dessous. L'opérateur de soustraction supprime les deux éléments supérieurs de la pile, exécute 3 − 4 et place le résultat de −1 sur la pile.

La terminologie courante est que les éléments ajoutés sont poussés sur la pile et les éléments supprimés sont supprimés .

L'avantage de la notation polonaise inversée est qu'elle supprime la nécessité d'ordre des opérations et des parenthèses qui sont requises par la notation infixe et peut être évaluée linéairement, de gauche à droite. Par exemple, l'expression infixe (3 + 4) × (5 + 6) devient 3 4 + 5 6 + × en notation polonaise inversée.

La notation polonaise inversée a été comparée à la façon dont on devait résoudre des problèmes avec une règle à calcul .

En comparant la notation polonaise inversée avec la notation algébrique, on a constaté que la notation polonaise inversée permettait des calculs plus rapides, et ce pour deux raisons. La première raison est que les calculatrices polonaises inversées n'ont pas besoin de mettre les expressions entre parenthèses, ce qui fait qu'il faut saisir moins d'opérations pour effectuer des calculs classiques. De plus, les utilisateurs de calculatrices polonaises inversées ont fait moins d'erreurs que les autres types de calculatrices. Des recherches ultérieures ont précisé que la vitesse accrue de la notation polonaise inversée peut être attribuée au nombre réduit de frappes nécessaires pour saisir cette notation, plutôt qu'à une charge cognitive plus faible pour ses utilisateurs. Cependant, des preuves anecdotiques suggèrent que la notation polonaise inversée est plus difficile pour les utilisateurs qui ont déjà appris la notation algébrique.

Edsger W. Dijkstra a inventé l' algorithme de triage pour convertir les expressions infixes en expressions postfixées (notation polonaise inversée), ainsi nommé parce que son fonctionnement ressemble à celui d'une gare de triage ferroviaire .

Il existe d'autres moyens de produire des expressions postfixées à partir d'expressions infixées. La plupart des analyseurs de priorité d'opérateur peuvent être modifiés pour produire des expressions postfixées ; en particulier, une fois qu'un arbre de syntaxe abstraite a été construit, l'expression postfixée correspondante est donnée par un simple parcours post-ordre de cet arbre.

Le premier ordinateur implémentant une forme de notation polonaise inversée (mais sans le nom et aussi sans pile ), était le Z3 de Konrad Zuse , qu'il a commencé à construire en 1938 et présenté publiquement le 12 mai 1941. En mode dialogue, il permettait aux opérateurs de saisir deux opérandes suivis de l'opération souhaitée. Il a été détruit le 21 décembre 1943 lors d'un bombardement. Avec l'aide de Zuse, une première réplique a été construite en 1961. Le Z4 de 1945 a également ajouté une pile à 2 niveaux .

D'autres ordinateurs précoces à mettre en œuvre des architectures permettant la notation polonaise inversée étaient la machine KDF9 de l' English Electric Company , annoncée en 1960 et disponible dans le commerce en 1963, et le Burroughs B5000 , annoncé en 1961 et également livré en 1963 :

On peut supposer que les concepteurs du KDF9 se sont inspirés du GEORGE (General Order Generator) de Hamblin, un système de programmation autocode écrit pour un ordinateur DEUCE installé à l' Université de Sydney , en Australie, en 1957.

L'un des concepteurs du B5000, Robert S. Barton , écrivit plus tard qu'il avait développé la notation polonaise inversée indépendamment de Hamblin en 1958 après avoir lu un manuel de 1954 sur la logique symbolique d' Irving Copi , où il trouva une référence à la notation polonaise, ce qui lui fit lire également les travaux de Jan Łukasiewicz, et avant qu'il ne soit au courant du travail de Hamblin.

Friden a introduit la notation polonaise inversée sur le marché des calculatrices de bureau avec l' EC-130 , conçue par Robert « Bob » Appleby Ragen , prenant en charge une pile à quatre niveaux en juin 1963. Le successeur EC-132 a ajouté une fonction racine carrée en avril 1965. Vers 1966, la calculatrice Monroe Epic prenait également en charge un schéma d'entrée sans nom ressemblant également à RPN.

Les ingénieurs de Hewlett-Packard ont conçu la calculatrice de bureau 9100A en 1968 avec une notation polonaise inversée avec seulement trois niveaux de pile avec des registres de travail X (« clavier »), Y (« accumuler ») et un registre de stockage visible Z (« temporaire »), une variante de notation polonaise inversée appelée plus tard RPN à trois niveaux . Cette calculatrice a popularisé la notation polonaise inversée parmi les communautés scientifiques et d'ingénierie. La HP-35 , première calculatrice scientifique portable au monde , a introduit le RPN classique à quatre niveaux avec son ensemble de règles spécifiques de la pile opérationnelle (mémoire) (appelée plus tard également pile mémoire automatique ) en 1972. Dans ce schéma, la touche duplique les valeurs dans Y sous certaines conditions ( élévation automatique de la pile avec désactivation temporaire de l'élévation de la pile ), et le registre supérieur T ("top") est dupliqué lors des chutes ( copie supérieure sur pop aka répétition du niveau de la pile supérieure ) afin de faciliter certains calculs et d'économiser des frappes. HP a utilisé la notation polonaise inversée sur chaque calculatrice portable qu'elle vendait, qu'elle soit scientifique, financière ou programmable, jusqu'à ce qu'elle introduise la calculatrice à additionner HP-10 en 1977. À cette époque, HP était le premier fabricant de calculatrices pour les professionnels, y compris les ingénieurs et les comptables. Enter ↑

Les calculatrices à écran LCD du début des années 1980, telles que la HP-10C , la HP-11C , la HP-15C , la HP-16C et la calculatrice financière HP-12C , utilisaient également la notation polonaise inversée. En 1988, Hewlett-Packard a lancé une calculatrice commerciale, la HP-19B , sans notation polonaise inversée, mais son successeur de 1990, la HP-19BII , a donné aux utilisateurs la possibilité d'utiliser à nouveau la notation polonaise algébrique ou inversée.

En 1986, HP a introduit RPL , un successeur orienté objet de la notation polonaise inversée. Il s'écarte de la notation polonaise inversée classique en utilisant une pile dynamique limitée uniquement par la quantité de mémoire disponible (au lieu de trois ou quatre niveaux fixes) et qui peut contenir toutes sortes d'objets de données (y compris des symboles, des chaînes, des listes, des matrices, des graphiques, des programmes, etc.) au lieu de simples nombres. Le système afficherait un message d'erreur en cas de manque de mémoire au lieu de simplement supprimer des valeurs de la pile en cas de débordement comme avec les piles de taille fixe. Il a également modifié le comportement de la pile pour ne plus dupliquer le registre supérieur lors des suppressions (puisque dans une pile illimitée, il n'y a plus de registre supérieur) et le comportement de la clé pour qu'elle ne duplique plus les valeurs dans Y, ce qui s'était avéré parfois source de confusion chez les utilisateurs non familiarisés avec les propriétés spécifiques de la pile de mémoire automatique . De 1990 à 2003, HP a fabriqué la série HP-48 de calculatrices graphiques RPL, suivie de la série HP-49 entre 1999 et 2008. La dernière calculatrice RPL s'appelait HP 50g , introduite en 2006 et abandonnée en 2015. Cependant, il existe plusieurs efforts communautaires comme newRPL ou DB48X pour recréer RPL sur des calculatrices modernes. Enter ↑

En 2011, Hewlett-Packard proposait les modèles de calculatrices 12C, 12C Platinum, 17bII+ , 20b , 30b , 33s , 35s , 48gII (RPL) et 50g (RPL) qui prennent en charge la notation polonaise inversée.

Alors que les calculatrices émulant des modèles classiques continuaient à prendre en charge la notation polonaise inversée classique, les nouveaux modèles de notation polonaise inversée présentent une variante de la notation polonaise inversée, où la touche se comporte comme dans RPL. Cette dernière variante est parfois connue sous le nom d'entrée RPN . Enter ↑

En 2013, le HP Prime a introduit une forme de RPN d'entrée à 128 niveaux appelée RPN avancé . Contrairement au RPL avec sa pile dynamique, il supprime simplement les valeurs de la pile en cas de dépassement, comme le font les autres piles de taille fixe. Cependant, comme le RPL, il n'émule pas le comportement d'une pile RPN opérationnelle classique pour dupliquer le registre supérieur lors des suppressions.

Fin 2017, la liste des modèles actifs prenant en charge la notation polonaise inversée ne comprenait que les modèles 12C, 12C Platinum, 17bii+, 35s et Prime. En juillet 2023, seuls les modèles 12C, 12C Platinum, la toute nouvelle HP 15C Collector's Edition et le Prime restent des modèles actifs prenant en charge la notation RPN.

En Grande-Bretagne, les modèles Sinclair Scientific (1974) et Scientific Programmable (1975) de Clive Sinclair utilisaient la notation polonaise inversée.

En 1974, Commodore a produit le Minuteman *6 (MM6) sans clé et le Minuteman *6X (MM6X) avec une clé, tous deux implémentant une forme de RPN à deux niveaux . Le SR4921 RPN était livré avec une variante de RPN à quatre niveaux avec des niveaux de pile nommés X, Y, Z et W (au lieu de T) et une clé (pour « entrée »). Contrairement à l'implémentation de la notation polonaise inversée de Hewlett-Packard, W était rempli de 0 au lieu que son contenu soit dupliqué lors des suppressions de pile. Enter ↑Enter ↑Ent

Prinz et Prinztronic étaient des marques commerciales propres de la chaîne britannique de magasins de produits photographiques et électroniques Dixons , rebaptisée plus tard Currys Digital Stores, et intégrée à DSG International. Divers modèles de calculatrices ont été vendus dans les années 1970 sous la marque Prinztronic, tous fabriqués pour eux par d'autres sociétés.

Parmi celles-ci se trouvait la calculatrice scientifique programmable PROGRAM qui comportait une notation polonaise inversée.

L'ordinateur de navigation aérienne Heathkit OC-1401 / OCW-1401 utilisait un RPN à cinq niveaux en 1978.

Les calculatrices programmables soviétiques (modèles MK-52 , MK-61 , B3-34 et les modèles antérieurs B3-21 ) utilisaient la notation polonaise inversée pour le mode automatique et la programmation. Les calculatrices russes modernes MK-161 et MK-152, conçues et fabriquées à Novossibirsk depuis 2007 et proposées par Semico, sont rétrocompatibles avec elles. Leur architecture étendue est également basée sur la notation polonaise inversée.

• Une pile à sept niveaux a été implémentée dans la calculatrice scientifique de bureau MITS 7400C en 1972
• Semiconducteurs nationaux 4615 et 4640
• Novus 650 Mathbox, 3500 Sliderule, 4510 Mathématicien, 4515 Mathématicien PRO/RG, 4520 Scientifique et 4525 Scientifique PR
• Certaines calculatrices APF comme la Mark 55 (1976)
• Calculatrices SwissMicros (initialement appelées RPN-Calc), notamment les modèles DM-10CC (2012), DM-11CC (2012), DM-12CC (2012), DM-15CC (2012), DM-16CC (2012), DM10 ( 2013), DM11 (2013), DM12 (2013), DM15 ( 2013), DM16 (2013), DM10L Collector's Edition (2020), DM11L (2016), DM12L (2016), DM15L (2015), DM16L (2015), DM41 (2015), DM41L (2015), DM41X (2020), DM42 (2017) et DM32 (2023).

Une pile à huit niveaux a été suggérée par John A. Ball en 1978.

Les calculatrices développées par la communauté WP 34S (2011), WP 31S (2014) et WP 34C (2015), qui sont basées sur la plate-forme matérielle HP 20b / HP 30b , prennent en charge la notation polonaise inversée classique de style Hewlett-Packard prenant en charge le comportement de levage automatique de la pile des copies de registres clés et supérieurs sur les pops, mais commutables entre une pile opérationnelle à quatre et huit niveaux. Enter ↑

En plus de la prise en charge optionnelle d'une pile à huit niveaux, le nouveau WP 43S basé sur SwissMicros DM42 ainsi que les dérivés WP 43C (2019) / C43 (2022) / C47 (2023) prennent en charge les types de données pour les objets de pile (nombres réels, entiers infinis, entiers finis, nombres complexes, chaînes, matrices, dates et heures). Les trois dernières variantes peuvent également basculer entre le comportement RPN classique et d'entrée de la clé, une fonctionnalité souvent demandée par la communauté. de chiffres significatifs rarement vu , qui était déjà disponible en tant qu'option de compilation pour les WP 34S et WP 31S. Enter ↑

Depuis 2021, le simulateur HP-42S Free42 version 3 peut être activé pour prendre en charge une pile RPN dynamique limitée uniquement par la quantité de mémoire disponible au lieu de la pile classique à 4 niveaux. Cette fonctionnalité a été intégrée en tant que fonction sélectionnable dans le DM42 depuis le firmware DMCP-3.21 / DM42-3.18.

Logiciels de calcul :

• Calculatrice Atari
• Calculatrice Mac OS X
• Plusieurs applications Apple iPhone, par exemple « calculatrice de notation polonaise inversée »
• Plusieurs applications Android par exemple « RealCalc »
• Plusieurs applications Windows 10 Mobile, par exemple « RPN9 »
• Programme de calculatrice du système Unix dc
• Paquet de bibliothèque Lisp Emacs calc
• Calculatrice Xorg ( xcalc )
• ARPCalc, une puissante calculatrice RPN scientifique/technique pour Windows, Linux et Android qui dispose également d'une version basée sur un navigateur Web
• grpn calculatrice scientifique/technique utilisant la boîte à outils GIMP ( GTK+ )
• Corrélatifs F dans les éléments du dictionnaire MultiValue
• RRDtool , un logiciel de tabulation et de création de graphiques largement utilisé
• grdmath, un programme pour les opérations algébriques sur les grilles NetCDF , faisant partie de la suite Generic Mapping Tools (GMT)
• galculator, une calculatrice de bureau GTK
• Mouseless Stack-Calculator calculatrice scientifique/technique incluant des nombres complexes
• rpCalc, un calculateur simple de notation polonaise inversée écrit en Python pour Linux et MS Windows et publié sous la licence GNU GPLv2
• orpie, calculatrice RPN pour le terminal pour nombres réels ou complexes ou matrices
• Qalculate!, une calculatrice de bureau multiplateforme puissante et polyvalente
• Calculateur WRPN

Les implémentations existantes utilisant la notation polonaise inversée incluent :

• Langages de programmation orientés pile tels que :
  • Quatrièmement
  • dc
  • STOÏQUE
  • Facteur
  • Langage de description de page PostScript
  • Fichiers de style BibTeX
  • Befunge
  • Joie
  • IPTSCRAE
  • Formules Lotus 1-2-3 et Lotus Symphony
  • RPL (aussi appelé Reverse Polish Language), un langage de programmation pour le Commodore PET vers 1979/1981
  • RPL (aussi appelé Reverse Polish Lisp), un langage de programmation pour les calculatrices Hewlett-Packard entre 1986 et 2015
  • RPNL (langage de notation polonaise inversée)
• Bibliothèques de classes
  • TRURL, une bibliothèque de classes pour la construction de calculatrices RPN en Object Pascal