Programowanie/Algorytmy/IPL
IPL - nieformalny język programowania
[edytuj]Powtarzam się, ale tak ma być:)
Informatycy teoretycznie udowodnili, że każdy algorytm (czyli każde zadanie możliwe do zaprogramowania) można zapisać przy pomocy trzech konstrukcji algorytmicznych zwanych kompozycjami: kompozycji sekwencyjnej, kompozycji warunkowej oraz kompozycji iteracyjnej.
Do szkicowania algorytmów można użyć nieformalnego języka programowania IPL (Informal Programing Language). Język ten posiada trzy podstawowe konstrukcje algorytmiczne, pozwala więc na zapis algorytmów. Konstrukcje języka IPL są analogiczne do języków imperatywnych (Pascal, C, C++, C#, Java, Fortran). Pozwala to na przeniesienie algorytmu na dowolne środowisko.
Są stosowane skróty myślowe, np. zapis rozkazów w języku potocznym. Algorytm musi być jednak zapisany logicznie, bo bez tego nie będzie algorytmem.
Kompozycja sekwencyjna
[edytuj]Kompozycja sekwencyjna jest w języku IPL reprezentowana przez wyrażenie A NASTĘPNIE.
Przykładowa konstrukcja sekwencyjna: I1 A NASTĘPNIE I2 .
Oznacza to, że najpierw zastaje wykonana instrukcja I1, a po jej zakończeniu zostanie wykonana instrukcja I2.
Pamiętamy, że każda instrukcja jest dla komputera bezwzględnym rozkazem. To znaczy komputer rozumie to tak: wykonaj instrukcję I1, a następnie wykonaj instrukcję I2.
Programista powinien sobie przyswoić traktowanie każdej instrukcji jako takiego twardego rozkazu dla komputera.
Przykłady konstrukcji sekwencyjnej dostarczają starodawne książki kucharskie. Przepisy są pisane w trybie rozkazującym. Weź to, zrób tamto a następnie zamieszaj itp.
Poniższy przykład algorytmu smażenia jajecznicy jest napisany w postaci języka nieformalnego, a taki nie jest akceptowany przez żaden kompilator (nie wiadomo, jak interpretować swobodnie napisane instrukcje). Z tego powodu napisałem to w postaci komentarza dla języka C. Komentarz jest tekstem zawartym pomiędzy znakami /* oraz */. Komentarz taki może rozciągać się na wiele wierszy. Drugą formą komentarza jest tekst od sekwencji // do końca wiersza (komentarz jednowierszowy). Wikipedia koloruje komentarze na niebiesko i oznacza kursywą w celu wyraźnego odznaczenia.
// komentarz jednowierszowy
/*
komentarz wielowierszowy
jest ignorowany przez kompilator
z tego powodu może służyć
do dokumentowania swojej cennej pracy
*/
// to jest komentarz "obrazkowy" do oddzielania fragmentów kodu w celu
// poprawienie czytelności
//=====================================================================
/*
//ALGORYTM SMAŻENIA JAJECZNICY Z DWÓCH JAJ
Weź dwa jaja
A NASTĘPNIE
Umyj jaja
A NASTĘPNIE
Rozbij jaja na patelnię
A NASTĘPNIE
Posól jaja
A NASTĘPNIE
Usmaż jaja
//KONIEC ALGORYTMU
*/
Jak widać, opisana kompozycja jest bardzo prosta. Można jeszcze powiedzieć o oznaczeniu słowa A NASTĘPNIE. Jest ono stosowane bardzo często, zatem dla uproszczenia w języku C, C++, Pascal, Java i wielu innych jest ono zastąpione średnikiem. Z kolei w języku Fortran, kompozycja sekwencyjna jest realizowana poprzez umieszczenie jednej instrukcji pod drugą (w przypadku braku innych specjalnych konstrukcji sygnalizowanych słowami zastrzeżonymi).
Przykład w języku "pseudo-C"
//czytelny komentarz w formie ramki
/**************************************************
* algorytm smażenia dwóch jaj w języku pseudo-C *
***************************************************/
wezDwaJaja();
umyjJaja();
wbijJajaNaPatelnie();
usmazJaja();
// teraz już mamy jajecznicę z dwóch jaj
Coś takiego mogłoby po pewnych poprawkach działać. Przede wszystkim komputer musi rozumieć wywoływane polecenia (w tym przypadku są to funkcje). Trzeba by je zdefiniować (w praktyce - napisać). W dalszym ciągu będziemy robić takie rzeczy.
Kompozycja warunkowa
[edytuj]Kompozycja warunkowa pozwala dokonać wyboru w zależności od poprawności jakiegoś predykatu. Postać konstrukcji warunkowej w języku IPL (jako komentarz języka C):
// przykładowa postać instrukcji warunkowej
/*
JEŻELI
Warunek
WÓWCZAS
Instrukcja_1
W PRZECIWNYM RAZIE
Instrukcja_2
*/
Jak nietrudno się domyślić, przedstawiona kompozycja najpierw sprawdza prawdziwość warunku Warunek.
Warunek może mieć wartość logiczną PRAWDA/(po angielsku TRUE) albo FAŁSZ/(po angielsku FALSE). Jeżeli Warunek jest prawdziwy, wówczas wykonana zostanie Instrukcja_1. Jeżeli zaś wartość warunku będzie fałszem, komputer wykona Instrukcja_2.
Ściślej mówiąc, warunek jest predykatem, tj. zdaniem logicznym, które może pobierać argumenty i zawsze zwraca jakąś wartość. Wyliczenie prawdziwości warunku jest prawie zawsze związane z wykonaniem jakiegoś algorytmu.
Instrukcja może być instrukcją pustą (to znaczy nic nie robić). W takim wypadku konstrukcja przyjmuje wersje uproszczoną (z pominiętą częścią W PRZECIWNYM RAZIE).
/*
JEŻELI
Warunek
WÓWCZAS
Instrukcja
*/
W przypadku wartości fałszywej powyższa konstrukcja nie zrobi nic.
Przykładowe kompozycje warunkowe:
// algorytm zakupu napoju w lecie
/*
JEŻELI
wiekKupujacego < 18 lat
WÓWCZAS
kup oranzade
W PRZECIWNYM RAZIE
kup małe piwko
*/
Kolejny ważny krok. W dotychczasowej postaci możliwe było wybranie jednej z dwóch instrukcji. Jednak wybrana instrukcja może być w także grupą instrukcji. Są one nazywane blokiem. W języku IPL blok jest oznaczany znacznikami w formie małych kątownic, jednak na klawiaturze komputera nie ma takich znaków. Dlatego będę używał par słów BEGIN oraz END. Oznaczają one początek i koniec bloku.
// Przykładowy algorytm w języku pseudo - IPL wykorzystujący bloki
//przypominam, że tekst ma postać komentarza wielowierszowego w języku C
/*
// Jasio budzi się rano i mogą wystąpić dwie sytuacje
JEŻELI
Jasio zaspał
WÓWCZAS
BEGIN //Jasio zaspał
//Jasio zaspał i musi jak najszybciej dostać się do szkoły
ubierz się szybko;
zapakuj szybko plecak;
biegnij do szkoły;
END //Jasio zaspał
W PRZECIWNYM RAZIE
BEGIN// Jasio nie zaspał
//Jasio ma dużo czasu i może się przygotować do szkoły
zjedz śniadanko;
zrób kanapki do szkoły;
zrób poranną toaletę;
sprawdź rozkład zajęć;
zapakuj uważnie plecak;
ubierz się ładnie;
idź do szkoły;
END//Jasio nie zaspał
*/
W powyższym przykładzie pojawiło się sporo nowych myśli. Po pierwsze - wystąpiły pary ograniczników bloków BEGIN i END. W naszym przykładzie zawierają one kompozycje sekwencyjne. Ale mogą to być każde inne kompozycje. Cały blok jest traktowany jako pojedyncza grupa instrukcji.
Po drugie, co ważne, pary ograniczników bloku są opisane komentarzami. W kodzie widać wyraźnie, np. że dane słowo END określa koniec bloku "Jasio nie zaspał". Ułatwia to szybkie zrozumienie kodu. Należy pamiętać, że kod musi być możliwie najbardziej czytelny i zrozumiały dla osoby, która nie miała z nim styczności (możliwe, że sam autor napisał go na tyle dawno, że zapomniał).
Komentarze opisują dwie opcje, które się wzajemnie wypluczają (prawda / fałsz). W przypadku Jasia jest to trywialne, ale warunki mogą być znacznie bardziej skomplikowane. Wtedy takie komentarze są niezmiernie ważne, bo pozwalają porównać kod z zamysłem projektanta.
Po trzecie, ciekawą sprawą jest spojrzenie na opcje normalną i nienormalną. Chodzi o to, że często w rozwiązywanych problemach występują opcje "typowe" (dane poprawne, znaczna większość typowych danych) oraz "nietypowe" (przypadki szczególne w problemach matematycznych, błędy, niepoprawne dane i inne przypadki, które należy obsłużyć, aby program był odporny na błędy). W naszym przypadku opcją szczególną było obsłużenie zaspania Jasia. Niektórzy informatycy przyjęli, że dobrze jest obsłużyć przypadki szczególne na początku i zastawić sobie opcje "standardowe" na deser. Argumentują to tym, że obsłużenie błędów na początku zapobiega zapomnieniu o tym w późniejszym natłoku spraw. Inni z kolei zostawiają to na koniec. Wybór należy do Czytelnika. Należy jednak pamiętać, że uporanie się z przypadkami szczególnymi znacznie poprawi jakość oprogramowania, które być może znajdzie jakieś poważniejsze zastosowania.
Po czwarte, w praktyce najpierw piszemy na komputerze szkielet konstrukcji. Obmyślamy warunek i komentarze specyfikujące bloki. Dopiero później wypełniamy bloki treścią.
//szkielet konstrukcji JEŻELI - WÓWCZAS - W PRZECIWNYM RAZIE
/*
JEŻELI
tu najpierw obmyślamy warunek
WÓWCZAS
BEGIN// obmyślamy komentarz specyfikujący blok true
//tu na początku zostawiamy pustkę
END//tu też komentarz specyfikujący blok true
W PRZECIWNYM RAZIE
BEGIN// i tu też obmyślamy komentarz specyfikujący,
// uważajmy, aby był on zaprzeczeniem specyfikacji bloku true
// tu zostawiamy pustkę
END// i tu też jest komentarz specyfikujący
*/
W bloku może znajdować się inna kompozycja. Oto kolejny przykład.
// Przykład zagniezdzenia kompozycji warunkowej
// Algorytm nauki z książki
/*
JEŻELI
książka jest potrzebna
WÓWCZAS
BEGIN// książka jest potrzebna
/// w tym bloku są instrukcje, jak zdobyć książkę
sprawdź dostępność książki w bibliotece;
// a następnie
JEŻELI
książka jest dostępna w bibliotece
WÓWCZAS
BEGIN//książka jest dostępna w bibliotece
idź do biblioteki;
wypożycz książkę;
wróć do domu;
przeczytaj książkę od deski do deski;
zrób notatki;
odnieś książkę do biblioteki;
END//książka jest dostępna w bibliotece
W PRZECIWNYM RAZIE
BEGIN// książka nie jest dostępna w bibliotece
JEŻELI
koleżanka ma książkę;
WÓWCZAS
BEGIN//koleżanka ma książkę
zaproś koleżankę z książką na obiad;
daj koleżance ładny kwiatek;
ładnie poproś o pożyczenie książki;
JEŻELI
koleżanka zgodzi się pożyczyć książkę
WÓWCZAS
BEGIN// koleżanka może pożyczyć książkę
pożycz książkę;
przeczytaj książkę;
zrób notatki z książki;
odnieś książkę do koleżanki;
podziękuj ładnie koleżance;
podyskutuj trochę na temat książki w ramach utrwalenia wiedzy;
zaofiaruj się na przyszłość pomocą w pożyczaniu książek
END//koleżanka może pożyczyć książkę
END//koleżanka ma książkę
W PRZECIWNYM RAZIE
BEGIN// koleżanka nie ma książki
poszukaj książki w internecie;
JEŻELI
książka jest w internecie
WÓWCZAS
BEGIN//książka jest w internecie
zaopatrz się w książkę z internetu
END//książka jest w internecie
W PRZECIWNYM RAZIE
BEGIN//nie ma książki w internecie
//no to lipa
wytłumacz się z braku książki swojemu profesorowi
END//nie ma książki w internecie
END// koleżanka nie ma książki
END//książka nie jest dostępna w bibliotece
END// książka jest potrzebna
W PRZECIWNYM RAZIE
BEGIN// książka nie jest potrzebna
//pieniądze nie mogą się zmarnować
kup kwiaty swojej kochanej osobie
END//książka nie jest potrzebna
*/
W powyższym przykładzie widać, że komentowanie znaczników początku/końca bloku ułatwia zrozumienie algorytmu. Tekst wewnątrz bloku jest wcięty względem znaczników. W języku Pascal zwykle wystarczają dwie spacje wcięcia. W językach C/C++ spotyka się 4 spacje. Styl kodowania BSD zaleca aż 8 spacji wcięcia (argumentuje to tym, że jeżeli algorytm nie mieści się na ekranie, to trzeba go rozłożyć na kawałki, będzie o tym mowa później).
Kompozycja iteracyjna
[edytuj]Kompozycja iteracyjna jest najbardziej potężną instrukcją w języku IPL, ponieważ umożliwia wykonanie teoretycznie nieograniczoną liczbę operacji.
Ma ona postać
/*
DOPÓKI
warunek
DOPÓTY
refren
*/
Oznacza ona: dopóki jest spełniony warunek, dopóty wykonuj refren. W praktyce działanie konstrukcji iteracyjnej przebiega następująco. Wykonawca sprawdza prawdziwość warunku. Jeżeli jest on prawdziwy, wówczas wykonany zostanie refren i znowu będzie sprawdzany warunek w celu określenia, czy wykonać refren. Jeżeli jednak warunek będzie fałszywy, wówczas refren nie zostanie wykonany.
Jeżeli warunek jest już na początku fałszywy, to refren nie zostanie wykonany ani razu.
Jeżeli warunek będzie zawsze prawdziwy, to pętla nie będzie mogła zostać zakończona. Refren będzie wykonywany przez cały czas działania aplikacji. Dlatego należy uważnie planować zakończenie wykonywania iteracji.
Refren ma zazwyczaj formę bloku. Blok zawiera w sobie inne konstrukcje algorytmiczne.
Konstrukcja iteracyjna także musi być odpowiednio wyspecyfikowana.
// przykład wyspecyfikowanej konstrukcji iteracyjnej
/*
//pętla podlewająca kwiatki
//stoimy przed oknem z kwiatkami
DOPÓKI
jest kwiatek do podlania
DOPÓTY
BEGIN//(specyfikacja refrenu)podlewanie kolejnego kwiatka
//podlewanie kwiatka
podlej kwiatek;
przesuń się do następnego niepodlanego kwiatka
END//podlewanie kolejnego kwiatka
//(specyfikacja postkondycji) teraz już wszystkie kwiatki zostały podlane
// zawsze należy specyfikować sytuację po zakończeniu pętli.
*/
W powyższym przykładzie opisaliśmy sytuację przed wejściem do pętli. Ponadto, opisaliśmy refren. Na koniec (co ważne), umieściliśmy komentarz opisujący sytuację po zakończeniu pętli.
Przy tworzeniu pętli należy najpierw napisać jej szkielet. To znaczy określić dobrze warunek oraz sytuację po zakończeniu wykonywania pętli (komentarz: "teraz już.."). Dopiero po naszkicowaniu pętli przystępujemy do pisania refrenu.
Czasem przed wykonywaniem pętli należy umieścić preludium. Jest to grupa instrukcji, która wykonuje czynności przygotowujące wykonywanie pętli. Przykładowo, przed podlewaniem kwiatków należy podejść do okna. Podobnie, po pętli należy odejść od okna.
/*
//Przykładowa pętla w języku IPL
//preludium
podejdź do okna;
//refren
DOPÓKI
są kwiatki do podlania
DOPÓTY
BEGIN//refren - podlewanie kwiatka
podlej kolejnego kwiatka;
sprawdź, czy są kwiatki do podlania;
END//refren - podlewanie kwiatka
//specyfikacja sytuacji po refrenie
//teraz już wszystkie kwiatki zostały podlane
//po pętli porządkujemy sytuację
odejdź od okna;
ubierz się;
idź do pracy;
*/
goto - instrukcja skoku
[edytuj]Instrukcja skoku GOTO umożliwia skok do innego miejsca w algorytmie. Pozwala to budować algorytmy niestrukturalne (tzn. niezgodne z regułą stosowania jedynie trzech struktur algorytmicznych).
/*
// przykład stosowania instrukcji skoku do sekretnego wyjścia z pętli
// instrukcja warunek ma swoją specyfikację, ale GOTO pozwala na obejście tego
// czyni to kod bardziej skomplikowanym i wymusza jego głębsze poznanie w celu zrozumienia
//preludium pętli
instrukcja_1;
instrukcja_2;
//teraz pętla
DOPÓKI
warunek
DOPÓTY
BEGIN//refren
//tu coś się robi...
//ale jest sekretne wyjście z pętli (mało tego, pominięte zostaną instrukcje po refrenie)
JEŻELI
warunek_2
WÓWCZAS
GOTO etykieta_2
END//refren
//teraz już... coś tam ma być
//po refrenie są jakieś instrukcje
instrukcja_3;
instrukcja_4;
//jeżeli pętla zostanie przerwana instrukcją GOTO, to nastąpi przeskoczenie dopiero do tego miejsca w algorytmie
//etykieta 2
etykieta_2
*/
Jednym z zastosowań GOTO jest wychodzenie ze złożonych pętli.
Stosowanie GOTO musi być dobrze przemyślane i udokumentowane. Można bowiem uczynić kod nieczytelnym i trudnym do zrozumienia.
Instrukcja skoku do zadanego miejsca w programie jest wykorzystywana w językach asemblerowych. Jest to wtedy jedyny sposób sterowania przebiegiem wykonania programu.
Dawniej w języku FORTRAN stosowanie GOTO było niezbędne do tworzenia niektórych pętli i obsługi błędów.
Obecnie w językach wysokiego poziomu instrukcji GOTO należy używać ostrożnie.