Wikipedia

Programowanie strukturalne

paradygmat programowania
(Przekierowano z Język strukturalny)

Programowanie strukturalne – paradygmat programowania opierający się na podziale kodu źródłowego programu na procedury i hierarchicznie ułożone bloki z wykorzystaniem struktur kontrolnych w postaci instrukcji wyboru i pętli. Rozwijał się w opozycji do programowania wykorzystującego proste instrukcje warunkowe i skoki. Programowanie strukturalne zwiększa czytelność i ułatwia analizę programów, co stanowi znaczącą poprawę w stosunku do trudnego w utrzymaniu „spaghetti code” często wynikającego z użycia instrukcji goto.

Początki programowania strukturalnego przypadają na Lata 60. XX wieku, a ważnym głosem w dyskusji o programowaniu strukturalnym był list Edsgera Dijkstry Goto Statement considered harmful.

Język programowania zgodny z paradygmatem programowania strukturalnego nazywa się językiem strukturalnym.

Cechy charakterystyczne edytuj

Struktury kontrolne edytuj

Podstawowe struktury kontrolne jakie wymienia twierdzenie o programowaniu strukturalnym, z których możliwe jest zbudowanie dowolnego programu to:

  • Sekwencja – wykonanie ciągu kolejnych instrukcji
  • Wybór – w zależności od wartości predykatu wykonywana jest odpowiednia instrukcja. W językach programowania zazwyczaj reprezentowana przez słowa kluczowe if..then..else.
  • Iteracja – wykonywanie instrukcji póki spełniony jest jakiś warunek. Reprezentowana w różnych wariantach jako pętle oznaczane między innymi przez: while, repeat, for lub do..until.

Każda ze struktur kontrolnych może być też rozumiana jako pojedyncza instrukcja. Według pierwotnych założeń struktury kontrolne powinny posiadać jedno wejście i jedno wyjście.

Podprogramy edytuj

Podprogramy pozwalają na wydzielenie pewnej grupy instrukcji i traktowania ich jako pojedynczej operacji, są dodatkowo mechanizmem abstrakcji.

Bloki edytuj

W językach programowania bloki odpowiadają sekwencjom instrukcji, umożliwiając budowanie programu przez komponowanie struktur kontrolnych – w miejscu, w którym umieścimy blok z instrukcjami jest on traktowany jak pojedyncza instrukcja.

W kodzie źródłowym programów bloki są wyróżniane na różne sposoby, przykładowo ograniczone przez if..fi jako blok dla instrukcji if w ALGOLU 68, czy dowolne bloki instrukcji obejmowanie poprzez BEGIN..END w Pascalu, PL/I, przy pomocy wcięć w Pythonie czy Haskellu lub poprzez nawiasy klamrowe w języku C i pochodnych.

Historia edytuj

Przed programowaniem strukturalnym edytuj

Pierwsze komputery były programowane wprost z użyciem kodu maszynowego[1] lub z wykorzystaniem asemblera. Pierwsze asemblery przypadają na połowę lat 50. W 1954 roku Nathaniel Rochester napisał asembler dla IBM 701, natomiast w 1955 Stan Poley stworzył SOAP – asembler dla komputera IBM 650, początkowo programowanego wyłącznie przy pomocy kodu maszynowego[2]. Kontrola przepływu w programie odbywała się głównie przy pomocy warunkowych i bezwarunkowych instrukcji skoku, w ówczesnych komputerach IBM określanych jako branch lub instrukcje transferu[3][4].

Wprowadzony w roku 1957 FORTRAN, pierwszy poważny język programowania wysokiego poziomu, główny nacisk kładł na formuły arytmetyczne. Występujące w nim struktury (a raczej instrukcje) kontrolne nie wykraczały daleko poza możliwości instrukcji skoku w asemblerach[4] – język, poza skokiem bezwarunkowym, udostępniał przypisywalne (assigned goto) i obliczalne (computed goto) instrukcje skoku, oraz zbliżone do obliczalnego goto wyrażenie arytmetycznego (nie logicznego) if. Skoki były wykonywane do etykiet reprezentowanych przez wartości liczbowe. Dodatkowo występowała też prosta pętla.

ALGOL edytuj

Opublikowany w roku 1958 ALGOL 58 oraz jego dwa lata późniejsza, mocno rozwinięta wersja ALGOL 60, wprowadziły wiele kluczowych konstrukcji programistycznych, istotnych nie tylko z punktu widzenia programowania strukturalnego. Był to pierwszy język, w którym pojawił się koncept instrukcji złożonych – bloków – służących do grupowania instrukcji. Blok jest traktowany jako pojedyncza instrukcja i możliwe jest użycie go w miejscu dla niej przeznaczonym.

Język ALGOL wprowadził również fundamentalne dla programowania strukturalnego konstrukcje: logiczne instrukcje warunkowe if..then z opcjonalnym else, pętle for oraz instrukcję wyboru switch. Pozwolił też na deklarowanie procedur, w tym zagnieżdżonych w sobie, wraz z odpowiednim zasięgiem identyfikatorów. Instrukcja goto dalej pozostawała jednak ważnym elementem składniowym języka.

Podstawa teoretyczna edytuj

Jako fundament teorii programowania strukturalnego określa się twierdzenie o programowaniu strukturalnym. Jego autorstwo przypisuje się najczęściej ’Böhmowi i Giuseppe Jacopiniemu, wskazując jako źródło ich pracę Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules z maja 1966 roku[5]. W swojej pracy pokazali oni, że dowolny program zawierający skoki (czyli dowolny graf przepływu), może zostać znormalizowany do odpowiadającego mu ustrukturyzowanego grafu – zbudowanego z trzech podstawowych struktur:     oraz   wyrażającym odpowiednio: sekwencję, wybór oraz iterację. Ponieważ grafy przepływu mogą wyrażać dowolne funkcje obliczalne, to oznacza, że możemy też takie wyrazić przy pomocy tych podstawowych konstrukcji. W dalszej części pracy opisany jest język P′′ – pierwszy strukturalny język, dla którego udowodniono zupełność w sensie Turinga.

Twierdzenie Böhma i Jacopiniego nie mówi o tym w jaki sposób tworzyć dobre programy strukturalne lub je analizować. Prace nad tymi zagadnieniami odbywały się głównie na przełomie lat 60 i 70, z istotnym wkładem dokonamy przez Edsgera Dijkstrę, Roberta W. Floyda, Tonyego Hoarea, Ole-Johana Dahla, oraz Davida Griesa.

Dyskusja edytuj

Już na etapie projektowania języka ALGOL, w roku 1959, Heinz Zemanek rozważał ograniczenie użycia instrukcji goto, jednak jego uwagi zostały wtedy zignorowane[6]. Niedługo później Hoare proponował ograniczenie użycia skoków tylko do wyjść alarmowych, natomiast w roku 1966 razem z Wirthem proponowali ograniczenia w postaci instrukcji wyboru case[6][7].

W debacie pomiędzy programistami dotyczącej popularyzacji programowania strukturalnego i ograniczeniu programowania opartego na goto najistotniejszym punktem jest praca Edsgera Dijkstry z 1974 roku A Case against GO TO Statemant opublikowana pod tytułem Goto Statement considered Harmful. Autor w sposób zdecydowany wyraża się przeciwko użyciu tej instrukcji:

Instrukcja go to powinna zostać usunięta z wszystkich „wysokopoziomowych” języków programowania (to znaczy z wszystkich poza – prawdopodobnie - czystym kodem maszynowym)[6].

Odwołuje się też do twierdzenia Böhma i Jacopiniego, które umożliwia pokazanie, że goto jest instrukcją zbędną. Podaje przyczyny, przez które programy używające skoków są trudne w analizie. Dijkstra proponuje też odpowiednie ograniczenia na struktury kontrolne, jak na przykład Instrukcja opuszczenia, tak by dalej pozwalały na odpowiednią analizę, jeśli zestaw podstawowych instrukcji okazałby się zbyt ograniczający.

Jednym z pierwszych dużych komercyjnych projektów wykorzystujących programowanie strukturalne, który odniósł duży sukces było wykonane przez Harlana Millsa z IBM systemu indeksującego zbierane informacje dla New York Times.

Mimo kolejnych sukcesów związanych z aplikacją technik programowania strukturalnego, jak i rozwojowi teorii jej poświęconej, spora liczba programistów wciąż opierała się ograniczeniu lub wyeliminowaniu instrukcji goto z użycia[8]. Donald Knuth w 1974 roku opublikował pracę Structured Programming with GoTo Statements[9], w której opisywał sytuacje gdzie użycie skoku upraszcza rozwiązanie bez wpływu na trudność w jego analizie.

W roku 1987 na łamach Communications of the ACM po liście Franka Rubina „GOTO Considered Harmful” Considered Harmful[10] na nowo rozgorzała dyskusja dotycząca słuszności użycia goto, zarówno z głosami poparcia dla Rubina i użycia skoków, jak i mocnymi głosami przeciwko (razem z tytułami, stopniowo zawierającymi w coraz większej liczbie frazę „Considered Harmful”)[11][12]. Rubin twierdził:

Wiara, że GOTO są złe, stała się doktryną religijną, niepodważalną żadnymi dowodami[10]

Zdaniem edytora była to największa wymiana listów w historii forum[12]. Dyskusję uciął ostry list Dijkstry, poniekąd zawiedzionego poziomem dyskusji, jak i samymi próbami ponownej popularyzacji instrukcji goto[13][14].

Wpływ na języki programowania edytuj

Popularyzacja programowania strukturalnego zaowocowała wprowadzeniem konstrukcji programowania strukturalnego, często inspirowanych ALGOLEM, do języków programowania, które wcześniej ich nie posiadały, takich jak FORTRAN, COBOL czy BASIC.

Częste odstępstwa edytuj

O ile można obserwować zanik użycia goto, to istnieje niewiele czysto strukturalnych języków programowania. Najczęściej poza podstawowymi strukturami kontrolnymi pojawia się możliwość wczesnego wyjścia, łamiąc tym samym zasadę pojedynczego wyjścia z każdej struktury. Obsługa wyjątków również wykracza poza założenia programowania strukturalnego.

Wczesne wyjście edytuj

Najczęściej spotykana jest możliwość wyjścia z danej pętli lub podprogramu. Na poziomie podprogramu jest to zwykle instrukcja return. W przypadku pętli są to instrukcje break (przerwij daną pętlę) lub continue (przerwij daną iterację i przejdź do następnej). W czystym kodzie strukturalnym można napisać równoważne programy z wykorzystaniem dodatkowych instrukcji warunkowych, jednak może istotnie zwiększyć złożoność programów. Język C jest jednym z wczesnych przykładów wprowadzenia tego typu konstrukcji. Niektóre nowe języki programowania wprowadzają instrukcje „etykietowanego break”, które pozwalają opuścić więcej niż jeden poziom zagnieżdżonych pętli w pojedynczym kroku.

Wczesne wyjścia mogą powodować pewne trudności przy tworzeniu programów, związane na przykład z koniecznością zwalniania zaalokowanych zasobów przy każdym miejscu, w którym może być wykonany powrót z danego podprogramu. Występują różne podejścia: Pascal unika tych problemów nie dopuszczając tego typu konstrukcji, natomiast języki obiektowe wysokiego poziomu, takie jak C++ czy Java zawierają odpowiednie mechanizmy (RAII lub odśmiecanie pamięci) mające na celu ułatwienie pracy programiście.

Kent Beck, Martin Fowler wraz ze współautorami swoich książek na temat refaktoryzacji stwierdzają, że mocno zagnieżdżone bloki instrukcji warunkowych mogą być trudniejsze w zrozumieniu niż bardziej spłaszczona struktura z wieloma punktami wyjścia.

Pojedynczy punkt wyjścia nie jest tak naprawdę użyteczną regułą. Kluczem jest przejrzystość: Jeśli metoda jest prostsza z jednym punktem wyjścia, użyj jednego, w przeciwnym przypadku, użyj wielu[15]

Herb Sutter i Andrei Alexandrescu również stwierdzają, że zasada pojedynczego wyjścia nie ma zastosowania w C++, jest tak za sprawą obsługi wyjątków i destruktorów, przez co każda funkcja może mieć wiele niejawnych punktów wyjścia[16].

Odmienne zdanie wyraża natomiast Bertrand Meyer, który w 2009 opisał break i continue jako „stare goto w owczej skórze” i mocno odradzał ich użycie[17].

Obsługa wyjątków edytuj

Badacze spierają się co do użycia wyjątków w kontekście programowania strukturalnego, jako że łamią one zasadę pojedynczego wyjścia. Cytując wcześniejsze badania (1999-2004) i podając własne, Westley Weimer i George Necula stwierdzają, że problem z wyjątkami polega na tym, że „tworzą ukryte ścieżki przepływu sterowania, o których programistom ciężko wnioskować”[18]. Pojawiają się propozycje by sprowadzić wyjątki do pojedynczego wyjścia, jak i opinie, by pozostawić pełną dowolność w ich użyciu, jako że reguła pojedynczego wyjścia powstała przed pojawieniem się i popularyzacją wyjątków, a opakowywanie wyjątków by uczynić zgodnymi z regułą jednego wyjścia dodaje zbędne poziomy zagnieżdżenia utrudniając zrozumienie programów[19][20].

Zobacz też edytuj

Przypisy edytuj

  1. ↑ John von Neumann: First Draft of a Report on the EDVAC. [dostęp 2015-02-05]. [zarchiwizowane z tego adresu (2015-04-06)].
  2. ↑ The IBM 650 Magnetic Drum Calculator. [dostęp 2015-02-05].
  3. ↑ IBM: SOAP II. [dostęp 2015-02-05].
  4. ↑ a b Coding for the MIT-IBM 704 Computer. [dostęp 2015-02-05].
  5. ↑ David Harel. On Folk Theorems. „Communications of the ACM”. 23 (7), s. 379–389, lipiec 1980. DOI: 10.1145/358886.358892. 
  6. ↑ a b c Edsger Dijkstra. Go to statement considered harmful. „Communications of the ACM”. 11 (3), s. 147–148, marzec 1968. DOI: 10.1145/362929.362947. 
  7. ↑ C.A.R. Hoare, Wirth. A contribution to the development of ALGOL. „Communications of ACM”. 9, s. 413–432, czerwiec 1966. 
  8. ↑ P.J. Plauger: Programming on Purpose, Essays on Software Design. Prentice-Hall, 1993, s. 25. ISBN 978-0-13-721374-0.
  9. ↑ Donald Knuth: Structured Programming with GoTo Statements. [dostęp 2015-02-08]. [zarchiwizowane z tego adresu (2013-10-23)].
  10. ↑ a b Frank Rubin. „GOTO Considered Harmful” Considered Harmful. „Communications of the ACM”. 30 (3), s. 195–196, marzec 1987. 
  11. ↑ „'GOTO Considered Harmful’ Considered Harmful” Considered Harmful?. „Communications of the ACM”. 30 (5), s. 351–355, maj 1987. 
  12. ↑ a b „'GOTO Considered Harmful’ Considered Harmful” Considered Further. „Communications of the ACM”. 30 (6), s. 475–478, czerwiec 1987. 
  13. ↑ GOTO, One More Time. „Communications of the ACM”. 30 (8), s. 659–662, sierpień 1987. 
  14. ↑ Edsger Dijkstra: On a somewhat disappointing correspondence. [dostęp 1987-05-25].
  15. ↑ Jay Fields, Shane Harvie, Martin Fowler, Kent Beck: Refactoring: Ruby Edition. Pearson Education, 2009, s. 274–279. ISBN 978-0-321-60350-0.
  16. ↑ Herb Sutter, Andrei Alexandrescu: C++ Coding Standards: 101 Rules, Guidelines, and Best Practices. Pearson Education, 2004. ISBN 978-0-13-265442-5.
  17. ↑ Bertrand Meyer: Touch of Class: Learning to Program Well with Objects and Contracts. Springer Science & Business Media, 2009, s. 189. ISBN 978-3-540-92144-8.
  18. ↑ Westley Weimer, Necula George. „ACM Transactions on Programming Languages and Systems”. 30 (2). 
  19. ↑ Jim Bonang: The Pragmatic Defense: Making Defects Easier to Find. kwiecień 2012. [dostęp 2015-02-08]. [zarchiwizowane z tego adresu (2017-07-10)].
  20. ↑ Peter Ritchie: Single-Entry, Single-Exit, Should It Still Be Applicable In Object-oriented Languages?. 2008-03-07. [dostęp 2015-02-08].

Bibliografia edytuj

Źródło: „https://pl.wikipedia.org/w/index.php?title=Programowanie_strukturalne&oldid=72642746”