Sottoprogrammi e Sottoprogrammi e Unità di CompilazioneUnità di Compilazione

Nicola Fanizzi Laboratorio - Corso di Programmazione (B)C.d.L. in InformaticaDIB - Università degli Studi di Bari

22

SottoprogrammiSottoprogrammi attività ripetitive (routine) all'interno di un

programma possono essere fattorizzate

In Pascal si possono avere procedure e funzioni

intestazione in BNF

procedure <ID-procedura>(<listaparametri>);

<dichiarazioni>

<corpo-procedura>

function <ID-funzione>(<listaparametri>): <tipo>;

<dichiarazioni>

<corpo-funzione>

33

ParametriParametri la lista parametri è costituita da dichiarazioni

separate da ; passaggio parametri:

– per valore: <lista ID-parametri>: <tipo>

– per indirizzo: VAR <lista ID-parametri>: <tipo>

– <lista ID-parametri>::= <ID>{,<ID>}0

esempio:procedure insert_array

(var A:vettore; var n:integer; MAX:integer);

function restituisce un valore del tipo specificato:

– una variabile con il nome della funzione fa da parametro formale

44

Chiamata SottoprogrammiChiamata Sottoprogrammi la chiamata avviene scrivendo il nome del

sottoprogramma seguito dalla lista dei parametri effettivi da passare:– per valore: <ID-variabile>

del tipo indicato nella dichiarazione

– per indirizzo: <espressione> del tipo indicato nella dichiarazione

esempio: insert_array(A,i,10*DIM); le funzioni restituiscono un valore da

catturare in un'espressione: trovato := cerca(A,x,100);

supponendo ad es. di aver dichiarato: function ricerca(V: vettore; x,n:integer): boolean;

55

Attivazione dei SottoprogrammiAttivazione dei Sottoprogrammiad ogni chiamata corrisponde un record di attivazione su una pila: nome sottoprogramma e

riferimento all'inizio del suo corpo riferimento di catena statica

gerarchia di dichiarazione riferimento di ritorno

istruzione successiva all'invocazione

parametri formali variabili locali

Nome Prif. corpo di P

rif. catena statica di P

rif. ritorno da P

parametri formali di P

variabili locali di P

66

Attivazione dei SottoprogrammiAttivazione dei SottoprogrammiDimensioni del Record di AttivazioneDimensioni del Record di Attivazione

nome sottoprogramma e riferimento al corpo: 1 parola

riferimento di catena statica: 1 parola riferimento di ritorno: 1 parola parametri formali: 100 (oppure 1) + 1 =

= 101 (o 2) parole variabili locali: 1 + 1 = 2 parole

Totale: 106 (o 7) parole

type vettore= array[1..100] of integer;...procedure P (var a:vettore; n: integer);var i, temp: integer;begin...end;

77

Effetti CollateraliEffetti Collaterali effetti (indesiderati) che modificano la

semantica del programma, in genere dovuti a:– uso di variabili non locali– passaggio di parametri per riferimento a

funzioni esempio:

function doppio(var b:integer):integer;begin

b := b * 2;doppio := b;

end chiamata:

x:=1; write(doppio(x)); stampa 2x:=1; write(doppio(x)+doppio(x)) stampa 6 non 4

88

VisibilitàVisibilitàEsempioEsempioprogram Visibilita (input, output);var a, b, c: integer;

procedure p2;var a, d, e: integer;begina := 2;b := 2; d := 2; e := 2;writeln('*** p2 : a = ', a : 1, ', b = ', b : 1, ', c

= ', c : 1, ', d = ', d : 1, ', e = ', e : 1)end;

procedure p3;var x: integer;begin

x := 3;writeln('*** p3 : a = ', a : 1, ', b = ', b : 1,

', c = ', c : 1, ', x = ', x : 1)end;

begina := 1; b := 1; c := 1;writeln('*** main : a = ', a : 1, ', b = ', b : 1, ', c

= ', c : 1);p2;p3;writeln('*** main : a = ', a : 1, ', b = ', b : 1, ', c

= ', c : 1)end.

99

VisibilitàVisibilitàoutputoutput*** main : a = 1, b = 1, c = 1*** p2 : a = 2, b = 2, c = 1, d = 2, e = 2*** p3 : a = 1, b = 2, c = 1, x = 3*** main : a = 1, b = 2, c = 1

1010

Visibilità Visibilità Esempio (2)Esempio (2)program visibile (input, output);var x: integer;

procedure p2;var x: integer;begin x := 1; writeln(x);end;

procedure p1;var x: integer;begin x := 2; p2; writeln(x);end;

{Corpo del programma principale}

begin x := 3; p1; writeln(x); readln;end.

1111

Array come ParametriArray come Parametri il passaggio di un array va fatto tenendo conto

di:– minore efficienza del passaggio per valore a

causa della copia

– possibili effetti collaterali indesiderati nel passaggio per riferiento

esempio: – lettura:

procedure leggi(var A:Tvettore; var N: Tindice);

– scrittura: procedure stampa(A:Tvettore; N: Tindice);

– elaborazione: procedure ordina(var A:Tvettore; N: Tindice);

1212

Visibilità delle VariabiliVisibilità delle Variabili

Parametri: Tipo

(dominio dei valori + operazioni definite) Valore

(tra quelli del dominio) Ambito

(dove è accessibile l'identificatore della variabile)

Durata(quando esiste memoria allocata per la variabile)

1313

Ricerca Binaria IterativaRicerca Binaria Iterativaprocedure bsit (v: vettore; x: real; a,z: integer; VAR esito:boolean);

var m:integer;

beginif a > z then

esito := falseelse

beginrepeatm := (a+z) div 2; if x < v[m] then

z := m-1 else

a := m+1until (a>z) or (v[m]=x);esito := (v[m]=x)end

end;

function bsit (v: vettore; x: real; a,z: integer): boolean;

var m:integer;

beginif a > z then

bsit := falseelse

beginrepeatm := (a+z) div 2; if x < v[m] then

z := m-1 else

a := m+1until (a>z) or (v[m]=x);bsit := (v[m]=x)end

end;

1414

Ricerca Binaria RicorsivaRicerca Binaria Ricorsivaprocedure bsr (v: vettore; x: real; a,z: integer; VAR esito:boolean);

var m:integer;

beginif a > z then

esito := falseelse

beginm := (a+z) div 2; if v[m]=x then

esito := trueelse if x < v[m] then

bsr(v,x,a,m-1,esito) else

bsr(v,x,m+1,z,esito)end

end;

function bsr (v: vettore; x: real; a,z: integer): boolean;

var m:integer;

beginif a > z then

bsr := false else

begin m := (a+z) div 2; if v[m]=x then

bsr := trueelse if x < v[m] then

bsr:= bsr(v,x,a,m-1) else

bsr:= bsr(v,x,m+1,z)end

end;

1515

QuicksortQuicksort RicorsivoRicorsivoprogram quicks(input,output);

const N = 10;

type lista = array[1..N] of integer;

var v: lista; i: integer;

procedure qs (sin,des:integer); var i,j,m: integer;

procedure scambia (var a,b:integer); var aux: integer; begin

aux := a; a := b; b := aux;

end;

begin {quicksort ricorsivo } m:=(v[sin]+v[des]) div 2; i := sin; j := des; repeat while v[i]<m do i := i+1; while m<v[j] do j := j-1; if i<=j then begin scambia(v[i], v[j]); i := i+1; j := j-1; end until i>j; if sin<j then qs(sin,j); if i<des then qs(i,des); end;

begin {principale}for i:=1 to N do

begin write(i, '° elemento: ');

readln(v[i]); end;

qs(1,N); { Chiamata di qs }

writeln;for i:=1 to N do writeln(v[i])end.

1616

Quicksort Quicksort Versione IterativaVersione Iterativatype Vet = array[1..100] of real;

procedure Scambia (var a:Vet; i,j:integer);var temp: real;begin temp:=a[i]; a[i]:=a[j];a[j]:=tempend;

procedure Quicksortit (var v:Vet; l,r:integer);var i, j, stacklen: integer; x: real; stackl, stackr: array[1..50] of integer;

beginstacklen := 1;stackl[stacklen] := l;stackr[stacklen] := r;

repeatl:=stackl[stacklen];r:=stackr[stacklen];stacklen:=stacklen-1;i:=l; j:=r;x:=v[(l+r) div 2];repeat while x > v[i] do i:=i+1;

while v[j] > x do j:=j-1; if i<=j then begin

if v[i]<>v[j] then Scambia(vet, i, j);

i:=i+1; j:=j-1end

until i > j;if l < j then begin stacklen:=stacklen+1;

stackl[stacklen] := l;

stackr[stacklen] := jend;

if i < r then begin stacklen:=stacklen+1; stackl[stacklen] := i; stackr[stacklen] := r end;

until stacklen = 0end;

1717

Mutua RicorsioneMutua RicorsioneDirettiva ForwardDirettiva Forwardprogram Conversione;VAR num : integer; ancora : BOOLEAN; risposta : CHAR;

PROCEDURE stamparesto(q,r: integer); FORWARD;

PROCEDURE stampaB(x: integer); VAR q, r : integer;BEGIN q := x DIV 2; r := x MOD 2; stamparesto(q, r); END;

PROCEDURE stamparesto (q,r:

integer);BEGIN IF q > 0

THEN stampaB(q);write(r); END;

BEGIN writeln('Conversione');writeln('decimali -> binari');

REPEAT writeln;write('Immettere numero:');readln(num);

writeLn;

write(num, 'decimale ');write('in binario e'':');stampaB(num);

writeLn;

write('Ancora? S/N ');readln(risposta); ancora := (risposta = 'S') or (risposta = 's');

UNTIL NOT ancora; END.

1818

Unità di CompilazioneUnità di Compilazione estensione del Pascal standard unità compilabili separatamente (keyword unit) si dividono in 2 parti:

interfaccia (keyword interface): dichiarazioni esportabili (globali a tutta l'unità) implementazione (keyword implementation): definizioni dei sottoprogrammi dichiarati e di costanti, tipi, variabili e sottoprogrammi non esportabili (locali)

opzionalmente può comparire una sezione di inizializzazione, racchiusa in un blocco begin-end

1919

Unità di CompilazioneUnità di CompilazioneStrutturaStrutturaunit <ID-Unit>

interface<dichiarazione-costanti> <dichiarazione-tipi> <dichiarazione-variabili><definizione-sottoprogrammi>

implementation<dichiarazione-costanti> <dichiarazione-tipi> <dichiarazione-variabili><definizione-sottoprogrammi>

[begin {inizializzazioni} ] end.

2020

Unità di CompilazioneUnità di CompilazioneFunzioni di servizio su vettoriFunzioni di servizio su vettoriunit Servizio_Vettori;interfaceprocedure shell (var a:Tvettore; n:integer);procedure bubble (var a:Tvettore; n:integer);procedure leggi (var a:Tvettore; var n:integer);procedure stampa (a:Tvettore; n:integer);function cerca (x:Tbase; var a:Tvettore;

n:integer): boolean;

implementation

procedure shell (var a:Tvettore; n:integer);begin . . . end;procedure bubble (var a:Tvettore; n:integer);begin . . . end;procedure leggi (var a:Tvettore; var n:integer);begin . . . end;procedure stampa (a:Tvettore; n:integer);begin . . . end;function cerca (x:Tbase; a:Tvettore; n:integer): boolean;begin . . . end;

end.

2121

Unità di CompilazioneUnità di CompilazioneSomma usando solo succ() e pred()Somma usando solo succ() e pred()unit Somma;interface

function SommaIt(a,b:integer):integer;function SommaR(a,b:integer):integer;

implementation

function SommaIt(a,b:integer):integer;begin while a > 0 do

begin b := succ(b); a:=pred(a)

end; SommaIt := b;

end;

function SommaR(a,b:integer):integer;begin

if (a = 0) then SommaR := b else SommaR := succ(SommaR(pred(a),b))

end;