Компилятор және бағдарлама оптимизациясы

Компьютерлік командалардың орындалу реті

Компьютерлік командалардың орындалу реті: бақылау ағыны, императивтік бағдарламалау, командалар тізбегі, блоклар және лексикалық ауқым туралы ақпарат.

9 мин оқу

100%

Дереккөз: Control flow — Wikipedia

Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.

Мазмұны

Кіріспе

Компьютерлік командалардың орындалу реті

Компьютер ғылымында басқару ағыны (немесе басқарудың ағыны) — бұл императивті бағдарламаның жеке нұсқаулары, командалары немесе функция шақырулары орындалатын немесе бағаланатын рет. Нақты басқару ағынына жасалған баса назар, императивті бағдарламалау тілін декларативті бағдарламалау тілінен ерекшелендіреді. Императивті бағдарламалау тілінде басқару ағыны — екі немесе одан көп жолдың қайсысын таңдауды қамтамасыз ететін нұсқау. Қатаң емес функционалдық тілдерде функциялар мен тіл құрылымдары сондай-ақ нәтижеге жету үшін бар, бірақ олар көбінесе басқару ағыны операторлары деп аталмайды. Нұсқаулар жинағы өз кезегінде әдетте блок ретінде құрылады, ол топтастырудан басқа лексикалық кеңістікті де анықтайды. Үзілістер мен сигналдар — бұл төменгі деңгейдегі механизмдер, олар басқару ағынын субрутинаға ұқсас түрде өзгерте алады, бірақ көбінесе сыртқы күштерге немесе оқиғаларға жауап ретінде пайда болады (асинхронды түрде бола алады), басқару ағыны операторын орындаудың орнына. Машина тілі немесе ассемблер тілі деңгейінде басқару ағыны командалары әдетте бағдарлама санаушыны өзгерту арқылы жұмыс істейді. Кейбір орталық процессорлар (CPU) үшін қол жетімді басқару ағыны командалары шартты немесе шартсыз тармақтау командалары, сондай-ақ секірулер болып табылады.

Ішкі бағдарламалар

Субпрограммалар терминологиясы әр түрлі; оларды процедуралар, функциялар (әсіресе нәтижелер қайыратын болса), немесе әдістер (әсіресе сыныптарға немесе типтік сыныптарға жатса) деп те атауға болады. 1950 жылдары компьютерлердің жадысы қазіргі стандарттармен салыстырғанда өте шағын болғандықтан, бағдарламаның көлемін азайту мақсатында суброграммалар негізгі құрал болды. Кодтың бір бөлігі бір рет жазылып, бағдарламаның әртүрлі бөлімдерінде қайта-қайта қолданылатын. Бүгінде суброграммалар көбінесе бағдарламаны құрылымдырақ етуге, мысалы, белгілі бір алгоритмді бөліп шығару немесе деректерге қолжеткізу әдісін жасыру үшін қолданылады. Егер бір бағдарлама үстінде көптеген бағдарламашы жұмыс істесе, суброграммалар – жұмысты бөлуге көмектесетін модульдік құрылымның бір түрі.

Тізбе

Құрылымдық бағдарламалауда, бір-бірінше тікелей орындалатын командалардың реттілігі негізгі басқару құрылымдарының бірі саналады және итерация, рекурсия және таңдау сияқты бағдарлама құрудың негізгі элементтерімен бірге қолданылады.

Минималды құрылымдық басқару ағыны

1966 жылдың мамырында Бём мен Якопини ACM Communications журналында кез келген `goto` операторы бар бағдарламаны, тек таңдау (IF THEN ELSE) және циклдарды (WHILE condition DO xxx) пайдаланатын `goto` операторы жоқ түріне түрлендіруге болатынын көрсеткен мақала жариялады, бұл процесте кодтың қайталануы және/немесе Бульдік айнымалылардың (true/false флагтары) қосылуы мүмкін. Кейінгі авторлар таңдау операторларын циклдармен (және одан да көп Бульдік айнымалылармен) алмастыруға болатынын көрсетті. Мұндай минимализм мүмкін болғанымен, оның міндетті түрде қажет екенін білдірмейді; компьютерлер теориялық тұрғыдан тек бір машиналық нұсқауды қажет етеді (бір санды екіншіден азайту және нәтижесі теріс болса, басқаруды өзгерту), бірақ практикалық компьютерлерде ондаған, тіпті жүздеген машиналық нұсқаулар бар. Бём мен Якопинидің мақаласы барлық бағдарламаларды `goto` операторларынсыз жасауға болатынын көрсетті. Басқа зерттеулер көрсеткендей, бір кіріс және бір шығыс нүктесі бар басқару құрылымдарын түсіну, кез келген басқа формаға қарағанда әлдеқайда оңай, себебі оларды басқару ағынын бұзбай, кез келген жерде оператор ретінде қолдануға болады. Басқаша айтқанда, оларды құрастыру оңай. (Соңғы уақыттардағы дамулар, мысалы қатаң емес бағдарламалау тілдері және соңғы кезде құрастырылатын бағдарламалық транзакциялар осы стратегияны жалғастырып, бағдарламалардың компоненттерін одан да еркін құрастыруға мүмкіндік берді.) Кейбір ғалымдар Бём–Якопини нәтижесіне қатысты пуристтік көзқарас ұстанады және циклдердің ортасынан `break` және `return` сияқты операторлардың қолданылуы жаман тәжірибе деп санайды, себебі олар Бём–Якопини дәлелінде қажет емес, сондықтан барлық циклдардың бір шығу нүктесі болуы керек деп талап етеді. Бұл пуристтік көзқарас Паскаль тілінде (1968–1969 жылдары жасалған) көрініс тапқан, ол 1990-шы жылдардың ортасына дейін академиялық ортада кіріспе бағдарламалауды оқыту үшін ең қолайлы құрал саналды. Бём–Якопини теоремасын тікелей қолдану құрылымдық схемаға қосымша жергілікті айнымалыларды енгізуге және кодтың қайталануына әкелуі мүмкін. Паскаль тілі осы екі проблеманың да әсеріне ұшырайды және Эрик С. Робертстің келтірген эмпирикалық зерттеулеріне сәйкес, студент-бағдарламалаушылар Паскальде бірнеше қарапайым мәселелерді шешуде қиындықтарға тап болды, соның ішінде массивте элементті іздеуге арналған функцияны жазу. Робертс келтірген Генри Шапироның 1980 жылғы зерттеуі көрсеткендей, тек Паскальдің ұсынған басқару құрылымдарын пайдаланып, субъектілердің тек 20% дұрыс шешім берді, ал циклдің ортасынан `return` операторын пайдалануға рұқсат етілген жағдайда ешбір субъект дұрыс емес код жазған жоқ. Функционалдық бағдарламалау тілдерінде, мысалы, Хаскелл және Схема, рекурсивті және итеративтік процестер синтаксистік циклдік конструкциялардың орнына құйрық рекурсивті процедуралармен бейнеленеді.

In May 1966, Böhm and Jacopini published an article in Communications of the ACM which showed that any program with gotos could be transformed into a goto free form involving only choice (IF THEN ELSE) and loops (WHILE condition DO xxx), possibly with duplicated code and/or the addition of Boolean variables (true/false flags). Later authors showed that choice can be replaced by loops (and yet more Boolean variables). That such minimalism is possible does not mean that it is necessarily desirable; after all, computers theoretically need only one machine instruction (subtract one number from another and branch if the result is negative), but practical computers have dozens or even hundreds of machine instructions. What Böhm and Jacopini's article showed was that all programs could be goto free. Other research showed that control structures with one entry and one exit were much easier to understand than any other form, mainly because they could be used anywhere as a statement without disrupting the control flow. In other words, they were composable. (Later developments, such as non strict programming languages – and more recently, composable software transactions – have continued this strategy, making components of programs even more freely composable.) Some academics took a purist approach to the Böhm–Jacopini result and argued that even instructions like break and return from the middle of loops are bad practice as they are not needed in the Böhm–Jacopini proof, and thus they advocated that all loops should have a single exit point. This purist approach is embodied in the language Pascal (designed in 1968–1969), which up to the mid 1990s was the preferred tool for teaching introductory programming in academia. The direct application of the Böhm–Jacopini theorem may result in additional local variables being introduced in the structured chart, and may also result in some code duplication. Pascal is affected by both of these problems and according to empirical studies cited by Eric S. Roberts, student programmers had difficulty formulating correct solutions in Pascal for several simple problems, including writing a function for searching an element in an array. A 1980 study by Henry Shapiro cited by Roberts found that using only the Pascal provided control structures, the correct solution was given by only 20% of the subjects, while no subject wrote incorrect code for this problem if allowed to write a return from the middle of a loop. In functional programming languages, such as Haskell and Scheme, both recursive and iterative processes are expressed with tail recursive procedures instead of looping constructs that are syntactic.

Жалпы қайталау

C-тің for операторы және Common Lisp-тің do түрі сияқты жалпы итерациялық конструкцияларды жоғарыда аталған циклдардың кез келгенін, сондай-ақ параллель түрде бірнеше жиынтықты қарап шығу сияқты басқа да жағдайларда қолдануға болады. Нақтырақ цикл конструкциясын қолдану мүмкіндігі болғанда, оны жалпы итерациялық конструкциядан көбінесе артық көруге болады, себебі ол өрнектің мақсатын көбінесе анықтап көрсетеді.

Шексіз циклдер

Шексіз циклдар бағдарлама сегментінің мәңгілікке дейін немесе қате сияқты ерекше жағдай туғанға дейін қайталануын қамтамасыз ету үшін қолданылады. Мысалы, оқиғаларға негізделген бағдарлама (сервер сияқты) оқиғалар пайда болатын кезде оларды өңдеп, мәңгілік циклмен жұмыс істеуі керек, және оператор процесті тоқтатқанда ғана тоқтатылады. Шексіз циклдар басқа басқару ағыны құрылымдарын пайдаланып іске асырылуы мүмкін. Көбінесе, құрылымдалмаған бағдарламалауда бұл кері секіру (goto) болып табылады, ал құрылымдалған бағдарламалауда бұл шексіз цикл (while loop), шартты жою арқылы немесе оны нақты түрде `true` деп белгілеу арқылы, мысалы `while (true)` арқылы ешқашан аяқтамайтындай етіп орнатылады. Кейбір тілдер шексіз циклдар үшін арнайы құрылымдарды ұсынады, әдетте, шексіз циклден шартты алып тастау арқылы. Мысалдарға Ada (`loop end loop`), Fortran (`DO END DO`), Go (`for {}`), және Ruby (`loop do end`) жатады. Көбінесе, шексіз цикл шартты басқарылатын циклдегі бағдарламалау қатесінен туындайды, онда цикл шарты цикл ішінде ешқашан өзгермейтін айнымалыларды пайдаланады.

Келесі қайталаумен жалғастыру

Кейде циклдің ішінде цикл денесінің қалған бөлігін өткіріп, циклдің келесі итерациясымен жалғастыру қажеттігі туындайды. Кейбір бағдарламалау тілдері `continue` (көптеген тілдерде), `skip`, `cycle` (Fortran) немесе `next` (Perl және Ruby) сияқты операторларды ұсынады, олар осы мүмкіндікті іске асырады. Бұл ішкі цикл денесін мерзімінен бұрын тоқтатып, келесі итерацияны әдеттегідей бастауға мүмкіндік береді. Егер итерация циклдың соңғысы болса, онда цикл толығымен ертерек аяқталады.

Редо ток қайталау

Кейбір тілдер, мысалы Perl және Ruby, ағымдағы итерацияны басынан қайтадан бастауға мүмкіндік беретін "қайталау" операторына ие.

Қайта бастау

Ruby-де циклді бастапқы итерациядан қайтадан бастайтын қайталау операторы бар.

Бұраулардың нұсқалары мен инварианттары

Цикл түрлері мен инварианттары циклдардың дұрыстығын көрсету үшін қолданылады. Нақтырақ айтқанда, цикл түрі – бастапқы теріс емес мәні бар бүтін сан өрнегі. Бұл түрдің мәні әр цикл итерациясында кемуі керек, бірақ цикл дұрыс орындалғанда теріс болмауы керек. Цикл түрлері циклдың аяқталуын қамтамасыз етуге пайдаланылады. Цикл инварианты – бұл циклдың бірінші итерациясынан бұрын шын болып, әр итерациядан кейін де шын болып қалатын шарт. Осыдан цикл дұрыс аяқталғанда, шығу шарты да, цикл инварианты да орындалады деген қорытынды шығады. Цикл инварианттары циклдың кезекті итерацияларындағы нақты қасиеттерін бақылау үшін қолданылады. Кейбір бағдарламалау тілдері, мысалы, Eiffel, цикл түрлері мен инварианттарына тікелей қолдау көрсетеді. Ал басқа жағдайларда, қолдау қосымша мүмкіндік ретінде ұсынылады, мысалы, Java-дағы цикл операторлары үшін Java Модельдеу Тілінің спецификациясы.

Loop субтілдігі

Кейбір Lisp диалектілері циклдарды (Loops) сипаттауға арналған кеңейтілген кіші тілді (субтілді) ұсынады. Алғашқы мысалы Interlisp-тің Conversional Lisp нұсқасында кездеседі. Common Lisp мұндай кіші тілді іске асыратын Loop макросын қамтамасыз етеді.

Күлгілік жүйелердің тік сілтеме кестесі

Бағдарламалау тілі шартты цикл ерте шығу циклінің жалғасу қайталап қайталап дұрыстық мүмкіндіктері басталады ортасы соңы санау жинағы жалпы шексіз нұсқасы инвариант Ada массивтері APL терең ұялы C терең ұялы C++ терең ұялы C# терең ұялы COBOL терең ұялы Common Lisp кіріктірілген ғана D Eiffel бір деңгейлі бүтін сан ғана F# FORTRAN 77 бір деңгей Fortran 90 Fortran 95 және одан кейінгі массивтер Haskell Java OCaml PHP Perl Python терең ұялы Rebol бір деңгей Ruby терең ұялы Standard ML Visual Basic NET бір цикл түрі үшін бір цикл түрі үшін бір деңгей PowerShell (тура) осы мақсат үшін шексіз цикл ретінде есептелмейді, өйткені ол арнайы тіл құрылымы емес. C-тің for (init; test; increment) циклы – жалпы цикл конструкциясы, нақты санау циклы емес, бірақ көбінесе осы мақсатта қолданылады. APL, C, C++ және C# тілдерінде белгілер мен goto операторларын қолдану арқылы терең үзілістерге қол жеткізуге болады. PHP 5 нысандарды итерациялау мүмкіндігін қосты. Санау циклін өсу тізімі немесе генератор арқылы итерациялау арқылы симуляциялауға болады, мысалы, Python-ның range функциясы. Терең үзілістерді ерекшеліктерді өңдеу арқылы жүзеге асыруға болады. Арнайы конструкция жоқ, өйткені while функциясын осы үшін қолдануға болады. Арнайы конструкция жоқ, бірақ пайдаланушылар жалпы цикл функцияларын анықтай алады. C++11 стандарты range-based for циклын енгізді. STL-де std::for_each атты шаблондық функция бар, ол STL контейнерлерінде итерациялай алады және әр элемент үшін бірлік функцияны шақырады. Бұл функционалдылық осы контейнерлерде макрос ретінде де құрастырылуы мүмкін. Санаумен басқарылатын циклдеу бүтін сан интервалы бойынша итерациялау арқылы жүзеге асырылады; ерте шығу үшін қосымша шығу шартын қосу арқылы. Eiffel retry резервтелген сөзін қолдайды, бірақ ол цикл басқару үшін емес, ерекшеліктерді өңдеу үшін қолданылады. Java Modeling Language (JML) мінез-құлық интерфейсін сипаттау тілін қажет етеді. Цикл нұсқаларының бүтін сандар болуын талап етеді; трансфинит нұсқалар қолдау көрсетілмейді. D шексіз жинақтарды қолдайды және осы жинақтар бойынша итерациялау мүмкіндігі бар. Бұл үшін арнайы конструкция қажет емес. Терең үзілістерге GO TO және процедураларды қолдану арқылы қол жеткізуге болады. Common Lisp жалпы жинақ түрінің тұжырымдамасынан бұрын пайда болған.

Programming language conditional loop early exit loop continuation redo retry correctness facilities begin middle end count collection general infinite variant invariant Ada arrays APL deep nested C deep nested deep nested C++ deep nested deep nested C# deep nested deep nested COBOL deep nested deep nested Common Lisp builtin only D Eiffel one level integer only F# FORTRAN 77 one level Fortran 90 Fortran 95 and later arrays Haskell Java JavaScript Natural OCaml PHP Perl Python deep nested deep nested Rebol one level Ruby deep nested deep nested Standard ML Visual Basic NET one level per type of loop one level per type of loop PowerShell
while (true) does not count as an infinite loop for this purpose, because it is not a dedicated language structure. C's for (init; test; increment) loop is a general loop construct, not specifically a counting one, although it is often used for that. Deep breaks may be accomplished in APL, C, C++ and C# through the use of labels and gotos. Iteration over objects was added in PHP 5. A counting loop can be simulated by iterating over an incrementing list or generator, for instance, Python's range Deep breaks may be accomplished through the use of exception handling. There is no special construct, since the while function can be used for this. There is no special construct, but users can define general loop functions. The C++11 standard introduced the range based for. In the STL, there is a std::for each template function which can iterate on STL containers and call a unary function for each element. The functionality also can be constructed as macro on these containers. Count controlled looping is effected by iteration across an integer interval; early exit by including an additional condition for exit. Eiffel supports a reserved word retry, however it is used in exception handling, not loop control. Requires Java Modeling Language (JML) behavioral interface specification language. Requires loop variants to be integers; transfinite variants are not supported. D supports infinite collections, and the ability to iterate over those collections. This does not require any special construct. Deep breaks can be achieved using GO TO and procedures. Common Lisp predates the concept of generic collection type.

Құрылымдалған жергілікті емес басқару ағыны

Көптеген бағдарламалау тілдері, әсіресе динамикалық стильдегі бағдарламалауды қолдайтындары, жергілікті емес басқару ағыны құрылымдарын ұсынады. Бұл орындалу ағынының белгілі бір контекстен шығып, бұрыннан белгіленген нүктеде жалғасуына мүмкіндік береді. Шарттар, қателіктер және жалғастырулар – жергілікті емес басқару құрылымдарының үш кең таралған түрі; генераторлар, корутиналар және async кілт сөзі сияқты сирек кездесетін түрлері де бар.

Қадамдаспау

C# 5.0 асинхронды I/O-ны "тікелей стильде" қолдау үшін async кілт сөзін ұсынды.

Генераторлар

Генераторлар, жартылай түйіндемелер деп те аталады, бақылауды тұтынушы әдісіне уақытша беруге мүмкіндік береді, әдетте түйін сөзді (yield сипаттамасы) пайдалана отырып. async түйін сөзі сияқты, бұл "түзу стильде" бағдарламалауды қолдайды.

Корутиндер

Корутиндер - бір-біріне басқаруды беруге қабілетті функциялар. Бұл - жіптерді пайдаланбастан, өзара әрекеттесетін көп тапсырмалылықтың бір түрі. Корутиндерді бағдарламалау тілі жалғастыруларды немесе генераторларды ұсынса, кітапхана ретінде жүзеге асыруға болады, сондықтан корутиндер мен генераторлар арасындағы айырмашылық практикада техникалық мәселе болып табылады.

Жергілікті емес басқару ағыны бойынша тік сілтеме

Бағдарламалау тілдерінің шарттары ерекшеліктер генераторлар/корутиндер асинхронды Ada C C++ C# COBOL Common Lisp D Eiffel Erlang F# Go Haskell Java JavaScript Objective C PHP PL/I Python Rebol Ruby Rust Scala Tcl Visual Basic NET PowerShell

Ұсынылған бақылау құрылымдары

1973 жылы Datamation журналындағы пароди мақаласында Р. Лоуренс Кларк GOTO операторын COMEFROM операторымен алмастыруға болатынын ұсынды және ойын-сауыққа толы мысалдар келтірді. COMEFROM INTERCAL деп аталатын экзотикалық бағдарламалау тілінде іске асырылды. Дональд Кнуттың 1974 жылғы «go to операторларымен құрылымдық бағдарламалау» мақаласы жоғарыда тізілген басқару құрылымдарымен қамтылмаған екі жағдайды анықтады және осы жағдайларды шеше алатын басқару құрылымдарының мысалдары берілді. Олардың пайдалы болуына қарамастан, бұл конструкциялар әлі де кең таралған бағдарламалау тілдеріне енбеді.

Қауіпсіздік

Бағдарламаға шабуыл жасаудың бір жолы – бағдарламаның орындалу ретін өзгерту. Мұндай шабуылдарға қарсы тұру үшін бақылау ағынының сақталуын қамтамасыз ететін әртүрлі техникалар қолданылады, оларға стек канари, буфер асып кетуден қорғау, көлеңкелік стектер және vtable көрсеткішін тексеру жатады.