Linguaggi di programmazione. Informatica

(1)

Evoluzione dei paradigmi di programmazione Traduzione di programmi Programmazione logica Esercizi e Approfondimenti

Linguaggi di programmazione

rif.: J.G. Brookshear, Informatica generale, Cap. 5.1–5.4, 5.7

Università di Catania, Facoltà di Lingue e L.S.

Corso di laurea in Scienze della comunicazione internazionale

Informatica

29 novembre – 6 dicembre 2006

Università di Catania, Facoltà di Lingue e L.S., Informatica Linguaggi di programmazione

Sommario

1 Evoluzione dei paradigmi di programmazione Linguaggi di programmazione: i primordi Paradigmi di programmazione

Programmazione dichiarativa

2 Traduzione di programmi Il processo di traduzione Analisi sintattica

3 Programmazione logica

Clausole Horn positive e principio di risoluzione Processi di calcolo deduttivo

Formalizzazione di grammatiche in Prolog

4 Esercizi e Approfondimenti Esercizi

Approfondimenti

(2)

Linguaggi di programmazione: i primordi Paradigmi di programmazione

Programmazione dichiarativa

linguaggi di prima generazione

una storia di progressiva astrazione dalla macchina linguaggi assembler :

rappresentazione mnemonica di codici operativi e registri nomi alfanumerici (identificatori, variabili)

delle locazioni di memoria dei dati esempio: CostoTotale = Prezzo + CostoSpedizione

156C LD R5 Prezzo

166D LD R6 CostoSpedizione 5056 ADDI R0 R5 R6

306E ST R0 CostoTotale C000 HALT

corrispondenza biunivoca delle primitive assembler ⇐⇒ linguaggio macchina

linguaggi di seconda generazione

programma assembler :

traduttore da linguaggio assembler a linguaggio macchina linguaggi macro-assembler :

estensione dell’assembler con definizioni di macro-istruzioni:

nomi (con eventuali parametri) per sequenze frequenti di istruzioni espansione delle macro-istruzioni: sostituzione testuale

programma macro-assembler : macro pre-processor ; assembler

limite di queste prime 2 generazioni di linguaggi:

dipendenza dall’architettura della macchina

=⇒ scarsa portabilità dei programmi

=⇒ algoritmi orientati alla macchina

piuttosto che al problema

(3)

linguaggi di terza generazione

linguaggi di programmazione di alto livello, obiettivi:

affrancare lo sviluppo di algoritmi dalla dipendenza dalla macchina

individuare primitive e costrutti orientati al problema, di uso generale in un ampio dominio applicativo

ampia diffusione trovano i primi linguaggi di terza generazione (anni ’50), dotati di costrutti sofisticati:

FORTRAN: FORmula TRANslator applicazioni scientifiche

COBOL: COmmon Business Oriented Language applicazioni commerciali e gestionali di notevole rilievo storico, sebbene trovi minor diffusione, è il coevo apparire del linguaggio

LISP: per applicazioni di Intelligenza Artificiale

paradigmi di programmazione

negli anni ’50 e ’60 la programmazione imperativa, ispirata dall’architettura Von Neumann, rimane il paradigma dominante

a partire dagli anni ’70 emergono altri paradigmi di programmazione:

nuclei di concetti fondamentali che danno vita a diversi approcci e modi di pensare all’espressione di algoritmi

approssimativamente, con qualche correzione:

(4)

programmazione imperativa e procedurale

le primitive dei linguaggi imperativi esprimono comandi all’esecutore costrutti caratteristici:

istruzione di assegnamento: v := E composizione sequenziale di comandi iterazione di comandi

le istruzioni di “salto” vengono progressivamente abbandonate, secondo i canoni della programmazione strutturata

astrazione procedurale invece che macro-istruzioni:

parametri formali: nella definizione della procedura parametri attuali: nella invocazione della procedura passaggio dei parametri:

per valore per riferimento

programmazione orientata agli oggetti

estende la programmazione procedurale con i concetti di

classe: incapsulamento di dati e operazioni per l’accesso ad essi oggetto: istanza dinamica di una classe,

ha stato (variabili di istanza) e identità

nasce nell’ambito dei linguaggi di simulazione: Simula 67 ben si presta alla rappresentazione della concorrenza si sviluppa negli anni ’80 come

paradigma di progettazione del software

linguaggi più diffusi: Smalltalk, C++, Eiffel, Java anni ’90: diventa il paradigma dominante nella

produzione industriale di software , standardizzazione:

OMG: Object Management Group, http://www.omg.org CORBA: Common Object Request Broker Architecture

UML: Unified Modeling Language

(5)

programmazione funzionale

basata sulla composizione di funzioni

precursori: λ-calcolo (A. Church, 1941), LISP (J. McCarthy, 1958) nasce come paradigma con la 1977 Turing Award Lecture di J. Backus:

Can programming be liberated from the von Neumann style?

A functional style and its algebra of programs. CACM, 21(8):613–641 (1978) http://www.stanford.edu/class/cs242/readings/backus.pdf

idea: interpretazione di equazioni come regole di riscrittura di termini programmazione funzionale pura:

priva dell’assegnamento (imperativo) ben si presta al calcolo parallelo linguaggi più diffusi:

ML, Scheme, CAML, Haskell funzioni higher order, currying : (A × B) → C =

^∼

A→(B→C)

programmazione logica

basata sulla deduzione in una logica dei predicati ristretta:

clausole Horn strettamente positive γ ₁ , . . . , γ _n ⇒ α γ ₁ , . . . , γ _n , α: predicati (con variabili)

quantificazione universale implicita

“scoperta da R. Kowalski nel 1974,

implementata da A. Colmerauer nel 1973” . . . =⇒ Prolog primitive:

fatti: clausole Horn strettamente positive con n = 0 regole: clausole Horn strettamente positive con n > 0 programma: insieme di fatti e regole

query : predicato, di solito con variabili

soluzione: sostituzione di valori per le variabili della query che ne

rende la corrispondente istanza deducibile dal programma

l’ordine di fatti e regole dovrebbe essere irrilevante

(6)

Il processo di traduzione Analisi sintattica

il processo di traduzione

due tipi principali di traduttori:

compilatori: traduttori “puri”: sorgente =⇒ oggetto interpreti: eseguono ciascuna istruzione sorgente

subito dopo averla tradotta fasi principali della traduzione:

analisi lessicale: riconoscimento dei lessemi (tokens ) del linguaggio (identificatori, parole riservate, separatori, operatori, etc.) analisi sintattica (parsing ):

controllo di correttezza del sorgente rispetto alla grammatica libera del linguaggio (v. avanti) costruzione dell’albero sintattico del sorgente generazione del codice: da albero sintattico e tabella dei simboli

esecuzione di un traduttore

l’esistenza di una logica sequenzialità delle fasi del processo di traduzione non ne impedisce l’ esecuzione parallela

l’attività di ciascuna fase trasforma un flusso (stream ) di dati in ingresso in un flusso di dati in uscita

una porzione del flusso in ingresso è in genere sufficiente per produrre una corrispondente porzione del flusso in uscita

ciò permette l’esecuzione in pipeline delle fasi della traduzione

(7)

oltre la traduzione

compilazione separata: i compilatori sono generalmente in grado di tradurre moduli di programma (ad es. procedure, definizioni di funzioni, classi) separatamente e in tempi diversi linker : il risultato della traduzione di un modulo sorgente

non è generalmente un programma eseguibile, bensì

un modulo oggetto, che va collegato ad altri moduli oggetto per costruire un eseguibile

loader : in un programma eseguibile gli indirizzi di memoria non sono generalmente assoluti, bensì relativi ad una locazione di base, determinata all’atto del caricamento del programma in memoria

diagrammi sintattici

rappresentazioni grafiche delle produzioni (regole) di una grammatica libera:

cerchi: simboli (lessemi) terminali rettangoli: simboli non terminali

istruzione

G

_L

= (V

_T

, V

_N

, P, s

₀

) : grammatica libera del linguaggio L, dove:

V

_T

: vocabolario terminale V

_N

: vocabolario non terminale

P ⊆ V

_N

× (V

_T

∪V

_N

)

^∗

: produzioni di G

_L

s

₀

∈V

N

:

simbolo iniziale di G

_L

(8)

costruzione di alberi sintattici

linguaggio L generato da G

_L

: sottoinsieme di V

^∗_T

costituito dalle stringhe terminali derivabili dal simbolo iniziale con le produzioni di G

_L

esempio: parsing dell’espressione x+y x z

derivazione dal simbolo iniziale espressione: top-down o bottom-up?

ambiguità sintattica

una grammatica è ambigua se qualche espressione del linguaggio che essa genera ha più derivazioni dal simbolo iniziale

esempio: il precedente diagramma sintattico per if . . . then . . . [else . . . ]

rende ambigua la grammatica di simbolo iniziale istruzione

(9)

Clausole Horn positive e principio di risoluzione Processi di calcolo deduttivo

Formalizzazione di grammatiche in Prolog

clausole Horn positive e principio di risoluzione

forma clausale di un enunciato nella logica dei predicati:

congiunzione di un insieme (finito) di clausole, dove:

clausola: disgiunzione di un insieme finito di atomi, dove:

atomo: predicato (atomo positivo)

o negazione di predicato (atomo negativo)

principio di risoluzione:

se P e R sono entrambi vuoti,

con la regola di risoluzione si deduce la clausola vuota, ovvero l’inconsistenza della forma clausale data

clausola Horn (strettamente) positiva:

clausola in cui solo un atomo è positivo è facile verificare l’equivalenza logica:

α ∨ ¬γ

₁

∨ . . . ∨ ¬γ

_n

≡ γ

₁

∧ . . . ∧ γ

_n

⇒ α

deduzione per refutazione

per dedurre il predicato P da una forma clausale C si cerca di dedurre la clausola vuota da C ⁰ = C∧¬P esempio: C = (P∨Q)∧(R∨¬Q)∧¬R

la deduzione per refutazione di P da C procede come in figura, usando il principio di risoluzione:

oppure

(10)

sostituzione e unificazione

le clausole Horn con variabili sono (implicitamente) universalmente quantificate: C(X) ≡ ∀X C(X)

una sostituzione è una funzione da variabili in termini: σ :V→T(V) ogni sostituzione si estende naturalmente a termini e predicati, determinandone corrispondenti istanze

esempio: σ: X7→0, Y7→X σ somma(X,Y,Y) = somma(0,X,X) un unificatore di due predicati è una sostituzione che ne dà istanze identiche (sintatticamente)

esempio: somma(X,0,X) e somma(0,Y,Y) hanno l’unificatore σ: X7→0, Y7→0 una sostituzione chiusa manda variabili in termini chiusi,

cioè privi di variabili (come nell’esempio precedente)

la programmazione logica si basa su risoluzione e unificazione, per determinare soluzioni di una query in un programma, ovvero sostituzioni chiuse che, applicate al predicato costituente la query, ne danno un’istanza deducibile dalle clausole Horn del programma

uso computazionale delle clausole Horn positive

convenzioni sintattiche Prolog :

le variabili hanno iniziale maiuscola

simboli di funzioni e di predicati hanno iniziale minuscola la clausola Horn γ

1

, . . . , γ

n

⇒ α si scrive α :- γ

1

, . . . , γ

n

. il predicato binario infisso is, predefinito su termini aritmetici, è soddisfatto dall’identità di valutazione piuttosto che sintattica esempio: un programma Prolog per il calcolo di n!, il fattoriale di n:

fact(0, 1) .

**fact(N, M) :- N1 is N-1, fact(N1, Z), M is N*Z .**

compilazione del programma ed esecuzione di una query :

?- [fact].

% fact compiled 0.00 sec, 1,004 bytes

?- fact(3,X).

X = 6

(11)

regole DCG in Prolog

le liste sono una struttura dati predefinita in Prolog:

sintassi: [], [Head | List], e [t

1

, . . . , t

n

]

si possono inoltre rappresentare regole di una grammatica libera, dette Definite Clause Grammar (DCG) rules o semplicemente grammar rules , che vengono automaticamente tradotte in clausole Horn positive secondo una tecnica detta delle liste-differenza

sintassi: t --> t

1

, . . . , t

n

. (inoltre “;” separa alternative) esempio 1: (i lessemi terminali sono in parentesi quadre)

frase --> soggetto, predicato, [’.’].

soggetto --> articolo, sostantivo.

predicato --> verbo_intrans ;

verbo_trans, compl_oggetto.

compl_oggetto --> articolo, sostantivo.

sostantivo --> [nutrice] ; [bimbo].

articolo --> [il] ; [la] ; [un] ; [una].

verbo_intrans --> [dorme].

verbo_trans --> [nutre].

vincoli sintattici con le regole DCG

si possono imporre vincoli di concordanza usando variabili e struttura di termini per simboli non terminali

esempio 2: così, rispetto all’esempio 1, si possono modificare le regole per soggetto, compl_oggetto , articolo e sostantivo come segue:

soggetto --> articolo(Gen), sostantivo(Gen).

compl_oggetto --> articolo(Gen), sostantivo(Gen).

sostantivo(f) --> [nutrice].

sostantivo(m) --> [bimbo].

articolo(f) --> [la] ; [una].

articolo(m) --> [il] ; [un].

compilazione del programma ed esecuzione di query :

?- [nbg2].

% ngb2 compiled 0.00 sec, 3,096 bytes

?- phrase(frase, [il, bimbo, X, .]).

X = dorme ; No

phrase(frase, [X, Y, nutre, il, bimbo, .]).

X = la

Y = nutrice

Yes

(12)

costruzione dell’analisi sintattica con regole DCG

variabili e struttura di termini per simboli non terminali possono essere usati anche per la costruzione dell’albero sintattico di una data frase

a tal fine le regole DCG della grammatica vanno modificate così che la query phrase(frase(X), [ lista_terminali ]).

abbia come soluzione X = t, dove t sia l’albero sintattico di lista_terminali esempio 3: ecco una modifica in tal senso rispetto all’esempio precedente:

frase(fs(S,P)) --> soggetto(S), predicato(P), [’.’].

soggetto(sg(A,S)) --> articolo(Gen,A), sostantivo(Gen,S).

predicato(pi(V)) --> verbo_intrans(V).

predicato(pt(V,O)) --> verbo_trans(V), compl_oggetto(O).

compl_oggetto(co(A,S)) --> articolo(Gen,A), sostantivo(Gen,S).

sostantivo(f,s(nutrice)) --> [nutrice].

sostantivo(m,s(bimbo)) --> [bimbo].

articolo(f,a(la)) --> [la].

articolo(f,a(una)) --> [una].

articolo(m,a(il)) --> [il].

articolo(m,a(un)) --> [un].

verbo_intrans(vi(dorme)) --> [dorme].

verbo_trans(vt(nutre)) --> [nutre].

automazione dell’analisi sintattica con Prolog DCG

la tecnica esemplificata sopra trasforma in modo relativamente meccanico una grammatica libera in una DCG Prolog che può essere compilata ed eseguita per ottenere l’analisi sintattica delle espressioni del linguaggio che essa genera esempio: compilazione del programma ed esecuzione di query :

?- [nbg2p].

% ngb2p compiled 0.00 sec, 4,136 bytes

?- phrase(frase(X), [la, nutrice, nutre, il, bimbo, .]).

X = fs(sg(a(la), s(nutrice)), pt(vt(nutre), co(a(il), s(bimbo)))) ;

No

?- phrase(frase(X), [la, nutrice, Y, .]).

X = fs(sg(a(la), s(nutrice)), pi(vi(dorme))) Y = dorme ;

No

?- phrase(frase(X), [Y, Z, W, .]).

X = fs(sg(a(la), s(nutrice)), pi(vi(dorme))) Y = la

Z = nutrice

W = dorme

Yes

(13)

Esercizi Approfondimenti

esercizi: linguaggi di programmazione

1

Quale delle seguenti asserzioni sul paradigma funzionale è vera?

(a) È basato sulla composizione di funzioni.

(b) Consta di funzioni elaborate appositamente per ciascun dato problema.

(c) È anche noto come paradigma procedurale.

(d) Consiste nella costruzione di funzioni complesse.

2

Quale dei seguenti programmi traduce e immediatamente esegue ciascuna istruzione di un programma sorgente?

(a) analizzatore lessicale (b) parser

(c) compilatore (d) interprete

3

La regola classica di deduzione logica detta modus ponens può essere espressa come segue: se A e A→B allora B. Mostrare che questa regola è equivalente a un caso particolare del principio di risoluzione.

Suggerimento:

Tener conto dell’equivalenza logica A→B ≡ B∨¬A.

4

Estendere la grammatica dell’esempio illustrato a lezione con regole DCG che ammettano la congiunzione di frasi come frase del linguaggio

Esercizi Approfondimenti

temi per ulteriori approfondimenti

1

Programmazione orientata agli oggetti

Il tema è introdotto nella sez. 5.5 del testo adottato. È inoltre disponibile il testo di una lezione sull’argomento, nell’area on-line Supplementi/oop:

http://www.flingue.unict.it/didattica_online/mod/resource/view.php?id=299 2

Programmazione concorrente

Il tema è introdotto nella sez. 5.6 del testo adottato.

3

Programmazione dichiarativa

Ecco dei siti su alcuni linguaggi di programmazione funzionale e logica:

Haskell: http://www.haskell.org

Scheme: http://swiss.csail.mit.edu/projects/scheme SML: http://www.smlnj.org

Caml: http://caml.inria.fr

SWI-Prolog: http://www.swi-prolog.org GNU Prolog: http://gnu-prolog.inria.fr

4

Automazione della costruzione di analizzatori sintattici

Le Prolog DCG rules non sono trattate nel libro di testo adottato. Una rapida introduzione all’argomento è disponibile nell’area on-line Dispense:

http://www.flingue.unict.it/didattica_online/mod/resource/view.php?id=298

? È allo studio la fattibilità di un breve ciclo di lezioni di laboratorio, per

l’illustrazione pratica di metodi e strumenti disponibili allo scopo in tema.

Linguaggi di programmazione. Informatica