Linguaggi di Programmazione

Linguaggi di programmazione

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Martina Contestabile — Mat. 7310441

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Indice

• Introduzione 8
• Che cosa è un linguaggio di programmazione? 8
• Verso LP di alto livello 8
• Programmazione scientifica 8
• Paradigmi 9
• Programmazione imperativa 9
• Programmazione orientata agli oggetti 9
• Programmazione funzionale 9
• Programmazione logica 9
• LP ed architettura degli elaboratori 10
• Qualità dei LP 11
• Qualità del software 11
• Affidabilità 11
• Manutenibilità 11
• Efficienza 11
• LP e affidabilità 11
• Scrivibilità 11
• Leggibilità 12
• Semplicità 12
• Sicurezza 13
• Robustezza 13
• LP e manutenibilità 13

Martina Contestabile — Mat. 731044

• LP ed efficienza 13
• Specifica di un Linguaggio di Programmazione 14
• Lessico 14
• Terminologia 14
• Stringa lessicale 14
• Simbolo 14
• Pattern 15
• Specifica dei simboli 15
• Alfabeto 15
• Stringa 15
• Linguaggio 15
• Esempio di linguaggio 16
• Espressioni regolari 16
• Definizione di Espressione Regolare 16
• Esempi di espressioni regolari 17
• Proprietà algebriche 17
• Espressioni regolari estese 17
• Esempio 17

2ffiffi fi fifi ffi ffi è fi

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

• Esempio 17
• Esempi 17
• Esempi 18
• Esempio 18
• Definizioni regolari 18
• Esempi 18
• Espressioni Regolari per Token nei LP 18
• Sintassi 19
• Riconoscitori del linguaggio 20
• Generatori del linguaggio 20
• Metodi formali per la definizione della sintassi 20
• BNF 21
• Linguaggio per tabelle 22
• Esempio 22
• Esempio 23
• EBNF 23
• Opzionalità 23
• Ripetizione 23
• Disgiunzione 24
• EBNF vs BNF 24
• Ripetizione non vuota 24
• EBNF come linguaggio per tabelle 24

Martina Contestabile — Mat. 731044

• Diagrammi sintattici 24
• Semantica dinamica 25
• Semantica operazionale 25
• Semantica denotazionale 26
• Esempio — Numeri binari 26
• Esempio — Numeri decimali 26
• Esempio — Espressione, senza effetti collaterali 27
• Ciclo a condizione iniziale 28
• Espressioni 30
• Scelte progettuali 30
• Precedenza 30
• Associatività 30
• Valutazione degli operandi 31
• Overloading 31
• Conversioni di tipo 32
• Conversione di Tipo Implicita 32
• Espressioni booleane 32
• Programmazione Funzionale 34

3fi fi ff

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

• Programmazione funzionale 34
• Funzione matematica 34
• Funzioni Semplici 34
• Forme funzionali 34
• Esempi 34
• Fondamenti dei LP Funzionali 35
• Scheme 35
• Espressioni 35
• Valutazione delle espressioni 36
• Governate da 3 regole: Nomi sostituiti dai loro binding correnti 36
• Liste 37
• Costrutti di Controllo 39
• Selezione ad una via 39
• Selezione a due vie 40
• Definizione di funzioni 40
• Fattorizzazione di Sottoespressioni 42
• Forme Funzionali 43
• Applicazione universale 43
• Uniformità strutturale di dati codice 43
• Haskell 45
• Valutazione di espressioni 45
• Definizioni 45

Martina Contestabile — Mat. 731044

• Definizione di Funzioni 45
• Tipi Primitivi 46
• Bool 46
• Int 46
• Char — import Data.Char 47
• Float, Double 47
• Guardie 47
• Espressioni Condizionali 48
• Operatori e Funzioni 48
• Ricorsione 48
• Costruttori di Tipo 50
• Tupla 50
• Esempi 50
• Esempi 51
• Lista 51
• Definizione di Liste mediante Range 52
• Definizione Intensionale di Liste 52
• Esempio — Biblioteca 53

4fififififi

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

• Esempio — Cifratura di Cesare 54
• Funzioni Generiche 56
• Polimorfismo 56
• Funzioni di Libreria per Liste — Prelude.hs 58
• Programmazione con Liste — Picture 58
• Definizioni Locali nella Specifica di Funzioni 59
• Somma del quadrato di due numeri 59
• Somma di elementi corrispondenti 59
• Elementi non sommati in coda 59
• → Pattern Matching 59
• Distinzione fra diversi casi nella definizione di funzione 59
• Identificazione di componenti di tupla 59
• Identificazione di parti di lista 59
• Possibili pattern 60
• Pattern per liste 60
• Lista vuota 60
• Lista non vuota 60
• Pattern per liste 60
• Unica occorrenza di ogni variabile in pattern 60
• Raddoppio di ogni elemento di una lista 61
• Selezione dei numeri pari 61
• Ordinamento di lista di numeri per inserzione 61

Martina Contestabile — Mat. 731044

• Creazione di liste di coppie 61
• Prelievo di un prefisso della lista 62
• Quicksort di una lista di numeri 62
• Forme Funzionali 62
• Foldr 64
• Foldl 65
• Composizione 65
• Trasmissione di stringhe 66
• Dichiarazione di tipi 68
• Dichiarazione di tipi sinonimi: type 68
• Non possono essere ricorsive 68
• Possono essere parametrizzate 68
• Dichiarazione di nuovi tipi: data 69
• Verifica di Tautologie 72
• Overloading di funzioni 76
• Classi di tipi 76
• Dichiarazione di una classe di tipi 78
• Istanziazione di una Classe di Tipi 78

5fi fi fifi fi fi fi fi

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

• Definizioni di Default 79
• Classi Derivate 80
• Vincoli Multipli 80
• Ordinamento di una lista e visualizzazione del risultato come stringa 80
• Visualizzazione come stringa del risultato di lookupFirst 80
• Vincoli multipli nella istanziazione 81
• Vincoli multipli nella definizione di classe — Ereditarietà multipla 81
• Lazy Evaluation 81
• Strategie di Valutazione 81
• Innermost evaluation — Chiamata per valore 82
• Outermost evaluation — Chiamata per nome 82
• Lambda espressioni 82
• Innermost evaluation 83
• Outermost evaluation 83
• Terminazione 83
• Chiamata per valore 83
• Chiamata per nome 83
• Numero di riduzioni 84
• Per valore 84
• Per nome 84
• Strutture Infinite 84
• Programmazione Modulare 85

Martina Contestabile — Mat. 731044

• Generazione di numeri primi 85
• Setaccio di Eratostene 86
• Applicazione Stretta 86
• Programmazione Logica 89
• Paradigma Logico 89
• Logica Proposizionale 89
• Logica dei Predicati 90
• Logica Proposizionale e Logica dei Predicati 90
• Clausole di Horn 91
• Risoluzione e Unificazione 91
• Prolog 92
• Interazione — swipl 93
• Risposta ad una query 93
• Strutture 93
• Operatori 94
• Ricerca di soluzioni 95
• Interrogazione di Basi di Dati 96
• Liste 97

6fi fi fi fi

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

• Concatenazione 97
• Appartenenza 97
• Inversione 98
• Ultimo elemento 98
• Elementi consecutivi 98
• Prefisso 98
• Cut 99
• Esempio — Servizi offerti da una biblioteca, limitati per utenti non affidabili 99
• Uso del cut per inibire ricorsione infinita 100
• Soluzione alternativa 101
• Efficienza vs chiarezza 101
• Processing di Liste 102
• Cancellazione di tutte le occorrenze di un elemento 102
• Sostituzione di tutte le occorrenze di un elemento E con S 103
• Rimozione di duplicati 103
• Sottoinsieme 103
• Unione 104
• Differenza 104
• Intersezione 105
• Prodotto Cartesiano — Generazione di strutture binarie con funtore pair 105
• Allocazione degli Inquilini 105
• Le Torri di Hanoi 106

Martina Contestabile — Mat. 731044

• Tecnica di risoluzione per N dischi 106
• Ricerca in un Labirinto 107
• Copertura di un grafo 108
• Numeri di Fibonacci 108
• Setaccio di Eratostene 109
• Espressioni aritmetiche 109
• Espressioni Pseudo-Regolari 110

7ffi ff fi ff fi ffi

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Introduzione

Specificare un linguaggio di programmazione significa che, come nella lingua parlata, c’è la sintassi e il lessico, dobbiamo indicare quali sono gli elementi base, atomici, di un linguaggio. È come se fossero i nostri mattoni con cui creiamo una costruzione solida. Tuttavia, non basta che una frase sia sintatticamente corretta, ma serve che lo sia anche a livello semantico. Di conseguenza, serve il piano semantico: una volta che conosco la sintassi, devo dire anche il significato che ciò che ho scritto ha, è quello che si chiama semantica.

Che cosa è un linguaggio di programmazione?

Un Linguaggio di Programmazione (LP) è uno strumento di astrazione che permette di specificare computazioni tali da poter essere eseguite su un elaboratore.

Il concetto di astrazione cosa significa? È un’astrazione dalla macchina fisica su cui verrà effettivamente eseguito il programma. Come si astrae dalla macchina? È il linguaggio che lo permette, non dobbiamo preoccuparcene.

Argomenti del corso

Esistono migliaia di LP, ognuno progettato in modo da soddisfare certi requisiti. Tuttavia, al di là dell’elevato numero di linguaggi esistenti, il progettista di un LP deve bilanciare due requisiti fondamentali:

• Computazione espressa convenientemente per la persona, ossia deve essere adatto a chi lo scrive, alla mentalità di chi sta programmando. Un esempio è il linguaggio che permette di scrivere espressioni matematiche con le regole di precedenza che tutti conosciamo.
• Uso efficiente degli elaboratori. Meno è efficiente, meno è di alto livello.

Verso LP di alto livello

Partiamo dal presupposto che più il linguaggio è conveniente a chi programma più è di alto livello, ma questo può comportare ad una difficile esecuzione dello stesso.

LP inventati per rendere l’uso degli elaboratori, macchine, facile.

Martina Contestabile — Mat. 731044

Termine informale di livello utile per una distinzione di massima dei LP. Se usiamo un linguaggio più vicino alla macchina, allora si parla di basso livello, il viceversa è l’alto livello.

Abbiamo appena detto che il linguaggio macchina è di basso livello, siccome pieno di dettagli che hanno a che fare più con il modo con cui funziona la macchina che con l’oggetto della computazione.

LP progettati in modo da essere:

• Alto livello, cioè indipendente dalla macchina.
• General-purpose, cioè applicabile ad un ampio dominio.

Questi due requisiti sono indipendenti fra loro. Esempi di alto livello sono C e Java.

Si parla di Special-purpose quando il LP è adatto solo per specifiche situazioni. Un esempio è Prolog.

L’Assembly, invece, è un linguaggio di basso livello e General-purpose. Viene tradotto in linguaggio macchina automaticamente — per questo si parla di «programmazione automatica».

Un programma che gestisce un orologio digitale è di basso livello e Special-purpose.

Inizio della storia evolutiva dei LP verso l’alto: definizione di un linguaggio simbolico, mnemonico, da tradurre manualmente.

LP di alto livello hanno sostituito il linguaggio Assembly virtualmente in tutte le aree della programmazione, poiché:

• Notazione: familiare e leggibile.
• Indipendenti dalla macchina, portabilità.
• Disponibilità di librerie di programmi.
• Permettono analisi del programma, ossia supporta l’individuazione di errori.

Programmazione scientifica

Fortran (FORmula TRANslation) permetteva di scrivere espressioni matematiche in modo naturale — sulla macchina del tempo, che era la IBM 704.

8fi éfiffi ù à è ff fi fi ffi fi à è ffi fi fi fi

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Con naturale si intende nel modo a noi conosciuto, secondo le convenzioni utilizzate nel quotidiano.

Si valuta il tutto come un albero sul quale mano a mano si risale. I vari termini dell’operazione sono come delle foglie.

Paradigmi

Ogni LP supporta uno stile di programmazione, che coincide con il paradigma di programmazione, di cui abbiamo parlato poco fa.

Un LP che suggerisce un particolare paradigma si dice orientato al paradigma.

Un LP può avere diversi paradigmi, come possiamo capire da figura.

Un LP che supporta diversi paradigmi si dice ibrido. Un esempio è il C++.

Metodo di design astrazioni del design ⇒ Quando si ha con stesso paradigma.

Linguaggio di direttamente mappabili sui componenti del programma Programmazione.

Altrimenti, si ha scollamento, ossia l’aumento del costo della codifica. Quindi, il programma deve implementare la soluzione del problema e i concetti del paradigma, OO in FORTRAN.

Martina Contestabile — Mat. 731044

Programmazione imperativa

Nella programmazione imperativa il programma è una sequenza di passi.

Ad ogni passo si ha la lettura dell’input, la computazione e la scrittura dell’output.

Il meccanismo di astrazione è una procedura, cioè un’istruzione complessa, e tutto ciò consente il riuso.

I costrutti fondamentali sono gli assegnamenti, le sequenze, le istruzioni condizionali e i cicli.

Esempi sono FORTRAN, Cobol, C, Pascal.

Programmazione orientata agli oggetti

Nella programmazione orientata agli oggetti il programma è una collezione di oggetti che interagiscono passandosi messaggi che trasformano il loro stato.

I costrutti fondamentali sono la modellazione degli oggetti, la classificazione e l’ereditarietà.

Esempi sono Smalltalk, C++, Java, C#, Ruby.

Programmazione funzionale

Nella programmazione funzionale il programma è una collezione di funzioni matematiche.

Ogni funzione ha un dominio e un codominio.

I costrutti fondamentali sono composizione, condizionali e ricorsione — diretta o indiretta.

Non esistono le variabili, gli assegnamenti e le istruzioni di controllo.

Esempi sono Lisp, Scheme, ML, Haskell.

Scheme è nato poco dopo FORTRAN per soddisfare richieste nell’intelligenza artificiale.

Assieme a Scheme studieremo anche Haskell.

Programmazione logica

Nella programmazione logica il programma è una collezione di dichiarazioni logiche su cosa una certa funzione deve computare piuttosto che sul come.

L’esecuzione applica le dichiarazioni per trovare possibili soluzioni al problema.

Tipicamente, i problemi sono risolvibili mediante i cosiddetti «tentativi».

9ò fi fi fi fi

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Il backtracking è ritorno sui propri passi per percorrere una strada alternativa. È utile, ad esempio, quando si vuole creare un cruciverba e, dopo l’elaborazione in orizzontale, non si riesce a proseguire con parole corrette in verticale.

Una caratteristica della programmazione logica è anche il nondeterminismo, ossia la soluzione del problema non unica.

Un esempio, che vedremo anche in modo approfondito nel corso, è Prolog.

LP ed architettura degli elaboratori

Abbiamo detto che c’è una doppia influenza sui LP.

Nonostante le macchine si siano evolute, esse si basano tuttora sulla macchina di Von Neumann.

I metodi di design sono requisiti sul LP in modo da supportare meglio lo sviluppo, design, del software.

L’architettura degli elaboratori, invece, sono i requisiti sul LP in modo che possa essere implementato efficientemente sulle macchine correnti, sempre per la sopracitata architettura di Von Neumann.

Ricordiamoci che l’architettura della macchina di Von Neumann è fatta nel seguente modo.

Martina Contestabile — Mat. 731044

La CPU, che interagisce con la memoria ed effettua il lavoro vero e proprio di elaborazione del dato, preleva una istruzione alla volta dalla memoria.

Durante l’esecuzione di una istruzione si ha il prelievo di dati dalla memoria, la manipolazione dei dati e la copiatura dei risultati nella memoria. Tutto ciò comporta la transizione di stato della macchina, ossia il contenuto delle celle, anche solo di una di esse.

Assomiglia ad un automa, ci sono dei cambiamenti, le transizioni di stato, ad ogni singola esecuzione. Al termine del programma si ha lo stato finale desiderato.

Passare da esecuzione a transizione significa avere un modello computazionale.

Gli LP convenzionali, imperativi, sono visti come astrazione di una architettura di Von Neumann, ossia si comportano praticamente allo stesso modo, a meno di astrazione più alta per LP.

Dobbiamo sottolineare come l’astrazione è l’evidenza di aspetti rilevanti ed ignora tutti i dettagli superflui.

Il modello computazionale di un LP imperativo consente l’esecuzione sequenziale di istruzioni, ognuna delle quali cambia lo stato della computazione mediante la modifica dei valori di un insieme di variabili.

Vediamo in questa tabella le analogie fra loro due.

Storicamente, gli LP si sono evoluti verso livelli di astrazione crescenti.

10ffi fl fi fi ff fi fl

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Ad un certo punto, i LP si sono evoluti a tal punto da decretare l’abbandono del modello computazionale di Von Neumann.

Per LP logici e funzionali, che hanno basi matematiche, si sono create logica matematica e la teoria delle funzioni ricorsive. Ciò è dovuto al fatto che ci sono fondamenti concettuali non definiti in relazione all’architettura di Von Neumann. Il conflitto con l’efficienza di esecuzione ha richiesto un compromesso, ossia il miglioramento dell’efficienza mediante l’introduzione di costrutti imperativi.

Qualità dei LP

È possibile valutare la qualità dei LP in base alle caratteristiche che possiede?

Possiamo stabilire non guardando lo strumento, ma il prodotto ottenuto dallo strumento. Ad esempio, per valutare una macchina fotografica, valutiamo le foto che scatta, per uno strumento musicale il suono emesso… infatti, un LP è uno strumento che serve per lo sviluppo di software, quindi deve esserci una correlazione di qualità fra LP e software.