Newsgroup: it.comp.lang.c
Titolo: stack, push, pop...

Salve a tutti,
volevo sapere come funziona il dimensionamento dello stack in C, e delle
funzioni push e pop (sempre in C, niente assembler). Il mio problema
riguarda un esercizio sulla notazione polacca inversa, qualcuno mi puo'
essere d'aiuto?
Grazie,
Diego.

 inversa, qualcuno mi puo' essere d'aiuto?
  Non esiste nessuna nozione di stack in C, se non quella utilizzata da
alcuni compilatori per il passaggio di parametri alle funzioni e per
l'allocazione delle variabili automatiche, comunque non accessibile
programmaticamente.
  Tuttavia e` possibile implementarlo, per esempio utilizzando un array.
<code>
	/*
	 * Add some controls if you hate surprises...
	 */
	#define STACK_SIZE ...
 
	static int stack[STACK_SIZE];
	static head=0;
	void push(int what)	{ *(stack+head++)=what; }
	int  pop()		{ return *(stack+head--); }
</code>
	Alla prossima,
		Marco

Attenzione. La funzione pop() e' sbagliata.
Per completezza aggiungerei anche i controlli fondamentali. Ecco la
versione corretta:
#define STACK_SIZE ...
static int stack[STACK_SIZE];
static head=0;
void push(int what) { if (head<STACK_SIZE) stack[head++]=what; }
int  pop() { if (head>0) return stack[--head]; else return 0;}

int  pop() { if (head>0) return stack[--head]; else return 0;}
NO! ... secondo me questo codice C e' *pessimo*.
Ho visto spesso questo tipo di approccio alla programmazione e
non posso che manifestare il mio totale dissenso. Le routine che
hai scritto non sono affatto migliori di versioni che non
facciano i controlli; se possibile sono in realta' *peggiori*.
Una routine che, come proponi tu, nasconde un errore logico e'
l'equivalente di qualcuno che emette assegni scoperti, oppure
equivale a un tecnico di radiologia che se la macchina per i
raggi e' rotta invece di dirtelo ti consegna le lastre mai
ritirate di qualcun altro e strilla "avanti il prossimo".
Il codice che hai scritto evita i crash ma NASCONDE GLI ERRORI;
questo mi fa credere che tu abbia una visione non corretta
della programmazione; un paio regole basilari da ricordare sono
a mio parere:
  *************************************************
  I crash sono tuoi amici: gli errori sono i nemici
  *************************************************
  Un buon programmatore i crash li cerca. Scrive righe di
  codice con il solo scopo di provocare degli arresti brutali
  del programma. Una versione migliore di quella che non
  fa controlli potrebbe essere:
     void push(int what)
     {
       assert(head<STACK_SIZE);
       stack[head++]=what;
     }
     int pop(void)
     {
       assert(head>0);
       return stack[--head];
     }
  Le due righe di codice aggiunte (le assert) altro non sono
  che qualcosa che blocchera' istantaneamente il programma in
  modo molto chiassoso nel caso che la condizione non venga
  rispettata... qualcosa di molto simile a quello che succede
  in caso di crash... una specie di "crash pilotato".
  Trasformare un crash in un errore silenzioso e' un passo
  deciso nella direzione sbagliata.
  ******************************************************
  Un programma che provoca un crash contiene sicuramente
  un errore. Un programma che contiene un errore NON E'
  PERO' DETTO che provochi un crash. La conseguenza e'
  che un programma senza crash non e' necessariamente
  un programma senza errori.
  ******************************************************
  Se un programma si blocca con un crash in uno statement come
                      stack[head++]=what;
  perche' head ha assunto il valore 123452821 la tua soluzione
  non migliora affatto il programma; semplicemente nasconde
  agli altri (e finge di non vedere) l'errore. Chi ha messo
  piu' di 120 milioni di elementi in uno stack dimensionato
  per riceverne al massimo 1000 probabilmente sta sbagliando
  qualcosa (oppure lo stack doveva essere dimensionato di
  conseguenza) e se il tuo codice semplicemente "ignora"
  silenziosamente le richieste di push altro non sta facendo
  che come quel tecnico di radiologia che fornisce al dolorante
  malcapitato le lastre di qualcun altro che si sentira' poi
  dire dal medico "non si preoccupi... il braccio non e'
  rotto: ci vada pure a giocare a tennis".
  Una versione seria deve *ANTICIPARE* il crash, bloccando il
  programma violentemente non appena il chiamante tenta di
  fare la push numero 1001 (supponendo che STACK_SIZE sia 1000).
  Un programmatore che abbia a cuore la correttezza del codice
  che scrive cerca di trasformare il maggior numero possibile
  di errori in crash. Una tecnica abbastanza nota e' quella
  chiamata DBC (Design By Contract) che, ridotta al contesto
  delle funzioni C, potrebbe essere riassunta in:
  Per ogni funzione:
  1) Stabilire esattamente e formalmente quali sono i
     valori accettabili in ingresso e le condizioni di
     operativita' previste (pre-condizioni)
  2) Stabilire esattamente quali sono le garanzie fornite
     all'uscita dalla funzione (post-condizioni)
  3) Verificare le pre-condizioni in ingresso e provocare
     un crash pilotato in caso di violazioni. In questi
     casi la "colpa" e' del chiamante che non ha rispettato
     il contratto e li' deve essere cercato l'errore.
  4) Verificare le post-condizioni in uscita e provocare un
     crash pilotato in caso di violazioni. In questi casi
     la "colpa" e' della routine stessa che non ha rispettato
     il contratto e li' deve essere cercato l'errore.
  A volte il codice in (4) e' cosi' banale che il test delle
  post-condizioni e' tanto o piu' complicato della funzione
  stessa e in questi casi semplicemente non ha a mio parere
  molto senso metterlo.
  Le pre-condizioni invece dovrebbero essere sempre valutate
  (anche nelle funzioni banali come push e pop) in quanto il
  contesto in ingresso e' sempre ignoto.
HTH
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

  in caso di crash... una specie di "crash pilotato".
Sono perfettamente d'accordo.
C'e' un bell'articolo su Computer Programming di questo mese sul
Design by Contract, che consiglia, per l'appunto, l'uso di assert per
il controllo delle pre/post-condizioni.
--
Andrea Laforgia (ICQ 87230455)
http://www.geocities.com/AndreaLaforgia
"ci sono tre tipi di persone nel mondo : quelli che
 sono bravi in matematica e quelli che non lo sono."

Non vorrei turbare la quiete del gruppo, oltre che al suo spirito
filosofico, ma quando parlavo di errore nella funzione pop() proposta,
piu' brevemente mi riferivo al decremento postifisso dell'indice, una
veniale svista del pur abile autore.
Ovviamente non cerchero' di difendere a spada tratta la mia versione
(5 righe di codice non sono certo un vanto), ma solo per completezza
faccio sapere che ho scelto questo stile perche' di livello piu'
"adeguato" alla domanda e per fornire una versione alternativa
volutamente corta in numero di _caratteri_.
In merito alle altre vostre considerazioni, i paragoni proposti, ...
potrei essere d'accordo purche' si giudichi nel modo piu' congruo
l'opportunita' di tali eventi quando, per esempio, avvengono
improvvisamente (qualunque cosa ne sia la causa) in software che
dovrebbero garantire la robustezza di un sistema (alcuni diffusi
sistemi operativi, ...). In tali casi, volendo aggiungere un nuovo
paragone a quelli proposti, sarebbe indicato un paracadute che non si
apre nel momento opportuno.
In definitiva sono d'accordo sulle considerazioni aggiunte a patto che
il campo di attivita' lo permetta (chissa' perche' mi tornano alla
mente esempi di sistemi di ausilio programmati sia in campo militare
che in quello astronautico).
Plaudo all'uso della "assert" spero secondo i dettami delle "weakest
precondition", sulle quali non mi esprimo.

"weakest precondition", sulle quali non mi esprimo.
Perche plaudi sull'adottare una cosa su cui pero' non ti
esprimi ? Comunque .... Ahhhh ... mi hai colpito a morte:
non so cosa sia questa weakest precondition... 
Ha per caso qualcosa a che fare con la tecnica di usare la
stessa variabile indice in due cicli nidificati che hai
mostrato in quella specie di mal riuscito crivello di
eratostene del post su clock() ?
Io avevo scritto un po' di appunti su alcune imprecisioni
di quel post ma non ho inviato la cosa perche' avevo appena
scritto il post su push/pop e non volevo che tu pensassi che
ce l'ho con te (io contro di te non ho nulla... semplicemente
odio il pressapochismo in programmazione).
Comunque visto che ci siamo:
 - time_t non e' un long... e' un time_t
 - time_t e' restituito ad esempio da time(...) e non e' il
   numero di clock dall'accensione del computer ma il numero
   di secondi dalla mezzanotte dell'1/1/1970 (ci sarebbe il
   discorso dei secondi bisestili ma lasciamo stare).
 - intendevi forse clock(...) ? questa restituisce pero' un
   numero di "colpi di clock" non dall'accensione del
   computer ma dall'esecuzione del programma.
   Inoltre non restituisce time_t ma clock_t (che diviso per
   CLOCKS_PER_SEC da un tempo in secondi).
   No... neanche clock_t e' un long... e' un clock_t.
 - oltre al formato time_t e stringa esiste anche la
   comodissima struct tm (con giorno, mese, anno e altri
   campi in formato numerico).
 - non e' bello scrivere main come funzione void
 - due loop nidificati che usano la stessa variabile ?
 - a cosa serve num ? doveva forse contare i numeri primi ?
Mah... vado a nanna, che e' meglio


Ultimo mio messaggio a questa discussione.
Cito dal primo messaggio che la struttura a pila doveva servire ad
implementare la RPN ("Reverse Polish Notation") tipica di linguaggi
come il FORTH (ed altri), e di praticamente tutte le implementazioni
di macchine calcolatrici HP (dal vetusto modello HP11C, ad oggi).
Ora, in tale modello di calcolo matematico, non e' ammissibile una
pila "dati" che si blocca, anche quando si cerca di prelevare un dato
da pila vuota; in particolare, in questo caso, viene "estratto" per
default il numero "0".
Ecco spiegato l'uso dell'else nella mia pop();
Rimangono valide tutte le altre mie precisazioni sulla prima versione.
Per quanto riguarda le "weakest precondition", dovrei rimandarti alla
lettura attenta di "Progettazione razionale di programmi" - prof.
V.Ambriola , prof. P.Ciancarini - Dipartimento di Informatica -
Universita' degli studi di PISA.
Brevemente, non sono esattamente la stessa cosa che declamavi, ma con
un po' di sforzo sono formalmente riconducibili a quanto asserivi.
Approvo ogni replica, se scaturita da questo metodo progettuale, e
analizzata non prescindendo dal contesto del problema, in questo caso,
l'implementazione di una pila per RPN, appunto.
Appurato che la moltitudine di messaggi porta inevitabilmente ad una
lettura, spesso, superficiale, e talvolta a risposte frammentate e
poco esaustive, che ovviamente si prestano a tutta una serie di
interpretazioni, anche sbagliate, ti esorterei non a farti alcuno
scrupolo nel rivelare quelle che tu credi inesattezze o imperfezioni,
arrivando ad aprire nuove discussioni su argomenti che ti giungono
nuovi. (Per quanto mi riguarda, adottero' tale metodo)
Con riferimento a quanto scrivi nella parte conclusiva della tua
replica (la mia soluzione al problema del clock interno), posso
senz'altro concludere che ho felicemente terminato una discussione che
si prolungava stancamente da decine di messaggi.
La versione proposta ha un pregio: funziona, indipendentemente dalla
macchina, sistema operativo, compilatore, programmatore, lettore, ...
La ridondanza del programma di esempio e' lecita e voluta per vincere
alcune piccole eventuali ottimizzazioni citate nei messaggi
precedenti. L'uso di quel codice era finalizzato ad altri scopi:
quello di misurazione del tempo, non certo alla pur corretta
risoluzione del problema proposto.
Passo e chiudo.

Passo e chiudo.
nano-nano
