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

From Studia Informatyczne

Spis treści

Wstęp

Donald Ervin Knuth (1938-)Zobacz biografię
Enlarge
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.

John von Neumann (1903-1957)Zobacz biografię
Enlarge
John von Neumann (1903-1957)
Zobacz biografię
Niklaus E. Wirth (1934-)Zobacz biografię
Enlarge
Niklaus E. Wirth (1934-)
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.