Programmi

(1)

Programmi

Corso di Informatica

CdL:

Chimica

Claudia d'Amato

claudia.damato@di.uniba.it

(2)

2

2 Comunicazione

Comunicazione

dell’algoritmo all’elaboratore



Linguaggi non ambigui e sequenziali



Comprensibili alla macchina



Requisiti per la descrizione



Univoca

Non dà adito ad interpretazioni errateNon dà adito ad interpretazioni errate



Completa

Prevede tutte le azioni necessariePrevede tutte le azioni necessarie



Ripetibile

Garantisce il medesimo risultato se eseguita da più Garantisce il medesimo risultato se eseguita da più

esecutori con medesime caratteristiche esecutori con medesime caratteristiche

(3)

3

3 Programmazione

Programmazione



Descrizione del procedimento di

soluzione di un problema ad un

esecutore meccanico



Poiché l’esecutore è meccanico,

consiste nel



Ricondurre il problema da risolvere a

problemi primitivi

 Eseguibili come insieme di azioni primitive



Organizzare ed utilizzare le “risorse”

(4)

4

4 Programmazione

Programmazione



Trasformazione della descrizione di

un algoritmo in un Insieme di

istruzioni codificate in un linguaggio

interpretabile da un esecutore



con indicazioni sui dati di ingresso e

uscita



Passa attraverso un’astrazione



delle operazioni che del procedimento

prevede



della rappresentazione dei dati su cui il

(5)

6

6 Programma: Sintesi

Programma: Sintesi



Procedura eseguibile su calcolatore, che

rappresenta una soluzione ad un problema



Risultato di un lavoro di analisi e progetto che

inizia dalla formulazione del problema



Corrisponde alla tripla

(6)

7

7 Dati

Dati



Entità su cui lavora il programma



Costanti



Variabili



Rappresentati come sequenze di bit



Nei linguaggi ad alto livello il

programmatore può ignorare i dettagli della

rappresentazione

(7)

8

8 Istruzioni

Istruzioni



Operative



Lavorano su rappresentazioni delle entità del

problema



Dichiarative



Consentono di definire come interpretare e

rappresentare tali entità in termini di

variabili nel programma

Totale caratterizzazione mediante la definizione di:

 Un nome

 Un tipo → Determinano: 1) Insieme dei valori Insieme dei valori permessi; 2) Insieme delle operazioni applicabili

(8)

10

10 Tipi di Istruzioni

Tipi di Istruzioni



Un linguaggio di programmazione dispone di:

 Istruzioni di ingressoIstruzioni di ingresso

 Permettono all’esecutore di conoscere informazioni fornite _{Permettono all’esecutore di conoscere informazioni fornite}

dall’esterno dall’esterno

 Istruzioni di uscitaIstruzioni di uscita

 Permettono all’esecutore di notificare all’utente i risultati Permettono all’esecutore di notificare all’utente i risultati

ottenuti dall’elaborazione ottenuti dall’elaborazione  Istruzioni operativeIstruzioni operative

 Permettono di effettuare calcoli o, comunque, operazioni Permettono di effettuare calcoli o, comunque, operazioni

sulle entità astratte rappresentanti gli elementi del problema sulle entità astratte rappresentanti gli elementi del problema  Strutture di controlloStrutture di controllo

(9)

14

14 Variabile

Variabile



Nome simbolico per denotare un’area di

memoria e, tramite essa, il valore

contenuto



Contiene una rappresentazione di un oggetto

su cui l’algoritmo opera



Memorizzazione di un valore

 Istruzioni di ingressoIstruzioni di ingresso

(10)

15

15 Variabile I 2

Variabile I 2



Caratterizzata da



Un nome

 IdentificatoreIdentificatore 

Un valore



Un tipo

 Attributo che specifica l’insieme di valori che Attributo che specifica l’insieme di valori che

la variabile può assumere

 L'insieme delle operazioni effettuabili sulla L'insieme delle operazioni effettuabili sulla

variabile

 Non ci interessiamo della rappresentazione

(11)

18

18 Definizione di Tipo

Definizione di Tipo

nei Ling. di Programmazione



I moderni linguaggi di programmazione

mettono a disposizione



Un insieme di tipi di uso più comune

 Tipi predefinitiTipi predefiniti



Gli strumenti per poter costruire qualunque

tipo di dati

(12)

19

19 Tipi Standard

Tipi Standard



Tipi più comuni di variabili

 InteriInteri  RealiReali

 BooleaniBooleani  CaratteriCaratteri

(13)

21

21 Tipo degli Interi

Tipo degli Interi



Valori nell’insieme dei numeri interi



Stringa di cifre,

eventualmente preceduta dal segno

 PositiviPositivi  NegativiNegativi



Operazioni basilari



somma, prodotto, differenza, quoziente, resto,

elevamento a potenza

(14)

22

22 Tipo degli Interi

Tipo degli Interi



Non sono in numero infinito nell’aritmetica dei

calcolatori

 Per ogni macchina esistonoPer ogni macchina esistono

 il più grande intero_{il più grande intero}  il più piccolo interoil più piccolo intero

rappresentabile in una locazione di memoria



Alcune proprietà dell’aritmetica non restano

valide in generale

 Risultato di un’operazione non rappresentabileRisultato di un’operazione non rappresentabile

 Overflow_Overflow

(15)

28

28 Tipo dei Reali

Tipo dei Reali



Rappresentazione ottenuta per

troncamento o arrotondamento



Possibili errori di precisione anche consistenti



Esiste un valore massimo



Overflow

 Rappresentazione indefinita per tutti i valori Rappresentazione indefinita per tutti i valori

maggiori maggiori

(16)

35

35 Tipo dei Valori Logici

Tipo dei Valori Logici



Rappresentano valori di verità



Falso, Vero

 Falso < VeroFalso < Vero



Usati tipicamente nelle condizioni

(17)

36

36 Tipo dei Valori Logici

Tipo dei Valori Logici

Operatori



Per priorità decrescente:



not



and



or



Sottoinsieme completo



Può simulare tutti gli altri operatori logici

V V F V V V F F F V V F V V F F F V F F x or y x and y not x y x

(18)

37

37 Tipo dei Caratteri

Tipo dei Caratteri



Insieme finito ed ordinato di simboli

 Lettere dell’alfabetoLettere dell’alfabeto  Cifre decimaliCifre decimali

 PunteggiaturaPunteggiatura  Simboli specialiSimboli speciali

 Spaziatura (_{Spaziatura (}blank_blank), Ritorno carrello, A capo, Separatore di _{), Ritorno carrello, A capo, Separatore di}

linea (EOL), … linea (EOL), …



Costanti di tipo Carattere racchiuse tra apici

(19)

38

38 Tipo dei Caratteri

Tipo dei Caratteri

Rappresentazione



Corrispondenza biunivoca tra l’insieme dei

caratteri e un sottoinsieme degli interi

 Standard Standard ASCIIASCII

(American Standard Code

for Information Interchange)

7 bit

→

2

77

_{= 128 simboli}

 UNICODEUNICODE

16 bit

(20)

40

40 Tipo dei Caratteri

Tipo dei Caratteri

Note



Alcuni caratteri non sono stampabili



Esempio:

campanello (

bell

)



NB: caratteri che rappresentano cifre

hanno come rappresentazione interna un

valore diverso dalla cifra che

rappresentano



Relazione d’ordine totale



Proprietà riflessiva, antisimmetrica, transitiva



∀

x, y: x

≤

y

∨

y

≤

x

(21)

41

41 Istruzioni di Ingresso

Istruzioni di Ingresso



Permettono di acquisire informazioni

dall’esterno, inserendole in opportune

variabili del programma



Attivano un’operazione di lettura

 Assegnazione del valore letto su un supporto di memorizzazione esterno

 schede, nastri e dischi magnetici, …

ad un’area di memoria individuata dal nome che compare nell’istruzione di lettura

(22)

43

43 Assegnazione

Assegnazione



Per produrre il valore si possono usare

espressioni (aritmetiche o logiche) il cui risultato

è un singolo valore



Il valore prodotto dall’espressione a destra viene

memorizzato nell’area di memoria riservata alla

variabile a sinistra

 La memorizzazione del valore ottenuto nella locazione di memoria riservata alla variabile implicata

nell’assegnamento rimpiazza qualunque valore contenuto in precedenza

(23)

44

44 Legami degli Identificatori

Legami degli Identificatori



Identificatore – Posizione di memoria



Statico



Identificatore – Valore



Dinamico nel programma

Identificatore Identificatore Posizione Posizione di Memoria di Memoria Posizione Posizione di Memoria

di Memoria ValoreValore

denota staticamente

denota

dinamicamente contiene

(24)

45

45 Legami degli Identificatori

Legami degli Identificatori



La dinamicità del legame identificatore-

La dinamicità del legame

identificatore-valore consente di scrivere senza

valore consente di scrivere senza

contraddizioni assegnazioni del tipo

x

←

x + 1



Alla posizione di memoria identificata da

x

_x

assegna il valore ottenuto calcolando la

somma del valore già memorizzato e

(25)

46

46 Assegnazione

Assegnazione

Computo dei Valori



Le operazioni di assegnazione possono

implicare calcoli complessi



Espressioni aritmetiche

(26)

47

47 Espressioni Aritmetiche

Espressioni Aritmetiche



Formate da associazioni di variabili e costanti

secondo regole opportune e attraverso

l’applicazione di definiti operatori numerici

Potenza “ **, ˆ, … Divisione “ /, ÷, DIV, … Prodotto “ *, ·, … Differenza “ -, … Somma Numerico + Operazione Tipo di valore cui dà luogo

(27)

48

48 Espressioni Logiche o

Predicati



Usate in:

 Assegnazioni fatte ad una variabile logica  Strutture di controllo che comportano la verifica di condizioni Minore o uguale “ ≤ Maggioranza “ > Maggiore o uguale “ ≥ Minoranza “ < Diversità “ ≠ Uguaglianza “ = Connettivi logici Logico NOT, AND, OR Operazione Tipo di valore cui dà luogo Simbolo

(28)

49

49 Costanti

Costanti



Dati il cui valore viene definito

inizialmente e non varia per tutta

l’esecuzione del programma



Accessibili solo in lettura



Garanzia nell’uso



Impossibile eseguire assegnazioni sugli

identificatori corrispondenti

(29)

50

50 Strutture di Controllo

Strutture di Controllo



Obbligatorie



Sequenza



Selezione binaria



Una Iterazione illimitata



Opzionali



Selezione multipla



L’altra iterazione illimitata



Iterazione limitata

(30)

51

51 Dati Strutturati

Dati Strutturati



Insiemi di valori correlati



Indicati collettivamente da un unico nome



Tra essi esiste una struttura legata

all’organizzazioneall’organizzazione

al tipo di valori che compongono l’insiemeal tipo di valori che compongono l’insieme alle operazioni per estrarre i dati dall’insiemealle operazioni per estrarre i dati dall’insieme



È fondamentale il modo in cui vengono

individuati i dati componenti

(31)

52

52 Vettore

Vettore



Struttura lineare a dimensione fissa



Sequenza di elementi dello stesso tipo



Operazioni consentite:

Lettura (selezione)

 Reperimento del valore di un elemento

Scrittura (sostituzione)

 Sostituzione del valore di un elemento con un

nuovo valore

(32)

53

53 Vettore

Vettore



Numero fissato di componenti

 Tutte dello stesso tipoTutte dello stesso tipo

 Ciascuna esplicitamente denotata ed indirizzata Ciascuna esplicitamente denotata ed indirizzata

tramite un selettore (

tramite un selettore (indice)indice)

 Non si è legati ad uno specifico tipo di indiceNon si è legati ad uno specifico tipo di indice



Definito da:

 Tipo degli elementiTipo degli elementi  Numero degli indiciNumero degli indici  Tipo degli indiciTipo degli indici

(33)

54

54 Vettore

Vettore

vettore (

tipo_indice

) di

tipo_base



Accesso a qualunque componente



Specificandone la posizione

Nome della variabile vettore seguito dall’indiceNome della variabile vettore seguito dall’indice



In un tempo indipendente dal valore

dell’indice

Accesso diretto (Accesso diretto (randomrandom))



Un elemento di un vettore può essere a sua

volta di un tipo strutturato

(34)

58

58 Vettore: Esempio

Vettore: Esempio

 lati : vettore[1..100] of integer;lati : vettore[1..100] of integer;

 NumeroLati, i, perimetro : integer;NumeroLati, i, perimetro : integer;  read numeroLati;read numeroLati;

 while numeroLati > lati.size() DO while numeroLati > lati.size() DO

 Read numeroLatiRead numeroLati

 i = 1;i = 1;

 while i<=numeroLatiwhile i<=numeroLati

 read lati(i)read lati(i)  i = i + 1i = i + 1

 perimetro = 0;perimetro = 0;  i = 1;i = 1;

 while i<=numeroLatiwhile i<=numeroLati

 perimetro = perimetro + lati(i)perimetro = perimetro + lati(i)  i = i + 1i = i + 1

(35)

59

59 Vettori Multidimensionali

Vettori Multidimensionali



Vettori di Vettori



Esempio:

enum materia : (“italiano”, “matematica”, enum materia : (“italiano”, “matematica”,

“religione”) “religione”) orario :

orario : vettore (lun … sab) di vettore (lun … sab) di

vettore (8 … 13) di materia vettore (8 … 13) di materia



Abbreviazione:

orario : vettore(lun … sab, 8 … 13) di materia orario : vettore(lun … sab, 8 … 13) di materia



Uso di tipi intermedi

lezioni : vettore(8 … 13) di materia lezioni : vettore(8 … 13) di materia orario : vettore(lun … sab) di lezioni orario : vettore(lun … sab) di lezioni

(36)

61



Int n :=3, m:=5, elem :=0



matrice m : vettore(n,m) of int



matrice mTrasp : vettore(m,n) of int



For (i:=0; i<n; i++)



write(i+“-esima riga ”)



For (j:=0; j<m; j++)

 write(j+“-esimo elemento: ”, elem)write(j+“-esimo elemento: ”, elem)  m(i,j) := elemm(i,j) := elem



For (i:=0; i<n; i++)



For (j:=0; j<m j++)

 mTrasp[j,i] := m[i,j] mTrasp[j,i] := m[i,j]

Matrici: Esempio...

(37)

62



Int n :=3, m:=5, elem :=0



matrice m : vettore(n,m) of int



matrice mTrasp : vettore(m,n) of int



For (i:=0; i<n; i++)



write(i+“-esima riga ”)



For (j:=0; j<m; j++)

 write(j+“-esimo elemento: ”, elem)write(j+“-esimo elemento: ”, elem)  m(i,j) := elemm(i,j) := elem

 mTrasp[j,i] := elem mTrasp[j,i] := elem

...Matrici: Esempio

(38)

63

63 Programmazione Modulare

Programmazione Modulare



Tecnica basata sulla scomposizione di un

problema in sottoproblemi logicamente

indipendenti tra loro



Ad ogni sottoproblema corrisponde un modulo

 Codificati separatamenteCodificati separatamente

 Compilati separatamente (talvolta)Compilati separatamente (talvolta)

 Integrati alla fine per formare il programma Integrati alla fine per formare il programma

complessivo complessivo



Algoritmo coordinatore

→

programma principale



Algoritmi secondari

→

sottoprogrammi

(39)

65

65 Programmazione Modulare

Programmazione Modulare

Tecniche



Basate sul metodo di soluzione di problemi

consistente nello scomporre un problema

in sottoproblemi più semplici



Sviluppo top-down

 Approccio step-wise refinementApproccio step-wise refinement



Sviluppo bottom-up



Sviluppo “a sandwich”

(40)

66

66 Sviluppo Top-Down

Sviluppo Top-Down



Costruzione del programma per livelli successivi

 Corrispondenza con la scomposizione del problema Corrispondenza con la scomposizione del problema

cui è relativo

 Strumento concettuale per la costruzione di algoritmiStrumento concettuale per la costruzione di algoritmi

 Dettagliamento successivo delle parti in cui viene Dettagliamento successivo delle parti in cui viene

scomposto (sottoprogrammi) fino al codice finale

 Strumento operativo per l’organizzazione e lo sviluppo di Strumento operativo per l’organizzazione e lo sviluppo di

programmi complessi programmi complessi

(41)

68

68 Sviluppo Bottom-Up

Sviluppo Bottom-Up



Partendo dalle istruzioni del linguaggio



Costruzione di programmi molto semplici



Collegamento successivo in programmi più

complessi

fino ad ottenere il programma finale



Usato soprattutto nell’adattamento

di algoritmi codificati già esistenti a

nuove situazioni

(42)

69

69 Metodo a Sandwich

Metodo a Sandwich



Basato su una cooperazione fra le tecniche

top-down e bottom-up



Necessità di raffinare via via la soluzione del

problema principale

Scomposizione in algoritmi che ne risolvono delle Scomposizione in algoritmi che ne risolvono delle

sottoparti sottoparti



Disponibilità di algoritmi di base per problemi

semplici

(43)

70

70 Sottoprogramma

Sottoprogramma



Insieme di istruzioni



Individuate da un nome



Che concorrono a risolvere un problema

Ben definitoBen definito

 SensatoSensato

Non necessariamente fine a sé stessoNon necessariamente fine a sé stesso

 Supporto per la risoluzione di problemi più _{Supporto per la risoluzione di problemi più}

complessi



Esempi:



Scambio, Ricerca del Minimo, Ordinamento,

…

(44)

73

73 Sottoprogrammi

Utilità



Necessità di risolvere uno stesso problema



Più volte

 All’interno dello stesso programmaAll’interno dello stesso programma  In programmi diversiIn programmi diversi



Su dati eventualmente diversi



Unicità

dello sforzo creativo



Modifiche

(45)

74

74 Sottoprogramma

Sottoprogramma



Indipendentemente dalle regole sintattiche del

particolare linguaggio di programmazione

 Individuabile con un nomeIndividuabile con un nome

 Identificatore_{Identificatore}

 Prevede l’uso di un certo insieme di risorsePrevede l’uso di un certo insieme di risorse

 Variabili, costanti, …_{Variabili, costanti, …}

 Costituito da istruzioniCostituito da istruzioni

 Semplici o, a loro volta, composte_{Semplici o, a loro volta, composte}

 Differisce da un programma nelle istruzioni di inizioDifferisce da un programma nelle istruzioni di inizio

 Specificano che (e come) altri pezzi di programma possono _{Specificano che (e come) altri pezzi di programma possono}

sfruttarlo sfruttarlo

(46)

75

75 Chiamata di

Chiamata di

Sottoprogrammi



Esecuzione delle istruzioni di un

sottoprogramma



Modalità: deve essere comandata dal

programma chiamante

 Specifica del nome associatoSpecifica del nome associato



Effetto: si comporta come se il

sottoprogramma fosse copiato nel punto in cui

è stato chiamato

(47)

76

76 Chiamata di

Chiamata di

Sottoprogrammi



All’atto dell’attivazione (su chiamata) dell’unità

di programma

 Viene sospesa l’esecuzione del programma (o unità) Viene sospesa l’esecuzione del programma (o unità)

chiamante

 Il controllo passa all’unità attivataIl controllo passa all’unità attivata



All’atto del completamento della sua esecuzione

 L’attivazione terminaL’attivazione termina

(48)

77

77 Sottoprogrammi

Sottoprogrammi



Definizione

 Titolo o intestazioneTitolo o intestazione

 Identificatore_{Identificatore}

 Specifica delle risorse usate Specifica delle risorse usate

 CorpoCorpo

 Sequenza di istruzioni denotata dal nome della proceduraSequenza di istruzioni denotata dal nome della procedura



Comunicazione

 Come si connettono i sottoprogrammi tra di loro?Come si connettono i sottoprogrammi tra di loro?  Come si scambiano dati?Come si scambiano dati?

(49)

78

78 Sottoprogrammi

Sottoprogrammi

Nidificazione



Le risorse di cui fa uso un sottoprogramma

possono includere altri sottoprogrammi



Completa analogia con i programmi



Si viene a creare una gerarchia di

sottoprogrammi



Struttura risultante ad albero

(50)

80

80 Vista

Vista



L’insieme di risorse cui ha accesso il

sottoprogramma

 DatiDati

 Altri sottoprogrammi (utile per limitare l’accesso alle Altri sottoprogrammi (utile per limitare l’accesso alle

risorse ai soli interessati)



Può capitare che diversi sottoprogrammi

dichiarino risorse con lo stesso nome



Oggetti diversi totalmente scorrelati

(51)

85

85 Sottoprogrammi

Sottoprogrammi

Tipi di Variabili



Variabili locali



Interne al sottoprogramma



Temporanee

Create quando il sottoprogramma entra in azioneCreate quando il sottoprogramma entra in azione Distrutte quando il sottoprogramma è stata Distrutte quando il sottoprogramma è stata

eseguita eseguita

 Liberazione del relativo spazio di memoria_{Liberazione del relativo spazio di memoria}



Variabili non locali



Definite nel resto del programma, al di fuori

del sottoprogramma

(52)

86

86 Vista

Vista

Esempio

Unità di Programma P Unità di Programma P R R e, f e, f Q Q a, b a, b U U x, w, a x, w, a V V c, d, y, z c, d, y, z S S a, d a, d T T f, g f, g P P x, y x, y

(53)

87

87 Visibilità e Sottoprogrammi

Visibilità e Sottoprogrammi



L’

ambito di visibilità

(

scope

) di una variabile

locale si estende dalla sua dichiarazione a tutto il

blocco che la contiene



Uno stesso identificatore di variabile può essere

usato da sottoprogrammi diversi:

 le due variabili saranno le due variabili saranno indipendentiindipendenti l’una dall’altra l’una dall’altra



è possibile riusare gli stessi identificatori per

variabili locali con ambiti non sovrapposti

(54)

92

92 Effetti Collaterali

Effetti Collaterali



Effetti di un sottoprogramma che altera il valore

di una variabile non locale

 La presenza di tali variabili impedisce che il

sottoprogramma possa essere considerato come un’entità completa e autoconsistente

 Non si riferisce esclusivamente alle sue costanti, variabili e parametri

 Valutare attentamente l’uso, all’interno di un sottoprogramma, di variabili non locali

 Chiarezza  Sicurezza

(55)

93

93 Parametri Formali

Parametri Formali



Segnaposto utili ad indicare simbolicamente

 gli oggetti su cui il sottoprogramma lavoragli oggetti su cui il sottoprogramma lavora  il loro tipo e strutturail loro tipo e struttura

 boolean pari(integer x) {.... }boolean pari(integer x) {.... }



I loro nomi appaiono nell’intestazione della

procedura

 Non hanno alcuna connessione con nomi usati altroveNon hanno alcuna connessione con nomi usati altrove



All’atto della chiamata vengono sostituiti dai

parametri

effettivi

(o

reali

)

 Dati su cui effettivamente il sottoprogramma deve Dati su cui effettivamente il sottoprogramma deve

operare

(56)

95

95 Parametri Effettivi

Parametri Effettivi

(actual parameters)



Alla chiamata di un sottoprogramma, si

specificano i dati effettivi su cui esso dovrà

operare

 valori costanti, variabili, espressioni, …valori costanti, variabili, espressioni, …  conformità con i parametri formaliconformità con i parametri formali

 Numero, tipo e ordine_{Numero, tipo e ordine}



L’esecuzione dell’istruzione di

chiamata

(o

invocazione

) comporta la sostituzione dei

parametri formali con quelli reali

(57)

97

97 Parametri

Parametri

Tipi di Passaggio

La sostituzione può essere:

 Per valorePer valore

 il valore del parametro reale si sostituisce al corrispondente _{il valore del parametro reale si sostituisce al corrispondente}

parametro formale (assegnazione) parametro formale (assegnazione)  Per riferimentoPer riferimento

 Il parametro effettivo è una variabile ed ha a disposizione una Il parametro effettivo è una variabile ed ha a disposizione una

locazione di memoria il cui indirizzo viene “passato” al locazione di memoria il cui indirizzo viene “passato” al parametro formale

(58)

100

100 Passaggio di Parametri

Passaggio di Parametri

Esempio Pseudo-Pascal

program

program legaparametri(…,…); legaparametri(…,…); var

var n: int; n: int;

procedure

Incr(?var x: int)Incr(?var x: int)

begin begin x := x + 1; x := x + 1; writeln(n); writeln(n); {1}{1} writeln(x) writeln(x) {2}{2} End

End; //end Incr; //end Incr

begin begin n := 3; n := 3; Incr(n); Incr(n); writeln(n) writeln(n) {3}{3} end end..

 x_x per valore per valore

1. 1. 33 2. 2. 44 3. 3. 33

 x_x per riferimento per riferimento

1. 1. 44 2. 2. 44 3. 3. 44

(59)

104

104 Passaggio di Parametri

Passaggio di Parametri

per Valore



Generalmente usato per parametri che



Rappresentano un argomento di una

funzione/sottoprogramma e non il

risultato

 Inutile (anzi potenzialmente dannoso) Inutile (anzi potenzialmente dannoso)

consentirne la modifica consentirne la modifica

(60)

105

105 Passaggio di Parametri

Passaggio di Parametri

per Riferimento



Usato più spesso quando il parametro

rappresenta un risultato

necessità di conoscere la modifica necessità di conoscere la modifica

ha dimensioni notevoli

computazionalmente costoso ricopiarlo interamente computazionalmente costoso ricopiarlo interamente



Minore leggibilità

stessa variabile usata sotto diverse

denominazioni



Potenziale fonte di errori

errori nel sottoprogramma non più recuperabili

(61)

106

106 Procedure

Procedure

definizione e chiamata

 Sottoprogrammi il cui compito è quello di produrre un Sottoprogrammi il cui compito è quello di produrre un

effetto

 Modifica del valore di variabiliModifica del valore di variabili

 Comunicazione di informazioni all’utenteComunicazione di informazioni all’utente

 intestazione di proceduraintestazione di procedura

void cercaNome(Studente[] v, int matricola, String nome)

 Nome della proceduraNome della procedura

 Paragonabile ad una nuova istruzione del linguaggio_{Paragonabile ad una nuova istruzione del linguaggio}

 Lista di parametriLista di parametri

 chiamata chiamata

cercaNome(studentiITPS, 123456, nomeCercato)

 argomenti: argomenti:

 variabili (riferimenti): studentiITPS, nomeCercatovariabili (riferimenti): _{studentiITPS, nomeCercato}  espressioni (valori): 123456espressioni (valori): 123456

(62)

107

107 Funzioni

Funzioni



Sottoprogrammi che hanno come risultato il

calcolo di un valore

 hanno un’istruzione che ritorna il risultatohanno un’istruzione che ritorna il risultato



L’intestazione di funzione prevede una lista di

parametri formali

String cercaNome(Studente[] v, int matricola) String cercaNome(Studente[] v, int matricola)  Nome della funzione: Nome della funzione: _cercaNome_cercaNome

 Il Il designatoredesignatore di funzione specifica l’attivazione della di funzione specifica l’attivazione della

funzione funzione

 Lista di parametri: Lista di parametri: _{(Studente[] v, int matricola)}_{(Studente[] v, int matricola)}  Tipo del risultato: Tipo del risultato: _String_String

(63)

109

109 Procedure vs. Funzioni

Procedure vs. Funzioni

in un’espressione autonoma Chiamata x Valore di uscita x Possibilità di modificare il

valore dei parametri

x x Parametri x Tipo associato

Funzioni

Procedure

(64)

113

113 Attivazione di

Attivazione di

Sottoprogrammi



In generale, l’attivazione dei

sottoprogrammi è gestita tramite una

pila



Ad ogni attivazione di un’unità di programma

Viene creato un Viene creato un record di attivazionerecord di attivazione Il record viene messo in cima alla pilaIl record viene messo in cima alla pila



Al termine dell’attivazione

Il record è tolto dalla pilaIl record è tolto dalla pila La memoria viene rilasciataLa memoria viene rilasciata

(65)

114

114 Record di Attivazione

Record di Attivazione

Informazioni Contenute

 Nome (rif. interno) dell’unità di programmaNome (rif. interno) dell’unità di programma

 Riferimento all’area di memoria in cui è memorizzato il Riferimento all’area di memoria in cui è memorizzato il

corpo di istruzioni da eseguire

 Punto di ritornoPunto di ritorno

 Riferimento all’istruzione a cui tornare al termine Riferimento all’istruzione a cui tornare al termine

dell’attivazione

 Gerarchia creata al momento della dichiarazione Gerarchia creata al momento della dichiarazione

(

(catena staticacatena statica))

 Dà i riferimenti agli identificatori non localiDà i riferimenti agli identificatori non locali

 Parametri formali e loro legame con parametri effettiviParametri formali e loro legame con parametri effettivi  Variabili locali secondo le aree di memoria allocateVariabili locali secondo le aree di memoria allocate

(66)

152

152 Ricorsione

Ricorsione



Gestita come una normale attivazione di

procedura o funzione



Disciplina a stack



Per ogni variabile

v

dichiarata locale alla

procedura

R

Una chiamata di Una chiamata di RR che dia vita alla generazione di che dia vita alla generazione di

k

k chiamate di procedura ricorsiva produrrà chiamate di procedura ricorsiva produrrà kk+1 +1 distinte istanze della variabile

distinte istanze della variabile vv

Il tempo di vita di ciascuna di esse è contenuto Il tempo di vita di ciascuna di esse è contenuto

(innestato) in quello delle altre che la precedono (innestato) in quello delle altre che la precedono

(67)

156

156 Mutua Ricorsione

Mutua Ricorsione



Insieme di sottoprogrammi che si

chiamano a vicenda, l’ultimo dei quali

chiama il primo



A

chiama

B

che chiama

C

… che chiama

Z

che

chiama

A



Caso più semplice



2 sottoprogrammi

AA chiama chiama BB BB chiama chiama AA

(68)

157

157 Mutua Ricorsione

Mutua Ricorsione



È un caso (più complesso) di ricorsione

 La chiamata di un sottoprogramma a se stesso avviene La chiamata di un sottoprogramma a se stesso avviene

attraverso una serie di chiamate intermedie



Correttezza dipendente da 2 fattori

 È necessario un livello assiomaticoÈ necessario un livello assiomatico

 Soluzione nota senza chiamata ricorsivaSoluzione nota senza chiamata ricorsiva

 Bisogna assicurarsi che la chiamata ricorsiva avvenga Bisogna assicurarsi che la chiamata ricorsiva avvenga

su un problema di ordine inferiore