Strukturirano programiranje

Strukturirano programiranje je programska paradigma usmerena na poboljšanje jasnoće, kvaliteta i vremena razvoja računarskog programa putem ekstenzivne upotrebe selekcije strukturiranih konstrukata toka kontrole (if/then/else) i ponavljanja (while i for), blokovskih struktura i podrutina. Edsger Dajkstra je 1968. godine skovao termin „strukturirano programiranje”.

Strukturirano programiranje je nastalo 70-ih godina, a njemu je prethodilo kompozitno programiranje.^[1] Činjenica da nije postojao softver, koji bi mogao da iskoristi novonastale velike mogućnosti hardvera dovela je do prve softverske krize. Godine 1968. holandski informatičar Edsher Dajkstra napisao je članak „Go to naredba se smatra štetnom”, gde izlaže rezultate svog istraživanja, na osnovu kojih je zaključio da je broj grešaka u softveru proporcionalan broju upotreba goto naredbe. Godine 1969, konačno je stvoren programski jezik koji je omogućio pisanje programa bez upotrebe goto naredbe. To je bio Paskal, koji je stvorio Niklaus Virt. Faktori koji su doprineli popularnosti i širokom prihvaćanju ovog pristupa, prvo u akademskim krugovima i kasnije među praktičarima, uključuju otkriće onoga što je sada poznato kao teorema strukturiranog programa iz 1966. godine.^[2] Dajkstra, Hoare i Dahl su napisali knjigu „Strukturirano programiranje”, u kojoj se nalaze i članci koji se bave rešavanjem problema eliminisanja upotrebe goto naredbe.

Danas, pod stukturiranim programiranjem podrazumeva skup tehnika za razvijanje programskih modela koji koriste strogo definisane upravljačke strukture i strukture podataka. Strukturirano programiranje se najčešće koristi sa odstupanjima koja omogućavaju jasnije programe u nekim posebnim slučajevima, kao što je obrada izuzetaka.

Pravilni programi

Ciljna klasa programa naziva se pravilni program. Pod ovim podrazumevamo program koji zadovoljava sledeća tri uslova:

ima tačno jednu ulaznu granu
ima jednu izlaznu granu
kroz svaki čvor prolazi se bar jednom od ulaza do izlaza

Funkcija prva dva uslova jeste da se ceo pravilni program može zameniti tačno jednim čvorom, a funkcija trećeg jeste da eliminiše mogućnost beskonačnih ciklusa izolovanih delova programa.

Strukturna teorema i programiranje bez goto

Posebna baza strukturnih programa, koju čine sekvenca, iteracija tipa "while-do" i selekcija tipa "if-then-else" jeste baza pomoću koje se može izvesti svaki program i na osnovu koje možemo napraviti neke druge baze koje su nam potrebne.

1966. godine C. Boehm i G. Jacopini su izveli strukturnu teoremu koja pokazuje da se sveki pravilan program može ostvariti superpozicijom ove tri strukture (može se ostvariti bez upotrebe skokova), što je bilo ključno za rešavanje problema, koji su tražili uvođenje strukturiranih programa.

Elementi

Kontrolne strukture

Prema teoremi strukturiranog programa, smatra se da se svi programi sastoje od kontrolnih struktura:

„Sekvenca”; uređeni izjave ili potprogrami izvršeni u nizu.
„Selekcija”; jedna ili više izjava se izvršava zavisno od stanja programa. Ovo se obično izražava sa rezervisanim rečima kao što su if..then..else..endif.
„Iteracija”; izraz ili blok se izvršava dok program ne dosegne određeno stanje, ili su operacije primenjene na svaki element kolekcije. Ovo se obično izražava sa rezervisanim rečima kao što su while, repeat, for ili do..until. Često se preporučuje da svaka petlja ima samo jednu ulaznu tačku (u izvornom strukturalnom programiranju takođe samo jednu izlaznu tačku, a nekoliko jezika to nameće).
„Rekurzija”; izjava se izvršava ponovljenim pozivanjem dok se ne ispune uslovi raskida. Iako su u praksi slične iterativnim petljama, rekurzivne petlje mogu biti računski delotvornije i različito se implementiraju kao kaskadni stek.

Podrutine

Podrutine su jedinice koje se mogu pozvati, kao što su procedure, funkcije, metode ili potprogrami. Podrutine omogućavaju pozivanje sekvence programskih linija pojedinačnom izjavom.

Blokovi

Blokovi se koriste kako bi se omogućilo da se grupe izjava tretiraju kao da su jedna izjava. Blokovno strukturirani jezici imaju sintaksu za ograđujuće strukture na neki formalan način, kao što je if izjava ograđena sa if..fi u jeziku ALGOL 68, ili sekcija koda ograđena sa BEGIN..END u PL/I i Paskalu, uvlačenje znakom razmaka kao u Pajtonu - ili vitičaste zagrade {...} u C jeziku i mnogim kasnijim jezicima.

Istorija

Teorijska osnova

Teorema strukturiranog programa pruža teorijsku osnovu strukturiranog programiranja. U njemu se navodi da su tri načina kombinovanja programa — sekvenciranje, selekcija i iteracija — dovoljna za izražavanje bilo koje izračunljive funkcije.^[3]^[4] Ovo zapažanje nije poteklo od pokreta strukturiranog programiranja; ove strukture su dovoljne da opišu ciklus instrukcija centralne procesorske jedinice, kao i rad Turingove mašine.^[5]^[6]^[7]^[8] Stoga, procesor uvek izvršava „strukturirani program“ u ovom smislu, čak i ako instrukcije koje čita iz memorije nisu deo strukturiranog programa. Međutim, autori obično pripisuju rezultat radu iz 1966. Bema i Jakopinija, verovatno zato što je Dijkstra sam citirao ovaj rad.^[9] Teorema strukturiranog programa ne govori o tome kako napisati i analizirati korisno strukturiran program. Ove teme su razmatrane tokom kasnih 1960-ih i ranih 1970-ih, uz velike doprinose Dijkstre, Roberta V. Flojda, Tonija Hora, Ole-Johana Dala i Dejvida Grisa.

Debata

P. Dž. Ploger, rani usvojilac strukturiranog programiranja, opisao je svoju reakciju na teoremu strukturiranog programa:

Mi, preobraćenici, mahali smo ovom zanimljivom vesti pred nosom nerekonstruisanih programera na asemblerskom jeziku koji su neprestano izvlačili uvrnute delove logike i govorili, 'Kladim se da ne mogu da strukturišem ovo.' Ni dokazi Bema i Jakopinija, niti naši ponovljeni uspesi u pisanju strukturiranog koda nisu ih pridobili ni jedan dan ranije nego što su oni sami bili spremni da se uvere.^[10]

Donald Knut je prihvatio princip da programi moraju biti napisani imajući na umu dokazljivost, ali se nije složio sa ukidanjem izjave GOTO, i od 2018. je nastavio da je koristi u svojim programima.^[11] U svom radu iz 1974. godine, „Strukturirano programiranje sa Goto izjavama“,^[12] dao je primere u kojima je verovao da direktan skok vodi ka jasnijem i efikasnijem kodu bez žrtvovanja dokazivosti. Knut je predložio labavije strukturno ograničenje: trebalo bi da bude moguće nacrtati dijagram toka programa sa svim granama napred na levoj strani, sa svim granama unazad na desnoj strani i nijednim granama koje se međusobno ukrštaju. Mnogi od onih koji poznaju kompajlere i teoriju grafova zagovarali su dozvoljavanje samo reducibilnih grafova toka.^[13]

Teoretičari strukturiranog programiranja stekli su glavnog saveznika 1970-ih nakon što je istraživač IBM-a Harlan Mils primenio svoje tumačenje teorije strukturiranog programiranja na razvoj sistema indeksiranja za istraživački fajl Njujork Tajmsa. Taj projekat je bio veliki inženjerski uspeh, a menadžeri drugih kompanija su ga citirali u prilog usvajanju strukturiranog programiranja, iako je Dijkstra kritikovao načine na koje se Milsova interpretacija razlikuje od objavljenog rada.^[14]

Godine 1987, još uvek je bilo moguće pokrenuti pitanje strukturiranog programiranja u časopisu o računarskim naukama. Frenk Rubin je to učinio te godine sa otvorenim pismom pod naslovom „'GOTO smatrano štetnim' smatra se štetnim“.^[15] Usledile su brojne primedbe, uključujući odgovor Dijkstre koji je oštro kritikovao Rubina i ustupke koje su drugi pisci činili kada su mu odgovarali.

Reference

^ Clark, Leslie B. Wilson, Robert G.; Robert, Clark (2000). Comparative programming languages (3rd изд.). Harlow, England: Addison-Wesley. стр. 20. ISBN 9780201710120. Приступљено 25. 11. 2015.
^ Bohm, Corrado; Giuseppe Jacopini (maj 1966). „Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules” (PDF). Communications of the ACM. 9 (5): 366—371. CiteSeerX 10.1.1.119.9119  . S2CID 10236439. doi:10.1145/355592.365646. Архивирано из оригинала (PDF) 23. 09. 2015. г. Приступљено 11. 04. 2019.
^ Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second изд.). USA: Elsevier. стр. 209. ISBN 0-12-238452-0.
^ Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second изд.). USA: Elsevier. стр. 208,262. ISBN 0-12-238452-0.
^ B. Jack Copeland ed. , The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK. Turing, Alan Mathison (2004). The Essential Turing. Oxford University Press. ISBN 978-0-19-825079-1. . Contains the Turing papers plus a draft letter to Emil Post re his criticism of "Turing's convention", and Donald W. Davies' Corrections to Turing's Universal Computing Machine
^ Martin Davis (ed.). (1965), The Undecidable, Raven Press, Hewlett, NY.
^ Emil Post (1936), "Finite Combinatory Processes—Formulation 1", Journal of Symbolic Logic, 1, 103–105, 1936. Reprinted in The Undecidable pp. 289ff.
^ Emil Post. „Recursive Unsolvability of a Problem of Thue”. Journal of Symbolic Logic. 12: 1—11. 1947. JSTOR 2267170. S2CID 30320278. doi:10.2307/2267170. . Reprinted in The Undecidable pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on Turing's first and second proofs.
^ Dijkstra 1968.
^ Plauger, P. J. (12. 2. 1993). Programming on Purpose, Essays on Software Design (1st изд.). Prentice-Hall. стр. 25. ISBN 978-0-13-721374-0.
^ DLS • Donald Knuth • All Questions Answered. YouTube (на језику: енглески). University of Waterloo. 15. 11. 2018. 48 мин. Приступљено 24. 7. 2022.
^ Donald E. Knuth (децембар 1974). „Structured programming with go to statements” (PDF). Computing Surveys. 6 (4): 261—301. S2CID 207630080. doi:10.1145/356635.356640. Архивирано из оригинала (PDF) 2013-10-23. г.
^ „Archived copy” (PDF). Архивирано из оригинала (PDF) 2020-08-01. г. Приступљено 2018-03-24.
^ In EWD1308, „What led to "Notes on Structured Programming"”. , dated 10 June 2001, Dijkstra writes, "Apparently, IBM did not like the popularity of my text; it stole the term "Structured Programming" and under its auspices Harlan D. Mills trivialized the original concept to the abolishment of the goto statement."
^ Frank Rubin (март 1987). „"GOTO Considered Harmful" Considered Harmful” (PDF). Communications of the ACM. 30 (3): 195—196. S2CID 6853038. doi:10.1145/214748.315722. Архивирано из оригинала (PDF) 2009-03-20. г.

Literatura

Dušan Malbaški: Programski jezici i strukure podataka, Novi Sad
Edsger Dijkstra, Notes on Structured Programming, pg. 6
Böhm, C.; Jacopini, G. (1966). „Flow diagrams, Turing machines and languages with only two formation rules”. Communications of the ACM. 9 (5): 366—371. S2CID 10236439. doi:10.1145/355592.365646.
Dijkstra, Edsger W. (1968). „Letters to the editor: Go to statement considered harmful” (PDF). Communications of the ACM. 11 (3): 147—148. S2CID 17469809. doi:10.1145/362929.362947.
Michael A. Jackson, Principles of Program Design, Academic Press, London, 1975.
O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, . 1972. ISBN 978-0-12-200550-3. Недостаје или је празан параметар |title= (помоћ)
- this volume includes an expanded version of the Notes on Structured Programming, above, including an extended example of using the structured approach to develop a backtracking algorithm to solve the 8 Queens problem.
- a pdf version is in the ACM Classic Books Series
- Note that the third chapter of this book, by Dahl, describes an approach which is easily recognized as Object Oriented Programming. It can be seen as another way to "usefully structure" a program to aid in showing that it is correct.
Elder, Matt; Jackson, Steve; Liblit, Ben (2008). Code Sandwiches (PDF) (Технички извештај). University of Wisconsin–Madison. 1647, abstract
Sarah Brooks (1981). "Structure Charts and Basic Programming". in: MATYC Journal, v15 n2 p. 107-112 Spring 1981.
Tom DeMarco (1979). Structured Analysis and System Specification. Prentice Hall.
Edward Yourdon (1999). Modern Structured Analysis, Yourdon Press Computing Series, 1999,
Edsger W. Dijkstra "On a somewhat disappointing correspondence", EWD1009-0, 25 May 1987 full text
„Shell Command Language”. pubs.opengroup.org.
Jan A. Bergstra; A. Ponse, D.J.C. Staudt (2010). „Short-circuit logic”. arXiv:1010.3674  [cs.LO].
ISO/IEC 9899 standard, sections 6.2.5, 6.3.1.2, 6.5 and 7.16.
„Beckhoff Information System - English”. infosys.beckhoff.com. Приступљено 2021-08-16.
„Beckhoff Information System - English”. infosys.beckhoff.com. Приступљено 2021-08-16.
„Referential Transparency, Definiteness and Unfoldability” (PDF). Itu.dk. Приступљено 2013-08-24.
Wasserman, Louis. „Java - What are the cases in which it is better to use unconditional AND (& instead of &&)”. Stack Overflow.
J. Darlinton; M. Ghanem; H. W. To (1993), „Structured Parallel Programming”, In Programming Models for Massively Parallel Computers., IEEE Computer Society Press: 160—169, CiteSeerX 10.1.1.37.4610  , ISBN 0-8186-4900-3, S2CID 15265646, doi:10.1109/PMMP.1993.315543
Cobb, Gary W. (1978). „A measurement of structure for unstructured programming languages”. ACM SIGSOFT Software Engineering Notes. 3 (5): 140—147. ISSN 0163-5948. doi:10.1145/953579.811114  .

Spoljašnje veze

BPStruct - A tool to structure concurrent systems (programs, process models)

[1] Clark, Leslie B. Wilson, Robert G.; Robert, Clark (2000). Comparative programming languages (3rd изд.). Harlow, England: Addison-Wesley. стр. 20. ISBN 9780201710120. Приступљено 25. 11. 2015.

[2] Bohm, Corrado; Giuseppe Jacopini (maj 1966). „Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules” (PDF). Communications of the ACM. 9 (5): 366—371. CiteSeerX 10.1.1.119.9119  . S2CID 10236439. doi:10.1145/355592.365646. Архивирано из оригинала (PDF) 23. 09. 2015. г. Приступљено 11. 04. 2019.

[3] Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second изд.). USA: Elsevier. стр. 209. ISBN 0-12-238452-0.

[4] Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second изд.). USA: Elsevier. стр. 208,262. ISBN 0-12-238452-0.

[5] B. Jack Copeland ed. , The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK. Turing, Alan Mathison (2004). The Essential Turing. Oxford University Press. ISBN 978-0-19-825079-1. . Contains the Turing papers plus a draft letter to Emil Post re his criticism of "Turing's convention", and Donald W. Davies' Corrections to Turing's Universal Computing Machine

[6] Martin Davis (ed.). (1965), The Undecidable, Raven Press, Hewlett, NY.

[7] Emil Post (1936), "Finite Combinatory Processes—Formulation 1", Journal of Symbolic Logic, 1, 103–105, 1936. Reprinted in The Undecidable pp. 289ff.

[8] Emil Post. „Recursive Unsolvability of a Problem of Thue”. Journal of Symbolic Logic. 12: 1—11. 1947. JSTOR 2267170. S2CID 30320278. doi:10.2307/2267170. . Reprinted in The Undecidable pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on Turing's first and second proofs.

[FOOTNOTEDijkstra1968-9] Dijkstra 1968.

[10] Plauger, P. J. (12. 2. 1993). Programming on Purpose, Essays on Software Design (1st изд.). Prentice-Hall. стр. 25. ISBN 978-0-13-721374-0.

[11] DLS • Donald Knuth • All Questions Answered. YouTube (на језику: енглески). University of Waterloo. 15. 11. 2018. 48 мин. Приступљено 24. 7. 2022.

[12] Donald E. Knuth (децембар 1974). „Structured programming with go to statements” (PDF). Computing Surveys. 6 (4): 261—301. S2CID 207630080. doi:10.1145/356635.356640. Архивирано из оригинала (PDF) 2013-10-23. г.

[13] „Archived copy” (PDF). Архивирано из оригинала (PDF) 2020-08-01. г. Приступљено 2018-03-24.

[14] In EWD1308, „What led to "Notes on Structured Programming"”. , dated 10 June 2001, Dijkstra writes, "Apparently, IBM did not like the popularity of my text; it stole the term "Structured Programming" and under its auspices Harlan D. Mills trivialized the original concept to the abolishment of the goto statement."

[15] Frank Rubin (март 1987). „"GOTO Considered Harmful" Considered Harmful” (PDF). Communications of the ACM. 30 (3): 195—196. S2CID 6853038. doi:10.1145/214748.315722. Архивирано из оригинала (PDF) 2009-03-20. г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]