Newsgroup: it.scienza.informatica
Titolo: dal diagramma di flusso...

Salve a tutto il NG,
vi propongo il seguente problema:
ipotizziamo di avere un linguaggio che
abbia tutte le piu' comuni istruzioni di un
linguaggio strutturato, eccezion fatta
per le istruzioni ripetitive di cui ne e'
presente una sola che consiste di un ciclo infinito:
LOOP
....
END
Sia presente *una sola* istruzione di salto:
BREAK(condizione)
Se "condizione" e' vera si verifica un salto
all'istruzione immediatamente successiva al corpo
del ciclo in cui si trova tale istruzione
(in modo simile al 'break' in C++).
L'uso del BREAK e' l'unico modo per uscire dal ciclo.
Per esempio
" while(condizione) { istruzioni } "
diventa:
" LOOP
     BREAK( not(condizione) )
     istruzioni
END "
oppure:
" do { istruzioni } while(condizione) "
diventa:
" LOOP
     istruzioni
     BREAK( not(condizione) )
END "
La domanda e' la seguente:
dato *un qualsiasi* diagramma di flusso (questo puo' essere
rappresentato mediante un grafo orientato o una tabella),
e' possibile scriverne il relativo codice in questo linguaggio?
Se si', qual e' l'algoritmo che mi permette di costruire tale codice?
Io penso di aver trovato un tale algoritmo, non ho pero' una
dimostrazione formale della sua validita'.
Non sono un informatico 'puro', quindi per me aver trovato una
soluzione a questo problema e' una grossa soddisfazione,
tenendo anche conto che la soluzione mi serviva urgentemente.
Vorrei sapere (se mi sono spiegato bene) come e' stato risolto
il problema in letteratura, se qualcuno ne e' a conoscenza
magari mi puo' dare un indizio o una documentazione.
Grazie, Phoenix.

 e' possibile scriverne il relativo codice in questo linguaggio?
No. I diagrammi a blocchi (intesi come flow-chart) permettono di scrivere
costrutti più ampi dei "soli" costrutti presenti nei linguaggi strutturati.
In generale per codificare un generico flow-chart potrebbe essere necessario
utilizzare istruzioni GOTO label. Questo tipo di istruzione rende i
programmi non strutturati.
Ciao. Federico M.

 costrutti più ampi dei "soli" costrutti presenti nei linguaggi
strutturati.
Su questo sono d'accordo e capisco anche perche' hai messo
"soli" tra virgolette, ma siamo sicuri che l'uso del break non
reintroduca l'ampliamento di cui parlavi?
Ti faccio un esempio, sia dato il seguente frammento di codice:
    ....
    ....
L1:  B1;
        switch (b1)
        {
            case 1:  goto L1;
            case 2:  goto L2;
            case 3:  goto L3;
        }
L3:  B2;
        switch (b2)
        {
            case 1:  goto L1;
            case 2:  goto L2;
            case 3:  goto L3;
        }
L3:  B3;
        switch (b3)
        {
            case 1:  goto L1;
            case 2:  goto L2;
            case 3:  goto L3;
        }
    ....
    ....
B1, B2, B3 rappresentano blocchi di istruzioni sequenziali.
Ciascuno di questi blocchi produce un valore (intero da 1 a 3):
B1 produce b1, B2 produce b2, B3 produce b3.
Il blocco con indice k puo' alterare solo la variabile bk,
ad esempio B1 non puo' manipolare b2 o b3.
Possiamo visualizzare il diagramma di flusso come un
grafo orientato in cui B1, B2, B3 sono i nodi.
Gli archi del grafo rappresentano, chiaramente, i possibili
salti da un blocco a un altro. A ciascun arco e'
assegnato un valore (intero da 1 a 3). Archi che hanno
origine (archi orientati) nello stesso nodo hanno valori diversi.
Un arco e' "attivato" quando il valore ad esso assegnato
e' uguale a quello prodotto dal nodo da cui esso ha origine.
Dal precedente codice si deduce che ogni nodo e' connesso ad ogni altro.
Cioe' si puo' verificare ogni tipo di salto, da un generico
nodo ad un altro (compreso verso se stesso).
Ci troviamo dunque nella situazione "peggiore",
ovvero in quella piu' complessa possibile per quanto riguarda
grafi con tre nodi.
Il seguente codice (non ottimizzato), privo dei goto,
ha esattamente lo stesso flusso del precedente frammento:
.....
.....
while(true)
{
    B1;
    if (b1==2)
    {
        while(true)
        {
            B2;
            if (b2==1) break;
            if (b2==3)
            {
                while(true)
                {
                    B3;
                    if(b3!=3) break;
                }
                if(b3==1) break;
            }
        }
    }
    else if (b1==3)
    {
        while(true)
        {
            B3;
            if (b3==1) break;
            if (b3==2)
            {
                while(true)
                {
                    B2;
                    if(b2!=2) break;
                }
                if(b2==1) break;
            }
        }
    }
}
.....
.....
Aumentando il numero di nodi (ho verificato solo fino a cinque
perche' per ora eseguo l'algoritmo a mano) penso che si
possa sempre trovare un codice che faccia a meno dei goto e
che usi in alternativa il break.
Probabilmente si puo' dimostrare per induzione che la cosa
funziona sempre. Ti viene in mente un controesempio?
Grazie e ciao,
Phoenix.

 L3:  B2;
correzione:
L2:  B2;



Non c'è bisogno di alcun controesempio, anche perchè non c'è!
Vale infatti il seguente teorema (se non ricordo male è di Bohm-Jacopini):
"un qualunque algoritmo può essere espresso usando esclusivamente le
struture di sequenza, selezione e iterazione", cioè i costrutti dei
linguaggi strutturati.
Se si può fare con gli algoritmi, allora si può fare anche con i diagrammi a
blocchi. Quello che intendevo dire io è che è impossibile una traslazione
(leggi codifica) di un qualunque diagramma a blocchi in un programma scritto
con un linguaggio strutturato. Occorre prima applicare una serie di passi
per "strutturare" il programma e questo penso sia quello che vuoi fare tu...
Ciao. Federico.


Questa e' l'alternativa (migliore) a cio' che penso di aver fatto io.
Ripeto: se guardi bene i due codici del mio precedente post,
questi hanno *esattamente* lo stesso diagramma di flusso (quello inteso
secondo le mie convenzioni, definito con un approccio probabilmente
piu' topologico che informatico).
Non penso di aver strutturato il codice, oppure mi sfugge qualcosa...
Mi puoi rimandare a qualche testo sull'argomento, oppure indicarmi
qualche sito che lo affronta?
Grazie, Phoenix.

 funziona sempre. Ti viene in mente un controesempio?
Ciao,
secondo me il problema non e' nell'"uscita" da un loop (cosa fattibile
con il tuo BRAK) ma nei loop con piu' di un'entrata. Questi strutture
improprie (mi sa che questa e' una traduzione uscita male) non possono
essere generate con dei linguaggi strutturate ma solo con l'uso di un
goto.
L'esempio piu' semplice di un diagramma del genere ha tre nodi A,B a C 
con i seguenti archi:
A -> B
A -> C
B -> C
C -> B
Ciao
    Matteo
-- 
Matteo Corti
Computer Systems Institute
Swiss Federal Institute of Technology Zurich


Nel tuo esempio va bene anche un costrutto strutturato,
il seguente codice copre il diagramma da te proposto:
A;
if ( 'A->B' )  B;
while(true)
{
    C;
    B;
}
Ciao, Phoenix.

 }
Ciao,
hai ragione, in effetti "clonando" il blocco B il programma e'
strutturato. Al momento non mi vengono in mente altri controesempi ma
purtroppo non sono neanche riuscito a trovare una referenze a una
dimostrazione del contrario.


 strutturato.
Forse hai colto il centro della questione, il termine che hai usato,
"clonando", mi ha illuminato.
Nel mio codice ho duplicato (o clonato) il blocco B e probabilmente
nel diagramma di flusso devo considerare due blocchi
distinti B e B' anche se questi hanno la stessa funzione.
Il diagramma relativo sarebbe:
A -> B'
A -> C
B' -> C
C -> B
B -> C
ben diverso da quello originario.
In questi termini, scrivendo quel codice ho realizzato una
sorta di "strutturazione" e forse era quello che cercava di
dirmi Federico nei precedenti post.
Ciao, Phoenix.

Allora nella programmazione strutturata usare istruzioni di salto
incodizionato è considerato quasi un sacrilegio, a meno che non
contribuiscano ad una scrittura di codice piu chiara e meno prolissa ( senza
esagerare però ).
Ora se invece di lambiccarsi il cervello con teorie e ca@@i vari ci dici
qual'è il tuo problema di programmazione ( perchè di questo si tratta )
forse una soluzione la possiamo trovare.
Ciao
--------------------------------
Inviato via 
http://usenet.libero.it

 e' possibile scriverne il relativo codice in questo linguaggio?
Ti sei gia' risposto: se hai branching e sequencing, e le strutture di 
ciclo nel linguaggio di partenza sono  ad esempio, while <condition> 
<block> oppure do <block> while <condition>, basta prevedere un passo di 
riscrittura che riscriva la prima struttura in loop if <condition> break; 
<block> end oppure loop <block> if <condition> break; end.
Pero' occhio che un diagramma di flusso (se intendi flusso di controllo) 
*non* denota necessariamente un blocco strutturato (anche se si puo' sempre 
scrivere un blocco strutturato semanticamente equivalente - era il punto 
del "goto considered harmful" di Dijkstra).
-- 
Life's something u don't get out alive..
ObjectZone - 
http://space.tin.it/computer/csadun


Ok, ti spiego il mio problema:
Dovevo tradurre il programma X da Fortran a Matlab.
Chi ha programmato X (la prima versione del programma
risale a 20 anni fa e ha subito diverse modifiche)
non e' stato molto raffinato, ha fatto una serie di schifezze,
tra le quali ha abusato dell'istruzione goto con conseguente
incasinamento del codice (circa 15000 righe).
Allora io ho pensato: taglio la testa al toro e uso anche io i goto!
Invece no: il Matlab non ha tale istruzione!
Cosi' mi sono disperato e poi ho trovato una
soluzione mia personale che usa cicli infiniti e
l'istruzione break (presente in matlab), quindi il problema l'ho risolto.
Mi e' rimasta pero' la curiosita' di sapere come avrebbe
affrontato e risolto la questione un informatico, anche per
valutare la bonta' della mia soluzione, e ho cercato
di isolare il problema dal mio caso particolare, quindi
ho postato su questo NG (i miei amici informatici non
hanno saputo darmi una risposta).
Forse adesso la cosa e' piu' chiara, spero di si.
Grazie, Phoenix.