Teoria języków programowania

Teoria języków programowania (ang. programming language theory, PLT) – dziedzina informatyki teoretycznej zajmująca się analizą, charakteryzacją, klasyfikacją, projektowaniem i wdrażaniem języków programowania. Ważniejszymi obszarami PLT są semantyki formalne (ang. formal semantics), teoria typów (ang. type theory), metaprogramowanie, konstrukcja kompilatorów. PLT jest związana także z językoznawstwem, matematyką i kognitywistyką.

Historia

Historia teorii języków programowania poprzedza rozwój samych języków programowania. Rachunek lambda, opracowany przez Alonzo Church i Stephena Cole Kleene w latach 30. XX wieku, jest uważany przez niektórych za pierwszy na świecie język programowania, mimo że miał on służyć jedynie modelowaniu obliczeń matematycznych, a nie programistom do opisywania algorytmów w systemach informatycznych.

Pierwszym wymyślonym językiem programowania był Plankalkül, zaprojektowany przez niemieckiego pioniera informatyki Konrada Zuse w latach 40. XX wieku, ale znany publicznie dopiero w 1972 r. (a wdrożony w 1998 r.). Natomiast pierwszym znanym i praktycznie powszechnie stosowanym wysokopoziomowym językiem programowania był Fortran, opracowywany w latach 1954–1957 przez zespół badaczy IBM pod przewodnictwem Johna Backusa. Użyteczność Fortranu doprowadziła do powołania komitetu naukowego w celu opracowania „uniwersalnego” języka komputerowego. Rezultatem ich wysiłków był ALGOL 58. Osobno John McCarthy z MIT opracował język programowania Lisp (oparty na rachunku lambda), pierwszy język mający pochodzenie akademickie, który znalazł zastosowanie praktyczne. Języki programowania stały się aktywnym tematem badań naukowych od lat 60. XX w. Kluczowe wydarzenia w historii teorii języków programowania:

Lata 50. XX w.

• Noam Chomsky rozwinął hierarchię Chomsky’ego w dziedzinie językoznawstwa;

Lata 60. XX w.

• Ole-Johan Dahl i Kristen Nygaard opracowali język Simula; pierwszy przykład obiektowego języka programowania; Simula wprowadziła również pojęcie współprogramów.
• W 1964 r. Peter Landin jako pierwszy zastosował rachunek lambda Church’a do modelowania języków programowania. Wprowadził maszynę SECD, która „interpretuje” wyrażenia lambda.
• W 1965 r. Landin wprowadził konstrukcję programistyczną operator J (ang. J operator).
• W 1966 roku Landin wprowadził ISWIM, abstrakcyjny język programowania w artykule The Next 700 Programming Languages. Miał on wpływ na ewolucję projektowania przyszłych języków, która doprowadziła do powstania języka Haskell.
• W 1966 r. Corrado Böhm wprowadził język programowania CUCH (Curry-Church).
• W 1967 r. Christopher Strachey opublikował wpływowe notatki z wykładu Podstawowe pojęcia w językach programowania, wprowadzając terminologię R-wartości, L-wartości, parametryczny polimorfizm i polimorfizm ad hoc.
• W 1969 r. J. Roger Hindley opublikował Główny schemat typów obiektu w logice kombinatorycznej, później uogólniony na algorytm wnioskowania typu Hindley–Milner.
• W 1969 r. Tony Hoare wprowadził Logikę Hoare’a, formę semantyki aksomatycznej.
• W 1969 r. William Alvin Howard zauważył, że system dowodowy „wysokiego poziomu”, zwany dedukcją naturalną, można bezpośrednio interpretować w jego intuicyjnej wersji jako typowy wariant modelu obliczeniowego zwanego rachunkiem lambda. To stało się znane jako izomorfizm Curry’ego-Howarda.

Lata 70. XX w.

• W 1970 r. Dana Scott opublikował pracę na temat semantyki denotacyjnej.
• W 1972 r. opracowano programowanie logiczne i Prolog, umożliwiając tym samym wyrażanie programów komputerowych jako logiki matematycznej.
• Zespół naukowców z Xerox PARC, kierowany przez Alana Kaya, opracował Smalltalk, język obiektowy znany z innowacyjnego środowiska programistycznego.
• W 1974 r. John C. Reynolds odkrył System F, który jak się okazało został odkryty niezależnie 3 lata wcześnniej przez logika Jean-Yves Girarda.
• Od 1975 r. Gerald Jay Sussman i Guy Steele opracowują język programowania Scheme, dialekt Lisp obejmujący zasięg leksykalny, ujednoliconą przestrzeń nazw oraz elementy z modelu aktorskiego (ang. actor model), w tym kontynuacje (ang. continuation) pierwszej klasy.
• Backus podczas wykładu ACM Turing Award w 1977 r. skrytykował stan języków przemysłowych i zaproponował nową klasę języków programowania, znaną obecnie jako języki programowania na poziomie funkcji (ang. function-level programming).
• W 1977 r. Gordon Plotkin wprowadził programowalne funkcje obliczeniowe, abstrakcyjny język funkcjonalny.
• W 1978 r. Robin Milner wprowadził algorytm wnioskowania typu Hindley – Milner dla języka programowania ML. Teoria typów została zastosowana jako dyscyplina dla języków programowania, co doprowadziło do rozwoju teorii typów na przestrzeni lat.

Lata 80. XX w.

• W 1981 r. Gordon Plotkin opublikował artykuł na temat strukturalnej semantyki operacyjnej.
• W 1988 r. Gilles Kahn opublikował artykuł na temat semantyki naturalnej.
• Wprowadzono i rozwijano rachunek procesowy do modelowania systemów współbieżnych, m.in. rachunek systemów komunikacyjnych Robina Milner’a, rachunek communicating sequential processes Tonego Hoare oraz model aktora Carla Hewitta.
• W 1985 r. język programowania Miranda wzbudził u naukowców zainteresowanie leniwie-szacowanymi czystymi funkcyjnymi językami programowania. Utworzono komitet w celu zdefiniowania otwartego standardu, którego skutkiem było wydanie standardu Haskell 1.0 w 1990 roku.
• Bertrand Meyer stworzył metodologię programowania kontraktowego i włączył ją do Eiffel.

Lata 90. XX w.

• Gregor Kiczales, Jim Des Rivieres i Daniel G. Bobrow opublikowali książkę The Art of the Metaobject Protocol.
• Eugenio Moggi i Philip Wadler wprowadzili monady w paradygmacie funkcyjnym do strukturyzacji programów.

Główne obszary

Można wyróżnić kilka kierunków badań, które albo leżą w obrębie teorii języka programowania, albo które mają na nią głęboki wpływ. Nakładające się na siebie obszary obejmują:

• semantyki formalne
• teoria typów
• analiza i transformacja programów
• analiza porównawcza języków programowania
• programowanie uogólnione i metaprogramowanie
• języki dziedzinowe
• systemy czasu wykonywalnego (ang. runtime system)

Znane czasopisma i konferencje naukowe

• ACM Transactions on Programming Languages and Systems (TOPLAS);
• Journal of Functional Programming (JFP);
• Journal of Functional and Logic Programming;
• Higher-Order and Symbolic Computation;
• Symposium on Principles of Programming Languages (POPL);
• Programming Language Design and Implementation (PLDI);
• International Conference on Functional Programming (ICFP);
• International Conference on Object Oriented Programming, Systems, Languages and Applications (OOPSLA);
• International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).