Paradygmaty programowania/Wykład 1: Co to jest paradygmat programowania?
Wstęp
Zobacz biografię
Powinniśmy zapewne zacząć od wyjaśnienia, o czym będzie mowa w niniejszym wykładzie. W takim razie warto przyjrzeć się znaczeniu słowa „paradygmat”, bezlitośnie nadużywanemu przez filozofów, lingwistów i informatyków — by wymienić tylko paru sprawców zamieszania. Otóż, jak podaje Słownik języka polskiego PWN, paradygmat to «przyjęty sposób widzenia rzeczywistości w danej dziedzinie, doktrynie itp.» lub «zespół form fleksyjnych (deklinacyjnych lub koniugacyjnych), właściwy danemu typowi wyrazów; wzorzec, model deklinacyjny lub koniugacyjny». Jak to się ma do programowania? Trudno orzec; sięgnijmy jeszcze do greckich korzeni słowa. Greckie παράδειγμα oznacza wzorzec bądź przykład. Czyżby chodziło więc o typowy, wzorcowy sposób pisania programów? Niezupełnie; chodzi raczej o zbiór mechanizmów, jakich programista używa, pisząc program, i o to, jak ów program jest następnie wykonywany przez komputer. Zatem paradygmat programowania to ogół oczekiwań programisty wobec języka programowania i komputera, na którym będzie działał program. Przyjrzyjmy się paru przykładom. Przykłady te, obejmujące najbardziej powszechne paradygmaty programowania, będą zarazem stanowiły kanwę całego wykładu.
 Zobacz biografię |
 Zobacz biografię |
Przykład pierwszy: programowanie imperatywne
Programowanie imperatywne to najbardziej pierwotny sposób programowania, w którym program postrzegany jest jako ciąg poleceń dla komputera
- Ściślej, obliczenia rozumiemy tu jako sekwencję poleceń zmieniających krok po kroku stan maszyny, aż do uzyskania oczekiwanego wyniku.
- Stan maszyny należy z kolei rozumieć jako zawartość całej pamięci oraz rejestrów i znaczników procesora.
- Ten sposób patrzenia na programy związany jest ściśle z budową sprzętu komputerowego o architekturze von Neumanna, w którym poszczególne instrukcje (w kodzie maszynowym) to właśnie polecenia zmieniające ów globalny stan.
- Języki wysokiego poziomu — takie jak Fortran, Algol, Pascal, Ada lub C — posługują się pewnymi abstrakcjami, ale wciąż odpowiadają paradygmatowi programowania imperatywnego.
- Przykładowo, instrukcje podstawienia działają na danych pobranych z pamięci i umieszczają wynik w tejże pamięci, zaś abstrakcją komórek pamięci są zmienne.
Przykładowy program w języku imperatywnym
program pierwszy;
var i, n, s: integer;
begin
read(n);
s := 1;
for i := 2 to n do
s := s * i;
write(s)
end.
Przykład drugi: programowanie obiektowe
W programowaniu obiektowym program to zbiór porozumiewających się ze sobą obiektów, czyli jednostek zawierających pewne dane i umiejących wykonywać na nich pewne operacje
- Ważną cechą jest tu powiązanie danych (czyli stanu) z operacjami na nich (czyli poleceniami) w całość, stanowiącą odrębną jednostkę — obiekt.
- Cechą nie mniej ważną jest mechanizm dziedziczenia, czyli możliwość definiowania nowych, bardziej złożonych obiektów, na bazie obiektów już istniejących.
Zwolennicy programowania obiektowego uważają, że ten paradygmat dobrze odzwierciedla sposób, w jaki ludzie myślą o świecie
- Nawet jeśli pogląd ten uznamy za przejaw pewnej egzaltacji, to niewątpliwie programowanie obiektowe zdobyło ogromną popularność i wypada je uznać za paradygmat obecnie dominujący.
Przykładowy program(ik) w języku obiektowym
public class Hello {
public static void main(String[] args) {
System.out.println("Hello, I am James B.");
}
}
Przykład trzeci: programowanie funkcyjne
Tutaj program to po prostu złożona funkcja (w sensie matematycznym), która otrzymawszy dane wejściowe wylicza pewien wynik
- Zasadniczą różnicą w stosunku do poprzednich paradygmatów jest brak stanu maszyny: nie ma zmiennych, a co za tym idzie nie ma żadnych efektów ubocznych.
- Nie ma też imperatywnych z natury, tradycyjnie rozumianych pętli (te wymagają np. zmiennych do sterowania ich przebiegiem).
- Konstruowanie programów to składanie funkcji, zazwyczaj z istotnym wykorzystaniem rekurencji. Charakterystyczne jest również definiowanie funkcji wyższego rzędu, czyli takich, dla których argumentami i których wynikami mogą być funkcje (a nie tylko „proste” dane jak liczby lub napisy).
Przykładowy program (definicja funkcji) w języku funkcyjnym
(DEFINE (suma m n)
(IF (> m n)
0
(+ m (suma (+ m 1) n))
)
)
Przykład czwarty: programowanie w logice (programowanie logiczne)
Na program składa się zbiór zależności (przesłanki) i pewne stwierdzenie (cel)
- Wykonanie programu to próba udowodnienia celu w oparciu o podane przesłanki.
- Obliczenia wykonywane są niejako „przy okazji” dowodzenia celu.
- Podobnie jak w programowaniu funkcyjnym, nie „wydajemy rozkazów”, a jedynie opisujemy, co wiemy i co chcemy uzyskać.
Przykładowy program w języku logicznym
ojciec(jan, jerzy).
ojciec(jerzy, janusz).
ojciec(jerzy, józef).
dziadek(X, Z) :- ojciec(X, Y), ojciec(Y, Z).
?- dziadek(X, janusz).
Należy pamiętać, że istnieje wiele innych paradygmatów
- Często obejmują one tylko niektóre aspekty programowania, przeto można je uznać za podzbiór tych wspomnianych wcześniej.
- Dla przykładu, tzw. programowanie na poziomie wartości (w odróżnieniu do programowania „wyższego rzędu” — na poziomie funkcji) można traktować jako jedną z cech typowych dla programowania imperatywnego, choć jest również obecna np. w programowaniu obiektowym i funkcyjnym.
- Inny przykład to programowanie skalarne i macierzowe — rozróżnienie odnoszące się do tego, czy działamy na pojedynczych wartościach, czy na całych tablicach (macierzach).
- Paradygmat programowania proceduralnego będziemy omawiali jako istotny składnik programowania imperatywnego.
Istnieją paradygmaty przeciwstawne
- Przykładowo, programowanie sterowane zdarzeniami to przeciwieństwo klasycznego programowania z własnym wątkiem sterowania
- To wcale nie oznacza, że nie można łączyć obydwu paradygmatów w jednym programie; tak jest np. w typowych aplikacjach bazodanowych.
Konkretny język programowania ucieleśnia jeden lub więcej paradygmatów
- Fortran, Pascal i C to języki pozwalające stosować paradygmat programowania imperatywnego. Mówi się wręcz, że są to języki imperatywne.
- Java bądź C# to z kolei języki obiektowe, w których typowe programowanie imperatywne zostało mocno ograniczone.
- Natomiast C++ jest językiem zarówno obiektowym, jak i imperatywnym.
- Do pewnego stopnia można zresztą uznać, że programowanie imperatywne to szczególny, wynaturzony przypadek programowania obiektowego, gdzie wszystko rozgrywa się wewnątrz jednego „superobiektu”.
Wykład będzie dotyczył wspomnianych tu czterech paradygmatów
- Omówimy ich charakterystyczne elementy, przedstawiając przykłady z popularnych języków programowania.
- Będziemy też zajmowali się tym, jak owe mechanizmy są implementowane w realnych systemach komputerowych.
- Trzeba mieć na uwadze to, że — przynajmniej na razie — wszystkie komputery działają w oparciu o imperatywną architekturę von Neumanna.
- Każdy program, który chcemy uruchomić, musi być zatem najpierw przetłumaczony do postaci imperatywnej, czyli do ciągu rozkazów w języku wewnętrznym konkretnej maszyny.
- Mechanizmy z różnych paradygmatów wymagają niekiedy skomplikowanych metod, by odwzorować je w formie rozkazów zwykłego komputera; bardzo różna jest też ich efektywność.
Mamy nadzieję, że wykład pozwoli lepiej zrozumieć ważne elementy języków programowania, dając zarazem szersze spojrzenie na programowanie w ogóle
- To zaś powinno sprzyjać podejmowaniu lepszych decyzji co do wyboru języka i użycia jego mechanizmów, a w konsekwencji — tworzeniu lepszego oprogramowania...
Niniejszy wykład jest zintegrowany z ćwiczeniami
- Zadania służą nie tylko do sprawdzenia nabytej wiedzy i do przećwiczenia jej w praktyce.
- Duża część zadań — zwłaszcza tych trudniejszych, z gwiazdką — istotnie poszerza wiedzę z głównego nurtu wykładu.
- Oprócz tego dostępne są krótkie testy wyboru, których rolą jest przede wszystkim szybkie sprawdzenie opanowania materiału z wykładu.
Uwagi historyczne
Programowanie imperatywne jest tak stare jak komputery, a nawet starsze. Przepisy kuchenne czy sformalizowane procedury urzędowe można uznać za przejaw programowania imperatywnego. Oczywiście używane dzisiaj języki imperatywne są znacznie bogatsze niż te z czasów pionierskich. Niesłychanie ważnymi elementami, o które wzbogacił się ten paradygmat, są programowanie strukturalne (używanie prostych, dobrze zdefiniowanych struktur jak np. pętla while, a unikanie skoków) i proceduralne.
Programowanie funkcyjne sięga korzeniami okresu międzywojennego, kiedy to stworzony został rachunek lambda. Pierwsze funkcyjne języki programowania powstały w połowie lat pięćdziesiątych XX wieku. Przełom lat pięćdziesiątych i sześćdziesiątych to pierwsze propozycje programowania w logice, natomiast narodziny paradygmatu obiektowego przypadają na drugą połowę lat sześćdziesiątych. Za datę graniczną można przyjąć powstanie języka Simula 67.
Jak opisywać języki programowania?
Zakładamy, że Czytelnik posiada elementarną wiedzę o sposobach formalnego opisu języków programowania. Tutaj przypomnimy tylko pokrótce to, co będzie potrzebne na użytek niniejszego wykładu.
Składnia i semantyka
Składnia to zbiór reguł, mówiących jak wygląda poprawny program w danym języku, czyli np.:
- Jak tworzy się polecenia i wyrażenia.
- Jaką postać mają struktury sterowania (if, while, for itp.).
- Jak zapisuje się deklaracje.
Nota bene, jak widać z powyższego wyliczenia, jesteśmy tak przywiązani do języków imperatywnych i obiektowych, że chyba nie bardzo wyobrażamy sobie język bez poleceń, pętli while, zmiennych...
Semantyka to znaczenie wspomnianych wyżej form, czyli „co one robią”. Weźmy dla przykładu typową instrukcję warunkową
- Składnia może wyglądać tak: if "(" wyrażenie ")" instrukcja
- Semantyka jest następująca: sprawdź podane wyrażenie i jeśli jest prawdziwe, to wykonaj podaną instrukcję.
Powyższy opis semantyki instrukcji warunkowej jest co prawda niezbyt formalny, ale zupełnie zrozumiały
- W ogólności byłoby dobrze, gdyby semantykę dało się łatwo odgadnąć, patrząc na składnię języka.
- Dla prostych konstrukcji tak zazwyczaj bywa; bardziej skomplikowane twory są niestety mniej oczywiste.
- Stąd potrzebne są ścisłe metody opisu i składni, i semantyki.
Czym jest język i jak go opisać?
Język to zbiór napisów utworzonych ze znaków z ustalonego alfabetu
- Przyjmujemy, że mamy ustalony alfabet; nazwijmy go np. Σ.
- Alfabet to skończony i niepusty zbiór; jego elementy nazywamy symbolami, znakami lub literami.
- Zbiór wszystkich napisów, jakie można utworzyć z symboli alfabetu Σ, oznaczamy przez Σ*.
- Każdy podzbiór zbioru Σ* to pewien język.
- Rzecz jasna, nie każdy język jest interesujący.
Mówiąc o językach programowania, chcemy takie właśnie języki móc precyzyjnie opisywać
- Jeśli za alfabet Σ przyjmiemy np. zbiór znaków ASCII, to języki programowania są pewnymi szczególnymi podzbiorami zbioru Σ*.
- Są to oczywiście nieskończone podzbiory, których nie sposób opisać przez wyliczenie elementów; potrzebne są gramatyki.
- Nas szczególnie interesują dwa rodzaje gramatyk: regularne i bezkontekstowe.
- Te pierwsze doskonale nadają się do opisu prostych elementów języka — jednostek leksykalnych, czyli rzeczy takich, jak liczby i identyfikatory.
- Te drugie są przydatne do definiowania „większych” elementów składni: różnych rodzajów instrukcji, deklaracji czy wreszcie całego programu.
- Gramatyka pozwala opisać składnię języka, jednak nic (lub prawie nic) nie mówi o jego semantyce.
- Do opisu semantyki istnieją takie narzędzia, jak gramatyki atrybutowane oraz semantyki operacyjne, aksjomatyczne i denotacyjne.
Jak zatem my będziemy opisywać języki programowania lub ich elementy?
- Składnię języków będziemy opisywali za pomocą powszechnie znanej notacji BNF, odpowiadającej gramatykom bezkontekstowym.
- Semantykę rozmaitych konstrukcji będziemy na ogół opisywali w sposób „naiwny”, czyli zwyczajnie, po polsku.
- Ironią losu jest to, że stworzone przez informatyków-teoretyków narzędzia opisu semantyki nie są zbyt chętnie stosowane w praktyce inżynierii oprogramowania...
Notacja BNF (Backus Naur Form) jest powszechnie używana właśnie do opisu składni języków programowania. Stworzona została w trakcie prac nad językami Fortran i Algol na przełomie lat pięćdziesiątych i sześćdziesiątych XX wieku
- Definicja języka w notacji BNF to zbiór reguł.
- Poszczególne reguły mają postać <symbol> ::= <definicja symbolu>
- Sens takiej reguły jest następujący: symbol występujący po lewej stronie znaku ::= można zastąpić tym, co pojawia się po prawej stronie.
- Innymi słowy, stwierdzamy, że to, co stoi po lewej stronie, może wyglądać jak to, co stoi po prawej.
- Symbole pojawiające się po lewej stronie reguł zwane są symbolami nieterminalnymi.
- Symbole pojawiające się wyłącznie po prawej stronie to symbole terminalne.
- Generalnie symbole terminalne to symbole z alfabetu definiowanego języka, a zatem „docelowe”; symbole nieterminalne spełniają natomiast rolę pomocniczą przy jego definiowaniu.
- BNF to zatem w istocie sposób zapisywania produkcji gramatyk bezkontekstowych.
Często stosuje się dodatkowe symbole i konwencje, upraszczające zapis
- Pionowa kreska | oznacza alternatywne warianty reguły, np.
typ ::= char | int | float | double
- Nawiasy kwadratowe [...] oznaczają opcjonalną część reguły, np.
instr_warunkowa ::= if wyr_logiczne then instr [ else instr ]
- Nawiasy klamrowe {...} oznaczają fragment, który może być powtórzony dowolnie wiele razy (być może zero razy, czyli pominięty), np.
lista_arg ::= arg { "," arg }
- Zwykłych nawiasów okrągłych (...) używa się do grupowania alternatywnych fragmentów definicji, np.
liczba_ze_znakiem ::= ("+" | "–") liczba_bez_znaku
- Jednoznakowe symbole terminalne umieszcza się w cudzysłowie, dla odróżnienia ich od symboli samej notacji BNF.
- Symbole terminalne pisze się czcionką wytłuszczoną; nie jest wówczas konieczne pisanie nawiasów kątowych wokół symboli nieterminalnych.
Chcąc opisać powtarzające się elementy, możemy stworzyć definicję rekurencyjną lub wykorzystać nawiasy klamrowe
- Zdefiniujmy dla przykładu niepustą listę identyfikatorów, rozdzielonych przecinkami:
lista_identyfikatorów ::= identyfikator
| lista_identyfikatorów "," identyfikator
- Alternatywnie piszemy:
lista_identyfikatorów ::= identyfikator { "," identyfikator }
Klasyczny przykład użycia notacji BNF to opis składni notacji BNF:
składnia ::= { reguła }
reguła ::= identyfikator "::=" wyrażenie
wyrażenie ::= składnik { "|" składnik }
składnik ::= czynnik { czynnik }
czynnik ::= identyfikator
| symbol_zacytowany
| "(" wyrażenie ")"
| "[" wyrażenie "]"
| "{" wyrażenie "}"
identyfikator ::= litera { litera | cyfra }
symbol_zacytowany ::= """ { dowolny_znak } """
Zauważmy, że niektóre symbole, formalnie terminalne, są właściwie niedodefiniowanymi symbolami nieterminalnymi. Gwoli ścisłości powinniśmy zatem dopisać:
litera ::= "A" | "B" | "C" | ...
cyfra ::= "0" | "1" | ... | "9"
dowolny_znak ::= ...
Jak widać, użyliśmy kolejnego niedodefiniowanego symbolu, a mianowicie wielokropka. Nie brnijmy jednak dalej w formalizowanie rzeczy jasnych i znanych...
Kompilatory
Na pewno wszyscy wiedzą, jak uruchomić program napisany np. w języku C++. Dla naszych rozważań istotne jest to, że program taki musi zostać przetłumaczony na język wewnętrzny maszyny, na której program zamierzamy uruchomić. Owo tłumaczenie może być dokonane na jeden z dwóch sposobów:
- Kompilacja to przetłumaczenie całego programu „za jednym zamachem”. Otrzymujemy kod wynikowy, który (po konsolidacji, zwanej wulgarnie linkowaniem) wykonuje się bezpośrednio na maszynie docelowej.
- Interpretacja to tłumaczenie i wykonywanie programu instrukcja po instrukcji, cały czas za pomocą programu zwanego interpreterem.
- Są także formy pośrednie: kompilacja do kodu pośredniego, który jest następnie interpretowany lub ponownie kompilowany „w ostatniej chwili”. Taka forma jest bardzo często stosowana w przypadku języka Java. Daje nam to dobry kompromis między efektywnością a przenośnością kodu na różne komputery.
Nie zamierzamy zagłębiać się tu w tajniki budowy kompilatorów, czyli programów tłumaczących
- To jest temat na oddzielny wykład.
- Ponieważ jednak chcemy mówić o implementacji rozważanych mechanizmów językowych, będziemy musieli wspominać o konsekwencjach dla kompilatora (lub ewentualnie interpretera) związanych z tymi mechanizmami.
- Nie będziemy stronili od pewnych pomysłów na implementację, np. jak kompilator może przygotować wywołania polimorficzne.
- Jak już wspominaliśmy, rola kompilatora bywa trudna: musi on przetłumaczyć program napisany według jakiegoś paradygmatu na program w języku wewnętrznym komputera, czyli na raczej „toporny” program imperatywny.
Dlaczego w takim razie chcemy mówić o implementacji?
- To zdecydowanie ułatwia zrozumienie omawianych mechanizmów.
- Implementacja języka programowania (czyli, praktycznie rzecz biorąc, stworzenie kompilatora) to moment, gdy semantyka języka staje się namacalna i bezwzględnie obowiązująca.
- Jeśli twórca kompilatora źle ją zrozumiał, to powstanie kompilator nieco innego języka...
Przykład
- Ten przykład pokazuje, jaki wpływ na efektywność programu może mieć (nie)znajomość semantyki języka programowania
- Rozważmy pętlę for w Pascalu i w C:
for i := 1 to length(s) do ...
for (i = 1; i <= strlen(s); ++i) ...
- Na pierwszy rzut oka pętle te powinny zachowywać się tak samo.
- Jest jednak bardzo istotna różnica: w Pascalu długość napisu s zostanie policzona tylko raz, natomiast w języku C będzie ona liczona przy każdym obiegu pętli.
- To prowadzi do fatalnego pogorszenia złożoności obliczeniowej: zamiast liniowej, mamy kwadratową zależność od długości napisu s (przy założeniu, że operacje w pętli są niezależne od tej długości).
- Nie ma co liczyć na optymalizację wykonaną przez kompilator, gdyż ten na ogół nie może zbyt wiele zakładać o wywoływanych funkcjach.
- A zatem trzeba po prostu wiedzieć, co i gdzie można napisać, by nie trwonić czasu...
Uwagi bibliograficzne
Pisząc wykłady omawiające kwestie implementacyjne (2-4) oraz wykłady przeglądowe (5-7) korzystaliśmy z ciekawie opracowanej, rozległej tematycznie książki Sebesty „Concepts of Programming Languages”. Wykład o rachunku lambda bazuje na „Wybranych zagadnieniach z teorii rekursji”, zaś wykład o rachunku sigma — na „A Theory of Objects” Abadiego i Cardellego. Wiele informacji do wykładów o Haskellu zaczerpnęliśmy z „Introduction to Functional Programming using Haskell” Birda, zaś do wykładów o Prologu — z „Logic, Programming and Prolog” Nilssona i Małuszyńskiego. Pozostałe pozycje ze spisu literatury również stanowiły cenne źródło informacji.
