Paradygmaty programowania/Wykład 1: Co to jest paradygmat programowania?

From Studia Informatyczne

Wstęp

Donald Ervin Knuth (1938-)
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.

[Edytuj]

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.

[Edytuj]

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.");

        }

      }

[Edytuj]

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))

       )

     )

[Edytuj]

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.

[Edytuj]

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.

[Edytuj]

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.

[Edytuj]

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.

[Edytuj]

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 ...