Notation polonaise

La notation polonaise ( PN ), également connue sous le nom de notation polonaise normale ( NPN ), notation de Łukasiewicz , notation de Varsovie , notation polonaise préfixe ou simplement notation préfixe , est une notation mathématique dans laquelle les opérateurs précèdent leurs opérandes , contrairement à la notation infixe plus courante , dans laquelle les opérateurs sont placés entre les opérandes, ainsi qu'à la notation polonaise inversée (RPN), dans laquelle les opérateurs suivent leurs opérandes. Elle n'a pas besoin de parenthèses tant que chaque opérateur a un nombre fixe d'opérandes . La description « polonaise » fait référence à la nationalité du logicien Jan Łukasiewicz , qui a inventé la notation polonaise en 1924.

Le terme notation polonaise est parfois considéré (comme l'opposé de la notation infixe ) comme incluant également la notation polonaise inversée.

Lorsque la notation polonaise est utilisée comme syntaxe pour les expressions mathématiques par les interprètes de langage de programmation , elle est facilement analysée en arbres syntaxiques abstraits et peut, en fait, définir une représentation bijective pour celle-ci. Pour cette raison, Lisp (voir ci-dessous) et les langages de programmation associés définissent toute leur syntaxe en notation préfixe (et d'autres utilisent la notation postfixe).

Une citation d'un article de Jan Łukasiewicz en 1931 indique comment la notation a été inventée :

J'ai eu l'idée d'une notation sans parenthèses en 1924. J'ai utilisé cette notation pour la première fois dans mon article Łukasiewicz (1), p. 610, note de bas de page.

La référence citée par Łukasiewicz, c'est-à-dire Łukasiewicz (1), est apparemment un rapport lithographié en polonais . L'article de référence de Łukasiewicz a été examiné par Henry A. Pogorzelski dans le Journal of Symbolic Logic en 1965. Heinrich Behmann , éditeur en 1924 de l'article de Moses Schönfinkel , avait déjà eu l'idée d'éliminer les parenthèses dans les formules logiques. Dans l'un de ses articles, Łukasiewicz a déclaré que sa notation est la plus compacte et la première notation sans parenthèses écrite linéairement, mais pas la première puisque Gottlob Frege a proposé sa notation Begriffsschrift sans parenthèses en 1879 déjà.

Alonzo Church mentionne cette notation dans son livre classique sur la logique mathématique comme digne de remarque dans les systèmes de notation, même en contraste avec l'exposition de la notation logique d' Alfred Whitehead et de Bertrand Russell et le travail dans Principia Mathematica .

Dans son livre de 1951, Aristotle's Syllogistic from the Standpoint of Modern Formal Logic , Łukasiewicz mentionne que le principe de sa notation était d'écrire les foncteurs avant les arguments pour éviter les parenthèses et qu'il avait utilisé sa notation dans ses articles logiques depuis 1929. Il cite ensuite, à titre d'exemple, un article de 1930 qu'il a écrit avec Alfred Tarski sur le calcul des phrases .

Bien qu'elle ne soit plus beaucoup utilisée en logique, la notation polonaise a depuis trouvé une place en informatique .

L'expression pour additionner les nombres 1 et 2 s'écrit en notation polonaise comme + 1 2 (préfixe), plutôt que 1 + 2 (infixe). Dans les expressions plus complexes, les opérateurs précèdent toujours leurs opérandes, mais les opérandes peuvent eux-mêmes être des expressions comprenant des opérateurs again et leurs opérandes. Par exemple, l'expression qui s'écrirait en notation infixe conventionnelle serait

peut être écrit en notation polonaise comme

En supposant une arité donnée de tous les opérateurs impliqués (ici le « − » désigne l'opération binaire de soustraction, et non la fonction unaire de changement de signe), toute représentation de préfixe bien formée est sans ambiguïté et les crochets dans l'expression du préfixe sont inutiles. Ainsi, l'expression ci-dessus peut être encore simplifiée en

Le traitement du produit est différé jusqu'à ce que ses deux opérandes soient disponibles (c'est-à-dire 5 moins 6 et 7). Comme dans toute notation, les expressions les plus profondes sont évaluées en premier, mais dans la notation polonaise, ce « caractère le plus profond » peut être transmis par la séquence d'opérateurs et d'opérandes plutôt que par des crochets.

Dans la notation infixe conventionnelle, les parenthèses sont nécessaires pour remplacer les règles de priorité standard , car, en se référant à l'exemple ci-dessus, leur déplacement

ou les supprimer

modifie le sens et le résultat de l'expression. Cette version est écrite en notation polonaise comme suit

Lorsqu'il s'agit d'opérations non commutatives, comme la division ou la soustraction, il est nécessaire de coordonner la disposition séquentielle des opérandes avec la définition de la manière dont l'opérateur prend ses arguments, c'est-à-dire de gauche à droite. Par exemple, ÷ 10 5 , avec 10 à gauche de 5, a la signification de 10 ÷ 5 (lire comme « diviser 10 par 5 »), ou − 7 6 , avec 7 à gauche de 6, a la signification de 7 − 6 (lire comme « soustraire de 7 l'opérande 6 »).

La notation préfixe/postfixe est particulièrement populaire pour sa capacité innée à exprimer l'ordre prévu des opérations sans avoir recours à des parenthèses et autres règles de priorité, comme c'est généralement le cas avec la notation infixe . Au lieu de cela, la notation indique de manière unique quel opérateur évaluer en premier. Les opérateurs sont supposés avoir chacun une arité fixe , et tous les opérandes nécessaires sont supposés être explicitement donnés. Une expression de préfixe valide commence toujours par un opérateur et se termine par un opérande. L'évaluation peut se dérouler de gauche à droite, ou dans la direction opposée. En commençant par la gauche, la chaîne d'entrée, composée de jetons désignant des opérateurs ou des opérandes, est poussée jeton par jeton sur une pile , jusqu'à ce que les entrées supérieures de la pile contiennent le nombre d'opérandes qui correspond à l'opérateur le plus haut (immédiatement en dessous). Ce groupe de jetons au sommet de la pile (le dernier opérateur empilé et le nombre correspondant d'opérandes) est remplacé par le résultat de l'exécution de l'opérateur sur ces/ces opérandes. Ensuite, le traitement de l'entrée continue de cette manière. L'opérande le plus à droite d'une expression de préfixe valide vide ainsi la pile, à l'exception du résultat de l'évaluation de l'expression entière. En commençant à droite, le push des tokens est effectué de la même manière, seule l'évaluation est déclenchée par un opérateur, trouvant le nombre approprié d'opérandes qui correspond à son arité déjà au sommet de la pile. Maintenant, le token le plus à gauche d'une expression de préfixe valide doit être un opérateur, adapté au nombre d'opérandes dans la pile, ce qui donne à nouveau le résultat. Comme on peut le voir dans la description, un magasin push-down sans capacité d'inspection arbitraire de la pile suffit à implémenter cette analyse .

La manipulation de pile esquissée ci-dessus fonctionne, avec une entrée en miroir, également pour les expressions en notation polonaise inversée .

Le tableau ci-dessous montre le cœur de la notation de Jan Łukasiewicz dans la logique moderne. Certaines lettres du tableau de notation polonaise correspondent à des mots particuliers en polonais , comme indiqué :

Notez que les quantificateurs s'étendent sur des valeurs propositionnelles dans le travail de Łukasiewicz sur les logiques à valeurs multiples.

Bocheński a introduit un système de notation polonaise qui nomme les 16 connecteurs binaires de la logique propositionnelle classique . Pour la logique propositionnelle classique, il s'agit d'une extension compatible de la notation de Łukasiewicz. Mais les notations sont incompatibles dans le sens où Bocheński utilise et (pour la non-implication et la non-implication inverse) en logique propositionnelle et Łukasiewicz utilise et en logique modale.

La notation préfixe a été largement utilisée dans les expressions S de Lisp , où les parenthèses sont nécessaires puisque les opérateurs du langage sont eux-mêmes des données ( fonctions de première classe ). Les fonctions Lisp peuvent également être variadiques . Le langage de programmation Tcl , tout comme Lisp, utilise également la notation polonaise via la bibliothèque mathop. Le langage de programmation Ambi utilise la notation polonaise pour les opérations arithmétiques et la construction de programmes. La syntaxe du filtre LDAP utilise la notation préfixe polonaise.

La notation postfixe est utilisée dans de nombreux langages de programmation orientés pile comme PostScript et Forth . La syntaxe CoffeeScript permet également d'appeler des fonctions à l'aide de la notation préfixe, tout en prenant en charge la syntaxe postfixe unaire courante dans d'autres langages.

Le nombre de valeurs de retour d'une expression est égal à la différence entre le nombre d'opérandes dans une expression et l'arité totale des opérateurs moins le nombre total de valeurs de retour des opérateurs.

La notation polonaise, généralement sous forme postfixée, est la notation choisie par certaines calculatrices , notamment celles de Hewlett-Packard . À un niveau inférieur, les opérateurs postfixés sont utilisés par certaines machines à pile telles que les grands systèmes Burroughs .