Copertina
Autore Maurizio Gabbrielli
CoautoreSimone Martini
Titolo Linguaggi di programmazione
SottotitoloPrincipi e paradigmi
EdizioneMcGraw-Hill, Milano, 2005 , pag. 460, cop.fle., dim. 170x238x27 mm , Isbn 978-88-386-6261-4
LettoreLuca Vita, 2006
Classe informatica: linguaggi
PrimaPagina


al sito dell'editore


per l'acquisto su IBS.IT

per l'acquisto su BOL.IT

per l'acquisto su AMAZON.IT

 

| << |  <  |  >  | >> |

Indice

Prefazione                                              xiii

Introduzione                                              xv

1      Macchine astratte                                   1

1.1    La nozione di macchina astratta e l'interprete      1
1.1.1  Interprete                                          3
1.1.2  Un esempio di macchina astratta:
       la macchina hardware                                6
1.2    Implementazione di un linguaggio                    9
1.2.1  Realizzazione di una macchina astratta             10
1.2.2  Implementazione: il caso ideale                    13
1.2.3  Implementazione:
       il caso reale e la macchina intermedia             18
1.3    Gerarchie di macchine astratte                     21
1.4    Sommario del capitolo                              24
1.5    Nota bibliografica                                 25
1.6    Esercizi                                           25

2      Descrivere un linguaggio di programmazione         27

2.1    Livelli di descrizione                             27
2.2    Grammatica e sintassi                              28
2.2.1  Grammatiche libere                                 30
2.3    Vincoli sintattici contestuali                     40
2.4    Compilatori                                        42
2.5    Semantica                                          47
2.6    Pragmatica                                         54
2.7    Implementazione                                    55
2.8    Sommario del capitolo                              55
2.9    Nota bibliografica                                 55
2.10   Esercizi                                           56

3      Fondamenti                                         57

3.1    Il problema della fermata                          57
3.2    Espressività dei linguaggi di programmazione       59
3.2.1  Formalismi per la calcolabilità                    60
3.3    Esistono più funzioni che algoritmi                62
3.4    Sommario del capitolo                              64
3.5    Nota bibliografica                                 64
3.6    Esercizi                                           64

4      I nomi e l'ambiente                                67

4.1    Nomi e oggetti denotabili                          67
4.1.1  Oggetti denotabili                                 69
4.2    Ambiente e blocchi                                 70
4.2.1  I blocchi                                          72
4.2.2  Tipi di ambiente                                   72
4.2.3  Operazioni sull'ambiente                           75
4.3    Regole di scope                                    78
4.3.1  Scope statico                                      79
4.3.2  Scope dinamico                                     81
4.3.3  Alcuni problemi di scope                           84
4.4    Sommario del capitolo                              87
4.5    Nota bibliografica                                 88
4.6    Esercizi                                           88

5      La gestione della memoria                          93

5.1    Tecniche di gestione della memoria                 93
5.2    Gestione statica della memoria                     95
5.3    Gestione dinamica mediante pila                    96
5.3.1  Record di attivazione per i blocchi in-line        98
5.3.2  Record di attivazione per le procedure            100
5.3.3  Gestione della pila                               102
5.4    Gestione dinamica mediante heap                   104
5.4.1  Blocchi di dimensione fissa                       105
5.4.2  Blocchi di dimensione variabile                   106
5.5    Implementazione delle regole di scope             109
5.5.1  Scope statico: la catena statica                  109
5.5.2  Scope statico: il display                         114
5.5.3  Scope dinamico: lista di associazioni e CRT       116
5.6    Sommario del capitolo                             121
5.7    Nota bibliografica                                121
5.8    Esercizi                                          122

6      Strutturare il controllo                          125

6.1    Le espressioni                                    125
6.1.1  Sintassi delle espressioni                        126
6.1.2  Semantica delle espressioni                       129
6.1.3  Valutazione delle espressioni                     131
6.2    La nozione di comando                             136
6.2.1  La variabile                                      137
6.2.2  L'assegnamento                                    138
6.3    Comandi per il controllo di sequenza              142
6.3.1  Comandi per il controllo di sequenza esplicito    143
6.3.2  Comandi condizionali                              146
6.3.3  Comandi iterativi                                 150
6.4    Programmazione strutturata                        157
6.5    La ricorsione                                     159
6.5.1  La ricorsione in coda                             162
6.5.2  Ricorsione o iterazione?                          167
6.6    Sommario del capitolo                             168
6.7    Nota bibliografica                                168
6.8    Esercizi                                          169

7      Astrarre sul controllo                            171

7.1    Sottoprogrammi                                    172
7.1.1  Astrazione funzionale                             174
7.1.2  Passaggio dei parametri                           175
7.2    Funzioni di ordine superiore                      186
7.2.1  Funzioni come parametro                           187
7.2.2  Funzioni come risultato                           193
7.3    Eccezioni                                         195
7.3.1  Implementare le eccezioni                         200
7.4    Sommario del capitolo                             202
7.5    Nota bibliografica                                203
7.6    Esercizi                                          204

8      Strutturare i dati                                207

8.1    Tipi di dato                                      207
8.1.1  Tipi come supporto all'organizzazione concettuale 208
8.1.2  Tipi per la correttezza                           209
8.1.3  Tipi e implementazione                            210
8.2    Sistemi di tipi                                   211
8.2.1  Controlli statici e dinamici                      212
8.3    Tipi scalari                                      214
8.3.1  Booleani                                          215
8.3.2  Caratteri                                         215
8.3.3  Interi                                            215
8.3.4  Reali                                             216
8.3.5  Virgola fissa                                     216
8.3.6  Complessi                                         216
8.3.7  Void                                              217
8.3.8  Enumerazioni                                      217
8.3.9  Intervalli                                        218
8.3.10 Tipi ordinali                                     219
8.4    Tipi composti                                     219
8.4.1  Record                                            219
8.4.2  Record varianti e unioni                          221
8.4.3  Array                                             226
8.4.4  Insiemi                                           232
8.4.5  Puntatori                                         232
8.4.6  Tipi ricorsivi                                    238
8.4.7  Funzioni                                          240
8.5    Equivalenza                                       241
8.5.1  Equivalenza per nome                              242
8.5.2  Equivalenza strutturale                           242
8.6    Compatibilità e conversione                       245
8.7    Polimorfismo                                      248
8.7.1  Overloading                                       249
8.7.2  Polimorfismo universale parametrico               250
8.7.3  Polimorfismo universale di sottotipo              252
8.7.4  Cenni sull'implementazione                        254
8.8    Controllo e inferenza di tipo                     255
8.9    Sicurezza: un bilancio                            257
8.10   Evitare i dangling reference                      258
8.10.1 Tombstone                                         258
8.10.2 Lucchetti e chiavi                                260
8.11   Garbage collection                                260
8.11.1 Contatori dei riferimenti                         263
8.11.2 Mark and sweep                                    264
8.11.3 Intermezzo: rovesciare i puntatori                265
8.11.4 Mark and compact                                  267
8.11.5 Copia                                             268
8.12   Sommario del capitolo                             270
8.13   Nota bibliografica                                271
8.14   Esercizi                                          271

9      Astrarre sui dati                                 275

9.1    Tipi di dato astratti                             276
9.2    Nascondere l'informazione                         279
9.2.1  Indipendenza dalla rappresentazione               282
9.3    Moduli                                            282
9.4    Sommario del capitolo                             284
9.5    Nota bibliografica                                286
9.6    Esercizi                                          286

10     Il paradigma orientato agli oggetti               287

10.1   Limiti dei tipi di dato astratti                  287
10.1.1 Un primo bilancio                                 291
10.2   Concetti fondamentali                             291
10.2.1 Oggetti                                           292
10.2.2 Classi                                            294
10.2.3 Incapsulamento                                    296
10.2.4 Sottotipi                                         298
10.2.5 Ereditarietà                                      303
10.2.6 Selezione dinamica dei metodi                     308
10.3   Aspetti implementativi                            312
10.3.1 Ereditarietà singola                              314
10.3.2 Il problema della classe base fragile             316
10.3.3 Selezione dinamica dei metodi nella JVM           317
10.3.4 Ereditarietà multipla                             320
10.4   Polimorfismo e generici                           326
10.4.1 Polimorfismo di sottotipo                         326
10.4.2 Generici in Java                                  329
10.4.3 Implementazione dei generici in Java              333
10.4.4 Generici, array e gerarchia di sottotipo          334
10.4.5 Overriding covarianti e controvarianti            336
10.5   Sommario del capitolo                             339
10.6   Nota bibliografica                                340
10.7   Esercizi                                          340

11     Il paradigma funzionale                           343

11.1   Computazioni senza stato                          343
11.1.1 Espressioni e funzioni                            345
11.1.2 Computazione come riduzione                       347
11.1.3 Gli ingredienti fondamentali                      347
11.2   Valutazione                                       349
11.2.1 Valori                                            350
11.2.2 Sostituzione senza cattura                        350
11.2.3 Strategie di valutazione                          351
11.2.4 Confronto tra strategie                           353
11.3   Programmare in un linguaggio funzionale           355
11.3.1 Ambiente locale                                   355
11.3.2 Interattività                                     355
11.3.3 Tipi                                              356
11.3.4 Pattern matching                                  357
11.3.5 Oggetti infiniti                                  359
11.3.6 Aspetti imperativi                                360
11.4   Implementazione: la macchina SECD                 362
11.5   Il paradigma funzionale a confronto               364
11.6   Fondamenti: A-calcolo                             367
11.7   Sommario del capitolo                             374
11.8   Nota bibliografica                                374
11.9   Esercizi                                          375

12     Il paradigma logico                               377

12.1   Deduzione come computazione                       377
12.1.1 Un esempio                                        378
12.2   Sintassi                                          382
12.2.1 Il linguaggio della logica del prim'ordine        382
12.2.2 I programmi logici                                384
12.3   Teoria dell'unificazione                          385
12.3.1 La variabile logica                               386
12.3.2 Sostituzione                                      387
12.3.3 L'unificatore più generale                        390
12.3.4 Un algoritmo di unificazione                      392
12.4   Il modello computazionale                         395
12.4.1 L'universo di Herbrand                            395
12.4.2 Interpretazione dichiarativa e procedurale        396
12.4.3 La chiamata di procedura                          397
12.4.4 Controllo: il non determinismo                    401
12.4.5 Alcuni esempi                                     404
12.5   Estensioni                                        407
12.5.1 PROLOG                                            407
12.5.2 Programmazione logica e basi di dati              411
12.5.3 Programmazione logica con vincoli                 413
12.6   Pregi e difetti del paradigma logico              415
12.7   Sommario del capitolo                             417
12.8   Nota bibliografica                                418
12.9   Esercizi                                          418

13     Una breve panoramica storica                      421

13.1   Gli inizi                                         421
13.2   Fattori evolutivi dei linguaggi                   424
13.3   Anni '50 e '60                                    425
13.4   Anni '70                                          429
13.5   Anni '80                                          434
13.6   Anni '90                                          437
13.7   Sommario del capitolo                             440
13.8   Nota bibliografica                                440

Bibliografia                                             443
Indice analitico                                         449


 

 

| << |  <  |  >  | >> |

Pagina xiii

Prefazione


Ho accettato con grande piacere l'invito rivoltomi a scrivere queste poche righe di prefazione per almeno due ragioni. La prima è che la richiesta mi viene da due colleghi che ho sempre tenuto in grandissima considerazione, fin dal tempo in cui li ho potuti conoscere ed apprezzare come studenti e come giovani ricercatori.

La seconda ragione è che il testo di Gabbrielli e Martini è molto vicino al libro che io avrei sempre voluto scrivere e, per ragioni varie, non ho mai scritto. In particolare, l'approccio seguito dal libro è quello che io stesso ho seguito nell'organizzazione di vari corsi sui linguaggi di programmazione che ho insegnato, in diverse fasi e sotto diverse etichette, per quasi trent'anni.

L'approccio, schematizzato in due parole, è quello di introdurre i concetti generali (sia dei meccanismi linguistici che delle corrispondenti strutture di implementazione) in modo indipendente da linguaggi specifici e solo in un secondo tempo collocare nello schema i "linguaggi veri". Questo è l'unico approccio che permette di mettere in evidenza le similitudini tra linguaggi (ed anche tra paradigmi) apparentemente molto diversi. Allo stesso tempo si rende così più facile il compito di imparare linguaggi diversi. Nella mia esperienza di docente, anche dopo molti anni gli ex-studenti si ricordano i principi appresi nel corso e continuano ad apprezzarne l'approccio, che ha loro permesso di adattarsi alle evoluzioni delle tecnologie senza grandi difficoltà.

Il testo di Gabbrielli e Martini ha come riferimento prevalente un corso della laurea triennale in Informatica. Per questa ragione non ha prerequisiti complessi e affronta l'argomento trovando un perfetto equilibrio tra rigore e semplicità. Particolarmente apprezzabile e riuscito è lo sforzo di mettere in luce il collegamento con alcuni "pezzi di teoria" importanti (come i linguaggi formali, la calcolabilità, la semantica), che il libro giustamente richiama, anche perché in molti corsi di laurea triennali questi argomenti non vengono più trattati.

Prima di concludere, mi permetto un accenno polemico al fatto che purtroppo in alcuni corsi di laurea triennali (tra questi, quello in cui io insegno) sono stati eliminati dai corsi fondamentali oltre ai tradizionali contenuti di informatica teorica anche i contenuti di linguaggi, considerati anch'essi troppo teorici per un corso professionalizzante orientato alle nuove tecnologie. Gli studenti conoscono (o credono di conoscere) alla perfezione un unico linguaggio, magari Java, con tutte le cose "che servono", incluse le librerie. Ma non sapranno mai descrivere il linguaggio che usano in termini di concetti generali, perché nulla sanno di metodi per il passaggio di parametri, di regole di scoping e di polimorfismo. Almeno ora avranno la possibilità di imparare queste cose su un ottimo testo scritto in italiano.

Giorgio Levi

| << |  <  |  >  | >> |

Pagina xv

Introduzione


                Facilius per partes in cognitionem totius adducimur.
                                             (Seneca, Epist., 89, 1)



L'apprendimento di un linguaggio di programmazione costituisce per molti studenti il rito d'iniziazione all'informatica. Si tratta di un passaggio importante, ma che presto si rivela insufficiente: tra gli attrezzi del mestiere ci sono molti linguaggi ed una competenza importante del bravo informatico è quella di saper passare da un linguaggio all'altro (e di apprenderne di nuovi) con naturalezza e velocità.

Questa competenza non la si acquisisce soltanto imparando ex novo molti linguaggi diversi. Come le lingue naturali, anche i linguaggi di programmazione hanno tra loro somiglianze, analogie, fenomeni di importazione dall'uno all'altro, genealogie che ne influenzano le caratteristiche. Se è impossibile imparare bene decine di linguaggi di programmazione, è possibile conoscere a fondo i meccanismi che ispirano e guidano il progetto e l'implementazione di centinaia di linguaggi diversi. Questa conoscenza delle "parti" facilita la comprensione del "tutto" costituito da un nuovo linguaggio, fornendo dunque una competenza metodologica fondamentale nella vita professionale dell'informatico, in quanto consente di anticipare l'innovazione e di sopravvivere all'obsolescenza delle tecnologie.

per questi motivi che un corso sugli aspetti generali dei linguaggi di programmazione è, in tutto il mondo, un passaggio chiave della formazione avanzata (universitaria o professionale) di un informatico. Relativamente ai linguaggi di programmazione, le competenze fondamentali che un informatico deve possedere sono almeno di quattro tipi:

gli aspetti propriamente linguistici;

come i costrutti linguistici possono essere implementati ed il relativo costo;

gli aspetti architetturali che influenzano l'implementazione;

le tecniche di traduzione (compilazione).

raro che un singolo corso possa affrontare tutti e quattro questi aspetti. In particolare, la descrizione degli aspetti architetturali e delle tecniche di compilazione costituiscono ciascuno un argomento sufficientemente complesso ed elaborato da meritare una trattazione separata. Gli altri due aspetti sono il contenuto primario di un corso generale sui linguaggi di programmazione e costituiscono il contenuto principale di questo testo.

La letteratura anglosassone, a differenza di quella in lingua italiana, è ricca di testi che affrontano questi argomenti, alcuni carichi di storia e sui quali si sono formate generazioni di studenti. Tutti questi testi, tuttavia, hanno in mente un lettore avanzato che conosca già diversi linguaggi di programmazione, che abbia una competenza non superficiale dei meccanismi di base fondamentali, che non si spaventi davanti a frammenti di codice espressi in linguaggi a lui ignoti (perché riesce a comprenderli per analogia o per differenza da quelli che già conosce). Si tratta di testi, dunque, che potremmo chiamare di "linguaggi comparati": estesi, approfonditi, stimolanti. Ma troppo estesi e approfonditi (in una parola: difficili) per lo studente che inizia il suo cammino con un solo (o al massimo due) linguaggi di programmazione e che deve ancora approfondire i concetti di base.

Questo testo intende colmare questa lacuna. Gli esperti vedranno che l'indice delle materie ripercorre in larga misura i temi classici. Ma questi stessi temi sono trattati in modo elementare, cercando di assumere come prerequisiti solo il minimo indispensabile e sforzandosi di non fare un catalogo delle opzioni possibili nei diversi linguaggi di programmazione esistenti. Il lettore di riferimento è quello che conosce (bene) un linguaggio (per esempio Pascal, C, C++, o Java); meglio se ha avuto anche una qualche esposizione ad un altro linguaggio o ad un altro paradigma. Si sono evitati riferimenti consistenti a linguaggi ormai desueti e gli esempi di codice sono solo raramente espressi in uno specifico linguaggio di programmazione: il testo usa con libertà una sorta di pseudolinguaggio (ispirato nella sua sintassi concreta a C e Java), cercando di descrivere così gli aspetti più rilevanti che uniscono i diversi linguaggi.

Di tanto in tanto un "riquadro" a capo pagina presenta un approfondimento, o il richiamo di una nozione di base, o qualche dettaglio specifico dei linguaggi più comuni (C, C++, Java 5.0; ML e LIsP per i linguaggi funzionali; PROLOG per i linguaggi logici). Il materiale dei riquadri può quasi sempre essere tranquillamente omesso in una prima lettura.

Tutti i capitoli presentano una breve serie di esercizi, intesi come banco di prova per la comprensione del materiale. Non vi sono esercizi davvero difficili o che richiedano più di una decina di minuti per esser risolti.

Il Capitolo 3 (Fondamenti) affronta temi che solitamente non sono trattati in un testo di linguaggi di programmazione. tuttavia naturale, discutendo di semantica statica e confrontando tra loro linguaggi, chiedersi quali siano i limiti dell'analisi statica dei programmi e se quello che si può fare in un linguaggio si possa fare anche in un altro. Invece che rimandare ad altri testi, vista la rilevanza sia culturale che pragmatica di queste questioni, abbiamo deciso di rispondere direttamente a queste domande. In modo informale, ma rigoroso, nel contesto di poche pagine viene presentata l'indecidibilità del problema della fermata e l'equivalenza dei linguaggi di programmazione quanto alle funzioni calcolabili. Questo permette di esporre lo studente, che non sempre ha nel suo curriculum un corso completo sui "fondamenti", ai risultati principali relativi alle limitazioni dei procedimenti di calcolo, che riteniamo fondamentali per la sua formazione.

Insieme ai principi, il testo introduce anche ai tre principali paradigmi di programmazione: quello orientato agli oggetti (un tema ormai obbligato della formazione dell'informatico), quello funzionale, quello logico. La necessità di realizzare un testo introduttivo e, insieme, di mantenerne l'estensione in un numero di pagine ragionevole, spiega l'esclusione di temi importanti, quali la concorrenza e i linguaggi di scripting, che costituiscono competenze importanti ma che difficilmente possono essere affrontati correttamente assieme agli aspetti di base.

| << |  <  |  >  | >> |

Pagina 287

10

Il paradigma orientato agli oggetti


Presenteremo in questo capitolo gli aspetti salienti dei linguaggi orientati agli oggetti, un paradigma che vede i suoi precursori in Simula (fine anni '60) e Smalltalk (anni '70) e che ha ottenuto enorme successo, anche commerciale, nei due decenni seguenti (C++ e Java sono solo i due linguaggi più noti tra i tanti che sono tutt'oggi in uso). "Orientato agli oggetti" è ormai una locuzione abusata, che troviamo applicata non solo ai linguaggi di programmazione, ma anche ai metodi di sviluppo del software, alle basi di dati, ai sistemi operativi ecc. Il nostro tentativo sarà quello di presentare gli aspetti linguistici che riguardano gli oggetti e il loro uso, facendo qualche sporadico accenno alle tecniche di progetto orientate agli oggetti, per le quali, tuttavia, non possiamo che rimandare alla (sterminata) bibliografia.

Anche dopo aver così ristretto il campo, ci sono molti modi di avvicinarsi ai concetti che ci interessano. Noi seguiremo quello che crediamo il più semplice: presenteremo gli oggetti come un modo per ottenere astrazione sui dati, in modo flessibile ed estendibile. Inizieremo perciò il nostro studio mostrando alcune limitazioni delle tecniche che abbiamo introdotto nel Capitolo 9: questi limiti ci suggeriranno alcuni concetti che, di fatto, costituiscono i cardini di un linguaggio orientato agli oggetti. Dopo aver approfondito questi aspetti caratteristici, studieremo alcune estensioni delle soluzioni linguistiche oggi disponibili nei linguaggi commerciali, con riferimento in particolare alla nozione di sottotipo, polimorfismo e genericità.

Secondo lo stile che abbiamo mantenuto in tutto il testo, cercheremo di rimanere indipendenti da uno specifico linguaggio di programmazione, anche se questo non sarà sempre possibile. Il linguaggio al quale maggiormente ci ispireremo sarà Java, per la coerenza del suo progetto, che ci permette di discutere dei concetti (e non dei dettagli linguistici) in modo più chiaro e sintetico di altri linguaggi.

| << |  <  |  >  | >> |

Pagina 343

11

Il paradigma funzionale


Presentiamo in questo capitolo gli aspetti principali del paradigma di programmazione funzionale, nel quale la computazione avviene per riscrittura di funzioni e non per modifica dello stato. La caratteristica fondamentale dei linguaggi di questo paradigma, almeno nella loro versione "pura", è proprio quella di non possedere il concetto di memoria (e, dunque, di effetto collaterale): fissato un ambiente, un'espressione denota sempre lo stesso valore.

Discuteremo il paradigma puro nelle prime sezioni, evidenziandone gli aspetti fondamentali. I linguaggi di programmazione funzionale, tuttavia, immergono questi ingredienti "puri" in un contesto che aggiunge molti altri meccanismi, che passeremo in rassegna nel Paragrafo 11.3.

Accenneremo quindi alla macchina SECD, una macchina astratta per linguaggi funzionali di ordine superiore che costituisce il prototipo di molte implementazioni reali.

Saremo a questo punto nella posizione di discutere i motivi che rendono interessante il paradigma di programmazione funzionale, in rapporto agli ordinari linguaggi imperativi.

Conclude il capitolo un paragrafo più teorica che fornisce una succinta introduzione al lambda-calcolo, un sistema formale per la calcolabilità al quale tutti i linguaggi funzionali si ispirano e che ha costituito, sin dai tempi di ALGOL e LISP, un modello costante per il progetto dei linguaggi di programmazione.

| << |  <  |  >  | >> |

Pagina 377

12

Il paradigma logico


In questo capitolo analizziamo l'altro paradigma che, insieme a quello funzionale, permette la programmazione dichiarativa: il paradigma logico che include sia linguaggi teorici sia linguaggi effettivamente implementati ed usati, dei quali il più noto è sicuramente PROLOG. Anche se vi sono differenze abbastanza rilevanti di ordine pragmatico e, per certi versi, teorico, fra i vari linguaggi logici, questi condividono l'idea di intendere la computazione come deduzione logica.

In questo capitolo vedremo dunque queste nozioni, cercando di limitare la parte teorica, adottando anche per questo paradigma l'approccio che ha caratterizzato tutto il testo. Non intendiamo quindi insegnare a programmare in PROLOG, anche se faremo vedere vari esempi di programmi reali, ma intendiamo fornire la basi per poter comprendere e, in breve tempo, padroneggiare, questo ed altri linguaggi logici.


12.1 Deduzione come computazione

Un noto slogan, dovuto a R. Kowalski, così sintetizza la nozione alla base dell'attività di programmazione: Algoritmo = Logica + Controllo. Secondo questa "equazione" la specifica di un algoritmo, e quindi la sua formulazione in termini di un linguaggio di programmazione, può essere separata in due parti. Da un lato si specifica la logica della soluzione, ossia si definisce "cosa" debba essere fatto. Dall'altro invece si specificano gli aspetti relativi al controllo, e quindi si chiarisce "come" si deve arrivare alla soluzione desiderata. Il programmatore che usi un tradizionale linguaggio imperativo deve tener contro di entrambe queste componenti, usando i meccanismi che abbiamo diffusamente analizzato nei capitoli precedenti. La programmazione logica, invece, fu definita originariamente con l'idea di separare nettamente questi due aspetti. Al programmatore è richiesta solo, almeno in linea di principio, la specifica della parte logica. Tutto quanto riguarda il controllo è demandato alla macchina astratta: usando un meccanismo computazionale basato su una particolare regola di deduzione (la risoluzione), essa ricerca nello spazio delle possibili soluzioni quella specificata dalla "logica", definendo in questo modo la sequenza di operazioni necessarie ad arrivare al risultato finale.

Le basi di questa visione della computazione come deduzione logica possono essere ricondotte ai lavori di K. Gdel e J. Herbrand negli anni '30. In particolare, Herbrand anticipò, anche se in modo non completamente formale, alcune idee relative al processo di unificazione che, come vedremo, costituisce il meccanismo computazionale di base dei linguaggi logici.

Bisognerà attendere fino agli '60 per una definizione formale di tale processo (ad opera di A. Robinson) e solo dieci anni ancora più tardi (nei primi anni '70) ci rese conto che la dimostrazione automatica di formule di un tipo particolare poteva essere interpretata come un meccanismo computazionale. Nascevano così i primi linguaggi di programmazione del paradigma logico, tra cui PROLOG (il nome è un acronimo per PROgramming in LOGic, per ulteriori informazioni sulla storia del linguaggio si veda il Paragrafo 13.4).

Oggi ci sono molte versioni implementate di PROLOG ed esistono vari altri linguaggi logici reali (di particolare interesse, per le applicazioni, sono quelli con vincoli). Tutti questi linguaggi, PROLOG per primo, per motivi di efficienza permettono l'uso di costrutti che riguardano anche aspetti di specifica del controllo. Questi costrutti, non avendo una diretta interpretazione logica, rendono molto più complicata la semantica del programma e fanno perdere parte della natura puramente dichiarativa del paradigma logico. Nonostante ciò, anche in presenza di questi aspetti "impuri", si tratta pur sempre di linguaggi di programmazione che richiedono al programmatore poco più che formulare (o dichiarare) la specifica del problema da risolvere. In alcuni casi i programmi risultanti sono davvero sorprendenti per semplicità, brevità e chiarezza, come vedremo nel prossimo paragrafo.

| << |  <  |