Структурирано програмирање

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) и понављања (while и for), блоковских структура и подрутина. Едсгер Дајкстра је 1968. године сковао термин „структурирано програмирање”.

Структурирано програмирање је настало 70-их година, а њему је претходило композитно програмирање.^[1] Чињеница да није постојао софтвер, који би могао да искористи новонастале велике могућности хардвера довела је до прве софтверске кризе. Године 1968. холандски информатичар Едсхер Дајкстра написао је чланак „Go to наредба се сматра штетном”, где излаже резултате свог истраживања, на основу којих је закључио да је број грешака у софтверу пропорционалан броју употреба goto наредбе. Године 1969, коначно је створен програмски језик који је омогућио писање програма без употребе гото наредбе. То је био Паскал, који је створио Никлаус Вирт. Фактори који су допринели популарности и широком прихваћању овог приступа, прво у академским круговима и касније међу практичарима, укључују откриће онога што је сада познато као теорема структурираног програма из 1966. године.^[2] Дајкстра, Хоаре и Дахл су написали књигу „Структурирано програмирање”, у којој се налазе и чланци који се баве решавањем проблема елиминисања употребе goto наредбе.

Данас, под стуктурираним програмирањем подразумева скуп техника за развијање програмских модела који користе строго дефинисане управљачке структуре и структуре података. Структурирано програмирање се најчешће користи са одступањима која омогућавају јасније програме у неким посебним случајевима, као што је обрада изузетака.

Правилни програми

Циљна класа програма назива се правилни програм. Под овим подразумевамо програм који задовољава следећа три услова:

има тачно једну улазну грану
има једну излазну грану
кроз сваки чвор пролази се бар једном од улаза до излаза

Функција прва два услова јесте да се цео правилни програм може заменити тачно једним чвором, а функција трећег јесте да елиминише могућност бесконачних циклуса изолованих делова програма.

Структурна теорема и програмирање без гото

Посебна база структурних програма, коју чине секвенца, итерација типа "while-do" и селекција типа "if-then-else" јесте база помоћу које се може извести сваки програм и на основу које можемо направити неке друге базе које су нам потребне.

1966. године C. Боехм и Г. Јацопини су извели структурну теорему која показује да се свеки правилан програм може остварити суперпозицијом ове три структуре (може се остварити без употребе скокова), што је било кључно за решавање проблема, који су тражили увођење структурираних програма.

Елементи

Контролне структуре

Према теореми структурираног програма, сматра се да се сви програми састоје од контролних структура:

„Секвенца”; уређени изјаве или потпрограми извршени у низу.
„Селекција”; једна или више изјава се извршава зависно од стања програма. Ово се обично изражава са резервисаним речима као што су if..then..else..endif.
„Итерација”; израз или блок се извршава док програм не досегне одређено стање, или су операције примењене на сваки елемент колекције. Ово се обично изражава са резервисаним речима као што су while, repeat, for или do..until. Често се препоручује да свака петља има само једну улазну тачку (у изворном структуралном програмирању такође само једну излазну тачку, а неколико језика то намеће).
„Рекурзија”; изјава се извршава поновљеним позивањем док се не испуне услови раскида. Иако су у пракси сличне итеративним петљама, рекурзивне петље могу бити рачунски делотворније и различито се имплементирају као каскадни стек.

Подрутине

Подрутине су јединице које се могу позвати, као што су процедуре, функције, методе или потпрограми. Подрутине омогућавају позивање секвенце програмских линија појединачном изјавом.

Блокови

Блокови се користе како би се омогућило да се групе изјава третирају као да су једна изјава. Блоковно структурирани језици имају синтаксу за ограђујуће структуре на неки формалан начин, као што је if изјава ограђена са if..fi у језику АЛГОЛ 68, или секција кода ограђена са BEGIN..END у PL/I и Паскалу, увлачење знаком размака као у Пајтону - или витичасте заграде {...} у C језику и многим каснијим језицима.

Историја

Теоријска основа

Теорема структурираног програма пружа теоријску основу структурираног програмирања. У њему се наводи да су три начина комбиновања програма — секвенцирање, селекција и итерација — довољна за изражавање било које израчунљиве функције.^[3]^[4] Ово запажање није потекло од покрета структурираног програмирања; ове структуре су довољне да опишу циклус инструкција централне процесорске јединице, као и рад Турингове машине.^[5]^[6]^[7]^[8] Стога, процесор увек извршава „структурирани програм“ у овом смислу, чак и ако инструкције које чита из меморије нису део структурираног програма. Међутим, аутори обично приписују резултат раду из 1966. Бема и Јакопинија, вероватно зато што је Дијкстра сам цитирао овај рад.^[9] Теорема структурираног програма не говори о томе како написати и анализирати корисно структуриран програм. Ове теме су разматране током касних 1960-их и раних 1970-их, уз велике доприносе Дијкстре, Роберта V. Флојда, Тонија Хора, Оле-Јохана Дала и Дејвида Гриса.

Дебата

П. Џ. Плогер, рани усвојилац структурираног програмирања, описао је своју реакцију на теорему структурираног програма:

Ми, преобраћеници, махали смо овом занимљивом вести пред носом нереконструисаних програмера на асемблерском језику који су непрестано извлачили уврнуте делове логике и говорили, 'Кладим се да не могу да структуришем ово.' Ни докази Бема и Јакопинија, нити наши поновљени успеси у писању структурираног кода нису их придобили ни један дан раније него што су они сами били спремни да се увере.^[10]

Доналд Кнут је прихватио принцип да програми морају бити написани имајући на уму доказљивост, али се није сложио са укидањем изјаве ГОТО, и од 2018. је наставио да је користи у својим програмима.^[11] У свом раду из 1974. године, „Структурирано програмирање са Гото изјавама“,^[12] дао је примере у којима је веровао да директан скок води ка јаснијем и ефикаснијем коду без жртвовања доказивости. Кнут је предложио лабавије структурно ограничење: требало би да буде могуће нацртати дијаграм тока програма са свим гранама напред на левој страни, са свим гранама уназад на десној страни и ниједним гранама које се међусобно укрштају. Многи од оних који познају компајлере и теорију графова заговарали су дозвољавање само редуцибилних графова тока.^[13]

Теоретичари структурираног програмирања стекли су главног савезника 1970-их након што је истраживач ИБМ-а Харлан Милс применио своје тумачење теорије структурираног програмирања на развој система индексирања за истраживачки фајл Њујорк Тајмса. Тај пројекат је био велики инжењерски успех, а менаџери других компанија су га цитирали у прилог усвајању структурираног програмирања, иако је Дијкстра критиковао начине на које се Милсова интерпретација разликује од објављеног рада.^[14]

Године 1987, још увек је било могуће покренути питање структурираног програмирања у часопису о рачунарским наукама. Френк Рубин је то учинио те године са отвореним писмом под насловом „'ГОТО сматрано штетним' сматра се штетним“.^[15] Уследиле су бројне примедбе, укључујући одговор Дијкстре који је оштро критиковао Рубина и уступке које су други писци чинили када су му одговарали.

Референце

^ Цларк, Леслие Б. Wилсон, Роберт Г.; Роберт, Цларк (2000). Цомпаративе программинг лангуагес (3рд изд.). Харлоw, Енгланд: Аддисон-Wеслеy. стр. 20. ИСБН 9780201710120. Приступљено 25. 11. 2015.
^ Бохм, Цоррадо; Гиусеппе Јацопини (мај 1966). „Флоw Диаграмс, Туринг Мацхинес анд Лангуагес wитх Онлy Тwо Форматион Рулес” (ПДФ). Цоммуницатионс оф тхе АЦМ. 9 (5): 366—371. ЦитеСеерX 10.1.1.119.9119  . С2ЦИД 10236439. дои:10.1145/355592.365646. Архивирано из оригинала (ПДФ) 23. 09. 2015. г. Приступљено 11. 04. 2019.
^ Ендертон, Херберт (2002). А Матхематицал Интродуцтион то Логиц (Сецонд изд.). УСА: Елсевиер. стр. 209. ИСБН 0-12-238452-0.
^ Ендертон, Херберт (2002). А Матхематицал Интродуцтион то Логиц (Сецонд изд.). УСА: Елсевиер. стр. 208,262. ИСБН 0-12-238452-0.
^ Б. Јацк Цопеланд ед. , Тхе Ессентиал Туринг: Семинал Wритингс ин Цомпутинг, Логиц, Пхилосопхy, Артифициал Интеллигенце, анд Артифициал Лифе плус Тхе Сецретс оф Енигма, Цларендон Пресс (Оxфорд Университy Пресс), Оxфорд УК. Туринг, Алан Матхисон (2004). Тхе Ессентиал Туринг. Оxфорд Университy Пресс. ИСБН 978-0-19-825079-1. . Цонтаинс тхе Туринг паперс плус а драфт леттер то Емил Пост ре хис цритицисм оф "Туринг'с цонвентион", анд Доналд W. Давиес' Цоррецтионс то Туринг'с Универсал Цомпутинг Мацхине
^ Мартин Давис (ед.). (1965), Тхе Ундецидабле, Равен Пресс, Хеwлетт, НY.
^ Емил Пост (1936), "Фините Цомбинаторy Процессес—Формулатион 1", Јоурнал оф Сyмболиц Логиц, 1, 103–105, 1936. Репринтед ин Тхе Ундецидабле пп. 289фф.
^ Емил Пост. „Рецурсиве Унсолвабилитy оф а Проблем оф Тхуе”. Јоурнал оф Сyмболиц Логиц. 12: 1—11. 1947. ЈСТОР 2267170. С2ЦИД 30320278. дои:10.2307/2267170. . Репринтед ин Тхе Ундецидабле пп. 293фф. Ин тхе Аппендиx оф тхис папер Пост цомментс он анд гивес цоррецтионс то Туринг'с папер оф 1936–1937. Ин партицулар сее тхе фоотнотес 11 wитх цоррецтионс то тхе универсал цомпутинг мацхине цодинг анд фоотноте 14 wитх цомментс он Туринг'с фирст анд сецонд проофс.
^ Дијкстра 1968.
^ Плаугер, П. Ј. (12. 2. 1993). Программинг он Пурпосе, Ессаyс он Софтwаре Десигн (1ст изд.). Прентице-Халл. стр. 25. ИСБН 978-0-13-721374-0.
^ ДЛС • Доналд Кнутх • Алл Qуестионс Ансwеред. YоуТубе (на језику: енглески). Университy оф Wатерлоо. 15. 11. 2018. 48 мин. Приступљено 24. 7. 2022.
^ Доналд Е. Кнутх (децембар 1974). „Струцтуред программинг wитх го то статементс” (ПДФ). Цомпутинг Сурвеyс. 6 (4): 261—301. С2ЦИД 207630080. дои:10.1145/356635.356640. Архивирано из оригинала (ПДФ) 2013-10-23. г.
^ „Арцхивед цопy” (ПДФ). Архивирано из оригинала (ПДФ) 2020-08-01. г. Приступљено 2018-03-24.
^ Ин ЕWД1308, „Wхат лед то "Нотес он Струцтуред Программинг"”. , датед 10 Јуне 2001, Дијкстра wритес, "Аппарентлy, ИБМ дид нот лике тхе популаритy оф мy теxт; ит столе тхе терм "Струцтуред Программинг" анд ундер итс ауспицес Харлан D. Миллс тривиализед тхе оригинал цонцепт то тхе аболисхмент оф тхе гото статемент."
^ Франк Рубин (март 1987). „"ГОТО Цонсидеред Хармфул" Цонсидеред Хармфул” (ПДФ). Цоммуницатионс оф тхе АЦМ. 30 (3): 195—196. С2ЦИД 6853038. дои:10.1145/214748.315722. Архивирано из оригинала (ПДФ) 2009-03-20. г.

Литература

Душан Малбашки: Програмски језици и струкуре података, Нови Сад
Едсгер Дијкстра, Нотес он Струцтуред Программинг, пг. 6
Бöхм, C.; Јацопини, Г. (1966). „Флоw диаграмс, Туринг мацхинес анд лангуагес wитх онлy тwо форматион рулес”. Цоммуницатионс оф тхе АЦМ. 9 (5): 366—371. С2ЦИД 10236439. дои:10.1145/355592.365646.
Дијкстра, Едсгер W. (1968). „Леттерс то тхе едитор: Го то статемент цонсидеред хармфул” (ПДФ). Цоммуницатионс оф тхе АЦМ. 11 (3): 147—148. С2ЦИД 17469809. дои:10.1145/362929.362947.
Мицхаел А. Јацксон, Принциплес оф Програм Десигн, Ацадемиц Пресс, Лондон, 1975.
О.-Ј. Дахл, Е. W. Дијкстра, C. А. Р. Хоаре Струцтуред Программинг, Ацадемиц Пресс, Лондон, . 1972. ИСБН 978-0-12-200550-3. Недостаје или је празан параметар |титле= (помоћ)
- тхис волуме инцлудес ан еxпандед версион оф тхе Нотес он Струцтуред Программинг, абове, инцлудинг ан еxтендед еxампле оф усинг тхе струцтуред аппроацх то девелоп а бацктрацкинг алгоритхм то солве тхе 8 Qуеенс проблем.
- а пдф версион ис ин тхе АЦМ Цлассиц Боокс Сериес
- Ноте тхат тхе тхирд цхаптер оф тхис боок, бy Дахл, десцрибес ан аппроацх wхицх ис еасилy рецогнизед ас Објецт Ориентед Программинг. Ит цан бе сеен ас анотхер wаy то "усефуллy струцтуре" а програм то аид ин схоwинг тхат ит ис цоррецт.
Елдер, Матт; Јацксон, Стеве; Либлит, Бен (2008). Цоде Сандwицхес (ПДФ) (Технички извештај). Университy оф Wисцонсин–Мадисон. 1647, абстрацт
Сарах Броокс (1981). "Струцтуре Цхартс анд Басиц Программинг". ин: МАТYЦ Јоурнал, в15 н2 п. 107-112 Спринг 1981.
Том ДеМарцо (1979). Струцтуред Аналyсис анд Сyстем Специфицатион. Прентице Халл.
Едwард Yоурдон (1999). Модерн Струцтуред Аналyсис, Yоурдон Пресс Цомпутинг Сериес, 1999,
Едсгер W. Дијкстра "Он а сомеwхат дисаппоинтинг цорреспонденце", ЕWД1009-0, 25 Маy 1987 фулл теxт
„Схелл Цомманд Лангуаге”. пубс.опенгроуп.орг.
Јан А. Бергстра; А. Понсе, D.Ј.C. Стаудт (2010). „Схорт-цирцуит логиц”. арXив:1010.3674  [цс.ЛО].
ИСО/ИЕЦ 9899 стандард, сецтионс 6.2.5, 6.3.1.2, 6.5 анд 7.16.
„Бецкхофф Информатион Сyстем - Енглисх”. инфосyс.бецкхофф.цом. Приступљено 2021-08-16.
„Бецкхофф Информатион Сyстем - Енглисх”. инфосyс.бецкхофф.цом. Приступљено 2021-08-16.
„Референтиал Транспаренцy, Дефинитенесс анд Унфолдабилитy” (ПДФ). Иту.дк. Приступљено 2013-08-24.
Wассерман, Лоуис. „Јава - Wхат аре тхе цасес ин wхицх ит ис беттер то усе унцондитионал АНД (& инстеад оф &&)”. Стацк Оверфлоw.
Ј. Дарлинтон; M. Гханем; Х. W. То (1993), „Струцтуред Параллел Программинг”, Ин Программинг Моделс фор Массивелy Параллел Цомпутерс., ИЕЕЕ Цомпутер Социетy Пресс: 160—169, ЦитеСеерX 10.1.1.37.4610  , ИСБН 0-8186-4900-3, С2ЦИД 15265646, дои:10.1109/ПММП.1993.315543
Цобб, Гарy W. (1978). „А меасуремент оф струцтуре фор унструцтуред программинг лангуагес”. АЦМ СИГСОФТ Софтwаре Енгинееринг Нотес. 3 (5): 140—147. ИССН 0163-5948. дои:10.1145/953579.811114  .

Спољашње везе

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

[1] Цларк, Леслие Б. Wилсон, Роберт Г.; Роберт, Цларк (2000). Цомпаративе программинг лангуагес (3рд изд.). Харлоw, Енгланд: Аддисон-Wеслеy. стр. 20. ИСБН 9780201710120. Приступљено 25. 11. 2015.

[2] Бохм, Цоррадо; Гиусеппе Јацопини (мај 1966). „Флоw Диаграмс, Туринг Мацхинес анд Лангуагес wитх Онлy Тwо Форматион Рулес” (ПДФ). Цоммуницатионс оф тхе АЦМ. 9 (5): 366—371. ЦитеСеерX 10.1.1.119.9119  . С2ЦИД 10236439. дои:10.1145/355592.365646. Архивирано из оригинала (ПДФ) 23. 09. 2015. г. Приступљено 11. 04. 2019.

[3] Ендертон, Херберт (2002). А Матхематицал Интродуцтион то Логиц (Сецонд изд.). УСА: Елсевиер. стр. 209. ИСБН 0-12-238452-0.

[4] Ендертон, Херберт (2002). А Матхематицал Интродуцтион то Логиц (Сецонд изд.). УСА: Елсевиер. стр. 208,262. ИСБН 0-12-238452-0.

[5] Б. Јацк Цопеланд ед. , Тхе Ессентиал Туринг: Семинал Wритингс ин Цомпутинг, Логиц, Пхилосопхy, Артифициал Интеллигенце, анд Артифициал Лифе плус Тхе Сецретс оф Енигма, Цларендон Пресс (Оxфорд Университy Пресс), Оxфорд УК. Туринг, Алан Матхисон (2004). Тхе Ессентиал Туринг. Оxфорд Университy Пресс. ИСБН 978-0-19-825079-1. . Цонтаинс тхе Туринг паперс плус а драфт леттер то Емил Пост ре хис цритицисм оф "Туринг'с цонвентион", анд Доналд W. Давиес' Цоррецтионс то Туринг'с Универсал Цомпутинг Мацхине

[6] Мартин Давис (ед.). (1965), Тхе Ундецидабле, Равен Пресс, Хеwлетт, НY.

[7] Емил Пост (1936), "Фините Цомбинаторy Процессес—Формулатион 1", Јоурнал оф Сyмболиц Логиц, 1, 103–105, 1936. Репринтед ин Тхе Ундецидабле пп. 289фф.

[8] Емил Пост. „Рецурсиве Унсолвабилитy оф а Проблем оф Тхуе”. Јоурнал оф Сyмболиц Логиц. 12: 1—11. 1947. ЈСТОР 2267170. С2ЦИД 30320278. дои:10.2307/2267170. . Репринтед ин Тхе Ундецидабле пп. 293фф. Ин тхе Аппендиx оф тхис папер Пост цомментс он анд гивес цоррецтионс то Туринг'с папер оф 1936–1937. Ин партицулар сее тхе фоотнотес 11 wитх цоррецтионс то тхе универсал цомпутинг мацхине цодинг анд фоотноте 14 wитх цомментс он Туринг'с фирст анд сецонд проофс.

[FOOTNOTEDijkstra1968-9] Дијкстра 1968.

[10] Плаугер, П. Ј. (12. 2. 1993). Программинг он Пурпосе, Ессаyс он Софтwаре Десигн (1ст изд.). Прентице-Халл. стр. 25. ИСБН 978-0-13-721374-0.

[11] ДЛС • Доналд Кнутх • Алл Qуестионс Ансwеред. YоуТубе (на језику: енглески). Университy оф Wатерлоо. 15. 11. 2018. 48 мин. Приступљено 24. 7. 2022.

[12] Доналд Е. Кнутх (децембар 1974). „Струцтуред программинг wитх го то статементс” (ПДФ). Цомпутинг Сурвеyс. 6 (4): 261—301. С2ЦИД 207630080. дои:10.1145/356635.356640. Архивирано из оригинала (ПДФ) 2013-10-23. г.

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

[14] Ин ЕWД1308, „Wхат лед то "Нотес он Струцтуред Программинг"”. , датед 10 Јуне 2001, Дијкстра wритес, "Аппарентлy, ИБМ дид нот лике тхе популаритy оф мy теxт; ит столе тхе терм "Струцтуред Программинг" анд ундер итс ауспицес Харлан D. Миллс тривиализед тхе оригинал цонцепт то тхе аболисхмент оф тхе гото статемент."

[15] Франк Рубин (март 1987). „"ГОТО Цонсидеред Хармфул" Цонсидеред Хармфул” (ПДФ). Цоммуницатионс оф тхе АЦМ. 30 (3): 195—196. С2ЦИД 6853038. дои:10.1145/214748.315722. Архивирано из оригинала (ПДФ) 2009-03-20. г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]