Порядок выполнения команд в компьютере

Порядок выполнения команд в программировании: управление потоком, императивные и декларативные языки, блоки кода и лексическая область видимости.

10 мин чтения

100%

Источник: Control flow — Wikipedia

Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.

Содержание

Введение

Порядок выполнения компьютерных команд

В информатике, управление потоком (или поток управления) — это порядок, в котором отдельные операторы, инструкции или вызовы функций императивной программы выполняются или вычисляются. Акцент на явном управлении потоком отличает императивный язык программирования от декларативного языка программирования. В императивном языке программирования оператор управления потоком — это оператор, который приводит к выбору одного из двух или более путей выполнения. Для нестрогих функциональных языков существуют функции и языковые конструкции для достижения того же результата, но они обычно не называются операторами управления потоком. Набор операторов, в свою очередь, обычно структурирован как блок, который, помимо группировки, также определяет лексическую область видимости. Прерывания и сигналы — это механизмы низкого уровня, которые могут изменять поток управления аналогично подпрограмме, но обычно возникают в ответ на внешний стимул или событие (которые могут происходить асинхронно), а не в результате выполнения оператора управления потоком. На уровне машинного языка или языка ассемблера инструкции управления потоком обычно работают путем изменения счётчика команд. Для некоторых центральных процессоров (ЦП) единственными доступными инструкциями управления потоком являются условные или безусловные инструкции перехода, также называемые прыжками.

Подпрограммы

Терминология, используемая для обозначения подпрограмм, варьируется: их также могут называть рутинами, процедурами, функциями (особенно если они возвращают результат) или методами (особенно если они принадлежат классам или типам классов). В 1950-х годах объём компьютерной памяти был очень мал по современным меркам, поэтому подпрограммы использовались главным образом для уменьшения размера программ. Блок кода записывался однажды и затем многократно использовался из различных частей программы. Сегодня подпрограммы чаще применяются для повышения структурированности программы, например, путём выделения отдельного алгоритма или скрытия метода доступа к данным. Если над программой работает несколько программистов, подпрограммы служат одним из способов модульности, позволяющим разделить работу.

Последовательность

В структурированном программировании упорядоченная последовательность команд рассматривается как одна из базовых управляющих структур, используемая в качестве строительного блока программ вместе с итерацией, рекурсией и ветвлением.

Минимальный структурированный поток управления

В мае 1966 года Бём и Якопини опубликовали статью в Communications of the ACM, в которой показали, что любую программу с операторами `goto` можно преобразовать в форму, не использующую `goto`, с применением только выбора (IF THEN ELSE) и циклов (WHILE condition DO xxx), возможно, с дублированием кода и/или добавлением булевых переменных (флагов true/false). Позже другие авторы показали, что выбор можно заменить циклами (и ещё большим количеством булевых переменных). Тот факт, что такой минимализм возможен, не означает, что он обязательно желателен; в конце концов, компьютерам теоретически нужна всего одна машинная инструкция (вычитание одного числа из другого и переход, если результат отрицательный), но практические компьютеры имеют десятки или даже сотни машинных инструкций. Статья Бёма и Якопини показала, что все программы могут быть реализованы без использования `goto`. Другие исследования показали, что структуры управления с одним входом и одним выходом гораздо легче понять, чем любые другие формы, главным образом потому, что их можно использовать в любом месте как оператор, не нарушая поток управления. Иными словами, они компонуемы. (Последующие разработки, такие как языки программирования с нестрогой типизацией – и, более недавно, композируемые транзакции программного обеспечения – продолжили эту стратегию, делая компоненты программ ещё более свободно компонуемыми.) Некоторые исследователи придерживались пуристского подхода к результату Бёма–Якопини и утверждали, что даже инструкции, такие как `break` и `return` из середины цикла, являются плохой практикой, поскольку они не нужны в доказательстве Бёма–Якопини, и поэтому выступали за то, чтобы все циклы имели единственную точку выхода. Этот пуристский подход воплощён в языке Pascal (разработанном в 1968–1969 годах), который до середины 1990-х годов был предпочтительным инструментом для обучения основам программирования в академических кругах. Прямое применение теоремы Бёма–Якопини может привести к введению дополнительных локальных переменных в структурированную схему, а также к дублированию кода. Pascal подвержен обеим этим проблемам, и, согласно эмпирическим исследованиям, приведённым Эриком С. Робертсом, студентам-программистам было трудно сформулировать правильные решения на Pascal для нескольких простых задач, включая написание функции для поиска элемента в массиве. Исследование Генри Шапиро 1980 года, цитируемое Робертсом, показало, что при использовании только структур управления, предоставляемых Pascal, правильное решение дали только 20% испытуемых, в то время как ни один испытуемый не написал неправильный код для этой задачи, если ему разрешили использовать `return` из середины цикла. В функциональных языках программирования, таких как Haskell и Scheme, как рекурсивные, так и итеративные процессы выражаются с помощью хвостовых рекурсивных процедур вместо циклов, которые являются синтаксическими конструкциями.

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.

Общая итерация

Общие конструкции итерации, такие как оператор `for` в C и форма `do` в Common Lisp, могут быть использованы для выражения любого из вышеперечисленных видов циклов, а также других, например, для одновременной обработки нескольких коллекций. Если для решения задачи можно использовать более специализированную конструкцию цикла, то она обычно предпочтительнее общей конструкции итерации, поскольку зачастую делает назначение выражения более понятным.

Бесконечные петли

Бесконечные циклы используются для обеспечения непрерывной работы сегмента программы либо до возникновения исключительной ситуации, такой как ошибка. Например, программа, управляемая событиями (например, сервер), должна работать бесконечно, обрабатывая события по мере их поступления, и останавливаться только при принудительном завершении процесса оператором. Бесконечные циклы могут быть реализованы с использованием различных конструкций управления потоком выполнения. Чаще всего в неструктурированном программировании для этого используется переход (goto), а в структурированном программировании – неопределённый цикл (while loop), настроенный на бесконечное выполнение, либо путём опущения условия, либо явной установки его в истинное значение, например, `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, имеют оператор redo, который перезапускает текущую итерацию с начала.

Перезапустить цикл

В Ruby есть оператор `retry`, который перезапускает весь цикл с первой итерации.

Варианты и инварианты цикла

Варианты циклов и инварианты циклов используются для доказательства корректности циклов. В практическом смысле, вариант цикла – это целочисленное выражение, имеющее начальное неотрицательное значение. Значение варианта должно уменьшаться на каждой итерации цикла, но никогда не должно становиться отрицательным при корректном выполнении цикла. Варианты циклов используются для гарантии завершения циклов. Инвариант цикла – это утверждение, которое должно быть истинным перед первой итерацией цикла и оставаться истинным после каждой итерации. Это подразумевает, что при корректном завершении цикла выполняются как условие выхода, так и инвариант цикла. Инварианты циклов используются для отслеживания определенных свойств цикла на протяжении последовательных итераций. Некоторые языки программирования, такие как Eiffel, имеют встроенную поддержку вариантов и инвариантов циклов. В других случаях поддержка реализуется как дополнение, например, спецификация языка моделирования Java для операторов цикла в Java.

Подязык цикла

Некоторые диалекты Lisp предоставляют обширный подязык для описания циклов. Ранний пример можно найти в Conversional Lisp из Interlisp. Common Lisp предоставляет макрос Loop, который реализует подобный подязык.

Справочная таблица системы циклов

Язык программирования условный цикл ранний выход продолжение цикла повторная попытка корректность средства начало середина конец счет коллекция общий бесконечный вариант инвариант массивы Ada APL глубоко вложенный C глубоко вложенный глубоко вложенный C++ глубоко вложенный глубоко вложенный C# глубоко вложенный глубоко вложенный COBOL глубоко вложенный глубоко вложенный Common Lisp встроенный только D Эйфель один уровень только целые числа F# FORTRAN 77 один уровень Fortran 90 Fortran 95 и более поздние массивы Haskell Java Natural OCaml PHP Perl Python глубоко вложенный глубоко вложенный Rebol один уровень Ruby глубоко вложенный глубоко вложенный Standard ML Visual Basic NET один уровень для каждого типа цикла один уровень для каждого типа цикла PowerShell, при этом `while (true)` не считается бесконечным циклом для данной цели, поскольку это не выделенная языковая конструкция. Цикл `for (init; test; increment)` в C является общей конструкцией цикла, а не конкретно счетным, хотя он часто используется для этой цели. Выход из глубоко вложенных циклов может быть реализован в APL, C, C++ и C# с использованием меток и операторов `goto`. Итерация по объектам была добавлена в PHP 5. Счетный цикл может быть смоделирован путем итерации по возрастающему списку или генератору, например, `range` в Python. Выход из глубоко вложенных циклов может быть реализован с помощью обработки исключений. Специальной конструкции нет, поскольку для этого можно использовать функцию `while`. Специальной конструкции нет, но пользователи могут определять общие функции циклов. Стандарт C++11 представил цикл на основе диапазона. В 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 представил ключевое слово `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.

Предлагаемые структуры контроля

В пародийной статье в журнале Datamation 1973 года Р. Лоуренс Кларк предложил заменить оператор GOTO оператором COMEFROM и привел несколько забавных примеров. Оператор COMEFROM был реализован в одном эзотерическом языке программирования под названием INTERCAL. В статье Дональда Кнута 1974 года «Структурное программирование с использованием операторов перехода» были определены две ситуации, не охваченные вышеперечисленными структурами управления, и приведены примеры структур управления, способных их обрабатывать. Несмотря на свою полезность, эти конструкции пока не вошли в состав основных языков программирования.

Безопасность

Один из способов атаковать программное обеспечение — изменить нормальный ход выполнения программы. Для защиты от таких атак используются различные методы обеспечения целостности потока управления, в том числе "канарки" стека, защита от переполнения буфера, теневые стеки и проверка указателей виртуальных таблиц.