Linguaggi di Programmazione - Appunti in LaTeX

Linguaggi di Programmazione

Livio Zoccarato Simone Tomada

Anno Accademico 2020–2021 ii

Questo documento è stato scritto da due studenti del corso durante le

lezioni dell’anno accademico 2020/2021 (prof. Di Gianantonio), dunque viene

fornito as is e si declina ogni responsabilità in caso di errori, imprecisioni

e cambiamenti di contenuti negli anni successivi. Inoltre consigliamo di

accompagnarlo con le lezioni e con il libro per approfondirne i contenuti.

Indice

1 Introduzione 12

1.1 Aspetti di un linguaggio di programmazione . . . . . . . . . . 12

1.2 Tipologie di linguaggi . . . . . . . . . . . . . . . . . . . . . . 12

1.2.1 Imperativi . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.2 Dichiarativi . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3 Macchina astratta . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4 Compilazione vs. Interpretazione . . . . . . . . . . . . . . . . 14

1.4.1 Compilazione pura . . . . . . . . . . . . . . . . . . . . 14

1.4.2 Interpretazione pura . . . . . . . . . . . . . . . . . . . 14

1.4.3 Vantaggi e svantaggi . . . . . . . . . . . . . . . . . . . 14

1.5 Traduzione in codice macchina . . . . . . . . . . . . . . . . . 15

1.5.1 Supporto a run-time . . . . . . . . . . . . . . . . . . . 16

1.5.2 Assemblaggio post-compilazione . . . . . . . . . . . . . 16

1.5.3 Traduzioni da linguaggio a linguaggio (C++) . . . . . 17

1.5.4 Compilazione dinamica just-in-time . . . . . . . . . . . 17

1.6 Bootstrapping . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.6.1 Il caso del pascal . . . . . . . . . . . . . . . . . . . . . 17

1.7 Panoramica sulla compilazione . . . . . . . . . . . . . . . . . 20

1.7.1 Analisi lessicale - scansione . . . . . . . . . . . . . . . 20

1.7.2 Analisi sintattica - Parsing . . . . . . . . . . . . . . . . 21

1.7.3 Analisi semantica . . . . . . . . . . . . . . . . . . . . . 21

1.7.4 Modulo intermedio . . . . . . . . . . . . . . . . . . . . 21

1.7.5 Ottimizzazione . . . . . . . . . . . . . . . . . . . . . . 21

1.7.6 Tabella dei simboli . . . . . . . . . . . . . . . . . . . . 22

2 Sintassi 23

2.1 Grammatiche . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.1.1 Derivazione . . . . . . . . . . . . . . . . . . . . . . . . 23

2.1.2 Albero di derivazione . . . . . . . . . . . . . . . . . . . 23

2.1.3 Grammatiche ambigue . . . . . . . . . . . . . . . . . . 26

2.1.4 Problematiche dell’ambiguità . . . . . . . . . . . . . . 26

2.1.5 Gestione dell’ambiguità . . . . . . . . . . . . . . . . . 28

2.1.6 Alberi di derivazione astratti . . . . . . . . . . . . . . 29

iii iv

INDICE 2.1.7 Classi di grammatiche . . . . . . . . . . . . . . . . . . 31

2.1.8 Uso delle grammatiche libere dal contesto nei parser . 31

2.2 Front end del compilatore . . . . . . . . . . . . . . . . . . . . 32

2.2.1 Analisi lessicale (scanner, lexer) . . . . . . . . . . . . . 33

2.3 Linguaggi regolari . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3.1 Operazioni sui linguaggi regolari . . . . . . . . . . . . 34

2.3.2 Sintassi delle espressioni regolari . . . . . . . . . . . . 34

2.3.3 Esempi di espressioni regolari e stringhe generate . . . 34

2.3.4 Estensioni . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.3.5 Risultati teorici . . . . . . . . . . . . . . . . . . . . . . 35

2.3.6 Automi deterministici . . . . . . . . . . . . . . . . . . 36

2.3.7 Automi non deterministici . . . . . . . . . . . . . . . . 36

2.3.8 Applicazione dei risultati teorici . . . . . . . . . . . . . 37

2.4 Scanner (o lexer) per l’analisi lessicale . . . . . . . . . . . . . 37

2.4.1 Come costruire uno scanner . . . . . . . . . . . . . . . 38

2.5 Generatori di scanner (analizzatori lessicali) . . . . . . . . . . 38

2.5.1 (F)LEX . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.5.2 Definizioni . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.5.3 Sintassi delle espressioni regolari in C . . . . . . . . . 40

2.5.4 Funzioni ausiliarie . . . . . . . . . . . . . . . . . . . . 40

2.5.5 Altri esempi . . . . . . . . . . . . . . . . . . . . . . . . 41

2.5.6 Uso di Flex . . . . . . . . . . . . . . . . . . . . . . . . 42

2.6 Analizzatore sintattico (o parser) per l’analisi sintattica . . . 43

2.6.1 Automi a pila . . . . . . . . . . . . . . . . . . . . . . . 43

2.6.2 Automi a pila LL(n) . . . . . . . . . . . . . . . . . . . 44

2.6.3 Automi a pila LR . . . . . . . . . . . . . . . . . . . . . 47

2.7 Generatori di parser (analizzatori sintattici) . . . . . . . . . . 49

2.7.1 Yacc (Yet Another Compiler Compiler) . . . . . . . . 49

2.7.2 Differenze tra Yacc e LALR . . . . . . . . . . . . . . . 54

2.7.3 Creazione del codice . . . . . . . . . . . . . . . . . . . 55

3 Nomi e ambiente 56

3.1 Astrazione attraverso i nomi . . . . . . . . . . . . . . . . . . . 56

3.2 Binding e ambiente . . . . . . . . . . . . . . . . . . . . . . . . 57

3.3 Dichiarazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.4 Blocchi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.4.1 Vantaggi dei blocchi . . . . . . . . . . . . . . . . . . . 59

3.4.2 Annidamento . . . . . . . . . . . . . . . . . . . . . . . 59

3.4.3 Utilizzabilità di una dichiarazione . . . . . . . . . . . . 60

3.4.4 Validità di una dichiarazione . . . . . . . . . . . . . . 61

3.5 Ambiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.5.1 Operazioni sull’ambiente . . . . . . . . . . . . . . . . . 62

3.5.2 Operazioni sugli oggetti denotabili . . . . . . . . . . . 62

3.5.3 Eventi base del binding . . . . . . . . . . . . . . . . . 62

v

INDICE 3.5.4 Regole di scope . . . . . . . . . . . . . . . . . . . . . . 64

3.5.5 Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.5.6 Overloading . . . . . . . . . . . . . . . . . . . . . . . . 68

3.5.7 Costrutto let su scheme . . . . . . . . . . . . . . . . . 68

3.5.8 Mutua ricorsione . . . . . . . . . . . . . . . . . . . . . 69

3.5.9 Moduli . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4 Gestione della memoria 72

4.1 Uso della memoria RAM . . . . . . . . . . . . . . . . . . . . . 72

4.2 Tipi di allocazione della memoria . . . . . . . . . . . . . . . . 72

4.2.1 Allocazione statica . . . . . . . . . . . . . . . . . . . . 73

4.2.2 Allocazione dinamica: stack di attivazione . . . . . . . 74

4.2.3 Allocazione dinamica: heap . . . . . . . . . . . . . . . 79

4.2.4 Allocazione dinamica: regole di scope . . . . . . . . . 81

5 Strutture di controllo 93

5.1 Espressioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.1.1 Notazione . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.1.2 Rappresentazione ad albero . . . . . . . . . . . . . . . 96

5.1.3 Effetti collaterali ed ordine di valutazione . . . . . . . 97

5.1.4 Ottimizzazione e ordine di valutazione . . . . . . . . . 98

5.1.5 Aritmetica finita . . . . . . . . . . . . . . . . . . . . . 99

5.1.6 Valutazione eager e lazy . . . . . . . . . . . . . . . . . 100

5.2 Comandi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

5.2.1 Modello a valore . . . . . . . . . . . . . . . . . . . . . 103

5.2.2 Modello a riferimento . . . . . . . . . . . . . . . . . . 103

5.2.3 Differenze di implementazione tra i due modelli . . . . 103

5.2.4 Valori denotabili, memorizzabili, esprimibili . . . . . . 105

5.2.5 Operazioni di assegnamento . . . . . . . . . . . . . . . 106

5.3 Espressioni e comandi . . . . . . . . . . . . . . . . . . . . . . 106

5.4 Comandi per il controllo sequenza . . . . . . . . . . . . . . . . 108

5.4.1 Blocchi . . . . . . . . . . . . . . . . . . . . . . . . . . 108

5.4.2 GOTO – istruzione salto . . . . . . . . . . . . . . . . . 109

5.4.3 Comandi condizionali – if then else . . . . . . . . . . . 110

5.4.4 Condizioni in Scheme . . . . . . . . . . . . . . . . . . 110

5.4.5 Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5.4.6 Implementazione del costrutto case . . . . . . . . . . . 113

5.5 Iterazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

5.5.1 Iterazione indeterminata . . . . . . . . . . . . . . . . . 114

5.5.2 Iterazione determinata . . . . . . . . . . . . . . . . . . 116

5.6 Ricorsione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

5.6.1 Definizione induttiva di funzioni . . . . . . . . . . . . 119

5.6.2 Ricorsione ed iterazione . . . . . . . . . . . . . . . . . 120

5.6.3 Ricorsione di coda . . . . . . . . . . . . . . . . . . . . 120

vi

INDICE 5.6.4 Chiave di lettura della ricorsione di coda . . . . . . . . 121

5.6.5 Esempi di ricorsione di coda . . . . . . . . . . . . . . . 121

6 Astrarre sul controllo 124

6.1 Parametri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

6.2 Comunicazione chiamato – chiamante . . . . . . . . . . . . . 125

6.3 Modalità di passaggio dei parametri . . . . . . . . . . . . . . 125

6.3.1 Passaggio per valore . . . . . . . . . . . . . . . . . . . 126

6.3.2 Passaggio per riferimento . . . . . . . . . . . . . . . . 126

6.3.3 Call by sharing . . . . . . . . . . . . . . . . . . . . . . 127

6.3.4 Riassunto: value, reference, sharing . . . . . . . . . . . 129

6.3.5 Passaggio per costante (o read only) . . . . . . . . . . 130

6.3.6 Passaggio per risultato . . . . . . . . . . . . . . . . . . 130

6.3.7 Passaggio per valore-risultato . . . . . . . . . . . . . . 131

6.3.8 Passaggio per nome . . . . . . . . . . . . . . . . . . . 132

6.4 Parametri di default . . . . . . . . . . . . . . . . . . . . . . . 134

6.5 Funzioni di ordine superiore . . . . . . . . . . . . . . . . . . . 135

6.5.1 Semantica . . . . . . . . . . . . . . . . . . . . . . . . . 136

6.5.2 Politiche di binding . . . . . . . . . . . . . . . . . . . . 136

6.5.3 Implementazione con scope statico . . . . . . . . . . . 137

6.5.4 Implementazione con scope dinamico: shallow binding 137

6.5.5 Implementazione con scope dinamico: deep binding . . 137

6.5.6 Deep vs shallow binding con scope statico . . . . . . . 138

6.5.7 Funzioni come argomento in C . . . . . . . . . . . . . 139

6.5.8 Funzioni come risultato . . . . . . . . . . . . . . . . . 139

6.6 Eccezioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

6.6.1 Gestione delle eccezioni . . . . . . . . . . . . . . . . . 141

6.6.2 Uso delle eccezioni per aumentare l’efficienza . . . . . 143

6.6.3 Implementazione delle eccezioni . . . . . . . . . . . . . 144

7 Strutture dati 146

7.1 I tipi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

7.2 Categorie di sistemi di tipo . . . . . . . . . . . . . . . . . . . 147

7.2.1 Statici e dinamici . . . . . . . . . . . . . . . . . . . . . 147

7.2.2 Strong e weak . . . . . . . . . . . . . . . . . . . . . . . 148

7.2.3 Concetti indipendenti . . . . . . . . . . . . . . . . . . 148

7.3 Catalogazione dei tipi e dei loro valori . . . . . . . . . . . . . 149

7.3.1 Tipi predefiniti o scalari . . . . . . . . . . . . . . . . . 150

7.3.2 Tipi ordinali (o discreti) . . . . . . . . . . . . . . . . . 152

7.3.3 Tipi composti, strutturati, non scalari . . . . . . . . . 153

7.4 Inferenza di tipo . . . . . . . . . . . . . . . . . . . . . . . . . 167

7.5 Equivalenza tra tipi . . . . . . . . . . . . . . . . . . . . . . . . 167

7.5.1 Equivalenza per nome . . . . . . . . . . . . . . . . . . 168

7.5.2 Equivalenza strutturale . . . . . . . . . . . . . . . . . 169

vii

INDICE 7.5.3 Equivalenza strutturale vs equivalenza per nome . . . 170

7.6 Compatibilità tra tipi . . . . . . . . . . . . . . . . . . . . . . 170

7.6.1 Conversione di tipo . . . . . . . . . . . . . . . . . . . . 172

7.7 Polimorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

7.7.1 Overloading . . . . . . . . . . . . . . . . . . . . . . . . 173

7.7.2 Polimorfismo universale parametrico . . . . . . . . . . 174

8 Tipi di dato astratti 178

8.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

8.2 Principio di incapsulamento . . . . . . . . . . . . . . . . . . . 182

8.3 Oggetti e classi . . . . . . . . . . . . . . . . . . . . . . . . . . 182

8.4 Moduli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

9 Paradigma ad oggetti 185

9.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

9.1.1 Debolezze del tipo di dato astratto . . . . . . . . . . . 186

9.2 Concetti fondamentali . . . . . . . . . . . . . . . . . . . . . . 187

9.2.1 Oggetti . . . . . . . . . . . . . . . . . . . . . . . . . . 187

9.2.2 Classi . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

9.2.3 Linguaggi prototype based . . . . . . . . . . . . . . . . 188

9.2.4 Identificatori this e self . . . . . . . . . . . . . . . . . . 190

9.2.5 Modello a riferimento – variabile . . . . . . . . . . . . 190

9.2.6 Incapsulamento . . . . . . . . . . . . . . . . . . . . . . 191

9.2.7 Metodi o campi statici . . . . . . . . . . . . . . . . . . 191

9.2.8 Costruttori . . . . . . . . . . . . . . . . . . . . . . . . 191

9.2.9 Distruttori . . . . . . . . . . . . . . . . . . . . . . . . 192

9.2.10 Sottoclassi . . . . . . . . . . . . . . . . . . . . . . . . . 192

9.2.11 Ridefinizione di metodi (Overriding) . . . . . . . . . . 192

9.2.12 Ridefinizione di campi (Shadowing) . . . . . . . . . . . 193

9.2.13 Getter e Setter - Esempio in Ruby . . . . . . . . . . . 193

9.2.14 Sottoclassi e meccanismi di hiding . . . . . . . . . . . 194

9.2.15 Ereditarietà . . . . . . . . . . . . . . . . . . . . . . . . 194

9.2.16 Polimorfismo di sottotipo . . . . . . . . . . . . . . . . 197

9.2.17 Sottoclassi e relazione d’ordine . . . . . . . . . . . . . 198

9.2.18 Metodi astratti, classi astratte, interfacce . . . . . . . 198

9.2.19 Ereditarietà e sottotipo . . . . . . . . . . . . . . . . . 199

9.2.20 Selezione dinamica dei metodi . . . . . . . . . . . . . . 200

9.2.21 Selezione statica . . . . . . . . . . . . . . . . . . . . . 200

9.2.22 Duck Typing . . . . . . . . . . . . . . . . . . . . . . . 201

10 Paradigma funzionale 202

10.1 Imperativi vs funzionali . . . . . . . . . . . . . . . . . . . . . 202

10.2 Meccanismo di valutazione . . . . . . . . . . . . . . . . . . . . 202

10.2.1 Meccanismo di valutazione teorico . . . . . . . . . . . 203

viii

INDICE 10.2.2 Meccanismo di valutazione implementato . . . . . . . 203

10.3 Caratteristiche dei linguaggi funzionali . . . . . . . . . . . . . 204

10.4 Vantaggi dei linguaggi funzionali . . . . . . . . . . . . . . . . 204

10.5 Haskell e Scheme . . . . . . . . . . . . . . . . . . . . . . . . . 205

10.5.1 Sintassi . . . . . . . . . . . . . . . . . . . . . . . . . . 205

10.5.2 Sistemi di tipi . . . . . . . . . . . . . . . . . . . . . . . 205

10.5.3 Meccanismo di valutazione . . . . . . . . . . . . . . . . 206

10.5.4 Vantaggi e svantaggi della valutazione lazy . . . . . . . 206

10.5.5 Valori . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

10.5.6 Purezza . . . . . . . . . . . . . . . . . . . . . . . . . . 207

10.6 Haskell - introduzione . . . . . . . . . . . . . . . . . . . . . . 207

10.7 Valori e tipi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

10.7.1 Sistema di inferenza di tipi . . . . . . . . . . . . . . . 208

10.7.2 Tipi scalari . . . . . . . . . . . . . . . . . . . . . . . . 208

10.7.3 Tipi composti . . . . . . . . . . . . . . . . . . . . . . . 209

10.7.4 Tipi definiti dall’utente . . . . . . . . . . . . . . . . . 210

10.8 Variabili e binding . . . . . . . . . . . . . . . . . . . . . . . . 215

10.9 Funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

10.9.1 Pattern matching . . . . . . . . . . . . . . . . . . . . . 216

10.9.2 Currying . . . . . . . . . . . . . . . . . . . . . . . . . . 217

10.9.3 Regole sintattiche per evitare le parentesi . . . . . . . 218

10.9.4 Alcune operazioni funzionali standard . . . . . . . . . 218

10.10Meccanismo di valutazione, passaggio dei parametri . . . . . . 219

10.11Dati lazy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

10.11.1 Estrarre parti finite dei dati lazy . . . . . . . . . . . . 220

10.11.2 Strutture dati infinite nei linguaggi eager . . . . . . . 220

10.12Sintassi infissa . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

10.13List comprehension . . . . . . . . . . . . . . . . . . . . . . . . 222

10.13.1 Esempio di uso delle liste: QuickSort . . . . . . . . . . 223

10.14Funzioni di base e Prelude . . . . . . . . . . . . . . . . . . . . 223

10.14.1 Esercizio sulle liste . . . . . . . . . . . . . . . . . . . . 224

10.15Pattern matching e definizione per casi . . . . . . . . . . . . . 225

10.15.1 Case singolo . . . . . . . . . . . . . . . . . . . . . . . . 226

10.15.2 Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . 226

10.15.3 Ordine di valutazione . . . . . . . . . . . . . . . . . . 227

10.15.4 Pattern con guardie . . . . . . . . . . . . . . . . . . . 227

10.15.5 If then else . . . . . . . . . . . . . . . . . . . . . . . . 228

10.15.6 Forma generale del pattern con guardia . . . . . . . . 228

10.15.7 Esempio . . . . . . . . . . . . . . . . . . . . . . . . . . 228

10.16Ambiente locale . . . . . . . . . . . . . . . . . . . . . . . . . . 229

10.17Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

10.18Record come campi etichettati . . . . . . . . . . . . . . . . . . 230

10.19Type classes e polimorfismo . . . . . . . . . . . . . . . . . . . 231

10.19.1 Overloading . . . . . . . . . . . . . . . . . . . . . . . . 232

ix

INDICE 10.19.2 Type classes – dichiarazioni e istanziazioni . . . . . . . 232

10.19.3 Esempio di uso delle type classes . . . . . . . . . . . . 232

10.19.4 Implementazione di default dei metodi . . . . . . . . . 233

10.19.5 Definizione di instance polimorfe . . . . . . . . . . . . 233

10.19.6 Relazione di sottoclasse . . . . . . . . . . . . . . . . . 234

10.19.7 Sottoclassi multiple . . . . . . . . . . . . . . . . . . . . 234

10.20Visibilità dei nomi . . . . . . . . . . . . . . . . . . . . . . . . 234

10.21Relazione con i linguaggi Object Oriented . . . . . . . . . . . 235

10.22Categorizzazione delle espressioni in Haskell . . . . . . . . . . 235

10.22.1 Kind . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

10.23Costruttori di tipo e classi predefinite . . . . . . . . . . . . . . 237

10.23.1 Esempi di classes – Functor . . . . . . . . . . . . . . . 237

10.23.2 Costruttori di tipo canonici – Maybe . . . . . . . . . . 237

10.23.