Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 1.Breve Presentazione del corso


Informazioni Generali sul Corso

  • Esame: Fondamenti dei linguaggi di programmazione (nel vecchio ordinamento: Semantica dei linguaggi)
  • Libri di testo:
    • Glynn Winskel “La semantica Formale dei Linguaggi di Programmazione” the MIT Press, 1993. Traduzione italiana a cura di Franco Turini
  • Approfondimenti:
    • John C. Mitchell, “Foundations for Programming Languages“, MIT Press, 1996.
    • Benjamin Pierce. “Types and Programming Languages”, MIT Press, 2002.
    • Robin Milner, “Communication and Concurrency”, Prentice Hall, 1989.
  • Modalità d’esame: Una prova scritta seguita da una prova orale facoltativa.
  • Modalità Lezioni: Tutte le lezioni sono erogate in modalità frontale ed in e-learning. Le lezioni frontali si svolgeranno da ottobre a dicembre, due lezioni a settimana della durata di due ore ciscuna.

Informazioni sul Docente

  • Prof. Dr. Aniello Murano, ricercatore universitario presso la Sezione di Informatica del Dipartimento di Scienze Fisiche – Università degli Studi di Napoli, Federico II
  • Sito web
  • Ricevimento: Giovedì 13:30 – 15:30, OF29b
  • E-mail: murano@ na.infn.it
  • Altre informazioni sul docente:
    • Laurea in Scienze dell’informazione e Dottorato di ricerca in Informatica presso l’Università degli Studi di Salerno. Visiting Student per un anno presso la Rice Univeristy di Houston (Texas – USA). Post-doc per un anno presso la Hebrew University di Gerusalemme (Israele).
    • Altri insegnamenti: Lab. di ASD – Corso di Laurea in Informatica, Facolta di Scienze MM.FF.NN. – Università di Napoli “Federico II”.
    • Interessi di ricerca: Teoria degli Automi e dei Linguaggi Formali. Logiche Temporali discrete e real-time, Metodi Formali per la Specifica, la Verifica e la Sintesi di sistemi hardware e software, Model Checking, Teoria dei Giochi.

Obiettivi del Corso

  • L’obiettivo del corso è quello di fornire i modelli formali necessari per capire il comportamento di un programma e ragionare su di esso.
  • Vengono dunque presentate le nozioni matematiche, le tecniche ed i concetti sui quali si fonda la semantica formale dei linguaggi di programmazione.

Che cosa questo corso non è

  • Un corso su un particolare linguaggio di programmazione.
  • Un corso sulla costruzione di un particolare compilatore o sulla costruzione di un parser.
  • Un corso per confrontare i vari linguaggi di programmazione.
  • Un corso sui vari paradigmi di programmazione (funzionali, orientati agli oggetti, logici, concorrenti, ecc.).

Programma del corso (provvisorio)

  • Semantica operazionale del linguaggio imperativo IMP (Cap. II, pag 15-32);
  • Induzione ben fondata (Cap. III-IV, pag 33-60);
  • Ordinamenti parziali completi, funzioni continue e teorema di punto fisso (Cap. V, pag 79-83);
  • Semantica denotazionale del linguaggio imperativo IMP e corrispondenza con la semantica operazionale (Cap. V, pag 65-78);
  • Linguaggi con tipi di ordine superiore: tipizzazione, semantica operazionale eager e lazy, semantica denotazionale lazy (Cap. XI, pag 201-209 e pag. 219-222);
  • Nondeterminismo e parallelismo: i linguaggi CSP e CCS (Cap. XIV, pag 321-341);
  • Breve introduzione alla verifica formale dei sistemi.

Prerequisiti al corso

  • Background in linguaggi di programmazione
    • Esperienza di programmazione in differenti linguaggi di programmazione (per esempio C, Java, Lisp, Prolog, ect.)
  • Background in logica matematica
    • Abilità nello scrivere e leggere prove formali (per esempio, dimostrazioni per induzione)
    • Una certa predisposizione ai “ragionamenti formali”.

Lo stato dell’arte

  • Quello dei linguaggi di programmazione è senza dubbio uno dei campi più vecchi, fondamentali e ferventi dell’informatica.
  • Ancora oggi, i linguaggi di programmazione sono in continua evoluzione.
  • I linguaggi di programmazione sono solitamente adottati per riempire dei vuoti:
    • Per implementare un’applicazione che prima era difficile o impossibile da implementare;
    • Per eseguire programmi su una nuova piattaforma.
  • Istruire nuovi programmatori comporta costi notevoli:
    • I linguaggi più largamente utilizzati sono raramente sostituiti;
    • I linguaggi più popolari con il passare del tempo si arrugginiscono;
    • Al contrario, nuove applicazioni e nuove piattaforme rappresentano interessanti opportunità per innovazioni.

Perché ci sono così tanti linguaggi

  • Molti linguaggi furono costruiti per specifiche applicazioni.
  • I domini di applicazione hanno solitamente bisogni differenti (e conflittuali).
  • Per esempio:
    • Intelligenza Artificiale: computazione simbolica (Lisp, Prolog);
    • Computazione Scientifica: grande performance (Fortran);
    • Computazione Commerciale: generazione di report (Cobol);
    • Programmazione di Sistemi: accesso a basso livello (C);
    • Castomizzazione: scripting (Perl, Javascript);
    • Sistemi distribuiti: computazione mobile (Java, C++);
    • e altri (Latex, AWK, Q, Hancock,…).

Paradigmi di Programmazione

  • Imperativo, procedurale:
    • Fortran, Algol, Cobol, C, Pascal.
  • Funzionali (principalmente liberi da assegnamento):
    • Lisp, Skeme, ML, Haskell.
  • Orientato agli oggetti:
    • C++, Java, Visual Basic, Simula, Smalltalk, Eiffel, Self.
  • Logici:
    • Prolog, lambda-Prolog.
  • Concorrenti:
    • Fortran90.

Cosa rende efficiente un linguaggio?

  • Una definizione sulla misura della scienza di Lord Kelvin (1824-1907): …”quando puoi misurare ciò di cui stai parlando e lo puoi esprimere in numeri, tu conosci qualcosa di ciò, ma quando non puoi esprimerlo in numeri, la tua conoscenza è povera e insoddisfacente; quello potrebbe essere l’inizio della conoscenza, ma si è lontani dall’aver elevato quel concetto allo stadio della scienza“.
  • Semplicità (nella sintassi e nella semantica).
  • Facilità di lettura e scrittura.
  • Familiarità.
  • Sicurezza.
  • Indipendenza dalla macchina.
  • Efficienza (di compilazione ed esecuzione).

Efficienza di un linguaggio

  • Spesso, gli obiettivi precedenti sono in conflitto tra di loro:
    • I controlli di sicurezza costano in termini di tempo di compilazione o esecuzione;
    • Sicurezza e indipendenza dalla macchina potrebbero vietare operazioni efficienti di basso livello;
    • Alcuni tipi di sistema possono restringere lo stile di programmazione negli scambi di informazione per rafforzare le garanzie di sicurezza.
  • Solitamente i compromessi sono difficili da trovare.
  • Dunque, progettare un buon linguaggio di programmazione è davvero difficile!

Valutare le caratteristiche di un linguaggio

  • Un concetto o un costrutto di un linguaggio può essere studiato nel contesto di un reale (e quindi di un grande) linguaggio.
  • Spesso però è più semplice studiare una caratteristiche di un linguaggio studiando un linguaggio minimo che ingloba quella caratteristica. Questo permette:
    • Una sperimentazione semplificata dell’intero linguaggio;
    • Una più profonda e precisa comprensione delle caratteristiche del linguaggio.

Un approccio formale di Specifica

Un approccio formale nella progettazione di un linguaggio consiste nella sua definizione rigorosa tramite una sintassi e una semantica.

Esistono tre approcci alla semantica dei linguaggi:

  • Semantica Operazionale
    • Definisce la macchina astratta che interpreta i programmi;
    • Utile per implementare un compilatore o un interprete;
    • Di basso livello, ma flessibile.
  • Semantica Denotazionale
    • Assegna denotazioni, o significati, ai programmi;
    • Usa oggetti matematici per descrivere i comportamenti dell’input e dell’output.
  • Semantica Assiomatica
    • Usa regole logiche per ragionare sul comportamento dei programmi;
    • Dato un programma, degli stati iniziali e dei dati di input, fornisce l’insieme degli stati finali raggiungibili dopo l’esecuzione;
    • Utile per provare la correttezza di un programma.

Sintassi di ARITH

  • Sintassi concreta: Le regole che permettono di esprimere i programmi come stringhe di caratteri
    • Utile per gli obiettivi di progettazione
    • Familiarità, leggibilità, velocità di compilazione
  • Gli stessi concetti possono essere espressi in molte sintassi concrete, non tutte ugualmente efficienti
  • Esistono comunque solidi principi per le sintassi concrete
    • Automi finiti e grammatiche context-free
    • Generatori di parser automatici

Sintassi astratta

  • Noi definiamo la sintassi del linguaggio ARITH rispetto ad un albero di sintassi astratto (parse tree).
  • L’albero di sintassi astratto è indipendente dalla sintassi concreta del linguaggio e meglio si adatta a manipolazioni formali e algoritmiche.
  • Una sintassi astratta per ARITH è

e::=n  dove n è un letterale intero (n Є {0,1,2,..})

| e1 + e2 somma

| e1 * e2 moltiplicazione

  • Dove “::=” significa “può essere” e “|” significa “oppure”

Analisi di ARITHM

Questioni da risolvere:

  • Qual è il significato di una data espressione di ARITH?
  • Come valutare una data espressione di ARITH?
  • Come sono collegati valutatore e significato di una espressione?

Una semantica Operazionale

Specifica come le espressioni dovrebbero essere valutate.

È definita in base alla particolare forma dell’espressione valutata:

  • n si valuta n

- n è una forma normale e non necessita di essere valutata ulteriormente

  • e1 + e2 si valuta n se

- e1 si valuta n1
- e2 si valuta n2
- ed n è la somma di n1 e n2

  • e1 * e2 si valuta n se

- e1 si valuta n1
- e2 si valuta n2
- ed n è il prodotto di n1 e n2

Formulazione Alternativa

  • Notazione: e + n significa che “e” si valuta in “n”
  • Questa è una valutazione, un’affermazione sulla relazione tra “e” ed “n”.
  • Questa notazione permette di riscrivere le regole precedenti in modo più conciso
  • n + n
  • e1 + e2 + n se
    • e1 + n1
    • e2 + n2
    • ed n è la somma di n1 ed n2
  • e1 * e2 + n se
    • e1 + n1
    • e2 + n2
    • ed n è il prodotto di n1 ed n2

Semantica operazionale come regole di inferenza

Interpretazione: “sopra la linea” implica “sotto la linea”

Interpretazione: “sopra la linea” implica “sotto la linea”


Esercizio

  • (3+5)*(4+2) in cosa si valuta?
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion