Notazione polacca

La notazione polacca è una particolare sintassi atta a denotare formule matematiche e algoritmi, caratterizzata dal fatto che gli operatori si trovano tutti a sinistra degli argomenti. Per questo motivo, viene anche detta notazione prefissa. Se l'interprete conosce in anticipo l'arietà di ogni operatore, la notazione polacca permette di descrivere univocamente qualsiasi formula o algoritmo senza utilizzare parentesi o altri elementi sintattici di separazione.

Deve il suo nome a Łukasiewicz, che la utilizzò per la prima volta intorno all'anno 1920 per semplificare il calcolo proposizionale; egli stesso ha dichiarato:

«I came upon the idea of a parenthesis-free notation in 1924. I used that notation for the first time in my article»

«L'idea di una notazione priva di parentesi mi venne nel 1924. Usai per la prima volta quella notazione nel mio articolo»

Sebbene non sia più di moda nell'ambito della logica, ha con il tempo acquisito una certa importanza in informatica. È parente stretta della più nota notazione polacca inversa (o notazione postfissa) che funziona in modo speculare (gli operatori si scrivono a destra, gli argomenti a sinistra).

Esempi

La formula in notazione infissa (standard):

2 + (3 × 4),

se trascritta in notazione polacca diventa:

+ 2 (× 3 4)

o più semplicemente:

+ 2 × 3 4

La notazione non è equivoca, dato che sappiamo che l'operatore "×" prenderà come argomenti i primi due argomenti disponibili (3 e 4), e restituirà un altro valore; similmente, "+" prenderà due argomenti: il risultato dell'operazione precedente è 14.

Supponendo ora di avere un operatore "mod" che presi due parametri interi $\alpha$ e $\beta$ restituisca il resto della divisione intera $\alpha /\beta$ ed un operatore "=" che dati due parametri $\alpha$ e $\beta$ restituisca Vero se hanno lo stesso valore e Falso altrimenti, l'espressione in notazione polacca

= mod n 3 0

restituisce Vero se e solo se il numero n è multiplo di 3.

Note

^ ^a ^b Jan Łukasiewicz, "Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls", Comptes rendus des séances de la Société des Sciences et des Lettres de Varsovie, 23:51-77 (1930). Tradotto da H. Weber come "Philosophical Remarks on Many-Valued Systems of Propositional Logics", in Storrs McCall, Polish Logic 1920-1939. Clarendon Press, Oxford, 1967.