LINGUAGGI DI PROGRAMMAZIONE Programmazione 2 z L’attività con cui si predispone l’elaboratore ad eseguire un particolare insieme di azioni su particolari dati, allo scopo di risolvere un problema Dati Input Elaboratore Elettronico Risultati Output Fondamenti di Informatica 1 3 Linguaggio di programmazione z Insieme di regole per la descrizione formale di un algoritmo eseguibile da un calcolatore: z Lessico (alfabeto): insieme dei termini disponibili z Sintassi: forma delle frasi z Semantica: significato delle frasi Fondamenti di Informatica Algoritmi, programmi e calcolatori 4 z Ogni elaboratore è una macchina in grado di eseguire azioni elementari su oggetti detti DATI z L’esecuzione delle azioni è richiesta all’elaboratore tramite comandi elementari chiamati ISTRUZIONI espresse mediante un opportuno formalismo: il LINGUAGGIO DI PROGRAMMAZIONE z La formulazione testuale di un algoritmo in un linguaggio comprensibile ad un elaboratore è detta PROGRAMMA Fondamenti di Informatica 2 Programma 5 z Un programma è un testo scritto in accordo alla sintassi e alla semantica di un linguaggio di programmazione z Un programma è la formulazione testuale, in un certo linguaggio di programmazione, di un algoritmo che risolve un dato problema z z È composto da un numero finito di istruzioni Ogni istruzione descrive una operazione Fondamenti di Informatica Algoritmo e programma 6 Passi per la risoluzione di un problema: z z z Individuazione di un procedimento risolutivo Scomposizione del procedimento in un insieme ordinato di azioni Æ ALGORITMO Rappresentazione dei dati e dell’algoritmo attraverso un formalismo comprensibile dal calcolatore Æ PROGRAMMA Problema Algoritmo Metodo risolutivo Programma Linguaggio di programmazione Fondamenti di Informatica 3 Compiti del programmatore 7 z Analizzare il problema riducendolo in termini astratti, eliminando ogni componente non indispensabile e formulando un modello del problema. z Individuare una strategia risolutiva e ricondurla ad un algoritmo. z Codificare l’algoritmo in modo tale da renderlo comprensibile al calcolatore. z Analizzare il risultato dell’elaborazione evidenziando eventuali errori nella formulazione del problema, nella strategia risolutiva, nella codifica dell’algoritmo. Fondamenti di Informatica Competenze ed abilità del programmatore 8 z Deve essere in grado di capire i problemi e schematizzarli, distinguendone le diverse componenti (dati in input, parametri del problema, dati in output). z Deve essere in grado di risolvere problemi mediante un approccio algoritmico, individuando gli aspetti del problema che possano essere risolti reiterando più volte operazioni simili. z Deve conoscere i metodi fondamentali di risoluzione dei problemi, gli approcci più comuni, le strade notoriamente meno convenienti. z Deve conoscere a fondo le caratteristiche e le capacità del calcolatore. z Deve essere in grado di comunicare con il calcolatore: ne deve conoscere il linguaggio. Fondamenti di Informatica 4 Linguaggi di programmazione 9 z Classificati rispetto alle caratteristiche principali: z z z potere espressivo che influenza lo stile di programmazione Storica Paradigma di progrmmazione Fondamenti di Informatica Linguaggio Macchina 10 z Insieme di istruzioni eseguibili dalla CPU z Dipende dalla CPU: z z cablata al suo interno, ogni istruzione genera una sequenza di segnali di controllo Linguaggio di basso livello z si può accedere direttamente alle funzionalità di base del calcolatore Fondamenti di Informatica 5 Linguaggio Macchina 11 z Complesso da utilizzare: z z z ogni istruzione esegue un'operazione semplicissima esistono librerie con procedure generali Gli altri linguaggi vengono “convertiti” in sequenze di istruzioni in linguaggio macchina Fondamenti di Informatica Linguaggio Macchina 12 z Il Linguaggio Macchina è estremamente efficiente z I programmi sono: z z z più veloci più corti … ma più complessi Fondamenti di Informatica 6 Linguaggi - basso livello 13 z Il linguaggio macchina specifica solo le operazioni che l'elaboratore può eseguire z sintattica molto elementare" z diverso per ogni processore z dipende dalle caratteristiche architetturali della CPU z E' più orientato alla macchina che ai problemi da trattare z è infatti definito di "basso livello“ z Le istruzioni devono essere espresse come sequenze di bit! Fondamenti di Informatica Linguaggio Macchina 14 z La scrittura è complessa: z istruzioni formate da stringhe di 1 e 0: quindi è necessario un insieme di simboli (Linguaggio Assembly) z per referenziare le locazioni di memoria è necessario avere delle etichette z necessario commentare ogni istruzione Fondamenti di Informatica 7 Linguaggi - basso livello 15 z Una prima evoluzione è stata l'introduzione di linguaggi simbolici: linguaggi assemblativi (assembly) z z z ancora orientati alla macchina e non ai problemi più immediati da utilizzare definiscono variabili, simboli,... Fondamenti di Informatica Linguaggi - alto livello 16 z Altri linguaggi sono basati su: z z la descrizione del problema in modo intuitivo, dimenticandosi che verranno eseguiti da un calcolatore obiettivo: fornire un mezzo espressivo per specificare all'elaboratore il compito da eseguire Fondamenti di Informatica 8 Linguaggi - alto livello 17 z Caratteristiche: z z ognuno ha i propri paradigmi che garantiscono forme espressive appropriate per alcuni problemi specifici questa specificità ha favorito la loro proliferazione (fenomeno intrinseco alla natura del linguaggio come forma di comunicazione) Fondamenti di Informatica Linguaggi 18 z z La programmazione a basso livello è più ardua e meno intuitiva, ma consente di sviluppare programmi efficienti. Ad alto livello la programmazione è più “naturale” e rapida, ma è possibile che non consenta di produrre software efficiente. Efficienza del programma Programmazione a basso livello Programmazione ad alto livello Facilità e velocità di programmazione Fondamenti di Informatica 9 Linguaggi: un po’ di storia Albori: Macchine a programma memorizzato, Programmi come dati LinguaggioMacchina Assemblatore FORTRAN (calcolo scientifico) COBOL (Data Processing) Anni ’60: Formalizzazione della sintassi, Strutture a blocchi, implementazione del λcalcolo ALGOL LISP (LISt Processing) PL/I – ALGOL ‘68 (Linguaggio universale) L’era moderna: Programmazione strutturata, Metodologie, Astrazione, Linguaggi ad alto livello per la programmazione di sistema LISP PASCAL Varie versioni della logica ADA Universale? C PROLOG ML Programmazion e orientata agli oggetti C++ JAVA 10 Paradigmi z z z Per paradigmi di programmazione si intendono i “modi” in cui vengono specificati i programmi Non si tratta tanto del tipo di linguaggio usato, ma del contesto più ampio al quale un certo linguaggio appartiene Parliamo di come viene organizzata la programmazione, con quali caratteristiche: stile, livello di dettaglio, “forma mentis” del programmatore Tipologie di linguaggi 22 z Possiamo aggregare i numerosi linguaggi di programmazione esistenti (ad alto livello) sulla base del modello astratto di programmazione che sottintendono e che è necessario adottare per utilizzarli. Linguaggi di programmazione Imperativi Procedurali C, Pascal, Fortran Ad oggetti Dichiarativi Paralleli Funzionali Logici Lisp Prolog C++, Java Fondamenti di Informatica 11 Linguaggi Imperativi 23 z Caratteristiche: z z z di utilizzo più semplice indipendenti dall'elaboratore purtroppo ancora legati al modello di Von Neumann: i programmi sono ancora una sequenza di istruzioni; l'evoluzione del calcolo è costituita da una variazione dello stato della memoria z Eseguono 3 tipi di operazioni: z trasferimento dati operazioni aritmetiche alterazione del flusso del programma Fondamenti di Informatica Programmazione imperativa z z z z Il programmatore deve definire tutte le strutture dati e tutti gli algoritmi che operano su di esse Il programma non può gestire strutture dati parziali Meccanismi dinamici e chiamate di sottoprogrammi gestiti (anche se non sempre completamente) dal programmatore ... Linguaggi di programmazione Imperativi Procedurali C, Pascal, Fortran Ad oggetti C++, Java Dichiarativi Paralleli Funzionali Logici Lisp Prolog 12 Linguaggi procedurali 25 z permettono di descrivere operazioni più complesse di quelle che l'elaboratore può eseguire direttamente livello di astrazione più alto rispetto al linguaggio macchina (detti di alto livello di tipo imperativo) risalgono agli anni '50 Es: Basic, Pascal, C z Sono basati sul concetto di blocco di istruzioni z z z Linguaggi di programmazione Imperativi Procedurali C, Pascal, Fortran Ad oggetti Dichiarativi Paralleli C++, Java Funzionali Logici Lisp Prolog Linguaggi a Oggetti 26 z z z z z z Sono nati più di recente Favoriscono la modularità ed il riutilizzo del codice Modellazione del problema da risolvere come un insieme di oggetti che si scambiano messaggi Esempi: C++, Java, Smalltalk, Eiffel I programmi definiscono delle astrazioni (classi) di elementi del dominio di applicazione del programma Le classi contengono informazioni sui dati ma anche il codice per gestirli (in genere di tipo imperativo) Linguaggi di programmazione Imperativi Procedurali Ad oggetti Fortran C++, Java Dichiarativi Paralleli Fondamenti di Informatica C, Pascal, Funzionali Logici Lisp Prolog 13 Programmazione concorrente z z z Un programma concorrente consiste di diversi processi che cooperano in un ambiente per raggiungere un risultato comune I processi possono avere meccanismi diversi di comunicazione (canali, memoria condivisa, multi-insieme di vincoli) L’attenzione della programmazione concorrente non è sul calcolo che effettuano i singoli processi, ma sulle loro interazioni Linguaggi di programmazione Imperativi Procedurali C, Pascal, Fortran Ad oggetti C++, Java Dichiarativi Paralleli Funzionali Logici Lisp Prolog Programmazione concorrente z Numerosi formalismi possibili: z z z z Algebre di processi: CCS, CSP Set di costrutti concorrenti che si aggiungono a linguaggi classici: Linda, Pascal o C concorrenti Programmazione concorrente con vincoli La formalizzazione è importante per effettuare verifiche formali di proprietà (es. mutua esclusione, raggiungibilità di stati, invarianze) sui programmi concorrenti 14 Paradigmi dichiarativi z z z I linguaggi dichiarativi sono molto utili per realizzare velocemente un prototipo di un’applicazione complessa Con poche righe di codice si possono realizzare operazioni molto complesse Il problema principale resta sempre l’efficienza Linguaggi di programmazione Imperativi Procedurali C, Pascal, Fortran Dichiarativi Ad oggetti Paralleli C++, Java Funzionali Logici Lisp Prolog Linguaggi Funzionali 30 z z Non sono legati al modello di Von Neumann ma al concetto di programmazione funzionale Il primo linguaggio funzionale: z z Lisp (List Processing), fine anni '50 caratteristiche di manipolazione agevole di informazioni di tipo simbolico Linguaggi di programmazione Imperativi Procedurali C, Pascal, Ad oggetti Dichiarativi Paralleli Fondamenti di Informatica Fortran C++, Java Funzionali Logici Lisp Prolog 15 Programmazione Funzionale z z z z Primo linguaggio funzionale: λ-calcolo (nucleo della programmazione funzionale) Molto importante soprattutto dal punto di vista teorico (versione non tipata Turing-equivalente) Altri linguaggi: Miranda, Haskell, Scheme, Standard ML (varie implementazioni tra cui CAML), LISP Differenze nell’efficienza, nella vastità di librerie, nel tipo di valutazione (lazy vs eager) Programmazione Funzionale z z z Approccio dichiarativo: il programma è una definizione di funzione, il “calcolo” è built-in I linguaggi funzionali possono essere usati come metalinguaggi per definire altri linguaggi ottenendo, da una definizione denotazionale della semantica, anche un interprete (gratis!) Le moderne implementazioni sono piuttosto efficienti 16 Differenze con i linguaggi imperativi 33 z z z z il calcolo è basato sul calcolo di valori e non sull'assegnamento di valori a variabili Il programma è una definizione di funzioni nel senso più matematico del termine z basato su valori e non su effetti z il risultato è il risultato di una funzione, non l'effetto causato dalla esecuzione di una sequenza di operazioni Ordine superiore: gli argomenti delle funzioni definite possono essere sia valori di tipi primitivi che altre funzioni L’interpete si occupa di valutare, in base alle funzioni di base e a quelle definite, una qualsiasi espressione ben formata Fondamenti di Informatica Programmazione Funzionale: esempio caml #let rec fatt = function # 0 -> 1 # | n -> n * fatt n-1;; fatt: int -> int = <fun> #let rec map = function # [], f -> [] # | (x::Xs), f -> (f x) :: map Xs;; map: ’a list * (’a -> ’b) -> ’b list = <fun> #map [2;0;3] fatt;; - int list = [2; 1; 6] #map [0;3] (function x -> x+1);; - int list = [1;4] 17 Linguaggi Logici 35 z z z z Anche qui il formalismo è dichiarativo: i programmi sono definizioni, in questo caso di relazioni e non di funzioni Basati sulla logica z obiettivo: formalizzare il ragionamento z caratterizzati da meccanismi deduttivi Programmazione: z semplice (occorre solo definire la propria conoscenza del problema) z avviene tramite una formulazione dichiarativa Esempio: Prolog Linguaggi di programmazione Imperativi Procedurali Ad oggetti Paralleli Fondamenti di Informatica C, Pascal, Fortran C++, Java Dichiarativi Funzionali Logici Lisp Prolog Linguaggi Logici 36 z Programmare significa: z z z descrivere il problema con formule del linguaggio interrogare il sistema, che effettua deduzioni sulla base delle definizioni pertanto Il motore di calcolo è un dimostratore di teoremi che cerca di dimostrare un goal (una clausola Horn senza la conseguenza) a partire dalle clausole del programma Il “risultato” viene fuori dagli assegnamenti alle variabili libere del goal che il dimostratore fa durante la visita (con backtracking) dell’albero di dimostrazione per il goal e il programma logico dati Fondamenti di Informatica 18 Programmazione logica z z Un programma logico è la definizione di un certo numero di predicati della logica del primo ordine Limitazione: la definizione può avvenire solo con clausole Horn definite: p1 ( X 11 ,K , X n1 ) ∧ L ∧ pk ( X 1k , K , X mk ) → q (Y1 , K , Yh ) dove n, m, k , h ≥ 0, pi sono simboli di predicato e gli X ij , Yi sono termini di un linguaggio del primo ordine : c, f(X), f(g(a)), g(c)... Programmazione logica: esempio #append([],Ys,Ys). #append([X|Xs],Ys,[X|Zs]) :append(Xs,Ys,Zs). :- sta per ← ?- append([1,2],[2,4],X). X = [1,2,2,4] ?- append(X,[3],[2,5,3]) X = [2,5] Ma c’è di più! 19 Programmazione logica: esempio ?- append(X,Y,[3,4,5]). X = [], Y=[3,4,5] ; X = [3], Y=[4,5] ... ?- append(X,Y,[3,4|Z]). X = [3], Y = [4|Z] ; X = [3,4], Y = Z Si definiscono relazioni che possono essere usate anche come funzioni, ma non solo! Linguaggi di programmazione Imperativi Proced urali C, Pascal, Fortran Ad oggetti C++, Java Parallel i Dichiarativi Funzio nali Lisp Logici DB Prolog 20 Traduzione dei programmi 41 z Affinchè un programma scritto in un qualsiasi linguaggio di programmazione sia comprensibile (e quindi eseguibile) da un calcolatore, occorre tradurlo dal linguaggio originario al linguaggio della macchina z Questa operazione viene normalmente svolta da speciali programmi detti traduttori Fondamenti di Informatica Traduzione di un programma 42 z Il traduttore converte: z z Il testo di un programma scritto in un particolare linguaggio di programmazione (sorgente) … … nella corrispondente rappresentazione in linguaggio macchina (programma eseguibile) sorgente … X=X+1; If X>0 … … traduzione eseguibile 0010100 … 01001.. 10010… Fondamenti di Informatica 21 Compilatori e Interpreti 43 z Esistono due categorie di traduttori: z i compilatori: traducono l’intero programma (senza eseguirlo) e producono in uscita il programma convertito in linguaggio macchina z gli interpreti: traducono ed eseguono immediatamente ogni singola istruzione del programma sorgente Fondamenti di Informatica Interprete 44 z L’ interprete: itera più volte questo processo z Legge un’istruzione del programma “sorgente” z Traduce l’istruzione in linguaggio macchina z Esegue l’istruzione z Passa all’interpretazione dell’istruzione successiva z Al termine di questa operazione, del programma in linguaggio macchina non rimane alcuna traccia (la traduzione non viene memorizzata) Se il programma torna più volte su una stessa istruzione, questa verrà tradotta (ed eseguita) ogni volta. È necessario disporre dell’interprete per poter eseguire il programma. z z Fondamenti di Informatica 22 Compilatore 45 z Compilatore: esegue una sola volta il processo z z z z z Legge tutte le istruzioni del programma “sorgente” e le traduce in linguaggio macchina. Memorizza su disco il programma “eseguibile” tradotto in linguaggio macchina. Al termine della compilazione avremo un programma eseguibile in linguaggio macchina. La traduzione di ogni istruzione del programma avviene una sola volta, anche se una stessa istruzione viene ripetuta più volte all’interno del programma. Non ho bisogno di avere il compilatore ed il sorgente per eseguire il programma: mi basta il programma eseguibile Fondamenti di Informatica Compilatori e Interpreti 46 sorgente … X=X+1; If X>0 … … traduzione eseguibile 0010100 … 01001.. 10010… esecuzione z Nel caso del compilatore, lo schema precedente viene percorso una volta sola, prima dell’esecuzione z Nel caso dell’interprete, lo schema viene invece attraversato tante volte quante sono le istruzioni che compongono il programma Fondamenti di Informatica 23 Compilatori e Interpreti 47 Tipicamente, l’esecuzione di un programma compilato è più veloce dell’esecuzione di un programma interpretato Fondamenti di Informatica Esecuzione dei programmi 48 z Nel caso dei compilatori, l'esecuzione di un programma scritto con un linguaggio ad alto livello è preceduta dai seguenti passi: 1. 2. 3. traduzione in linguaggio macchina collegamento con programmi di supporto (calcoli, comunicazione con periferiche,…) caricamento in memoria Fondamenti di Informatica 24 Traduzione in linguaggio macchina: compilatore 49 z Viene suddivisa in 2 passi: z z analisi (lessicale, grammaticale, contestuale) trasformazione del programma sorgente in programma oggetto (forma più vicina al linguaggio macchina): creazione tabella simboli z ottimizzazioni (rimozione ripetizioni, eliminazione cicli, sfruttamento registri,…); livelli di ottimizzazione z Fondamenti di Informatica Collegamento con programmi di supporto linker 50 z Il codice oggetto così formato: z può ancora contenere dei simboli irrisolti z z z riferimenti esterni a programmi di servizio (accesso alle periferiche, calcoli matematici,...) contiene indirizzi relativi Il linker serve per collegare diversi moduli oggetto, e formare un unico programma eseguibile Fondamenti di Informatica 25 Caricamento in memoria: loader 51 z z Il Loader serve per caricare in memoria un programma Nel caricamento vengono fissati tutti gli indirizzi relativi z z variabili, salti, … Vengono caricati anche i moduli di supporto, se necessari Fondamenti di Informatica Costruzione “manuale” 52 z In passato, la costruzione dell’eseguibile si faceva “a mano”, attivando compilatore e linker dalla linea di comando del sistema operativo (DOS, Unix, ...) z C:\PROVA> gcc -c f1.c (genera f1.obj) z C:\PROVA> ld -o prog.exe f1.obj –lc (genera prog.exe) Eseguibile da produrre FondamentiFile di Informatica oggetto Libreria di sistema C 26 Ambienti Integrati 53 z Oggi, gli ambienti di lavoro integrati (IDE – Integrated Development Environments) automatizzano la procedura: z z z compilano i file sorgente (se e quando necessario) invocano il linker per costruire l’eseguibile ma per farlo devono sapere: z z quali file sorgente costituiscono l’applicazione il nome dell’eseguibile da produrre. Fondamenti di Informatica 27