giovedì 16 febbraio 2012

RPN, la notazione polacca inversa

   Cosa sia una calcolatrice, oggi, è noto anche ai bambini. Viviamo in un mondo in cui le calcolatrici in grado di eseguire le quattro operazioni, tenere un numero in memoria e calcolare una percentuale si trovano ormai dentro le uova di pasqua. Anche le calcolatrici cosiddette "scientifiche", cioè  in grado di calcolare le funzioni trigonometriche, le radici, i logaritmi ed altro ancora, sono ormai molto diffuse. Le prime funzionano tutte seguendo la notazione algebrica, le ultime, invece, si possono trovare sia in notazione algebrica che in notazione polacca inversa, in inglese "reverse polish notation", normalmente abbreviata RPN.
   La notazione algebrica, la conosciamo tutti, è quella che si usa per scrivere normalmente le espressioni. Le calcolatrici moderne che la utilizzano sono in grado di eseguire i calcoli richiesti da una espressione semplicemente digitandoli così come sono scritti sulla carta, avendo come sola cura quella di sostituire le parentesi quadre e graffe con quelle tonde. La notazione polacca inversa, invece, è meno conosciuta. Sviluppata dall'australiano Charles Hamblin a partire dalla notazione polacca, l'RPN è una sintassi che consente non solo di descrivere qualunque espressione matematica senza la necessità di ricorrere all'uso delle parentesi ma, specialmente, di farlo senza perdere di vista, istante per istante, la logica di ciò che si sta facendo e, quando applicata ad una calcolatrice, osservando tutti i risultati intermedi. Tuttavia, non essendo di uso comune, presenta due controindicazioni: la prima è che servono alcuni minuti per comprenderne il funzionamento ed un'oretta per impratichirsi del suo uso, la seconda, ben più grave, è che dà dipendenza, proprio come l'eroina o la morfina. Sostanzialmente chi inizia ad usarla difficilmente, poi, riuscirà ad usare una normale calcolatrice per eseguire operazioni complesse.
   In realtà sia la notazione polacca che la notazione polacca inversa sono state concepite come sintassi per la descrizione di formule matematiche o algoritmi, l'RPN ad esempio è pesantemente utilizzato nel linguaggio FORTH, come la notazione diretta è usata nel LISP ma, a meno che noi non si programmi in questi linguaggi, il luogo dove avremo maggiori probabilità di incontrare l'RPN sono proprio le calcolatrici e, in particolare, quelle dell'Hewlett Packard. Ma come funziona una calcolatrice RPN?  Per spiegarlo occorre prima introdurre il concatto di Stack, o pila. Uno stack non è altro che una struttura di tipo LIFO, cioè Last In First Out. In pratica immaginiamo di avere la possibilità di impilare i numeri in una catasta, come se fossero dei pezzi di legna. Quando aggiungiamo tronchi nella catasta, quelli finiscono sopra, quando ne togliamo, li prendiamo sempre da sopra. L'ultimo tronco messo è anche il primo che verrà prelevato. Tuttavia, essendo i numeri molto più leggeri dei tronchi, preferiamo immaginarci la catasta come accessibile da sotto, e non da sopra, un po' come alcuni distributori di pacchetti di caramelle. Ora, che scegliamo di figurarci lo stack in un modo o nell'altro cambia poco, ma il secondo è quello proposto dalla HP nei manuali delle sue calcolatrici per cui, in seguito, lo adotteremo anche noi.
  Una volta definito il concetto di stack, procediamo col dire che la notazione polacca inversa vede gli operandi precedere gli operatori. In pratica gli operandi vengono progressivamente spinti nella catasta mano a mano che sono inseriti. Gli operatori unari, come ad esempio un seno, o un fattoriale, sfilano l'ultimo elemento della catasta e, dopo averlo processato, reinfilano il risultato. Gli operatori binari, come la somma o la sottrazione, sfilano due elementi dalla catasta. L'operazione viene eseguita fra il primo ed il secondo e, come nel caso di operazioni unarie, il risultato viene reinfilato nella catasta. Complicato? Solo apparentemente.
   Supponiamo, ad esempio, di voler trasformare in RPN l'espressione
10-3*2
scriveremo:
10 3 2 * -

In pratica, dopo aver inserito gli operandi nello stack, eseguiremo prima la moltiplicazione fra gli ultimi due operandi, togliendoli dallo stack. Il risultato verrà messo nello stack e quindi l'operazione successiva, la sottrazione, lo toglierà dallo stack e lo sottrarrà all'ultimo operando, sempre prelevandolo dallo stack, dove alla fine verrà messo il risultato.
   Facciamo, adesso, un esempio un po' più complesso, trasformando in RPN l'espressione
√((2-3)/(4-6))+√((2+3)*(4+5))
che diventerà
2 3 - 4 6 - / √ 2 3 + 4 5 + * √ +
   Interessante, direte voi, ma dov'è il vantaggio rispetto alla notazione algebrica? Bè, a parte la maggiore semplicità d'implementazione e l'ottimizzazione dell'uso della memoria, considerazioni che, con l'evolversi della tecnologia, sono divenute irrilevanti, il vero vantaggio è visibile quando si eseguono dei calcoli non partendo da una forma scritta, ma costruendo un ragionamento mano a mano che li si esegue. Facciamo un esempio chiarificatore: Sono in macchina (tranquilli, non guido io, quindi posso tranquillamente usare una calcolatrice senza provocare ecatombi) e mi viene la curiosità di calcolare l'energia cinetica accumulata dal veicolo. Guardo il tachimetro e scrivo 125 (siamo in autostrada) 1000 * 3600 / per avere la velocità in m/sec.  Butto un occhio sul display, quasi trentacinque metri al secondo, non male. Pigio per elevare al quadrato, poi prendo il libretto della macchina e scrivo 1850, chiedo a mia moglie che sta guidando, quanto pesa, scrivo 54 e + per sommare, scrivo il mio peso 95 e + per sommare, stimo il peso degli abiti che indossismo, scrivo 5 e + per sommare. Smanetto un po' col computer di bordo e scopro che ci sono 35 litri di gasolio nel serbatoio. Scrivo 35. Un litro di gasolio peserà meno di un chilogrammo, quanto esattamente non lo so, per cui tiro ad indovinare. Scrivo 0.8, * per moltiplicare e scopro che ci stiamo portando dietro 28 Kg di gasolio; pigio + per sommare. A questo punto sul display dovrei avere il peso totale del veicolo e penso: "cavoli, più di due tonnellate!" Però non è il peso che mi interessa, è l'energia. scrivo * per moltiplicare ed ottenere il doppio dell'energia, 2 / per averla in Joule ed ecco fatto.
   Se avete seguito con attenzione, avrete notato due cose:
  • se anche avessi deciso di sommare al peso del veicolo quello del contenuto dopo aver scritto il primo, non sarebbe cambiato nulla;
  • ho sempre avuto sott'occhio i valori intermedi e questi sono sempre stati valori logici, se ci fosse stato un errore marchiano, quindi, me ne sarei accorto.
   Vediamo, ora, come avrei fatto lo stesso calcolo con una calcolatrice in notazione algebrica.
   Avrei scritto 125/1000*3600=, per avere la velocità in m/sec. Elevo al quadrato ed inizio a moltiplicare per il peso, scrivendo X²*. A questo punto, o ho già chiaro che devo calcolare il peso dell'auto come una somma, e apro una parentesi, o inserisco il peso del libretto e, a questo punto, non posso più tornare indietro. Diciamo che sono una persona previdente, apro una parentesi ed inizio a sommare, fino a che non arrivo al gasolio, cioè (1850+54+95+5+. Decido, prima di scrivere i litri, che per convertirli in Kg servirà una moltiplicazione, quindi, vista la precedenza degli operatori, non ho bisogno di ulteriori parentesi, digito  35*0,8; chiudo la parentesi della somma e divido per due, cioè )/2=.
   Più semplice? Più complicato? No, nè più semplice nè più complicato, solo, in questo secondo caso, per decidere cosa digitare, ho dovuto fare delle considerazioni sulle operazioni successive, nel primo caso no. Irrilevante quando effettuiamo dei calcoli partendo da una equazione scritta ma, come già detto, significativo quando eseguiamo i calcoli mano a mano che costruiamo un ragionamento.
   Abbiamo visti i vantaggi delle calcolatrici che operano in RPN, ma quali sono i limiti? I limiti stanno nella dimensione dello stack che, nei modelli più economici, è limitata a quattro elementi. Questo non rappresenta un vincolo, nell'uso normale, perché ben difficilmente riusciremo a seguire a mente ragionamenti così complessi da richiedere uno stack di dimensioni maggiori, ma non è impossibile immaginare equazioni così complesse da non poter essere risolte con solo quattro livelli di stack. Del resto le stesse limitazioni si hanno nelle calcolatrici algebriche, dove il livello di nesting delle parentesi viene limitato. Anche in questo caso, però, l'RPN aiuta in quanto si presta a risolvere i problemi "osservandoli nel modo migliore".
   Presto i link alle migliori calcolatrici RPN per PC.

1 commento: