IPL - nieformalny język programowania

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

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

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

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.