Лекция 7
Лекция 7
Записи
На прошлой лекции мы рассмотрели массивы. Если массив - это декартово произведение D*…*D, то запись это D1*…*Dn. В отличие от массива, у которого основная операция – индексирование [ ], у элементов записи есть операция name.id, которая применима слева к объекту типа запись, а справа – к имени поля. Синтаксис записи во всех языках практически одинаков. Если мы заключаем набор объявлений переменных в скобки, то эта совокупность объявлений считается локализованной в записи, и доступ к ним может быть только по имени записи. На Паскале это выглядит так
{ record
…
end
}
В основном записи имеют одну и ту же семантику во всех ЯП. Есть только небольшие отличия в ряде ЯП.
Запись понятие старое. Современная точка зрения на ТД – то, что ТД должны характеризоваться множеством значений и множеством операций. Запись в чистом виде – это множество значений (структура данных) без операций. Поэтому необходимы в современных ЯП специальные механизмы, которые позволяют объединить структуру данных и операции.
Рекомендуемые материалы
Первый класс языков – это языки модульного типа. Это такие языки как Ада, Модула 2, Оберон и Оберон 2. В них есть специальная конструкция модуль, которая как раз и объединяет вместе запись – структуру данных и набор операций.
Подход, который используется в С++ несколько другой. Там само понятие записи обобщается таким образом, чтобы служить одновременно и модулем и структурой данных. В этом языке очень удачно произведена концепция расширение понятия записи до понятия класса. Т.е. в языке С++ как и в С остались записи. Тем не менее структура в языке С++ является одновременно и классом. Единственное отличие записи от класса в этом языке состоит в том, что у нас по умолчанию доступ ко всем элементам записи публичен. Т.е.
struct S{
…
};
абсолютно эквивалентно
class S{
public
…
};
Спецификатор доступа public делает все члены класса публичными.
Чем структура языка С отличается от структуры языка С++? В С++ имя S является обозначением типа и, следовательно, мы можем объявлять переменные типа S.
S x;
В языке С этого делать нельзя. В этом языке соответствующее имя является так называемым тэгом структуры. В С такую переменную надо объявлять
struct S x;
То же самое распространяется и на некоторые другие типы данных в языке С. Например объединения, перечисления и т.д..
Все имена, которые вводятся таким образом, не являются обычными именами данных, именами функций. Они принадлежат своему отдельному пространству. Имена данных в языке С могут быть структурированы. Например
void f {
int x; { double x; …}
}
Т.е. пространство имен в языке С является блочно структурированным, как и во многих других блочных языках. Пространство имен структур не является структурированным вообще. Оно представляет собой одну глобальную таблицу имен. Мы можем описать структуру
struct S {
struct C { … }
…
}
Видимым является не только имя структуры S, но и имя структуры C. Теперь мы можем писать
struct S x;
struct C i;
По-хорошему, надо бы считать структуру С вложенной. Как имена соответствующих объектов данных, которые описаны внутри структуры S, являются локализованными внутри S, так резонно считать, что и структура С локализована внутри структуры S.
В С++ структура – это класс, а класс может иметь вложенный класс, причем имя вложенного класса должно быть локализовано. Беда в том, что тем, что имена структур составляют свое собственное пространство имен, программисты часто пользовались на языке С. Постоянная ситуация: есть структура struct S и есть функция, которая эту структуру возвращает S( ){ }. В языке С подобного рода ситуации возможны потому, что тэг структуры и имя функции S находятся в разных пространствах имен, которые могут пересекаться. Подобного рода структуры мы наблюдаем в стандартных заголовках ОС UNIX. Есть struct stat, есть функция stat( ), которая выдает struct stat. Страуструп не мог составить язык таким образом, чтобы в этом языке не компилировался стандартный заголовочный файл ОС UNIX. Именно это требование было основным с точки зрения совместимости двух языков. Программы можно переделать. Например, заставить программиста прототипировать все функции. Это необходимо на языке С++ хотя бы потому, что в нем появился новый ссылочный ТД, и следовательно передача параметра по ссылке. Изменить программы на языке С так, чтобы они компилировались на языке С++ достаточно просто. Если программа написана на ANSI C, то она будет компилироваться и на С++. А стандартные заголовки ОС переделывать никто не будет. Поэтому совместимость по объявлениям должна быть полной. Было принято компромиссное, но в то же время удачное решение. Имена структур могут совпадать с именами функций. В этом случае считается, что имя функции закрывает имя типа, но к имени этого типа возможен доступ с помощью struct S. Обращаться ко вложенным структурам на языке С++ нельзя. Но оказалось, что подобного рода прием программисты используют достаточно редко.
В С++ все, что можно делать с классами, можно делать и со структурами: добавлять туда члены, управлять доступом, видимостью и т.д..
Несколько по-другому поступили создатели других языков программирования. Например, в языке Delphi тоже нужно было обеспечить совместимость с Турбо Паскалем. Объекты Delphi происходят из шестой и седьмой версии Паскаля, которые уже были объектно-ориентированными. В Турбо Паскале есть обычное понятие записи. Понятие класса в Delphi никакого отношения к записям не имеет. Т.е. вместо того, чтобы расширять старое понятие, придавая ему новую семантику, создатели языка Delphi оставили старое понятие записи. А то, что называется классом, вначале в Турбо Паскале имело название object. А в Delphi используется ключевое слово class. Слово object в Delphi осталось только для совместимости. Одно из основных отличий класса от обычных записей на языке Delphi в том, что все классы имеют ссылочную семантику, а записи – нет. Записи имеют обычную семантику размещения данных, т.е. они не будут размещаться в динамической памяти, если, конечно, мы их не разместим явно.
В языке Java, для которого проблема совместимости отсутствовала, понятия записи отсутствует. Но в ряде случаев понятие структуры оказывается достаточно эффективным. Классический пример:
Class Point {
…
int x,y;
};
В языке Java класс имеет только ссылочную семантику, то массив
Point [ ] arr = new Point [100];
выглядит так: каждый элемент массива есть Point, а каждый Point – ссылка. Причем в начальный момент этот массив проинициализирован нулевыми ссылками. Поэтому необходимо еще провести инициализацию каждого элемента массива:
for (int i= 0; i<100; i++)
arr[i]= new Point;
Мы получаем накладные расходы, как по времени, так и по памяти. Тип данных точка состоит всего из двух полей, а все остальное – операции. И от этого класса никто ни чего скорее всего наследовать не будет, это просто некоторый рабочий класс. Получается, что половина выделяемой памяти лишняя.
В языке С++ такой проблемы нет. Либо мы в языке С++ описываем массив из указателей, либо массив из структур, и тогда все эти структуры размещаются единым блоком памяти. Такое решение более эффективно.
Создатели языка C# пошли на некоторый компромисс. Радикальный подход языка Java, когда у нас нет понятия записи, а есть только понятие класса, а классы во всех современных языках имеют исключительно ссылочную природу, в некоторых случаях оказывается накладным. В языке С++ таких проблем нет, поскольку классы не имеют ссылочной семантики. Создатели C# хотели, с одной стороны, оставить ссылочную семантику класса, а с другой стороны, сделать так, чтобы в некоторых случаях программист мог управлять эффективностью распределения памяти. Поэтому в языке C# появилось понятие структуры
struct {
…
};
которое как и в языке С++ идентично понятию класса,
class{
…
};
Но в классе доступ по умолчанию приватный, а в структуре доступ по умолчанию так называемый внутренний. Кроме того, структура не имеет ссылочной семантики. Если мы Point описали как структуру в языке C#, то arr будет размещаться единым блоком памяти.
Кроме этого, структуры, в отличие от классов мы не имеем права выводить из других классов. Считается, что структура всегда неявно выведена из базисного ТД object, из которого явно или неявно выведены все остальные классы C#. От структуры ничего нельзя наследовать, т.е. структура создается только как оконечный класс. Есть еще ряд отличий, например, в структурах нельзя писать свой конструктор по умолчанию. Т.е. структура в языке C# - ограниченный вид класса, который нужен для того, чтобы ликвидировать некоторую неэффективность, которая связана с чисто ссылочной семантикой класса.
Объединения.
В старых языках возникает еще одно понятие, которое тесно связано с понятием записи. Это понятие объединения. Они появились одновременно с записями. Есть два вида объединений – размеченные и неразмеченные. Пример неразмеченного объединения – объединение в языке С и, следовательно в языке С++
union …{
…
}
Объединение – отождествление нескольких различных структур записи. Зачем оно нужно? Традиционные ЯП поддерживают в той или иной степени концепцию уникальности типа. Основной ее пункт гласит, что каждый ОД имеет только один тип, и этот тип не может меняться. В соответствии с этой концепцией у нас множество объектов делятся на непересекающиеся классы эквивалентности, которые мы и называем ТД. Преимущество этой концепции в надежности, т.к. возникает возможность контроля. Основной недостаток в том, что при такой концепции труднее становится моделировать поведение реального мира. Мы сталкиваемся с тем, что каждый объект реального мира играет различные роли. Например, человека можно рассматривать с одной стороны как, некоторую абстрактную запись в некоторой БД, а с другой стороны его можно рассматривать как некоторый живой организм со своими свойствами. Книга - с одной стороны некоторый информационный объект, который хранится в БД библиотеки. Про нее хранится название, автор, рубрика, кодировка, ключевые слова. Но с другой стороны книга является и физическим объектом, у которого есть объем, вес и т.д.. Подобного рода информация может пригодиться, когда обсуждается вопрос переезда библиотеки из одного здания в другое. Каким образом объединить эти роли – книга, как физический объект и как информационный объект? Каждая роль отражается каким-то ТД. Т.е. набор атрибутов, который описывает книгу как физический объект один, а набор атрибутов, который описывает книгу как информационный объект другой. Какой тип данных выбрать для передачи в процедуру, обрабатывающую данные типа книга. Проблема конфликтности ролей, т.е. то, что в реальном мире объекты играют разные роли, а в классических ЯП эта роль может быть только одна, и она описывается своим ТД, - это так называемая Янус-проблема. Чем ближе программная модель к модели реального мира, тем сильней обостряется эта проблема. Например, самой адекватной моделью пользовательского интерфейса в данный момент является событийная модель. В системе происходят некоторые события. Например, есть внешние события, такие как прерывание от таймера. И система должна реагировать на эти события. Разумеется, ТД события является ключевым в подобного рода системах. Что должен описывать ТД события? С клавиатурным событием мы связываем информацию о том, какая клавиша нажата, нажата она или отпущена и т.д.. С событием прерывание по таймеру связано время поступления события. С событием нажатия кнопки мыши связна информация о том, какая кнопка нажата, нажата она или отжата. С событием движения мыши связана информация о координатах. Фактически получается, что любое внешнее событие описывается своим набором параметров. Общее у них только время поступления. У нас ТД события является объединением разных типов. У всех событий есть общая часть – время поступления, а все остальное разное.
В ООЯП эта проблема решается с помощью наследования. У нас есть некоторый базовый класс, а далее мы из него выводим остальные классы.
Event
KBEvent MouseEvent TimerEvent
В традиционных ЯП решить эту проблему можно только с помощью объединений. Объединение – расширения понятия записи. Впервые объединения появились в языке Паскаль. Запись в Паскале – это постоянная часть и вариантная часть. Этот синтаксис был принят и в других языках практически один в один.
record
{ постоянная часть – возможно пустая совокупность описания полей ]
[ возможно пустая вариантная часть ]
end;
При этом вариантная часть выглядит так
case имя_дискриминанта : тип of
значение 1: (структура 1);
значение 2: (структура 2);
…
Где каждая структура является описанием записи без скобок и слов record, end.
Есть специальное поле, которое мы называем дискриминант. Структура записи выглядит следующим образом
 |
постоянная часть
 |
дискриминант
структура 1 структура 2 структура 3 …
 |
Структуры 1, 2 и 3 могут сильно отличаться.
Тип события может быть описан так: в постоянной части - время наступления этого события, дискриминант – вид события. Имеет смысл описывать подобного рода дискриминанты как данные перечислимого типа, хотя никто не запрещает поступать по-другому, главное чтобы тип был дискретный, как в операторе выбор. После дискриминанта идут различные структуры, описывающие тот или иной тип события, и они размещаются с одного адреса. Процедура обработки события
procedure HandleEvent (VAR E: Event);
которой по ссылке передается параметр - событие, будет выглядеть как большой оператор выбора
case E.EvType of
KBEvent: begin … end;
MouseEvent: begin … end;
…
end;
Языковые абстракции оператор выбора и объединение очень тесно связаны между собой. И программа в большинстве случаев имеет такой вид. Это позволяет считать, что Event – это в некотором смысле какой-то обобщенный ТД, который служит объединением частных случаев.
У данного стиля программирования есть проблема, связанная с ненадежностью. Программист сам должен связывать значение дискриминанта и операторы обработки. Никаких возможностей контроля у компилятора нет. Значение дискриминанта в языке Паскаль мы можем ошибочно изменить. В результате память отведена по одному варианту, но дискриминант изменен, и поэтому программа, которая обрабатывает соответствующие части, будет работать не правильно. Может получиться так, что память отведена по самому короткому варианту, а мы ошибочно поменяли значение дискриминанта и работаем по длинному варианту. Следовательно, мы портим память.
VAR x: Event;
В большинстве языков, в которых есть вариантные записи, компилятор в случае такого объявления отводит память по максимуму.
В языке Паскаль есть специальная процедура new(p), где р – указатель на тип данных Т. У этой процедуры есть еще один синтаксис: new(p, t1, …,tn). В случае, если р указывает на запись с вариантами, то t1, …, tn – значения дискриминантов во вложенных вариантных записях. Но в реальной жизни, как правило, синтаксис сводится к new(p, t), где t – это значение дискриминанта. В этом случае память будет отводиться по тому варианту, на который указывает значение t. Самое неприятное в этой процедуре то, что в Паскале в этот момент не происходит инициализация дискриминанта. Надо писать что-то вроде
p^.discr := t;
Возникает некоторая ненадежность. Если мы напишем
new(p, t1);
p^.discr := t2;
память будет отведена по одному варианту, дискриминант проинициализирован по другому варианту.
Записи с вариантами необходимы. Поэтому объединения есть во всех традиционных ЯП.
Приведенный синтаксис в языке Паскаль не полный потому, что имя дискриминанта может отсутствовать. А зачем нужен дискриминант, если поле отсутствует? А как без этого в языке Паскаль, реализованном на машине БЭСМ-6, получить доступ ко всем видам числа? Описать соответствующую структуру как неразмеченное объединение.
type word =
record
case Boolean of
true:(bits: packed array[1..48] of Boolean);
false:(w: integer);
end;
48 битов – длина ячейки памяти в соответствующей архитектуре. integer занимает 48 битов. Значит, обе эти части занимают одно и то же место, но они задают разную интерпретацию. Таким образом, на уровне языка без всяких побитовых операций мы можем получить доступ к отдельным битам. Т.е. описывая переменную
x: word;
мы можем писать
x.w := 127;
x.bits[1] – доступ по другому варианту. При этом нет никакого явного дискриминанта. Иногда нам нужны неразмеченные объединения. В языке С только неразмеченные объединения без постоянной части. По определению все поля, которые описаны в union, размещаются с одного и того же адреса.
Есть еще одна проблема – проблема трудной модификации программ. Если у нас есть некий комплекс процедур и функций, основанных на механизме событий, и появляется новое периферийное устройство, появляется еще один класс событий. Это события, которые поступают от нового периферийного устройства. Нужно расширить соответствующий ТД, пролистать всю программу, найти везде соответствующие case и расширить их. В случае если мы модифицируем объединение, мы должны модифицировать практически всю программу. Мы должны перекомпилировать всю систему. Если мы забудем что-нибудь исправить, это значит, что данный тип события в данном обработчике обрабатываться не будет. Компилятор не сможет найти такую ошибку.
Ненадежность и трудность модификации – основные проблемы, связанные с объединениями в традиционных ЯП.
Язык Ада создавался прежде всего с расчетом на надежность. Каким образом создатели языка Ада попытались решить эту проблему? Принцип языкового дизайна языка Ада: если есть какая-то критичная технологическая потребность, в базис языка вводится некоторая конструкция, которая отвечает этой критичной технологической потребности. Для решения проблемы объединения типов появляется новая концепция – параметризованные типы записи. Общий синтаксис параметризованной записи
type T(Discr: DT) is record
[постоянная часть]
case Discr of
when зн1|зн2|зн3 => вариант1 вариантная
when зн4 => вариант2 часть
…
end record;
Т.е. мы параметризуем запись дискриминантом. Ситуация аналогична ситуации с неограниченными массивами. Мы не можем написать
А:T;
потому, что компилятор не знает по какому варианту выделять место в памяти. В других языках в этом случае компилятор отводил максимальную память. В Аде память отводится ровно по тому варианту, который указывается. Такой не уточненный объект может применятся только как формальный параметр процедур.
А:T(t);
t должно принадлежать дискриминантному типу DT.
Тоже самое и в случае, если ОД размещается в динамической памяти.
type PT is access T;
X: PT := new T(t);
Просто написать new T в этом случае нельзя – компилятор выдает ошибку. Нельзя описать ОД без указания значения дискриминанта. При этом автоматически происходит инициализация значения дискриминанта. Изменяться значение дискриминанта не может. Т.е. мы не имеем права писать
A.Discr := -1;
Все объединения могут быть только дискриминированными, т.е. размеченными.
Таким образом часть ненадежности снимается. Однако проблемы с трудностями модификации остаются. ООЯП эту проблему снимают. В современных ООЯП, особенно в тех, которые проектировались без соображений совместимости с существующими языками, понятие запись с вариантами отсутствует. Это такие языки как Java, C# и Оберон. В языках С++ и Delphi понятие записи с вариантами осталось исключительно для совместимости со старым кодом. И если понятие struct расширено в языке С++, то понятие union никаким образом не расширяется потому, что в программах на С++ union употреблять не надо. В С++ есть механизм наследования, который обеспечивает механизм объединения типов, но без проблем, связанных с записями с вариантами. Именно поэтому в основном все современные языки объектно-ориентированные.
Множество.
Впервые множества появились в языке Паскаль.
type T = set of D;
где D – это некоторый дискретный тип данных. Основные операции, которые можно проводить над множествами это операция объединения двух множеств +, операция разности двух множеств -, операция пересечения двух множеств *. Кроме это есть конструктор множества [x1, …, xn]. Операция x in S дает логический результат – true, если х содержится в S, и false, если нет. Операция добавления элемента выглядит так
S:= S+[x]
Аналогично исключение элемента может быть описано с помощью операции -.
В языке Модула 2 была полностью перенята эта концепция, за исключением того, что для повышения эффективности компиляции были введены псевдофункции INCL(S, x) - включить элемент х в множество S, и EXCL(S, x) – исключить элемент х из множества S. В стандарте языка Паскаль ничего не сказано про мощность множества D. Но в большинстве реализаций она ограничена. Наиболее простая реализация множества – упакованный массив булевского типа.
packed array [D] of boolean;
Индекс D дискретного типа. Если S – переменная этого типа, то, если S[x]=true x содержится в этом множестве, если S[x]=false – не содержится. В Паскале, Модуле 2 и многих других языках множество реализуется в виде битовой шкалы, которая пакуется в одно или два машинных слова. Отсюда ограничение на размер множества в 32 или 64 элемента. Основное назначение множеств в такой реализации – именованный доступ к отдельным битам числа. В Паскаль и Модула 2 нет побитовых операций потому, что их можно заменить манипуляциями с объектами множества. Установка бита – включение соответствующего значения, сброс бита – исключение. Чаще всего такие манипуляции с именованными битами нужны для программ, которые управляют вводом/выводом. Регистры устройств – некоторые ячейки памяти. В ряде систем регистры устройств являются частью ОП (например, система PDP 11), а в ряде систем это особые отдельные ячейки, которые адресуются с помощью специальных команд ввода/вывода in и out (например, системы, построенные на базе процессоров Intel). Управление внешними устройствами осуществляется с помощью установки или сброса особых битов в регистрах внешних устройств. Получается, что для решения очень частной задачи в базис языка вводится некоторое понятие.
В языке Модула 2 дополнительно был введен специальный ТД
BITSET = SET OF [0..N-1]
Он был встроен в базис языка (т.е. это стандартный идентификатор языка). N – количество битов в слове для данной реализации.
В языке Оберон все дискретные ТД сводятся к ТД integer. Понятие множества исчезает полностью. Вместо него в Обероне появляется ТД, который называется SET. Он соответствует понятию BITSET в языке Модула 2.
В языке Ада понятия множество нет потому, что в Аде можно описывать упакованные массивы. Вместо того, чтобы встраивать в базис языка ТД множество, Ада предлагает нужный вариант множества реализовать в виде упакованного массива. В языке Ада можно перекрывать стандартные знаки операций. Учитывая это, можно описать ТД – упакованный массив логических чисел, перекрыть для него операции +, * и - , и работать с ним, как мы работали с множествами в языке Паскаль.
В современных ООЯП, таких как Java, C#, Delphi, C++, понятие множества отсутствует. Реализация множества на Паскале – битовая шкала. Множество можно реализовать и на других структурах данных. Множество всех целых чисел в виде упакованного массива скорее всего представить не удастся – большим будет диапазон индексов. А с помощью дерева поиска – можно. Тогда операция поиска – реализация операции in. При этом множество превращается в более обобщенное понятие – таблица. В множестве мы храним булевское значение, которое говорит есть элемент в множестве или нет. В таблице есть понятие ключа и связанное с ним понятие данных. Т.е. в таблице хранятся данные, а ищем мы их по ключу. В простейшем случае ключ может совпадать с данными, в этом случае мы приходим к обычному понятию множества. Таблица может реализовываться с помощью дерева поиска, хэш-таблицы. Какая реализация лучше – зависит от ситуации. (В случае если размер данных сопоставим с размером хэш-таблицы, она перестает работать. Есть специальные методы перехэширования.) Поэтому встраивать какой-то вариант в язык – не лучшая идея.
С++ предлагает стандартную библиотеку шаблонов STL, в которой есть тип Мар. Любая библиотека классов в любой реализации С++ обязательно предлагает свой набор таблиц. Множества и таблицы не встраиваются в базис языка, а моделируются с помощью стандартных библиотек.
Исключением служит язык Perl. В нем есть понятие ассоциативного массива. Это разновидность таблиц.
@names = {"igor", "sergey", "anton",…}
names["anton"] = 1;
Это способ реализации таблицы, где ключом служат строки. Perl язык без типов. Значением данных может быть значение любого объекта в языке.
X = @names["anton"];
Perl – язык скриптовый. Его цель не создание огромных системных библиотек, а быстрый способ написания программ, которые могут манипулировать с какого-либо рода данными. С этой точки зрения раздутие базиса ассоциативным массивом недостатком не является. Но когда идет речь о языке общего назначения, добавление подобного рода конструкций в базис выглядит весьма непривлекательно. Вместо этого есть понятие стандартной библиотеки. В Java – это просто набор пакетов в Языке Java. В С# это .NET Framework. Это набор классов и ТД, которые едины для всей системы .NET, и для всех языков, которые включены в эту систему.
Файлы.
В стандартном Паскале
write(…);
- это не процедура. На языке Паскаль нельзя написать процедуру, которая имеет переменное число параметров разных типов. Это псевдопроцедура. Встраивание в язык подобного рода процедур не очень хорошо. Начиная с языка С ввод/вывод не является частью языка. Вместо этого есть стандартные пакеты и стандартные библиотеки, которые обслуживают потребности ввода/вывода.
Глава 3: Управление последовательностью действий.
Рассмотрим операторный базис. Если с точки зрения ТД в ЯП существует какое-то разнообразие, то с точки зрения набора операторов современные языки очень похожи друг на друга. Разница между реализациями операторов в основном синтаксическая.
Самый главный оператор в традиционных ЯП – это оператор присваивания.
v:= e
В компиляторе он самый сложный с точки зрения реализации. Все остальные операторы сводятся к выполнению операторов присваивания в определенном порядке.
Операторы, управляющие последовательностью действий:
- оператор ветвления
- циклы
- переходы
В FORTRAN был один оператор ветвления, цикл с фиксированным числом повторений и четыре варианта перехода. Оператор ветвления рассматривался как частный случай оператора перехода. FORTRAN задумывался как язык программирования блок-схем. Поэтому самым важным после оператора присваивания был оператор перехода. Такая же ситуация была и в последующих ЯП, каждый из которых содержал несколько вариантов оператора перехода.
Ситуация изменилась в 1968, когда появилась знаменитая статья Дейкстры о вредности оператора goto. Впервые было высказано соображение что, если программист отказывается от каких-то приемов, то производительность его труда может возрасти.
Структурированное программирование – течение, появившееся в конце 60-ых г.г., основанное на идеях Дейкстры, Вирта и многих других программистов. Его идея – программирование в терминах некоторых абстракций. Сначала программа представляется как какая-то абстракция, потом эта абстракция реализовывается с помощью абстракций более нижнего уровня, и так до тех пор, пока мы не дойдем до абстракций, представленных конструкциями ЯП. В соответствии с этим подходом с точки зрения передачи управления любая конструкция должна иметь один вход и один выход.
нельзя
 |
Обычные переходы в эту схему не вписываются.
Раз это распространяется на все абстракции, это должно выполняться и для примитивных абстракций.
Оказалось, что такой подход способствует написанию более надежных, более читабельных и лучше модифицируемых программ. Писать программы стало значительно быстрей. В 60-ых г.г. был доказан такой факт, что любую программу можно свести программе, которая использует только операцию ветвления и цикл типа while. Появились программы, которые автоматически переводили неструктурированные программы в структурированные.
Современная точка зрения – все операторы должны представлять из себя некоторую структуру с одним входом и одним выходом.
Условный оператор
B?
S1 S2
Оператор S2 может отсутствовать.
Оператор цикла "пока".
 |
да
B?
нет
S
Оператор цикла "до"
S
да
B?
нет
 |
В 1974 г. Дональд Кнутт – известный программист – опубликовал статью, которая называлась "Структурное программирование с оператором goto". В ней Кнутт обратил внимание, что основная идея структурного программирования – это не программирование без goto. Основная идея структурного программирования, чтобы структура программы отражала структуру алгоритма. Оказывается ветвлений и операторов цикла для этого не хватает. Многие программы имеют такую структуру
 |
Подготовить данные
Обработать
да
Готовы?
нет
 |
Эта структура очень характерна для программ обработки данных. С точки зрения структурного программирования это конструкция, которая имеет один вход и один выход. Смоделируем ее с помощью цикла "пока".
 |
Подготовить
 | |||
 | |||
да
Вам также может быть полезна лекция "Орган зрения".
Готово? Обработать Подготовить
нет
Внешне она выглядит структурно. Однако ее структура хуже, чем была до этого. То же самое произойдет, если мы будем использовать цикл "до". Поэтому ограниченные формы оператора перехода есть во всех современных ЯП. Они моделируют выход из середины цикла.
