Paradygmaty programowania

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Forma zajęć

Wykład (30 godzin) + laboratorium (30 godzin)

Opis

Kurs omawia paradygmaty pojawiające się we współczesnych językach programowania: programowanie imperatywne, obiektowe, funkcyjne i programowanie w logice. Pozwala to pogłębić znajomość języków programowania, a także zrozumieć podstawowe zagadnienia implementacyjne.

Sylabus

Autor

  • Włodzimierz Moczurad

Wymagania wstępne

  • Logika i teoria mnogości
  • Wstęp do programowania
  • Algorytmy i struktury danych

Zawartość

  • Pojęcia ogólne
    • Opis składni i semantyki języków programowania
    • Typy
    • Przekazywanie parametrów do podprogramów
    • Abstrakcyjne typy danych
    • Przeładowywanie operatorów i podprogramów
    • Polimorfizm
  • Programowanie imperatywne
    • Zmienne
    • Struktura blokowa
    • Wiązanie statyczne i dynamiczne
    • Organizacja wywołań podprogramów
    • Przydział pamięci na stosie i na stercie
    • Przykłady z języków C, Fortran, Pascal
  • Programowanie obiektowe
    • Klasy jako abstrakcyjne typy danych
    • Dziedziczenie
    • Późne wiązanie wywołań
    • Polimorfizm
    • Szablony i klasy rodzajowe
    • Przykłady z języków C++, Java, C#, Ada 95, Smalltalk
  • Programowanie funkcyjne
    • Funkcje jako model programowania
    • Rachunek lambda
    • Dopasowywanie wzorca
    • Otypianie
    • Rekursja
    • Leniwa ewaluacja
    • Funkcje wyższego rzędu
    • Przykłady z języków Lisp, Scheme, ML, Haskell
  • Programowanie w logice
    • Rachunek predykatów w Prologu
    • Rezolucja
    • Listy

Literatura

  • Robert Sebesta: Concepts of Programming Languages. Addison Wesley, 2005
  • Peter Van Roy, Seif Haridi: Concepts, Techniques, and Models of Computer Programming. MIT Press, 2004
  • Ken Arnold, James Gosling: The Java Programming Language. Addison Wesley, 2005 / Java. Wydawnictwa Naukowo-Techniczne, 1999
  • Jeffrey Ullman: Elements of ML Programming. Prentice Hall, 1997

Moduł 1

Co to jest paradygmat programowania?


===Wprowadzenie.=== Pierwszy moduł wprowadza Czytelnika w tematykę wykładu. Wyjaśniamy, co mamy na myśli mówiąc o paradygmatach programowania, przypominamy podstawowe wiadomości o sposobach formalnego opisu składni języków programowania; w szczególności wspominamy o szeroko rozpowszechnionej notacji BNF. W paru słowach omówimy związek tego wykładu z kompilatorami.


1 Wstęp

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? Nie bardzo; 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.


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


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

}


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

)


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


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


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


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


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


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


Ćwiczenia

Zadanie 1. Przyjrzyj się programom, pokazanym w przykładach na początku wykładu. Zapewne od razu widzisz, do czego mogą służyć. Upewnij się, że masz dostęp do komputera i oprogramowania, które umożliwia uruchamianie programów w jakimś typowym języku imperatywnym (np. Pascal) i obiektowym (np. Java); C++ może spełniać obydwie te role. Następnie uruchom pierwsze dwa programy, imperatywny i obiektowy, ewentualnie dostosowując je do wymagań języków, których używasz.

Zadanie 2. Trzeci program, funkcyjny, można łatwo przerobić na program imperatywny. Zrób to i uruchom ów program. Czy potrafisz napisać program, który taki sam wynik obliczy znacznie prościej?

Wskazówka do zadania 2. Podany program (a właściwie funkcja) liczy oczywiście sumę kolejnych liczb całkowitych od m do n. W wersji imperatywnej można to osiągnąć za pomocą pętli dodającej owe liczby, ale prościej i szybciej jest wykorzystać wzór na taką sumę, czyli (n–m+1)(n+m)/2 wraz z ewentualnym sprawdzeniem, czy m Ł n.

<<<Pytanie do zespołu technicznego: Czy wskazówki do zadań mogłyby być zakryte i pojawiać się dopiero po kliknięciu czegoś?>>>

Zadanie 3*. Czwarty program, logiczny, jest znacznie trudniejszy w przetłumaczeniu na język imperatywny. Spróbuj jednak i tego. Zauważ, że oprócz przetłumaczenia treści tego konkretnego programu, trzeba zbudować zalążek „maszyny logicznej”, która potrafi wyciągać wnioski z podanych zależności.

Wskazówka do zadania 3. Tu pytamy, kto jest dziadkiem Janusza. Podane zależności pozwalają stwierdzić, że jest to Jan. Chcąc przetłumaczyć ten programik na język imperatywny, musimy skonstruować program, który nie tylko ma zapisane przykładowe „relacje rodzinne”, ale także próbuje znaleźć odpowiedź dopasowując zależności ze zmiennymi do konkretnych imion.

Zadanie 4. W historii informatyki parokrotnie podejmowano próby stworzenia „superjęzyka”, który zawierałby niemalże wszystkie znane w danym czasie mechanizmy. Przykładami są języki PL/I i Ada. PL/I dawno odszedł już w zapomnienie, zaś Ada dopiero w ćwierć wieku po powstaniu doczekała się przyzwoitych implementacji; trudno jednak uznać ją za język, który odniósł sukces. Wymień parę powodów, dla których superjęzyki wydają się skazane na porażkę.

Wskazówka do zadania 4. Po pierwsze, obszerny język wymaga bardzo złożonego kompilatora. Praca nad nim może trwać tak długo, że język zdąży się zestarzeć, zanim zyska popularność. Po drugie, superjęzyk jest kosztowny pod względem wykorzystania zasobów komputera. Po trzecie, obfitość rozmaitych mechanizmów sprawia, że te same algorytmy można zapisać na wiele sposobów — co nie sprzyja niezawodności. Po czwarte, programistom trudniej jest się nauczyć wielu nowych rozwiązań. Z punktu widzenia sukcesu rynkowego wydaje się zatem, że lepszym rozwiązaniem jest stosunkowo prosty, zwarty język, który dopiero później „obrasta” bibliotekami.

Zadanie 5. Zapisz za pomocą BNF składnię kilku typowych konstrukcji w wybranym języku programowania, np. instrukcji warunkowej (if), instrukcji wyboru (case lub switch), pętli while, deklaracji zmiennej tablicowej. Wyrażenia arytmetyczne oraz inne „żmudne” sytuacje pozostaw chwilowo bez definicji. Zauważ, że często definiujemy jakąś konstrukcję, a potem wykorzystujemy tę definicję do opisania większego lub bardziej ogólnego tworu.

Zadanie 6. Zapisz w BNF definicje liczby całkowitej i liczby w zapisie zmiennopozycyjnym (chodzi o liczby postaci 1.23, –1.23E+45, 1.23E–4). Zauważ że tam, gdzie występują powtarzające się elementy (np. cyfry w liczbie), można użyć rekurencji lub nawiasów klamrowych.

Zadanie 7. Zapisz w BNF definicję wyrażenia arytmetycznego z wybranego języka programowania.

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Paradygmaty_programowania&oldid=6367”