К первому уровню можно отнести поток управления внутри выражений подчиняющийся правилам ассоциативности о
Работа добавлена на сайт samzan.net:
Структуры управления на уровне операторов
Поток управления или последовательность выполнения в программе может изучаться на нескольких уровнях. К первому уровню можно отнести поток управления внутри выражений, подчиняющийся правилам ассоциативности операторов и приоритетам операций. Наивысшим уровнем является поток управления в среде подпрограмм и программных модулей.
Между этими уровнями находится поток управления между операторами, обсуждаемый ниже. Предмет обсуждения – эволюция управляющих операторов в императивных языках, затем конструкции ветвления, включая одновариантное, двухвариантное и многовариантное ветвление. Далее обсуждается множество циклических конструкций, применяемых в языках программирования. Затем детально рассматривается оператор безусловного перехода, вызывающий много споров и управляющие конструкции с защищенными командами.
3.1. Введение
Вычисления в программах, написанных на императивных языках программирования, выполняются путем вычисления выражений и присваивания результирующих значений некоторым переменным (далее – операторов присваивания). Однако количество полезных программ, состоящих исключительно из операторов присваивания, ограничено. Чтобы сделать вычисления, выполняемые в программах, гибкими и мощными, необходимо наличие, по крайней мере, еще двух лингвистических механизмов: некоторых средств выбора среди альтернативных путей потока управления (выполнения операторов) и некоторых средств для организации повторного выполнения определенных наборов операторов. Операторы, обеспечивающие такие возможности, называются управляющими операторами (control statements).
Управляющие операторы первого успешного языка программирования – языка FORTRAN – были, по существу, непосредственно связаны с инструкциями на машинном языке, так что их возможности в большей степени определялись структурой машинных команд, чем особенностями самого языка. В то время, т.е. в конце 1950-х годов, управляющие операторы языка FORTRAN считались вполне приемлемыми.
Далее управляющим операторам были посвящены многие исследования и дискуссии, проходившие в течение 10 лет с середины 1960-х до середины 1970-х годов. Один из основных выводов, сделанных на основе этих исследований, состоял в следующем: несмотря на очевидную достаточность одного управляющего оператора (условного оператора goto), язык программирования, не содержащий оператора goto, нуждается лишь в небольшом количестве различных управляющих операторов. В частности, было доказано, что все алгоритмы, которые можно выразить с помощью блок-схем, могут быть закодированы на языке программирования, имеющем только два управляющих оператора: один для выбора между двумя путями потока управления и один – для логически управляемых итераций (Bоhm and Jacopini, 1966). Важный результат, вытекающий из этого утверждения, заключается в том, что операторы безусловного перехода являются излишними – возможно, удобными, но несущественными. Этот факт вместе с проблемами использования безусловного перехода, или операторов goto, привел к большим спорам об операторе goto (раздел 3.5.1).
В действительности, все языки, получившие широкое признание, имеют больше управляющих операторов, чем два минимально необходимых, поскольку, чем больше в языке программирования управляющих операторов, тем легче писать программы на нем. Например, легче писать программы, в которых можно использовать оператор for, естественным образом управляемый счетчиком, чем применять для создания таких циклов оператор while. Основным фактором, ограничивающим количество управляющих операторов в языке, является читабельность программ (напомним, что лишь немногие люди знают все о каком-либо крупном языке программирования; вместо этого они изучают подмножество этого языка, выбранное ими для использования и часто отличающееся от подмножества, на котором написана читаемая ими программа). С другой стороны, недостаток управляющих операторов может привести к необходимости использования операторов низкого уровня, таких как операторы goto, что делает программу менее читабельной.
Вопрос о том, какая совокупность управляющих операторов обеспечивает требуемые возможности и нужную легкость создания программ, широко обсуждался в течение последней четверти столетия. По существу, это – вопрос о том, насколько следует расширить язык, чтобы увеличить легкость разработки программ за счет его простоты, размера и читабельности.
Управляющая структура (control structure) – это управляющий оператор и совокупность операторов, выполнение которых он контролирует. Исследования в области разработки языков программирования, проведенные в 1960 году, показали, что управляющие структуры должны иметь один вход и один выход. Наличие нескольких входов в итеративные структуры, в частности, делает программы менее читабельными и понятными.
3.2. Составные операторы
Одно из вспомогательных свойств языка, облегчающее разработку управляющих операторов, заключается в способе образования наборов операторов. Основная причина неприемлемости управляющих операторов ранних версий языка FORTRAN заключалась в отсутствии такой конструкции.
В языке ALGOL 60 впервые была введена структура для представления набора операторов, а именно: составной оператор (compound statement), имеющий следующий вид:
begin
оператор_1
. . .
оператор_n
еnd
Составной оператор позволяет создавать набор операторов, рассматриваемый как отдельный оператор. Это – мощная концепция, которую с большой пользой можно применять при разработке управляющих операторов. В некоторых языках в начало составного оператора можно добавлять объявления данных, превращая его в блок (см лекцию ХХ).
Язык Pascal унаследовал от языка ALGOL способ образования составных операторов, но не позволяет использовать блоки. Языки, основанные на синтаксисе языка С (С, C++, Java), для разграничения составных операторов и блоков используют фигурные скобки. Некоторые языки не нуждаются в специальном разграничении составных операторов, интегрируя их в свои управляющие структуры. Этот способ обсуждается в следующем разделе.
Существует один вопрос, связанный с разработкой управляющих структур, который относится ко всем условным и циклическим управляющим операторам: может ли управляющая структура иметь несколько входов. Все операторы ветвления и цикла управляют выполнением сегментов программы, и вопрос состоит в том, всегда ли выполнение этих сегментов начинается с их первого оператора. В настоящее время общепринятым считается мнение, что наличие нескольких входов лишь ненамного увеличивает гибкость управляющих конструкций, ухудшая читабельность программы вследствие ее повышенной сложности. Заметим, что наличие нескольких входов возможно только в языках, которые содержат операторы goto и метки операторов.
В этом месте читатель может поинтересоваться, почему наличие нескольких выходов из управляющих структур не указано в списке проблем, связанных с разработкой управляющих структур. Это сделано потому, что наличие нескольких выходов из управляющей структуры не создает опасности, они имеются во всех языках. Таким образом, они не вызывают никаких проблем.
3.3. Операторы ветвления
Оператор ветвления (selection statement) предоставляет программисту средства выбора между двумя или несколькими путями выполнения программы. Такие операторы являются основными и существенными частями всех языков программирования.
Операторы ветвления разделяются на две основные категории: двухвариантные и п-вариантные, или многовариантные операторы ветвления. В категории двухвариантных операторов ветвления существует вырожденный вид оператора, называемый одновариантным оператором ветвления. Существует также вырожденный многовариантный оператор ветвления, арифметический оператор IF в языке FORTRAN, являющийся трехвариантным оператором ветвления.
3.3.1. Двухвариантные операторы ветвления
Несмотря на то, что двухвариантные операторы ветвления в современных императивных языках совершенно одинаковы, вариации в их оценках основываются на совокупности соображений, связанных с разработкой языка.
3.3.1.1. Вопросы разработки
Возможно, наиболее простой проблемой, возникающей при разработке двухвариантных операторов ветвления, является тип выражения, которое управляет оператором ветвления. Самый интересный вопрос разработки – можно ли с помощью оператора ветвления выбрать отдельный оператор, составной оператор или последовательность операторов. Оператор ветвления, который может выбирать только отдельные операторы, является очень ограниченным и обычно приводит к сильной зависимости от операторов goto. Возможность выбора составных операторов была большим шагом вперед в развитии управляющих операторов. Возможность выбора последовательности операторов требует, чтобы оператор ветвления представлял собой синтаксическую сущность для определения такой последовательности. Другой интересный и связанный с предыдущим вопрос: как определить смысл вложенных операторов ветвления – синтаксическими или статическими семантическими правилами?
Эти вопросы разработки языка можно сформулировать следующим образом.
Какой вид и тип имеет выражение, контролирующее ветвление?
Можно ли выбрать отдельный оператор, последовательность операторов или со ставной оператор?
Как определить смысл вложенных операторов ветвления?
3.3.1.2. Примеры двухвариантных операторов ветвления
Все императивные языки программирования имеют одновариантный оператор ветвления, в большинстве случаев представляющий собой подвид двухвариантного оператора ветвления. Единственным исключением является язык FORTRAN IV, который не имел двухвариантного оператора ветвления.
Одновариантный оператор ветвления в языке FORTRAN IV, называемый логическим оператором IF, имеет вид
IF (булевское выражение) оператор
Семантика этого оператора заключается в том, что выбираемый оператор выполняется, только если булевское выражение имеет значение "истина". В языке FORTRAN IV в отношении логического оператора IF было принято следующее проектное решение: управляющее выражение в операторе ветвления имеет булевский тип, и может быть выбран только один оператор. Вложенные логические операторы IF не допускаются.
Одновариантный логический оператор IF очень прост, однако крайне негибок. Тот факт, что можно выбрать только один оператор, способствует использованию операторов goto, поскольку часто в зависимости от некоторого условия требуется выполнять несколько операторов. Единственным разумным способом для выполнения группы операторов в зависимости от некоторого условия является создание условного ветвления вокруг этой группы операторов. Предположим, что мы хотели инициализировать две переменные I и J значениями 1 и 2, но только в том случае, если переменная FLAG равна 1. Как сделать это с помощью языка FORTRAN IV, показано ниже:
IF(FLAG .NE. 1) GO TO 20 1 = 1 J = 2 20 CONTINUE
Эта структура имеет несколько входов, поскольку любой из операторов, входящих в сегмент, может быть отмечен меткой и , таким образом, являться целью операторов GO TO в любом месте программы. Негативная логика, предусмотренная таким видом оператора, может ухудшить читабельность программы.
Составной оператор, введенный в практику языком ALGOL 60, обеспечивает конструкцию ветвления с простым механизмом условного выполнения групп операторов. Он позволяет выбрать как отдельный, так и составной оператор, как показано ниже:
if (булевское выражение) then
begin
оператор_1
. . .
оператор_n
end
Большинство языков, разработанных после языка ALGOL 60, включая языки FORTRAN 77 и 90, имеют одновариантный оператор ветвления, который может выбирать составной оператор или последовательность операторов.
Язык ALGOL 60 ввел в практику первый двухвариантный оператор ветвления, имевший следующий общий вид:
if (булевское_выражение)
then
оператор
else
оператор
Здесь либо один из операторов, либо оба могут быть составными. Оператор, следующий за ключевым словом then, называется оператором then, а оператор, следующий за ключевым словом else, – оператором else.
Все императивные языки, разработанные после середины 1960-х годов, имели встроенные двухвариантные операторы ветвления, хотя их синтаксис варьировался.
Двухвариантные операторы ветвления в языках ALGOL 60, С и C++ могут иметь несколько входов, но в большинстве других современных языков программирования эти операторы могут иметь только один вход.
3.3.1.3. Вложенные операторы ветвления
Интересная проблема возникает, если допускается вложение двухвариантных конструкций ветвления. Рассмотрим следующий фрагмент кода, напоминающего программу на языке Pascal:
if sum = 0 then if count = 0 then result := 0 else
result := 1
Эту конструкцию можно интерпретировать двумя различными способами в зависимости от того, соответствует оператор else первому оператору then или второму. Заметим, что структурированное расположение текста указывает на то, что оператор else принадлежит первому оператору then. Однако такое расположение текста не влияет на семантику в большинстве современных языков и, следовательно, игнорируется их компиляторами.
Сложность этого примера заключается в том, что оператор else следует за двумя операторами then без промежуточных операторов else, и нет никаких синтаксических индикаторов, указывающих на соответствие оператора else одному из операторов then. В языке Pascal, как и во многих других императивных языках, статическая семантика языка означает, что оператор else всегда образует пару с ближайшим предшествующим оператором then, не имеющим пары. Для предотвращения неоднозначности здесь применяется правило, а не синтаксическая сущность. Таким образом, если бы приведенный выше пример был написан на языке Pascal, то оператор else представлял бы собой альтернативу второму оператору then. Недостаток использования правила вместо синтаксической сущности заключается в том, что, хотя программист может считать оператор else альтернативой первому оператору then, и компилятор сочтет эту структуру синтаксически правильной, ее семантика является прямо противоположной. Чтобы внести в язык Pascal альтернативную семантику, требуется наличие иной синтаксической формы, в которой внутренний блок оператора if-then представляет собой составной оператор.
Разработчики языка ALGOL 60 решили использовать синтаксис, а не правило, для того чтобы связывать операторы else с операторами then. В частности, не допускалось вложение оператора if непосредственно в оператор then. Если возникала необходимость вложить оператор if в оператор then, он должен был быть заключен в составной оператор. Например, если конструкция ветвления, приведенная выше, должна была связать оператор else со вторым оператором then, в языке ALGOL 60 это следовало записать следующим образом:
if sum = 0 then begin if count = 0 then
result := 0 else
result := 1 end
Если оператор else следовало связать с первым оператором then, то это можно было записать так:
if sum = 0 then begin if count = 0 then
result := 0 end else
result := 1
Именно это позволяет получить смысл, совпадающий со смыслом фрагмента кода на языке Pascal. Разница между двумя описанными проектными решениями заключается в том, что вариант, реализованный в языке Pascal, позволяет использовать вложенные операторы ветвления, которые выглядят так, как будто они связывают оператор else с первым оператором then, в то время как они этого на самом деле не делают, тогда как та же самая форма в языке ALGOL 60 является синтаксически недопустимой и не позволяет создавать хитроумные программы, характерные для языка Pascal.
В языках С, C++ и Java существуют те же самые проблемы, связанные с вложением операторов ветвления, что и в языке Pascal. Язык Perl требует, чтобы все операторы then и else были составными, предотвращая таким образом проблему их взаимного соответствия.
Альтернатива проектному решению, реализованному в языке ALGOL 60, как будет показано в следующем разделе, – введение специальных замыкающих слов для операторов then и else.
3.3.1.4. Специальные слова и завершение оператора ветвления
Рассмотрим синтаксическую структуру оператора if в языке Pascal. Оператор then начинается с зарезервированного слова then, а оператор else – с зарезервированного слова else. Если оператор then представляет собой отдельный оператор и присутствует оператор else, то зарезервированное слово else фактически отмечает конец оператора then, несмотря на то, что в этом нет никакой необходимости. Если оператор then является составным, он завершается зарезервированным словом end. Однако, если последний оператор в операторе if (либо then, либо else) не является составным, то не существует синтаксического способа для того, чтобы отметить конец всей конструкции ветвления. Использование ключевого слова для этой цели могло бы разрешить вопрос, связанный с семантикой вложенных операторов ветвления, и увеличить надежность конструкции. Именно так был решен этот вопрос при разработке языков ALGOL 60, FORTRAN 77 и 90, Modula-2 и Ada. Рассмотрим следующую конструкцию языка Ada:
if A > В then
SUM := SUM + А;
ACOUNT := ACOUNT + 1; else
SUM := SUM + B;
BCOUNT := BCOUNT + 1; end if;
Такая конструкция имеет более четкую структуру, чем конструкции ветвления в языках Pascal и ALGOL 60, поскольку ее форма остается той же самой независимо от количества операторов, входящих в операторы then и else. Эти операторы состоят из последовательностей операторов, а не из составных операторов. Первую интерпретацию примера ветвления, приведенного в начале раздела 3.3.1.3, можно записать на языке Ada следующим образом:
if SUM = 0 then
if COUNT = 0 then
RESULT := 0; else
RESULT := 1; end if; end if;
Если ключевые слова end if закрывают вложенный оператор if, значит оператор else соответствует внутреннему оператору then.
Вторую интерпретацию примера ветвления, приведенного в начале раздела 3.3.1.3, можно записать на языке Ada следующим образом:
if SUM = 0 then
if COUNT = 0 then
RESULT := 0; end if;
RESULT := 1; end if;
В языке Modula-2 все управляющие конструкции закрываются тем же самым зарезервированным словом END. Программа на языке Modula-2 достигает того же результата, что и пример на языке Ada, приведенный выше, используя при этом меньше зарезервированных слов. Несмотря на это, программы на языке Modula-2 менее читабельны, чем аналогичные программы на языке Ada, особенно если различные управляющие конструкции включаются одна в другую. Когда для закрытия управляющей конструкции IF используется зарезервированное слово END, оно несет лишь часть информации, которую содержат зарезервированные слова END IF.
3.3.2. Конструкции многовариантного ветвления
Конструкция многовариантного ветвления (multiple selection) позволяет выбрать для выполнения один оператор или одну группу операторов из произвольного количества операторов или групп операторов, соответственно. Следовательно, она представляет собой обобщение оператора ветвления. Действительно, одновариантный и двухвариантный операторы ветвления можно построить на основе многовариантного оператора ветвления. Исходная форма многовариантного оператора ветвления впервые была предложена в языке FORTRAN.
Необходимость выбирать путь передачи потока управления в программе – вполне обычное явление. Несмотря на то что многовариантный оператор ветвления можно построить на основе двухвариантного оператора ветвления и операторов безусловного перехода goto, структуры, полученные таким образом, являются громоздкими, трудными для создания и чтения программ, а также ненадежными. Следовательно, возникает потребность в специальной структуре.
3.3.2.1. Вопросы разработки
Некоторые из вопросов разработки многовариантных операторов ветвления похожи на аналогичные вопросы, возникающие при разработке двухвариантных операторов ветвления. Например: можно ли выбрать отдельный оператор, составной оператор или последовательность операторов. Если структура многовариантного выбора является инкапсулированной, то все выбираемые сегменты кода должны располагаться вместе. Это не позволяет потоку управления сбиться с пути и перейти во время выполнения программы к операторам, не являющимся частью структуры многовариантного ветвления. Поскольку это влияет на их читабельность, инкапсуляция представляет собой проблему. Другой вопрос, связанный с двухвариантным оператором ветвления, – это вопрос о типе выражения, на котором основывается выбор. В данном случае спектр возможностей широк, частично из-за количества вариантов выбора. Для двухвариантного оператора ветвления требуется выражение, которое может принимать всего два значения. Кроме того, существует вопрос, может ли при такой конструкции выполняться лишь отдельный выбираемый сегмент. Этот вопрос не относится к двухвариантному оператору ветвления, поскольку в этом случае во всех языках программирования передавать поток управления можно только одному оператору. Как мы вскоре увидим, решение этой проблемы для многовариантного оператора ветвления представляет собой компромисс между надежностью и гибкостью. В заключение отметим еще один вопрос – что следует считать результатом условного выражения, вычисляющего значение, которое не соответствует ни одному из сегментов, подлежащих выбору. Здесь разработчики должны принять решение – просто не допускать возникновения такой ситуации или сформулировать правило, описывающее, что именно происходит, когда такая ситуация возникает. Непредставленные значения условных выражений будут обсуждаться в разделе 3.3.2.3.
Вопросы разработки многовариантных операторов ветвления можно резюмировать следующим образом.
Какова форма и тип выражения, управляющего ветвлением?
Можно ли выбрать отдельный оператор, последовательность операторов или составной оператор?
Инкапсулирована ли вся конструкция в некую синтаксическую структуру?
Ограничен ли поток выполнения, проходящий через структуру, выбором лишь одного выбираемого сегмента?
Как обрабатывать непредставленные значения условных выражений и надо ли их обрабатывать вообще?
3.3.2.2. Ранние многовариантные операторы ветвления
Многовариантные операторы ветвления, введенные в практику языком FORTRAN I, упоминаются здесь по историческим причинам, а также потому, что они остаются частью последней версии языка FORTRAN языка FORTRAN 90. Подобно другим управляющим операторам языка FORTRAN, его многовариантные операторы ветвления основаны непосредственно на машинных командах компьютера IBM 704.
Как указывалось ранее, трехвариантный оператор ветвления языка FOTRAN, называемый арифметическим оператором IF, представляет собой вырожденный случай многовариантного оператора ветвления. Поскольку с помощью этого оператора можно выбрать не более трех наборов операторов, строго говоря, он не является многовариантным оператором ветвления.
Арифметический оператор IF производит выбор среди трех ветвей на основе значения некоего выражения. Ветвление математически основано на трихотомии чисел. Это означает, что заданное числовое значение либо больше нуля, либо равно нулю, либо меньше нуля. Арифметический оператор IF имеет вид:
IF (арифметическое выражение) N1, N2, N3
Здесь N1, N2 и N3 – метки операторов, которым передается управление, если значение выражения меньше нуля, равно нулю или больше нуля, соответственно. Например, при выборе среди трех последовательностей операторов арифметический оператор IF имеет следующий общий вид:
IF (выражение) 10, 20, 30
10 . . .
. . .
Goto 40
20 . . .
. . .
Goto 40
30 . . .
. . .
40 . . .
В действительности этот тип оператора ветвления мог бы быть еще более пагубным для читабельности программы, чем в приведенном примере, поскольку последовательность операторов, подлежащая выбору, может находиться буквально в любом месте программного модуля, содержащего оператор GO TO. Не существует синтаксической инкапсуляции оператора GO TO и выбираемых последовательностей операторов, которым он передает управление. Поскольку ответственность за размещение операторов GO TO в конце выбираемых сегментов несет пользователь, выполнение этой конструкции может вызвать передачу потока управления любому количеству выбираемых сегментов программы. Проблема состоит в том, что ошибка, заключающаяся в пропуске одной из этих ветвей программы, компилятором не обнаруживается. Даже когда выполнение многовариантного сегмента необходимо, увеличивается сложность структуры, нанося большой ущерб читабельности программы. Это проектное решение является компромиссом между читабельностью и небольшим увеличением гибкости программ.
Войти в арифметический оператор IF можно через любой из его операторов в любом месте программы.
Первые два действительно многовариантных оператора ветвления появились в языке FORTRAN I. Подобно арифметическому оператору IF, они входят во все версии языка FORTRAN. Вычисляемый оператор GO TO в языке FORTRAN имеет следующий вид:
GO TO (метка 1, метка 2, ..., метка п), выражение
Здесь выражение имеет целое значение, а метки представляют собой метки операторов в программе. Семантика этого оператора состоит в том, что значение выражения используется для выбора метки, которой следует передать управление. Первая метка связана со значением, равным 1, вторая метка– со значением, равным 2, и так далее. Если значение выходит за пределы диапазона от 1 до п, оператор не выполняет никаких действий. Встроенный механизм для обнаружения ошибок не предусмотрен.
Другой ранний многовариантный оператор ветвления в языке FORTRAN – назначенный оператор GO TO – по форме напоминает вычисляемый оператор GO TO. Оба эти многовариантные операторы ветвления имеют те же недостатки, что и арифметический оператор IF, а именно: отсутствие инкапсуляции и возможность нескольких входов. Кроме того, ничто не ограничивает поток управления одним выбираемым сегментом.
3.3.2.3. Современные многовариантные операторы ветвления
Усовершенствованный вид операторов многовариантного ветвления, названный оператором case, был предложен Хоаром и включен в язык ALGOL-W (Wirth and Hoare, 1966). Эта структура инкапсулирована и имеет один вход. Для каждого выбираемого или составного оператора предусмотрены неявные переходы, ведущие в одну точку в конце всей конструкции, что ограничивает поток управления через структуру одним выбираемым сегментом.
Общий вид хоаровского многовариантного оператора ветвления приведен ниже:
case целое_выражение of
begin
оператор_1
. . .
оператор_n
end
Здесь операторы могут быть либо отдельными, либо составными. Выполняемым является только один оператор, выбираемый по значению выражения. Значение, равное 1, соответствует первому оператору и так далее.
Оператор case языка Pascal очень похож на соответствующий оператор языка ALGOL-W, за исключением того, что все выбираемые сегменты помечены метками. Он имеет следующий вид:
case выражение of
список_констант_1: оператор_1;
список_констант_п: оператор__п;
end
Здесь выражение имеет порядковый тип (целый, булевский, символьный или перечислимый). Как и в большинстве (но не во всех) управляющих операторах языка Pascal, выбираемые операторы могут быть либо отдельными, либо составными.
Семантика оператора case языка Pascal заключается в следующем: вычисляется выражение, и его значение сравнивается с константами в списке констант. Если соответствие найдено, то управление передается оператору, приписанному к соответствующей константе. После выполнения оператора управление передается первому оператору, следующему за всей конструкцией case.
Список констант, конечно, должен иметь тот же тип, что и выражение. Они должны быть взаимоисключающими, но не обязаны быть исчерпывающими; т.е. константы не могут появляться в нескольких списках констант, но в списке констант не обязательно должны быть представлены все значения из диапазона, которому может принадлежать значение выражения.
Заметим, что, хотя список констант, соответствующих выбираемым сегментам, по форме похож на список меток, их нельзя использовать в качестве целей операторов ветвления.
Странно, что первое широко используемое описание языка Pascal (Jensen and Wirth, 1974) не рассматривало возможность наличия в программах непредставленных значений операторов ветвления (в этом случае выражение принимает значение, не входящее ни в один из списков констант). О таких выражениях говорилось, что они приводят к неопределенным результатам. Такая неопределенность, однако, означает, что данная проблема была просто проигнорирована. Более позднее описание ANSI/IEEE Pascal Standard (Ledgard, 1984) было конкретнее; в нем указывалось, что такие выражения являются ошибочными, предположительно подлежащими распознаванию и должны вызывать сообщения об ошибках во время выполнения кода, сгенерированного компилятором языка Pascal.
В настоящее время многие диалекты языка Pascal включают в себя условный оператор, который подлежит выполнению, если значение выражения не принадлежит ни одному из списков констант в операторе case, как показано ниже:
case index of
1, 3: begin
odd :=.add + 1;
sumodd := sumodd + index
end;
2, 4: begin
even := even + 1;
sumeven := sumeven + index end else writeln('Ошибка в операторе case, index -', index) end
Как только значение переменной index выйдет за пределы диапазона от 1 до 4 при выполнении оператора case, будет выведено сообщение об ошибке.
Отметим, что нет никакой необходимости использовать оператор else исключительно для обработки ошибочных ситуаций. Иногда он подходит и для обработки нормальных условий, а операторы case – наоборот, для обработки необычных условий.
Операционная семантика представляет собой эффективный способ описания семантики некоторых управляющих конструкций. Для этой цели расширим операционную семантику, введенную в главе 3, включив в нее операторы присваивания с такими общими выражениями, как RHS. Будем также использовать английские обозначения для некоторых операторов. Такие описания будут появляться в скобках. В заключение отметим, что мы позволяем включать в операционную семантику операторы вывода из того языка, который она описывает.
Описание операционной семантики предыдущего оператора case дано ниже:
if index = 1 goto one_three
if index = 3 goto one_three
if index = 2 goto two^four
if index = 4 goto two__four
writeln('Ошибка в операторе case, index = ',index)
goto out one_three:
odd: = odd + 1;
summodd := summod = index
goto out two_four:
even :•» even + 1
sumeven := sumeven + index out: ...
Структура конструкции switch многовариантного ветвления в языке С, входящей также и в языки C++ и Java, относительно проста. Ниже представлен ее общий вид:
switch (выражение) {
case выражение_константа_1: оператор_1;
case выражение_константа_п: оператор_п; [default: оператор_п+1] }
Здесь управляющее выражение и выражения-константы имеют целый тип. Выбираемые операторы могут быть последовательностями операторов, составными операторами или блоками.
Оператор switch инкапсулирует выбираемые сегменты кода, подобно оператору case языка Pascal, но он не запрещает наличия нескольких входов и не предусматривает неявных переходов в конец сегментов кода. Это позволяет пропускать поток управления через несколько выбираемых сегментов во время одного выполнения оператора switch. Рассмотрим следующий пример, похожий на приведенный выше пример использования оператора case в языке Pascal:
switch (index) { case 1:
case 3: odd += 1;
sumodd += index;
break;
case 2: case 4: even += 1;
sumeven += index;
break;
default: printf("Ошибка в операторе switch, index = %d\n", index); }
Иногда удобно позволить переход потока управления от одного выбираемого сегмента кода к другому. Очевидно, по этой причине в конструкции switch нет неявных переходов. И поэтому, если программист по ошибке пропустит в конструкции switch оператор break, возникает проблема с надежностью, поскольку поток управления ошибочно передается следующему сегменту. Разработчики оператора switch в языке С, подобно разработчикам вычисляемого оператора GO TO в языке FORTRAN, решили немного ослабить надежность, выиграв в гибкости языка. Исследования, однако, показали, что возможность передавать поток управления от одного выбираемого сегмента другому используется редко. Оператор switch в языке С создан по образцу многовариантного оператора ветвления в языке ALGOL 68, который также не имеет неявных переходов из выполняемых сегментов.
Оператор case языка Ada позволяет использовать такие ограниченные типы, как 10. .15, а также операторы ИЛИ, указываемые символом |, например, в выражениях 10 | 15 | 20 в списках констант. В случае применения непредставленных значений выполняется оператор others. Язык Ada вводит дополнительные ограничения, состоящие в том, что списки констант должны быть исчерпывающими, обеспечивая немного большую надежность, поскольку это предотвращает ошибки, вызванные неумышленным пропуском одной или нескольких констант. В выражениях оператора case допускаются только целые и перечислимые типы. Большинство операторов case в языке Ada содержит оператор others, позволяющий гарантировать, что список констант является исчерпывающим.
Оператор case языка FORTRAN 90 похож на оператор case языка Ada.
Во многих случаях конструкция case неприемлема для многовариантного выбора. Например, если выбор должен быть сделан на основе булевского выражения, а не некоторого порядкового типа, можно использовать вложенные двухвариантные операторы ветвления для моделирования многовариантного оператора ветвления. Чтобы избежать плохой читабельности программ, возникающей из-за глубоко вложенных двухвариантных операторов ветвления, такие языки, как FORTRAN 90 и Ada, были расширены. Расширения позволяют пропускать некоторые ключевые слова. В частности, последовательности else-if заменяются одним ключевым словом, а замыкающее ключевое слово вложенного оператора if отбрасывается. В этом случае вложенный оператор ветвления называется оператором elsif. Рассмотрим следующую конструкцию ветвления в языке Ada:
if COUNT < 10 then BAG1 := TRUE; elsif COUNT < 100 then BAG2 := TRUE; elsif COUNT < 1000 then BAG3 : TRUE; end if;
Она эквивалентна следующей конструкции:
if COUNT < 10 then
BAG1 := TRUE; else
if COUNT < 100 then
BAG2 := TRUE; else
if COUNT < 1000 then
BAG3 := TRUE; end if; end if; end if;
Из этих двух вариантов версия elsif более читабельна. Отметим, что данный пример довольно непросто моделируется с помощью оператора case, поскольку выбор каждого оператора производится на основе булевского выражения. Следовательно, конструкция elsif не является избыточной формой оператора case. В действительности, ни один из операторов многовариантного ветвления в современных языках не распространен так, как оператор if-then-elsif. Описание операционной семантики общего оператора ветвления на основе операторов elsif, в котором буквы Е с цифрами обозначают логические выражения, а буквы S с цифрами – операторы, приведено ниже:
if El goto 1 if El goto 1
1: SI
goto out 2: S2
goto out
out: ...
Это описание позволяет увидеть разницу между структурами многовариантного ветвления и конструкциями elsif. Она заключается в том, что в конструкции многовариантного ветвления все выражения, обозначенные буквами Е, можно свести к сравнениям между значениями отдельных выражений и некоторыми другими значениями.
Языки, не включающие в себя конструкцию elsif, могут использовать ту же управляющую структуру, лишь с ненамного большим количеством типов.
Конструкции elsif основываются на общей математической конструкции – условном выражении.
3.4. Операторы цикла
Операторы цикла (iterative statements) – это операторы, вынуждающие оператор или набор операторов выполняться один и сколько угодно раз, или не выполняться ни разу. Каждый язык программирования, начиная с языка Plankalktll, содержал некоторый метод для повторения выполнения сегмента кода. Если бы цикл был невозможен, программист был бы вынужден указывать каждое действие в последовательности операторов; полезные программы стали бы огромными, а их написание заняло бы громадный объем времени.
Первые циклические конструкции в языках программирования были непосредственно связаны с массивами. Это было следствием того факта, что на заре компьютерной эры вычисления были преимущественно числовыми по своей природе и часто использовали циклы для обработки данных, хранящихся в массивах.
Было разработано несколько видов операторов управления циклами. Основные виды этих операторов зависели от того, как разработчик решал две главные проблемы проектирования.
Как осуществляется управление циклом?
В каком месте цикла находится механизм управления?
Основные возможности управления циклом – логические выражения, индексирование или комбинация этих способов. Основные способы расположения механизма управления – в начале цикла или в конце цикла. Начало и конец цикла – это логические, а не физические понятия. Вопрос заключается не в физическом размещении механизма управления, а в том, может ли этот механизм выполняться и осуществлять управление перед или после выполнения тела цикла. Третья возможность, позволяющая пользователю самому решать, где разместить механизм управления циклом, обсуждается в разделе 3.4.3. Тело цикла– это набор операторов, выполнение которых управляется оператором цикла. Мы используем термин предварительная проверка (pretest) для того, чтобы отметить тот факт, что проверка условия завершения цикла осуществляется после выполнения тела цикла, а термин последующая проверка (posttest) означает, что эта проверка производится после выполнения тела цикла. Оператор цикла и связанное с ним тело цикла вместе образуют итеративную конструкцию (iteration construct).
Кроме основных операторов цикла, мы обсудим также альтернативную форму, которая сама по себе принадлежит некоторому классу операторов – определенным пользователем механизмам управления циклом.
3.4.1. Циклы со счетчиком
Оператор цикла со счетчиком имеет переменную, называемую счетчиком цикла (loop variable), в которой хранится значение счетчика. Он также обладает некоторыми средствами для указания начального и конечного значений счетчика цикла и разности между последовательными значениями счетчика цикла, которую часто называют величиной шага. Начальное и конечное значения счетчика, а также величина шага цикла называются параметрами цикла.
Несмотря на то что логически управляемые циклы имеют более общий вид, чем циклы со счетчиком, это не значит, что они более широко используются. Поскольку циклы со счетчиком сложнее, к их разработке предъявляются повышенные требования.
Циклы со счетчиком часто поддерживаются машинными командами. К сожалению, компьютерная архитектура зачастую переживает методы программирования, бывшие господствующими во время разработки этой архитектуры. Например, в компьютерах VAX есть команда, очень удобная для реализации циклов со счетчиком и последующей проверкой, которая была в языке FORTRAN во время проектирования этих компьютеров. Однако сейчас язык FORTRAN больше не содержит такого цикла, в то время как компьютеры VAX стали широко распространенными.
Конечно, языковые конструкции намного переживают машинную архитектуру. Например, автору неизвестен ни один современный компьютер, который имел бы трехвариантную команду ветвления для реализации арифметического оператора IF языка FORTRAN.
3.4.1.1. Вопросы разработки
Природа счетчика цикла и параметров цикла вызывает много вопросов. Типы счетчика цикла и параметров цикла, очевидно, должны быть одинаковыми или, по крайней мере, совместимыми, но какие именно типы следует считать допустимыми? Одно из очевидных решений– целые числа, но как насчет перечислимых и символьных типов, а также чисел с плавающей точкой? Другой вопрос заключается в том, является ли счетчик цикла обычной переменной с точки зрения области видимости или у него должна быть своя специальная область видимости. Связан с вопросом об области видимости и вопрос о том, какое значение имеет счетчик цикла после его завершения. Разрешение пользователю изменять счетчик или параметры цикла внутри цикла может привести к созданию кода, очень трудного для понимания, поэтому следующий вопрос состоит в том, компенсирует ли дополнительная гибкость, созданная таким решением, повышенную сложность. Аналогичный вопрос возникает и в отношении того, сколько раз и когда конкретно вычисляются параметры цикла: если они вычисляются только один раз, это приводит в простым, но менее гибким циклам.
Эти вопросы можно сформулировать следующим образом.
Какой тип и какую область видимости имеет счетчик цикла?
Чему равен счетчик цикла после завершения цикла?
Следует ли разрешать изменения счетчика и параметров цикла внутри цикла, и если да, влияет ли такое изменение на управление циклом?
Следует ли вычислять параметры цикла только один раз или это следует делать на каждой итерации?
3.4.1.2. Оператор DO в языках FORTRAN 77 и FORTRAN 90
Язык FORTRAN I содержал оператор со счетчиком DO, оставшийся без изменения в языках FORTRAN II и IV. Этот оператор имел последующую проверку, что отличало его от циклов со счетчиком во всех других языках программирования. Общий вид этого оператора приведен ниже:
DO метка переменная = начальное значение, конечное значение [, величина шага] . Здесь метка – последний оператор в теле цикла, а величина шага, если она не указывается явно, по умолчанию равна 1. Параметры цикла могут быть лишь беззнаковыми целыми константами или простыми целыми переменными, принимающими положительные значения.
Оператор DO языка FORTRAN 77 по внешнему виду похож на аналогичный оператор языка FORTRAN IV, за исключением последующей проверки условий. Счетчик цикла может иметь типы INTEGER, REAL или DOUBLE-PRECISION. Параметры цикла могут быть выражениями и иметь положительные или отрицательные значения. Они вычисляются в начале выполнения оператора DO и их значения используются для вычисления количества повторений цикла (iteration count). Цикл управляется именно количеством повторений цикла, а не параметрами цикла, так что даже если параметры цикла будут изменены внутри цикла, что допускается, эти изменения не смогут повлиять на управление циклом. Количество повторений цикла хранится во внутренней переменной, которая недоступна пользовательской программе.
В конструкцию DO можно войти только через оператор DO, что делает этот оператор структурой с одним входом. Когда выполнение оператора DO завершается (независимо от того, каким именно образом это происходит), счетчик цикла имеет то значение, которое было присвоено ему в последний раз. Таким образом, полезность счетчика цикла не зависит от того, как именно завершается цикл. Описание операционной семантики оператора DO языка FORTRAN 77 приведено ниже:
init_value := init_expression terminal_value := terminal_expression step_value := step_expression do_var := init__value iteration_count :=
max(int ( (terminal_value-init_value + step value) / Step_value), 0) loop:
if iteration_count < 0 goto out
[loop body]
do^var := do_var + step_value
iteration_count := iteration_count 1
goto loop out': . . .
Язык FORTRAN 90 содержит оператор DO языка FORTRAN 77 и добавляет новую форму:
[имя:] DO переменная = начальное значение, конечное значение [, величина шага]
END DO [имя]
В этом операторе DO счетчик цикла может иметь только тип INTEGER (как и его предшественник в языке FORTRAN 77). Другое изменение состоит в том, что этот оператор использует специальное замыкающее ключевое слово (или фразу) END DO, вместо оператора с меткой.
3.4.3.3. Оператор for в языке ALGOL 60
Оператор for языка ALGOL 60 описан здесь для того, чтобы показать, как погоня за гибкостью может привести к чрезмерной сложности. Оператор for языка ALGOL 60 представляет собой значительное обобщение оператора DO языка FORTRAN, как показано в его описании с помощью РБНФ (расширенной формы Бэкуса-Наура):
<for_stmt> –> for var:= <list_element> {, <list_element>) do
<statement> <list_element> –» <expression>
I <expression> step <expression> until
<expression> I <expression> while <Boolean_expr>
Значительное различие между этим и большинством других операторов со счетчиком заключается в том, что эта конструкция может комбинировать счетчик и булевское выражение в механизме управления циклом. Три простейшие формы этого оператора иллюстрируются следующими примерами:
for count := 1, 2, 3, 4, 5, 6, 7, 8, 10 do list[count] := 0
for count := 1, step 1 until 10 do
list[count] : = f
for count : = 1, count + 1 while (count <= 10) do list[count] := 0
Этот оператор становится намного сложнее, когда его различные простые формы комбинируются друг с 'другом, как показано ниже:
for index := 1, 4, 13, 41
step 2 until 47,
3 * index while index < 1000,
34, 2, -24 do
sum := sum + index
Эти операторы добавляют к переменной sum следующие значения:
1, 4, 13, 41, 43, 45, 47, 147, 441, 34, 2, -24
Конечно, возможна ситуация, в которой удобно использовать подобные сложные операторы, однако такие случаи слишком редки, чтобы служить оправданием усложнения языка.
Оператор for языка ALGOL 60 более труден для понимания, чем кажется на первый взгляд, поскольку все выражения в операторе for вычисляются при каждом выполнении цикла. Таким образом, если выражение step содержит ссылку, например, на переменную count, а операторы цикла изменяют эту переменную, то величина шага будет изменяться на каждой итерации. Например, рассмотрим цикл
i := 1;
for count := 1 step count until 3 * i do i := i + 1
Оператор for заставляет присваивание (i := i + 1) выполняться повторно, в то время как переменная count удваивается при каждом повторении (поскольку шаг всегда равен предыдущему значению переменной count). Переменная count увеличивается быстрее, чем значение выражения until (3 * i), и цикл не будет бесконечным, хотя на первый взгляд это не очевидно. Значения переменных и управляющих выражений в этом цикле приведены ниже:
|
count |
step |
until |
|
1 |
1 |
3 |
|
2 |
2 |
6 |
|
4 |
4 |
9 |
|
8 |
8 |
12 |
|
16 |
16 |
15 - |
1 1 2 3 4 5 16 16 15– завершает цикл
Проектное решение, касающееся оператора for языка ALGOL 69, было следующим: счетчик цикла может быть либо целым, либо вещественным числом и объявляется подобно всем другим переменным, так что его область видимости определяется его объявлением. Как и в языке FORTRAN 77, счетчик после завершения цикла имеет то значение, которое было присвоено ему при последнем повторении независимо от того, что именно вызвало завершение цикла. Параметры цикла, но не счетчик, могут изменяться в его теле. Переход в тело цикла извне не разрешается, а его параметры вычисляются при каждом повторении.
Нелегко охарактеризовать операционную семантику полного оператора for языка ALGOL 60 со всеми его возможностями. Вместо этого, мы сначала дадим описание общего оператора for только в форме step-until:
for_var := imit_expr loop:
unitl := until_expr
step := step_expr
temp : = (for_var until) * SIGN(step)
if (temp > 0 goto out
[loop body]
for__var : = for_var + step
goto loop out: ...
Ниже приводится описание операционной семантики более сложного примера оператора for:
for count := 10 step 2 * count until init * init, 3 * count while sum <= 1000 do
sum := sum + count
count := 10 loopl:
if count > init * init goto loop2
sum:= sum + count
count:=count+(2*count)
goto loopl loop2:
count:=3*count
if sum>1000 goto out
sum:=sum + count goto loop2 out: ...
3.4.14. Оператор for в языке Pascal
Оператор for языка Pascal представляет собой образец простоты. Он имеет следующий вид:
for переменная:=начальное_значение (to|downto) конечное_значение do оператор
Выбор (to | downto) позволяет значению счетчика цикла увеличиваться или уменьшаться с шагом 1. Проектное решение, касающееся оператора for языка Pascal, состоит в следующем: счетчик цикла должен иметь перечислимый тип, а его область видимости определяется его объявлением. При нормальном завершении цикла значение счетчика становится неопределенным. Если выполнение цикла прекратилось преждевременно, то счетчик цикла имеет последнее присвоенное ему значение. Счетчик цикла не может изменяться внутри тела цикла. Начальное и конечное значения определяются выражениями любого типа, совместимого с типом счетчика, и могут изменяться внутри тела цикла, но, поскольку они вычисляются только один раз, это не влияет на управление циклом.
3.4.3.5. Оператор for в языке Ada
Оператор for языка Ada похож на свой аналог в языке Pascal. Он представляет собой цикл с предварительной проверкой условия и имеет следующий вид:
for переменная in [reverse] дискретный_диапазон loop
end loop;
Дискретный диапазон – это ограниченный подтип целого или перечислимого типа, например, 1. .10.
Наиболее интересное новое свойство оператора for языка Ada относится к области видимости счетчика, которая ограничивается телом цикла. Счетчик неявно объявляется в начале оператора for и неявно выходит из области видимости после завершения цикла. Рассмотрим, например, следующий фрагмент кода:
COUNT : FLOAT := 1.35;
for COUNT in 1..10 loop SUM := SUM + COUNT;
end loop;
Здесь переменная COUNT типа FLOAT не затрагивается оператором for. После завершения цикла переменная COUNT сохраняет тип FLOAT и значение 1.35. Кроме того, переменная COUNT типа FLOAT скрывается от кода, находящегося в теле цикла, маскируясь счетчиком цикла COUNT, который неявно объявляется как переменная, имеющая тип INTEGER и принимающая значения из дискретного диапазона.
Переменной цикла в языке Ada нельзя присваивать никакого значения внутри тела цикла. Переменные, используемые для указания дискретного диапазона, могут изменяться внутри цикла, но, поскольку диапазон вычисляется только один раз, эти изменения не влияют на управление циклом. В языке Ada переходы внутрь тела цикла for не разрешаются. Ниже приводится описание операционной семантики цикла for языка Ada:
[define for_var (переменная, имеющая дискретный диапазон значений)]
[evaluate discrete range] loop:
if[нет ни одного элемента, выходящего за пределы дискретного диапазона] goto out
for_var:=[следующий элемент из дискретного диапазона]
[тело цикла]
goto loop out:
[неопределенное значение переменной for_var]
3.4.76. Оператор for в языках С, C++ и Java
Оператор for языка С имеет следующий общий вид:
for (выражение__1; выражение_2; выражение_3) тело цикла
Тело цикла может состоять из отдельного оператора, составного оператора или быть пустым.
Поскольку операторы в языке С вычисляют результаты и, следовательно, могут рассматриваться как выражения, в операторе for выражения часто являются операторами. Первое выражение предназначено для инициализации и вычисляется только один раз в начале выполнения оператора for. Второе выражение является управлением цикла и вычисляется перед каждым выполнением тела цикла. Как это принято в языке С, нулевое значение означает "ложь", а все ненулевые значения означают "истину". Следовательно, если значение второго выражения равно нулю, то выполнение оператора for прекращается; в противном случае операторы цикла продолжают выполняться. Последнее выражение в операторе for вычисляется после каждого выполнения тела цикла. Оно часто используется для увеличения счетчика цикла. Описание операционной семантики оператора for языка приводится ниже. Поскольку выражения в языке С также являются операторами, вычисление выражений показано как вычисление операторов.
выражение_1 loop:
if выражение_2 = 0 goto out
[тело цикла]
выражение_3
goto loop out: ...
Вот типичный пример цикла со счетчиком в языке С:
for (index = 0; index <= 10; index++) sum = sum + list[index];
Все выражения в операторе for языка С являются необязательными. Отсутствие второго выражения интерпретируется как истинное выражение, так что оператор for без второго выражения потенциально является бесконечным циклом. Если первое и/или третье выражение отсутствуют, то не делается никаких предположений. Например, если отсутствует первое выражение, это означает, что никакой инициализации не происходит.
Отметим, что оператор for языка С не нуждается в счетчике. Он может легко моделировать перечисление и логические циклические структуры, как показано в следующем разделе.
Проектное решение, касающееся оператора for языка С, было следующим: не существует никаких явных счетчиков или параметров цикла. Все переменные, относящиеся к циклу, могут изменяться в тела цикла. Выражения вычисляются в порядке, указанном выше. Несмотря на тот факт, что это может привести к катастрофе, в языке С допускается переход внутрь тела цикла for.
Оператор for языка С более гибок, чем аналогичные операторы в других рассмотренных нами языках программирования, поскольку каждое из его выражений может включать составные операторы, которые, в свою очередь, допускают использование нескольких счетчиков цикла любого типа. Когда в одном выражении оператора for используются составные операторы, они разделяются запятыми. Все операторы языка С имеют значения, и эта форма составного оператора – не исключение. Значением такого составного оператора является значение его последнего компонента.
Рассмотрим следующий оператор for:
for (countl = 0, count2 = 1.0;
countl <= 10 && count2 <= 100.0;
sum = ++countl + count2, count2 * = 2.5);
Описание операционной семантики этого фрагмента приведено ниже:
countl := 0
count2 := 0.0 loop:
if count > 10 goto out
if count2 > 100.0 goto out
countl := countl + 1
sum := countl + count2
count2 := count2 * 2.5
goto loop out: ...
Оператор for языка С, приведенный выше, не нуждается в теле цикла, а потому и не имеет его. Все требуемые действия являются частью самого оператора for, а не его тела. Первое и третье выражения – это составные операторы. В обоих случаях вычисляется все выражение, но результирующее значение для управления циклом не используется.
Оператор for языка C++ отличается от своего аналога в языке С двумя особенностями. Во-первых, в дополнение к арифметическим выражениям он может использовать булевское выражение для управления циклом. Во-вторых, первое выражение может содержать определения переменных. Например,
for (int count = 0; count < len; count++) { ... }
Область видимости переменной-счетчика цикла такая же, как и у оператора for в языке Ada. Однако в языке C++ область видимости переменной, определенная оператором for, начинается объявлением этой переменной и заканчивается концом функции, в которой она объявлена. Выражения оператора цикла for не входят в составной оператор, являющийся телом цикла for. Объявления переменных в функциях языка С должны предшествовать выполняемым операторам, так что приведенный выше оператор for в языке С недопустим.
Оператор for языка Java аналогичен оператору for языка C++, за исключением того факта, что выражение, управляющее выполнением цикла, должно быть булевским (boolean), и область видимости переменной, определенной в первом выражении, ограничена телом цикла, как и в языке Ada.
3.4.2. Логически управляемые циклы
Во многих случаях наборы операторов должны выполняться повторно, но управление повторениями основывается на булевских выражениях, а не на счетчике. В этих ситуациях удобно использовать логически управляемые циклы. Действительно, такие циклы представляют собой более общий случай, чем циклы со счетчиком. Каждый цикл со счетчиком можно создать с помощью логически управляемого цикла, но не наоборот. Кроме того, напомним, что только ветвление и логически управляемые циклы играют существенную роль при выражении управляющей структуры в любой блок-схеме.
3.4.2.1. Вопросы разработки
Поскольку логически управляемые циклы намного проще, чем циклы со счетчиками, список вопросов, связанных с ними, относительно короток. Один из таких вопросов относится также и к циклам со счетчиком. Среди этих вопросов мало спорных или трудных.
Управление должно основываться на предварительной или на последующей проверке условий?
Должен ли логически управляемый цикл представлять собой особый вид цикла со счетчиком или он должен быть отдельным оператором?
3.4.2.2. Примеры
Некоторые императивные языки (например, Pascal, С, C++ и Java) имеют логически управляемые циклы как с предварительной, так и последующей проверкой условий, которые не являются особым видом циклов со счетчиком. В языке C++ циклы с предварительной и последующей проверкой условий имеют следующий вид:
while (выражение) тело цикла
Возможен также такой вариант:
do
тело цикла while (выражение)
Эти операторы иллюстрируются следующим фрагментом кода на языке C++:
sum = 0;
cin >> indat;
while (indat >= 0) {
sum +«■ indat;
cin >> indat; } cin >> value;
do {
value /= 10; digits + + ; } while (value > 0);
Заметим, что все переменные в этих примерах являются целочисленными, cin – это стандартный входной поток (клавиатура), а >> – оператор ввода.
В варианте с предварительной проверкой условий (while) оператор выполняется до тех пор, пока результат выражения является истинным (ненулевым). В языках С, C++ и Java тело цикла с последующей проверкой условий (do) выполняется до тех пор, пока результат выражения не станет ложным (нулем). Единственное реальное различие между операторами do и while заключается в том, что оператор do всегда заставляет тело цикла выполняться хотя бы один раз. В обоих случаях оператор является составным. Описания операционной семантики этих двух операторов даны ниже:
while do-while
loop: loop:
if выражение = 0 goto out [тело цикла]
[тело цикла] if(выражение) * 0 goto loop
goto loop
out: ...
И в языке С, и в языке C++ допускается переход внутрь тел обоих операторов цикла while и do.
Операторы while и do языка Java аналогичны операторам while и do в языках С и C++, за исключением того факта, что управляющее выражение в языке Java должно быть булевским, и, поскольку язык Java не имеет операторов goto, в тело цикла нельзя войти ниоткуда, кроме его начала.
В языке FORTRAN 77 нет логически управляемых циклов с предварительной или последующей проверкой условий. То же относится и языку FORTRAN 90. В языке Ada есть логически управляемый цикл с предварительной проверкой условий, но нет цикла с последующей проверкой.
Оператор логически управляемого цикла с последующей проверкой условий repeat-until языка Pascal отличается от операторов do-while в языках С, C++ и Java тем, что он имеет противоположную логику управляющего выражения. Тело цикла выполняется до тех пор, пока результат управляющего выражения не станет ложным, а не истинным, как в языках С, C++ и Java.
Оператор repeat-until необычен, поскольку его тело может представлять собой либо составной оператор, либо последовательность операторов. Это единственная управляющая структура в языке Pascal, имеющая такую гибкость. Она представляет собой еще один пример отсутствия ортогональности в структуре языка Pascal.
Циклы с последующей проверкой условия редко бывают полезными и могут быть в некотором смысле опасными, поскольку программисты иногда забывают о том, что тело такого цикла всегда должно выполняться хотя бы один раз. Синтаксическое решение разместить последующую проверку условий после тела цикла, в котором она имеет семантическое значение, помогает избежать подобных проблем, делая логику такого оператора более ясной.
3.4.3. Циклы с механизмами управления, размещенными пользователем
В некоторых ситуациях программисту удобно выбирать расположение механизма управления циклом не в начале или конце цикла. Синтаксический механизм, позволяющий пользователю самому определять расположение управления циклом, относительно прост, так что его разработка не представляет трудностей. Наиболее интересный вопрос состоит в том, можно ли выйти из одного или нескольких вложенных циклов. Вопросы разработки такого механизма приведены ниже.
Должен ли механизм проверки условий быть неотъемлемой частью выхода из цикла?
Механизм может появляться в управляемом цикле или только в таком цикле, в котором нет никаких других механизмов управления?
Выходить можно только из одного тела цикла или из внешних циклов тоже?
В некоторых языках, в том числе в языке Ada, есть операторы цикла без управления повторениями; они становятся бесконечными, если программист не добавит средства управления ими. Бесконечный цикл в языке Ada имеет вид:
loop
end loop
Оператор exit в языке Ada может быть как условным, так и безусловным, кроме того, он может появляться в любом цикле. Его общий вид приведен ниже:
exit [метка_цикла][when условие]
При отсутствии необязательной части [when условие] оператор exit приводит к завершению выполнения только того цикла, в котором он появился. В качестве примера рассмотрим следующий фрагмент:
loop
if SUM >= 10000 then exit end if;
end loop;
Здесь при выполнении оператора exit управление передается первому оператору после конца цикла.
Оператор exit с условием when приводит к завершению цикла, в котором он появился, только если выполняется указанное условие. Например, приведенный выше цикл можно переписать так:
loop
exit when SUM > 10000; end loop;
Любой цикл можно обозначить меткой, и если метка цикла включена в оператор exit, то управление передается оператору, находящемуся непосредственно после указанной метки. Рассмотрим следующий сегмент кода:
OUTERJLOOP:
for ROW in 1 .. MAX_ROWS loop INNER_LOOP:
for COL in 1 .. MAX_COLS loop SUM := SUM + MAT(ROW, COL); exit OUTER_LOOP when SUM > 1000.0; end loop INNER_LOOP; end loop OUTER_LOOP;
В этом примере оператор exit представляет собой оператор условного перехода на первый оператор после внешнего цикла. Возможен вариант, когда оператор exit используется вместо выражения:
exit when SUM > 1000.0;
В этом случае его можно рассматривать как оператор условного перехода на первый оператор после внутреннего цикла. Заметим, что операторы exit часто используются для обработки необычных или ошибочных условий.
Языки С, C++ и Modula-2 имеют безусловные операторы выхода, не содержащие меток (break в языках С и C++ и оператор EXIT в языке Modula-2); в языках FORTRAN 90 и Java, как и в языке Ada, есть операторы безусловного выхода с метками (оператор EXIT в языке FORTRAN 90 и оператор break в языке Java), однако в языке Java целью перехода может быть любой внешний составной оператор.
Языки С и C++ имеют механизм управления continue, передающий управление ближайшему внешнему циклу. Этот оператор не является оператором выхода из цикла. Он позволяет пропустить оставшиеся операторы цикла при текущей итерации без прекращения выполнения цикла. Например, рассмотрим следующий фрагмент кода:
while (sum < 1000) { getnext(value); if (value < 0) continue;
sum += value; }
Отрицательное значение приведет к пропуску оператора присваивания и передаче управления в начало цикла. С другой стороны, в следующем фрагменте отрицательное значение приведет к завершению цикла:
while (sum < 1000) {
getnext(value);
if (value < 0) break;
sum += value; }
В языках FORTRAN 90 и Java есть операторы, подобные оператору continue, но, кроме того, они могут содержать метки, указывающие, какой именно цикл должен быть продолжен.
Операторы exit и break обеспечивают наличие нескольких выходов из циклов, что иногда мешает читабельности программ. Однако необычные условия, которые приводят к необходимости завершить выполнение цикла, встречаются так часто, что существование таких конструкций вполне оправданно. Более того, читабельность от этого серьезно не страдает, поскольку целью всех таких выходов является первый оператор после цикла, а не просто оператор, расположенный где-то в программе. Оператор break языка Java является исключением из этого правила, поскольку его целью может быть любой внешний составной оператор.
3.4.4. Циклы, основанные на структурах данных
Нам осталось рассмотреть только один дополнительный вид циклических структур – циклы, зависящие от структур данных. Эти циклы управляются количеством элементов в структуре данных, а не счетчиком или булевским выражением. Такие операторы есть в языках COMMON LISP и Perl.
В языке COMMON LISP функция dolist выполняет повторяющиеся операции над простыми списками, представляющими собой наиболее распространенную структуру данных в программах на языке LISP. Вследствие этого ограничения функция dolist является автоматической, т.е. она всегда неявно выполняет повторяющиеся операции над элементами списка. Эта функция вызывает выполнение ее тела один раз для каждого элемента списка. Оператор foreach языка Perl аналогичен функции dolist в языке COMMON LISP; он выполняет повторяющиеся операции над элементами списков или массивов. Например,
Snames = ("Bob", "Carol", "Ted", "Beelzebub");
foreach $name (@names) {
print $name; }
Более общий оператор цикла, основанный на структурах данных, использует структуры данных и функцию, определенные пользователем, для выполнения операций над каждым элементом структуры. Такая функция называется итератором (iterator). Итератор вызывается в начале каждого повторения, и каждый раз при вызове он возвращает некоторый элемент из конкретной структуры данных в некотором определенном порядке. Предположим, что программа работает с бинарным деревом, и данные в каждом узле должны быть обработаны в некотором конкретном порядке. Оператор цикла, определенный пользователем для дерева, мог бы успешно устанавливать переменную цикла в узлах дерева по одной при каждом повторении. При первом выполнении оператора цикла, определенного пользователем, следует выполнить специальный вызов итератора, чтобы получить первый элемент дерева. Итератор должен всегда помнить, какой элемент был обработан последним, чтобы обойти все узлы только по одному разу. Таким образом, итератор должен помнить предысторию. Оператор цикла, определенный пользователем, завершается, когда итератор больше не может найти ни одного элемента.
Конструкцию for языков С, C++ и Java в силу ее высокой гибкости можно использовать для имитации оператора цикла, определенного пользователем. Предположим, что программа должна обработать узлы бинарного дерева. Если корень дерева обозначен переменной root, и функция traverse устанавливает свои параметры так, чтобы они указывали на следующий элемент дерева в требуемом порядке, можно использовать следующий оператор:
for (ptr = root; ptr == null; traverse(ptr)) {
}
В этом операторе функция traverse представляет собой итератор.
Оператор цикла, определенный пользователем, играет более важную роль в объектноориентированном программировании, чем в ранних парадигмах программирования. Причина этого заключается в том, что пользователи в настоящее время обычно конструируют абстрактные типы данных для структур данных. В таких случаях оператор цикла, определенный пользователем, и его итератор должны быть созданы автором абстракции данных, поскольку представление объектов данного типа пользователю не известно. В языке C++ итераторы для типов, определенных пользователем, или классов часто реализуются либо через дружественные функции класса, либо как отдельные классы итераторов.
3.5. Безусловный переход
Оператор безусловного перехода передает управление выполнением в указанное место программы.
3.5.1. Проблемы безусловного перехода
Наиболее жаркие дебаты, связанные с разработкой языков программирования, в конце 1960-х годов шли вокруг вопроса, должен ли безусловный переход быть неотъемлемой частью любого языка программирования высокого уровня, и если да, то следует ли ограничивать его использование.
Безусловный переход, или оператор goto, является самым мощным оператором управления потоком выполнения программы. Однако неосторожное использование подобных операторов может создать проблемы. Оператор goto обладает ошеломляющей мощью и большой гибкостью (все другие управляющие структуры можно построить с помощью оператора goto и оператора ветвления), но эта сила делает его использование опасным. Если применять его без ограничений, наложенных либо языком, либо стандартами программирования, оператор goto может сделать программу действительно нечитабельной и, как результат, в высшей степени ненадежной и трудной для эксплуатации.
Эти проблемы непосредственно вытекают из способности оператора goto вынуждать выполнение любого оператора в программе вслед за любым другим оператором, образуя последовательность выполнения программы, независимо от того, предшествует ли этот оператор первому оператору или следует за ним в тексте программы. Читабельность является наилучшей, когда порядок выполнения операторов почти совпадает с порядком, в котором они приводятся в программе – в нашем случае это может означать порядок выполнения "сверху-вниз", к которому мы привыкли. Ограничение операторов goto таким образом, чтобы они могли передавать управление в программе только вниз, частично решает проблему. Подобные ограничения позволяют операторам goto передавать управление в некоторые разделы программы в ответ на ошибки или необычные условия, но не позволяет использовать их для построения циклов любого вида.
Несмотря на то что некоторые думающие люди еще раньше предлагали ограничить использование операторов goto, именно Эдсгер Дийкстра дал компьютерному сообществу первое получившее широкое распространение разъяснение опасности операторов безусловного перехода. В своем письме он писал: "Оператор goto сам по себе слишком примитивен; он слишком похож на предложение запутать программу" (Dijkstra, 1968a). На протяжении первых нескольких лет после публикации точки зрения Дийкстры на оператор goto большое количество людей публично выступали за то, чтобы либо прямо запретить, либо по крайней мере ограничить использование операторов goto. Среди тех, кто не поддерживал предложение о полном исключении оператора goto, был Доналд Кнут (Donald Knuth), объяснявший, что бывают случаи, когда эффективность оператора goto перевешивает его вред для читабельности (Knuth, 1974).
Было, разработано несколько языков программирования, не содержавших оператора goto, – например, языки Modula-2 и Java. Однако самые современные популярные языки программирования включают операторы goto. Керниган и Ритчи (Kemighan and Ritchie (1978)) назвали оператор goto бесконечно неправильным, однако, несмотря на это, он был включен в язык С, разработанный Ритчи. В языках, исключивших оператор goto из своего состава, предусмотрены дополнительные управляющие операторы (обычно в виде цикла или выходов из подпрограмм) для замены оператора goto в стандартных случаях его применения.
3.5.2. Виды меток
Одни языки, например ALGOL 60 и С, используют для меток форму своих идентификаторов, другие (FORTRAN и Pascal)– беззнаковые целые константы. Язык Ada использует форму своих идентификаторов в качестве цели для оператора goto, но, когда метка ставится возле оператора, она должна отделяться символами <<OUT>>. Рассмотрим следующий фрагмент программы:
goto FINISHED;
«FINISHED» SUM : = SUM + NEXT;
Угловые скобки облегчают поиск метки при чтении программы. В большинстве других языков метки приписываются к оператору с помощью двоеточия, как в следующем примере:
finished: sum := sum + next;
При разработке меток в языке PL/1 вновь была выбрана конструкция, обладающая предельной гибкостью и сложностью. Вместо использования меток в качестве простых констант язык PL/1 позволяет меткам быть переменными. В этом виде им можно присваивать значения и использовать в качестве параметров подпрограмм. Это позволяет оператору goto действительно передавать управление в любую точку программы, причем эта цель не может определяться статически. Несмотря на то что эта гибкость иногда бывает полезна, такое использование меток наносит слишком большой вред читабельности программ, который невозможно оправдать. Вообразите, что вы пытаетесь прочитать и понять программу с переходами, цели которых зависят от значений, присвоенных во время выполнения программы. Рассмотрите подпрограмму, имеющую несколько меток и оператор goto, цель которого является формальным параметром. Чтобы определить цель этого оператора goto, необходимо знать вызывающий программный модуль и фактическое значение параметра, используемого при вызове. Реализация переменных ссылок также сложна, в первую очередь из-за всевозможных способов, которыми переменные метки связываются со своими значениями.
3.5.3. Ограничения переходов
Вследствие сложности проблем, присущих операторам goto, большинство языков ограничивает их использование. Для того чтобы показать, как можно ограничить безусловный переход, рассмотрим язык Pascal. Метки в языке Pascal должны объявляться так, как будто они являются переменными, но их нельзя передавать в качестве параметров, хранить в памяти или изменять. Область видимости метки такая 'же, как и у переменных, рядом с которыми она объявлена. В качестве части оператора goto метки должны быть просто константами, а не выражениями или переменными со значениями в виде меток.
Пусть группа операторов представляет собой либо составной оператор, в том числе и полную подпрограмму, либо набор операторов в цикле repeat. Группа операторов является активной, если она начала, но не закончила свое выполнение. Ограничения языка Pascal устанавливают, что целью оператора goto не может быть оператор внутри группы операторов, не являющейся активной. Следовательно, цель никогда не может принадлежать группе операторов, находящейся на том же уровне и вложенной более глубоко, чем оператор goto. Это предотвращает наличие нескольких входов у управляющих структур.
Важная проблема, связанная с ограничениями языка Pascal, состоит в том, что возможен переход во внешнюю подпрограмму. Поскольку подпрограмма, в которую осуществляется переход, является внешней, она должна быть активной. Рассмотрим следующий пример:
procedure subl; label IOCprocedure sub2;
goto 100; end; {sub2}
100: ...
end; {subl}
Оператор goto в этом примере является допустимым. Он передает управление в родительскую подпрограмму subl, прерывая выполнение подпрограммы sub2, в которой находится оператор goto. Таким образом, оператор goto может прерывать выполнение одной или нескольких процедур, но не может инициировать их выполнение путем перехода внутрь одной из них. Конечно, переход к оператору, являющемуся вызовом некоторой процедуры, неявно приводит к началу выполнения этой процедуры.
Переход из одной процедуры в другую крайне вреден для читабельности программы и, следовательно, нежелателен. Поскольку в языке Pascal цели операторов goto ограничены внешними группами операторов, за исключением подпрограмм, можно предположить, что это сделано для повышения безопасности программ.
Положительным результатом таких ограничений в языке Pascal является возможность перехода из процедуры к ее родительской процедуре или другому предку. Это позволяет передавать ошибочные условия в родительские процедуры для исправления. Этот процесс, однако, лучше реализуется с помощью механизма обработки исключительных ситуаций, разработанного в этом языке. Обработка исключительных ситуаций будет обсуждаться в главе 13.
Все операторы выхода из циклов, рассмотренные в разделе 3.4.3, в действительности являются замаскированными операторами goto. Однако они представляют собой значительно ограниченные операторы безусловного перехода и не ухудшают читабельность программ, поскольку их отсутствие сделало бы код неестественным, и понять его было бы гораздо труднее.
3.6. Защищенные команды
Альтернативные и различные формы операторов ветвления и циклических структур были предложены Дийкстрой (Dijkstra (1975)). Он стремился создать управляющие структуры, которые позволяли бы создавать правильные программы и не требовали бы их верификации или тестирования. Эта методология описана в работе Dijkstra (1976).
Защищенные команды рассматриваются в этой главе, потому что они являются основой двух лингвистических механизмов, разработанных позднее для параллельного программирования в двух языках– GSP (Ноаге, 1978) и Ada. Параллельность в языке Ada обсуждается в главе 12.
Конструкция ветвления, предложенная Дийкстрой, имеет следующий вид:
if <булевское выражение> -> оператор
[] <булевское выражение> -> оператор
[] ...
[] <булевское выражение> -> оператор
fi
Замыкающее зарезервированное слово f i представляет собой открывающее зарезервированное слово, записанное наоборот. Эта форма замыкающего зарезервированного слова была взята из языка ALGOL 68. Маленькие блоки, названные барьерами, используются для того, чтобы отделить защищенные операторы и использовать последовательность операторов.
Эта конструкция ветвления похожа на многовариантное ветвление, но с другой семантикой. Все булевские выражения вычисляются каждый раз при достижении этой конструкции в программе. Если истинными являются несколько выражений, то для выполнения случайным образом выбирается один из соответствующих операторов. Если ни одно выражение не является истинным, возникает ошибка времени выполнения программы, приводящая к прекращению ее выполнения. Это вынуждает программиста рассматривать и перечислять все возможности, как это делается в операторе case языка Ada. Рассмотрим следующий пример:
if i = 0 -> sum := sum + i
[] i > j -> sum := sum = j
[] j > i -> sum := sum + i fi
Если i = 0 и j > i, то эта конструкция случайным образом выбирает первый или третий операторы присваивания. Если i = j и i * 0, то возникает ошибка времени выполнения программы, поскольку нет ни одного истинного условия.
С помощью этой конструкции программист может использовать произвольный порядок выполнения операторов. Например, чтобы найти наибольшее из двух чисел, можно использовать следующий оператор:
if х >= у -> max := х [] у >= х -> max := у fi
Представленный фрагмент программы вычисляет требуемый результат, не переопределяя решения. В частности, если х = у, то не имеет значения, что именно присваивается переменной max. Этот вид абстракции обеспечивается недетерминированной семантикой такого оператора.
Кроме того, конструкцию ветвления Дийкстры полезно использовать в программе, обслуживающей прерывания, которые имеют одинаковый приоритет.
Семантику защищенных команд трудно описать точно. В отличие от разработки программ, при описании семантики блок-схемы могут оказаться полезными. На рис. 3.1 показана блок-схема, описывающая подход, который использует оператор ветвления Дийкстры. Эта блок-схема относительно неточная, что отражает трудности в понимании семантики защищенных команд.
Структура цикла, предложенная Дийкстрой, имеет следующий вид:
do <булевское выражение> -> <оператор> ,
[] <булевское выражение> -> <оператор> [] ... od
Семантика этой конструкции заключается в том, что все булевские выражения вычисляются при каждом повторении цикла. Если истинными оказываются несколько выражений, то один из связанных с ними операторов выбирается для выполнения случайным образом, после чего все выражения снова вычисляются. Когда все выражения одновременно станут ложными, цикл завершается.
Рассмотрим следующий фрагмент программы, приведенный в слегка измененном виде в работе Dijkstra (1975). Значения четырех переменных ql, q2, q3 и q4 должны быть упорядочены так, чтобы выполнялось условие ql < q2 < q3 < q4.
Блок-схема, описывающая подход, используемый оператором цикла Дийкстры, показана на рис. 3.2. Снова отметим, что семантика потока управления в этой конструкции не может быть изображена на блок-схеме точно.
Рис. 3.1. Блок-схема, описывающая подход, использующийся оператором ветвления Дийкстры
Рис. 3.2. Блок-схема, описывающая подход, использующийся оператором цикла Дийкстры
Описанные выше конструкции называются "защищенными командами Дийкстры". Частично, интерес к ним объясняется тем, что они иллюстрируют, каким образом синтаксис и семантика операторов могут влиять на верификацию программ, и наоборот. Верификация программ действительно невозможна, если используются операторы безусловного перехода. Верификация намного упрощается, если используются либо только циклы с условиями и операторы ветвления, подобные операторам ветвления языка Pascal, либо только защищенные команды. Аксиоматическая семантика защищенных команд определена в работе Gries (1981). Однако очевидно, что сложность реализации защищенных команд значительно увеличивается по сравнению с их детерминированными аналогами.
3.3. Выводы
Мы описали и обсудили множество управляющих структур на уровне операторов. Теперь на очереди их краткая оценка.
Во-первых, мы получили теоретический результат, заключающийся в том, что для выражения вычислений абсолютно необходимы только последовательность, ветвление и логически управляемые циклы с предварительной проверкой условий (Bohm and Jacopini, 1966). Этот результат широко используется теми, кто желает запретить все безусловные переходы. Конечно, достаточно уже и практических проблем, связанных с операторами goto, для того чтобы осудить их без подыскивания теоретических причин. Одно из применений оператора goto, которое многие считают достаточным для его оправдания, состоит в использовании его для преждевременного выхода из циклов в языках, в которых для этого не предусмотрены специальные операторы выхода.
Не следует на основании результата Бема и Джакопини возражать против включения в язык любых управляющих структур, кроме ветвления и логически управляемых циклов с предварительной проверкой условий. Не существует ни одного широко используемого языка программирования, в котором был бы сделан такой шаг; кроме того, мы сомневаемся, что такой язык вообще когда-нибудь появится, вследствие влияния такого шага на читабельность и легкость создания программ. Программы, написанные с использованием исключительно операторов ветвления и логически управляемых циклов с предварительной проверкой условий обычно имеют менее естественную структуру, являются более сложными и, следовательно, более трудными для создания и чтения. Например, многовариантная структура ветвления языка Ada намного облегчила написание программ на этом языке без явных негативных последствий. Другим примером является цикл со счетчиком во многих языках, особенно, если этот оператор является таким же простым, как в языках Pascal и Ada.
Не всегда ясно, оправдывает ли полезность управляющей структуры ее включение в языки программирования (Ledgard and Maccotty, 1975). Этот вопрос следует из вопроса: надо ли минимизировать размеры языков. И Вирт (1975) и Хоар (1973) настаивают на простоте при разработке языка, т.е. в языке должно быть только несколько управляющих операторов, и все они должны быть простыми.
Разнообразие изобретенных управляющих структур на уровне операторов отражает расхождение во мнениях среди разработчиков языков программирования. После всех изобретений, обсуждения и оценок все еще нет единодушного мнения о том, какой именно набор управляющих операторов должен быть включен в язык. Многие современные языки, конечно, имеют подобные управляющие операторы, но все еще остаются большие вариации в деталях их синтаксиса и семантики. Кроме того, сохраняются разногласия по поводу того, должен ли язык программирования содержать оператор goto; языки C++ и Ada используют этот оператор, а языки Modula-2 и Java – нет.
Резюме
Управляющие операторы в императивных языках программирования разделяются на несколько категорий: операторы ветвления, многовариантные операторы ветвления, операторы цикла и операторы безусловного перехода.
Язык FORTRAN впервые ввел в практику программирования одновариантный оператор ветвления – логический оператор IF. Оператор ветвления в языке ALGOL 60 более сложен и позволяет выбирать составные операторы, а также использовать необязательный оператор else. Многие управляющие структуры выиграли от использования составного оператора, введенного в языке ALGOL 60.
Арифметический оператор IF языка FORTRAN– это трехвариантный оператор ветвления, требующий наличия других безусловных переходов.
Язык FORTRAN ввел в практику две формы многовариантных операторов ветвления: вычисляемый оператор GO TO и назначенный оператор GO TO. В точном соответствии со своими названиями они представляют собой многовариантные операторы ветвления. Оператор case языка Pascal является представителем современных многовариантных операторов ветвления; он содержит инкапсуляцию выбираемых сегментов и неявные переходы в конце каждого из них на одну точку выхода.
Языки Modula-2, C++, FORTRAN 90, Java и Ada имеют операторы выхода из своих циклов; эти операторы заняли место одного из наиболее распространенных употреблений оператора goto.
Итераторы, основанные на структурах данных, являются конструкциями цикла для обработки таких структур данных, как связные списки, мусор и деревья.
Безусловный переход, или оператор goto, был частью большинства императивных языков. Проблемы, связанные с ним вызвали широкое обсуждение и дебаты. Вывод таков: этот оператор должен остаться в большинстве языков, а опасность, которую он представляет, минимизируется за счет дисциплины программирования.
Защищенные команды Дийкстры являются альтернативными управляющими конструкциями, имеющими положительные теоретические характеристики. Несмотря на то что они не были одобрены в качестве управляющих конструкций языка программирования, частично их семантика была реализована в механизме параллельности в языках CSP и Ada.
Вопросы
- Дайте определение управляющей структуры.
- Дайте определение блока.
- Какие вопросы разработки связаны со структурами ветвления?
- Как обычно решаются проблемы, связанные со вложенными двухвариантными конструкциями ветвления? Что неправильно сделано в языке Modiula-2?
- Какие вопросы разработки связаны с многовариантными структурами ветвления?
- Что составляет основу управляющих операторов языка FORTRAN I?
- Какие недостатки имеет арифметический оператор IF языка FORTRAN?
- Что необычного есть в многовариантном операторе ветвления языка С? Какие проектные компромиссы были достигнуты при его разработке?
- Какие проблемы возникают при разработке циклов со счетчиком?
- Что представляет собой цикл с предварительной проверкой условий? Что представляет собой цикл с последующей проверкой условий?
- Какое самое значительное изменение было сделано в операторе DO языка FORTRAN 77 по сравнению с языком FORTRAN IV?
- Какие свойства оператора for языка ALGOL 60 делают использующие его программы трудными для чтения?
- В чем заключается разница между оператором for языка C++ и аналогичным оператором языка Java?
- Какие проблемы возникают при разработке циклов с условиями?
- Какова основная причина изобретения управляющих операторов, определяемых пользователем?
- Какие преимущества имеет оператор exit языка Ada над оператором break языка С?
- В чем заключается разница между оператором break языка C++ и аналогичным оператором в языке Java?
- Что представляет собой управление циклом, определяемое пользователем?
- Каковы два недостатка переменных меток в языке PL/1 ?
- В чем состоит основная проблема, связанная с ограничениями, наложенными на использование оператора goto в языке Pascal?
- Какие распространенные языки программирования заимствовали часть своей структуры у защищенных команд Дийкстры?
Упражнения
- Обоснуйте утверждение, что трехвариантный оператор ветвления языка FORTRAN I наиболее соответствовал ситуации во время его разработки.
- Придумайте ситуацию, в которой переменная метка языка PL/1 имела бы большое преимущество.
- Опишите три ситуации, в которых необходимо объединение цикла со счетчиком и логически управляемого цикла.
- Сравните вычисляемый оператор GO TO языка FORTRAN с оператором case языка Pascal, особенно с точки зрения читабельности и надежности.
- Каковы возможные причины, по которым язык Pascal содержит цикл с последующей проверкой условия, в то время как язык ALGOL 60 такого цикла не имеет.
- Изучите свойства итератора языка CLU, описанного в работе Liskov (1984), и определите его преимущества и недостатки.
- Сравните набор управляющих операторов языка Ada с аналогичным набором в языке FORTRAN 77 и решите, какой из них лучше и почему.
- Назовите аргументы "за" и "против" использования уникального замыкающего зарезервированного слова в составном операторе.
- Проанализируйте потенциальные проблемы читабельности, возникающие при использовании в качестве замыкающего зарезервированного слова для управляющих операторов обратной перестановки букв открывающего зарезервированного слова, например, case-esac в языке ALGOL 68. Рассмотрите распространенную ошибку набора, заключающуюся в перестановке соседних букв.
- Перепишите приведенный ниже фрагмент кода с использованием структуры цикла на следующих языках.
- Pascal.
- FORTRAN 73.
- Ada.
- С, C++или Java.
k:= (j + 13) / 27
loop:
if k > 10 then goto out
k := k + 1
i := 3 * k 1
goto loop out: ...
Предполагается, что все переменные являются целочисленными. Определите, какой язык для этого кода предоставляет наибольшую легкость написания программы, наилучшую читабельность и оптимальную комбинацию этих свойств.
11. Решите заново упражнение 10, только на этот раз предположите, что все переменные и константы представляют собой числа с плавающей точкой, и измените оператор
к := к + 1
на
к := к + 1.2
12. Перепишите приведенный фрагмент кода с использованием многовариантного оператора ветвления на следующих языках.
- Pascal.
- FORTRAN 90 (найдите описание этого языка в тексте).
- Ada.
- С, C++или Java.
if (k = 1) or (k = 2) then j := 2 * k 1
if (k = 3) or (k = 5) then j := 3 * k + 1
if (k = 4) then j := 4 * k 1
if (k = 6) or (k = 7) or (k = 8) then j := k 2
Предположите, что все переменные являются целочисленными. Рассмотрите относительные достоинства использования этих языков для данного конкретного кода.
13. Рассмотрите следующий оператор for в стиле языка ALGOL 60:
for i := j + 1 step i * j until 3*jdoj :j + 1
Предположите, что начальное значение переменной j равно 1. Перечислите последовательность значений использованной переменной i, предполагая следующую семантику.
- Все выражения вычисляются по одному разу при каждом входе в цикл.
- Все выражения вычисляются перед каждым повтором.
- Выражения step вычисляются один раз при входе в цикл, а выражения until вычисляются перед каждым повтором.
- Выражения until вычисляются один раз при входе в цикл, а выражения step вычисляются перед каждым повтором сразу после увеличения счетчика цикла.
Все одновременно вычисляемые выражения вычисляются справа налево. Кроме того, присваивание всегда выполняется, как только оказывается вычисленной правая часть оператора присваивания.
14. Рассмотрите следующий оператор case язык Pascal. Перепишите его, используя только двухвариантные операторы ветвления.
case index 1 of
2, 4: even : even + 1;
1, 3: odd := odd + 1;
0: zero : = zero + 1;
else error := true
end
I
15. Рассмотрите следующий фрагмент программы на языке С. Перепишите его, не используя операторы goto и break.
J = -3;
for (i=0; i < 3; i++) { switch (j + 2) { case 3:
case 2; j –; break; case 0: j +=2; break; default: j = 0;
}
if (J > 0) break;
j = 3 i }
16. В письме редактору журнала САСМ Рубин (Rubin, 1987) использует следующий сегмент кода в качестве доказательства того, что читабельность некоторых программ, содержащих операторы goto, лучше, чем читабельность аналогичных программ, не использующих операторы goto. Этот код находит первую строку матрицы целых чисел размером п х п с именем х, не содержащую ничего, кроме нулей.
for i := 1 to n do begin
for j : = 1 to n do
if x[i,j] <> 0
then goto reject; writeln('Первая нулевая строка:', i); break; reject: end;
Перепишите этот код без использования операторов goto на одном из следующих языков: С, C++, Pascal, Java или Ada. Сравните читабельность вашего кода с читабельностью кода, приведенного выше.
13. Приведите аргументы "за" и "против" исключительного использования булевских выражений в управляющих операторах языка Java (в отличие от языков С и C++, допускающих использование арифметических выражений в управляющих операторах).
2. тематизацію риторичних знань античності
3. Попытка 1 Начало формы Question1 Баллов- 1 Установите соответствие характеристик уровням формирования кол
4. Фет АА
5. множественная миелома в 1873 г
6. Пламя - КВ.html
7. Archimedes of Syracuse
8. і. Константи не змінюють свого значення до завершення роботи програми
9. тема незамкнутая
10. .1Местоположение объекта озеленения 5 1.
11. . Квотирование импорта ~ экспорта ~ установление ограничения на ввоз или вывоз товаров в количественном или
12. Курсовая работа- Промежуточная бухгалтерская отчетность
13. Маркетинг образования
14. Философский смысл и проблемы субстанции
15. Развитие графических образов в рисунках детей старшего дошкольного возраста в процессе ознакомления
16. 9кл 11-1215-16 лет Подросток в одно и тоже время ~ и ребенок и взрослый а точнее сказать уже не ребенок но ещ
17. Жизнь Карла Густава Юнга
18. Экология ХМАО (Ханты-Мансийский Автономный Округ)
19. Электронная таблица ~ это информационная технология для профессиональной работы с данными представляюща
20. по теме Эволюция человека на Emil olgkmilov@mil