Teoria dei linguaggi di programmazione

La lettera greca λ (lambda minuscola) è un simbolo non ufficiale dell'ambito di ricerca sui linguaggi di programmazione, proveniente dal lambda calcolo di Church, un modello teorico introdotto negli anni '30 e molto usato dai ricercatori. Decora la copertina di testi classici come Structure and Interpretation of Computer Programs e appare nel titolo dei cosiddetti Lambda Papers, scritti da Gerald Jay Sussman e Guy Steele, sviluppatori di Scheme.

La teoria dei linguaggi di programmazione è un settore della scienza informatica che si occupa della progettazione, dell'implementazione, dell'analisi, della caratterizzazione e della classificazione dei linguaggi di programmazione e dei loro componenti. Pur essendo propriamente una branca dell'informatica, dove è piuttosto nota, essa è in rapporto d'influenza reciproca con la matematica, l'ingegneria del software e linguistica. La ricerca nel campo è attiva e produce risultati pubblicati sia nelle diverse riviste scientifiche ad essa dedicate, sia in altre pubblicazioni più generali di informatica e ingegneria.

Storia

La storia della teoria dei linguaggi di programmazione precede, per certi versi, lo sviluppo degli stessi linguaggi. Alcuni ritengono infatti che il lambda calcolo, creato da Alonzo Church e Stephen Cole Kleene negli anni 1930 come modello di calcolo in senso astratto, e non come un mezzo per descrivere algoritmi ad un calcolatore, costituisca in realtà il primo linguaggio di programmazione della storia. Diversi linguaggi di programmazione funzionali moderni vengono appunto descritti come un «sottile rivestimento» al lambda calcolo o essere spiegati attraverso di esso.

Il primo linguaggio di programmazione mai inventato è il Plankalkül, progettato da Konrad Zuse negli anni '40, ma reso pubblico soltanto nel 1972 e implementato per la prima volta addirittura nel 1998. Il primo linguaggio che abbia avuto ampio riconoscimento e successo è invece il Fortran, che venne sviluppato tra il 1954 e il 1957 da una squadra di ricercatori dell'IBM guidata da John Backus. Il successo di Fortran portò alla formazione di un comitato di scienziati avente l'obiettivo di creare un linguaggio per calcolatori «universale» e che produsse l'ALGOL 58. Presso il MIT invece, John McCarthy sviluppò indipendentemente e ispirato dal lambda calcolo il linguaggio Lisp, il primo linguaggio accademico di successo. A partire da tali contributi iniziali, dagli anni '60 in poi i linguaggi di programmazione diventarono un tema di ricerca attivo.

Si riportano di seguito alcune tappe chiave successive nella storia della teoria dei linguaggi di programmazione.

Anni '50

• Noam Chomsky formalizza la gerarchia che porta il suo nome nel campo della linguistica, una scoperta che influenzerà direttamente non solo la teoria dei linguaggi di programmazione, ma anche altri branche della scienza informatica.

Anni '60

• Viene sviluppato il linguaggio Simula. Opera di Ole-Johan Dahl e Kristen Nygaard, è il primo linguaggio di programmazione orientato agli oggetti e primo ad avere la nozione di coroutine (tipo particolare di sotto-programma che incapsula uno stato e consente invocazione a partire da diversi punti).
• Nel 1964 Peter Landin, il primo a capire che il lambda calcolo di Church può essere utilizzato per progettare linguaggi di programmazione, introduce la macchina SECD che interpreta lambda termini.
• Nel 1965 Landin definisce l'operatore J, archetipo del concetto di continuazione.
• Nel 1966, nell'articolo The Next 700 Programming Languages ("I prossimi 700 linguaggi di programmazione"), Landin presenta ISWIM, un linguaggio di programmazione astratto che influenzerà lo sviluppo dei linguaggi che culmineranno con Haskell.
• Nel 1966 Corrado Böhm definisce il linguaggio di programmazione CUCH (dai cognomi di Haskell Curry e Alonzo Church).
• Nel 1967 Christopher Strachey pubblica la famosa serie di dispense Fundamental Concepts in Programming Languages ("fondamenti di linguaggi di programmazione") che introduce la terminologie degli L- ed R-valori, il polimorfismo parametrico e ad-hoc.
• Nel 1969 J. Roger Hindley pubblica The Principal Type-Scheme of an Object in Combinatory Logic ("Lo schema del tipo principale di un oggetto della logica combinatoria"), poi generalizzato nell'algoritmo di inferenza dei tipi Hindley–Milner
• Nel 1969 Tony Hoare presenta la logica che porta il suo nome, una forma di semantica di tipo assiomatico.
• Nel 1969, William Alvin Howard nota che la deduzione naturale, un sistema di calcolo dimostrativo, può essere direttamente interpretato, nella sua versione intuizionista, come una variante tipata del lambda calcolo. Tale corrispondenza prenderà il nome di corrispondenza di Curry–Howard.

Anni '70

• Nel 1970 Dana Scott pubblica la sua opera sulla semantica denotazionale.
• Nel 1972 vengono sviluppati la programmazione logica e il linguaggio Prolog permettendo così di esprimere programmi come logica matematica.
• Jean-Yves Girard nel 1971 e John C. Reynolds nel 1974 definiscono indipendentemente il sistema F.
• Nel 1975 Sussman e Steele creano il linguaggio Scheme, un dialetto di Lisp dotato di visibilità lessicale, di uno spazio di nomi unificato e avente tratti del modello ad attori, come le continuazioni esplicite.
• John Backus, nella sua lezione del 1977 di ringraziamento per il premio Turing di cui è insignito, critica duramente la situazione dei linguaggi industriali e propone una nuova categoria di linguaggi di programmazione, i linguaggi programmazione a livello funzione.
• Nel 1977 Gordon Plotkin presenta un linguaggio funzionale tipato astratto, Programming Computable Functions (PCF).
• Nel 1978 Robin Milner pubblica l'algoritmo d'inferenza di tipi Hindley–Milner per il linguaggio di programmazione ML. La teoria dei tipi diventa così una disciplina applicata ai linguaggi di programmazione, che negli anni a seguire gli permetterà enormi progressi.

Anni '80

• Nel 1981 Gordon Plotkin pubblica il suo articolo sulla semantica operazionale strutturata.
• Nel 1988 Gilles Kahn pubblica il suo articolo sulla semantica naturale.
• Una squadra di scienziati alla Xerox PARC guidata da Alan Kay sviluppa Smalltalk, un linguaggio orientato agli oggetti noto per il sistema di sviluppo innovativo.
• Emergono i calcoli di processo, come il Calculus of Communicating Systems di Robin Milner, il modello Communicating sequential processes di C. A. R. Hoare e diversi simili modelli di concorrenza, come il modello ad attori di Carl Hewitt.
• Nel 1985 la pubblicazione di Miranda accende l'interesse accademico per i linguaggi funzionali puri con valutazione pigra. Viene formato un comitato per la definizione di uno standard aperto che culmina con la definizione di Haskell 1.0 nel 1990.
• Bertrand Meyer definisce la metodologia progettazione per contratti incorporandola nel linguaggio Eiffel.

Anni '90

• Gregor Kiczales, Jim Des Rivieres e Daniel G. Bobrow pubblicano il libro The Art of the Metaobject Protocol.
• Eugenio Moggi e Philip Wadler introducono il concetto di monade per strutturare programmi scritti linguaggi funzionali.

Sotto-discipline e campi di ricerca correlati

Numerosi sono gli ambiti di studio che influenzano profondamente o sono influenzati dalla teoria dei linguaggi di programmazione, molti dei quali con vaste aree di sovrapposizione. Questa disciplina, infatti, si avvale di diverse altre branche della matematica, come la teoria della calcolabilità, quella delle categorie e quella degli insiemi.

Semantica formale

La semantica formale è la specifica formale, appunto, del comportamento dei programmi e dei linguaggi stessi. I tre approcci più comuni per descrivere il significato di un programma sono quello denotazionale, quello operazionale e quello assiomatico.

Teoria dei tipi

La teoria dei tipi è lo studio dei sistemi di tipo, un metodo sintattico e trattabile da un calcolatore per dimostrare l'assenza di certi comportamenti dei programmi tramite la classificazione dei costrutti secondo i valori che essi calcolano. Molti linguaggi di programmazione sono distinguibili dalle caratteristiche dei loro sistemi di tipi.

Analisi e trasformazione di programmi

L'analisi di programmi consiste nel problema di determinazione, a partire da un esame sintattico, di certe caratteristiche chiave di un programma, come l'assenza di certe classi di errori. La trasformazione di programmi si occupa invece dei processi di manipolazione di un programma da una forma, o linguaggio, ad un'altra.

Analisi comparata di linguaggi di programmazione

L'analisi comparata dei linguaggi di programmazione mira a classificare questi ultimi secondo diverse tipologie a seconda delle loro caratteristiche. Una nota macro-categorizzazione ad esempio, è quella che distingue i linguaggi secondo il paradigma di programmazione.

Metaprogrammazione e programmazione generica

La Metaprogrammazione è la generazione di programmi di ordine superiore la cui esecuzione produce in output dei programmi, eventualmente espressi in un altro linguaggio o in un sottoinsieme di quello di partenza.

Linguaggi di dominio specifico

I linguaggi di dominio specifico sono linguaggi concepiti per risolvere in maniera efficiente certi problemi propri di un ambito di applicazione particolare.

Costruzione di compilatori

La teoria dei compilatori si occupa della costruzione di compilatori, ovvero traduttori di programmi da un linguaggio sorgente ad uno obiettivo. Il processo di compilazione è tradizionalmente distinto in una fase di analisi sintattica, cioè la scansione e il parsing, una fase di analisi semantica, che determina cosa il programma debba fare, una fase di ottimizzazione, volta a migliorare le prestazioni del programma rispetto a certe metriche (p. es. il tempo di esecuzione o l'occupazione di memoria, e una fase finale di generazione del codice, che restituisce in output un programma equivalente a quello ricevuto in input (p.es. nel insieme di istruzioni di una CPU).

Sistemi a tempo d'esecuzione

sistemi a tempo d'esecuzione sono sia gli ambienti di esecuzione dei linguaggi di programmazione, sia i loro componenti, come le macchine virtuali, i garbage collector o le interfacce di funzioni esterne.

Riviste, pubblicazioni e conferenze

Il luogo primario dove le ricerche sui linguaggi di programmazione vengono presentate sono conferenze, come: il Symposium on Principles of Programming Languages (POPL), la Conference on Programming Language Design and Implementation (PLDI), la International Conference on Functional Programming (ICFP), la International Conference on Object Oriented Programming, Systems, Languages and Applications (OOPSLA).

Tra le riviste notevoli, invece, si trovano invece: gli ACM Transactions on Programming Languages and Systems (TOPLAS), il Journal of Functional Programming (JFP), il Journal of Functional and Logic Programming, e Higher-Order and Symbolic Computation.

Bibliografia

• Abadi, Martín and Cardelli, Luca. A Theory of Objects. Springer-Verlag.
• Michael J. C. Gordon. Programming Language Theory and Its Implementation. Prentice Hall.
• Gunter, Carl and Mitchell, John C. (eds.). Theoretical Aspects of Object Oriented Programming Languages: Types, Semantics, and Language Design. MIT Press.
• Harper, Robert. Practical Foundations for Programming Languages. Draft version.
• Knuth, Donald E. (2003). Selected Papers on Computer Languages Archiviato il 31 maggio 2017 in Internet Archive.. Stanford, California: Center for the Study of Language and Information.
• Mitchell, John C. Foundations for Programming Languages.
• Mitchell, John C. Introduction to Programming Language Theory.
• O'Hearn, Peter. W. and Tennent, Robert. D. (1997). Algol-like Languages. Progress in Theoretical Computer Science. Birkhauser, Boston.
• Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press.
• Pierce, Benjamin C. Advanced Topics in Types and Programming Languages.
• Pierce, Benjamin C. et al. (2010). Software Foundations.

Voci correlate

• Cronologia dei linguaggi di programmazione
• Linguaggio di programmazione ad altissimo livello

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla teoria dei linguaggi di programmazione

Collegamenti esterni

• (EN) Theoretical programming, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• Lambda the Ultimate, weblog comunitario che ospita discussioni professionali e depositi di documenti sulla teoria dei linguaggi di programmazione.
• Great Works in Programming Languages. Collected by Benjamin C. Pierce (University of Pennsylvania).
• Classic Papers in Programming Languages and Logic. Raccolti da Karl Crary (Carnegie Mellon University).
• Programming Language Research. Directory di Mark Leone.
• Programming Language Theory Texts Online. Presso la Utrecht University.
• λ-Calculus: Then & Now di Dana S. Scott in occasione delle celebrazioni del centenario di Turing
• Grand Challenges in Programming Languages. Sessione di POPL 2009.