Programmazione stack-oriented

La programmazione stack-oriented (letteralmente "orientata alla pila"), o stack-based ("basata su pila") è un paradigma di programmazione che basa il suo funzionamento su una macchina a stack (stack machine) a cui passare i parametri. Diversi linguaggi seguono questo paradigma, fra i più noti Forth, RPL, PostScript, e vari linguaggi assembly (di livello meno astratto).

I linguaggi stack-oriented operano su una o più pile (stack), ciascuna delle quali possono avere scopi diversi. Per cui, gran parte dei costrutti di programmazione che possono essere usati in altri linguaggi devono essere modificati per poter funzionare in un sistema a pila. Inoltre, alcuni linguaggi stack-oriented operano in notazione polacca inversa (o postfissa), ovvero, ogni argomento o parametro per un comando viene espresso prima del comando stesso. Per esempio, in notazione postfissa si scriverebbe 2, 3, multiply anziché multiply, 2, 3 (notazione polacca o prefissa), o 2 multiply 3 (notazione infissa).

Teoricamente l'interpretazione dei programmi scritti secondo il paradigma stack-based è più veloce rispetto a quelli scritti secondo modelli più classici, in quanto non dev'essere eseguita un'analisi sintattica, ma solo lessicale.

Algoritmi stack-based

Consideriamo un linguaggio stack-based in notazione postfissa, come PostScript. Per capire il funzionamento di un sistema a pila, consideriamo un'espressione matematica come 2 3 mul.

Illustrazione

Dapprima verrà preso 2 e posto sulla pila, seguito da 3. In seguito si incontra mul, che è un operatore che indica un'istruzione da eseguire. Le istruzioni dell'operazione mul prevede che gli ultimi due valori nella pila vengano estratti, moltiplicati e scartati, e che il risultato della loro moltiplicazione (6) venga ri-aggiunto sulla pila.

Nel caso di calcoli più complessi, come (2 + 3) × 11 + 1 (in notazione postfissa 2 3 add 11 mul 1 add), il calcolo può essere eseguito nella stessa maniera. I passi dell'algoritmo per eseguire il calcolo di cui sopra sono mostrati nella tabella seguente. Ogni colonna mostra un elemento in ingresso e il contenuto dello stack dopo aver processato tale input.

Input 2 3 add 11 mul 1 add
Stack 2 3
2 		5 11
5 		55 1
55 		56

La programmazione basata su stack funziona quindi prelevando un determinato numero di valori dalla cima alla pila (pop) per poterli processare e riaggiungere il risultato in cima allo stack (push).

Manipolazione dello stack

Generalmente, i linguaggi di programmazione basati su pila forniscono metodi per manipolare la pila stessa. Fra i più comuni, dup per duplicare l'elemento in cima allo stack, exch (o swap) per scambiare i due elementi in cima, roll per permutare in maniera ciclica un sottinsieme degli elementi in cima,[1] o pop (o drop) per scartare l'elemento in cima.

Per mostrare gli effetti di un operatore, può essere usato un commento. La notazione seguente è usata solitamente in Forth, dove i commenti sono inseriti fra parentesi. 

( prima -- dopo )

Per esempio, gli operatori basilari del Forth sono descritti come segue: 

dup  ( a -- a a )
drop ( a -- )
swap ( a b -- b a )
over ( a b -- a b a )
rot  ( a b c -- b c a )

E la funzione fib è descritta come segue: 

fib  ( n -- n' )

Note

  1. ^ (EN) 5.5.1 How Roll Works, su ubc.ca, Università della Columbia Britannica (archiviato il 22 febbraio 2003).

Voci correlate

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica