Объекты данных

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

ветственно, уменьшает количество совершаемых ошибок. Язык высокого уровня обеспечивает следующие возможности доступа к объектам данных и их обработки:

ссылки на объекты данных с помощью определенных пользователем имен, а не конкретных адресов памяти;

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

Рассмотрим более подробно, как программы оперируют объектами данных. Необходимо четко понимать это, иначе можно попасть в трудное положение при попытке описать некоторые наиболее сложные операции. Например, мы говорим "Х имеет значение 2. 4", хотя на самом деле имеем в виду "Х -- имя области памяти, где в данный момент хранится значение 2. 4".

Здесь мы четко провели различие между тем, где содержится, и тем, что содержится. Или

┌───┐ ╔══════════════════╗ ╔═════╗

│ │──────>║ Тип │ Указатель ║─────>║ ║

└───┘ ╚══════════════════╝ ╚═════╝

ИМЯ Ссылка Значение

Рис. 1. 3

можно сказать "Х имеет значение и", хотя на самом деле имеется в виду "Х -- это имя участка памяти, где в данный момент хранится число, названное п". Путаница между тем, где содержится, и тем, что содержится, возникает из-за того, что в обоих случаях мы используем одно и то же имя. Так, I в левой части оператора

I:=I+1;

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

Таким образом, для обработки объектов данных в программе используются специальные конструкции. Самая важная из них -- переменная, которая определяется тремя характеристиками (рис. 1. 3): ссылкой, однозначно идентифицирующей связанный с переменной объект данных и описывающей тип этого объекта; значением -- хранимым объектом, который обрабатывает программа; именем, под которым переменная известна в программе [49).

Теперь можно показать, как разрешается неоднозначность при использовании имен в таких операторах, как I:=I+1;.Имя I в левой части обозначает ссылку (поскольку оно определяет место для размещения), в правой части -- значение (поскольку оно требуется для вычислений). Таким образом, в правой части неявно выполняется операция определения значения по ссылке.

Переменные вводятся с помощью описаний, например:

I: тип;

┌───┐ ╔══════════════════╗ ╔═════╗

│ I │─────> ║ │ ║─────>║ 0 ║

└───┘ ╚══════════════════╝ ╚═════╝

ИМЯ Ссылка Значение

(не определено)

а)

┌───┐ ╔══════════════════╗ ╔═════╗

│ I │──────>║ │ ║─────>║ ║

└───┘ ╚══════════════════╝ ╚═════╝

ИМЯ Ссылка Значение

б)

Рис. 1.4

По этому описанию создается переменная указанного типа, однако значение ее не задается. Это проиллюстрировано диаграммой на рис. 1. 4, а. Одновременно с созданием переменной можно присвоить ей начальное значение (рис.1. 4,6):

I: тип:= значение;

Рассмотрим возможные способы взаимодействия имен, ссылок и значений переменных. Во-первых, несколько переменных с различными именами и ссылками могут иметь одно и то же значение (рис. 1. 5, а). Во-вторых, несколько переменных с различными именами могут иметь одну и ту же ссылку, а следовательно, и одно и то же значение (рис. 1. 5, б). В-третьих, несколько переменных могут иметь одинаковые имена и различные ссылки (рис. 1. 5, в). (Способы разрешения неоднозначности в последнем случае, а также ситуации, когда возникают такие взаимодействия имен и ссылок, рассмотрим позднее.)

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

┌───┐ ╔══════════════════╗

Х: тип:= 2; │ I │──────>║ │ ║───┐ ┌────────┐

└───┘ ╚══════════════════╝ │───┤ 2 │

┌───┐ ╔══════════════════╗ │ └────────┘

Y: тип:= 2; │ I │──────>║ │ ║───┘

└───┘ ╚══════════════════╝

┌───┐

│ │─┐

└───┘ │ ╔══════════════════╗ ┌────────┐

┌───┐ ├───>║ │ ║─────┤ │

│ │─┘ ╚══════════════════╝ └────────┘

└───┘

╔══════════════════╗ ┌────────┐

┌───>║ │ ║───┤ │

┌───┐ │ ╚══════════════════╝ └────────┘

│ │──┤

└───┘ │ ╔══════════════════╗ ┌────────┐

└───>║ │ ║──┤ │

╚══════════════════╝ └────────┘

которой можно было бы получить доступ к области памяти, где хранится ее значение, и изменить содержимое памяти); она определяется двумя характеристиками: именем и значением (рис.1. 6).

┌─────┐ ╔═════════╗

│ │ ───────────>║ ║

└─────┘ ╚═════════╝

ИМЯ Значение

Рис. 1. 6

Константы имеют предопределенные имена, которые отражают их значения, например 3. 1415926536. Однако часто в программе удобно использовать другие имена для констант, которые можно вводить с помощью описаний следующего вида:

РI: constant тип:=3.1415926536;

Переменные и константы не исчерпывают набора конструкций, используемых для обработки объектов данных. Другие конструкции позволяют обрабатывать безымянные объекты данных (рис.1. 7, а), вводить имена для обозначения объектов некоторого типа данных без создания самих объектов (рис. 1. 7, б), а также вводить имена для объектов данных, тип которых задается во время выполнения программы (рис. 1. 7, в). Подробно описание и использование таких конструкций мы рассмотрим позднее. Здесь лишь заметим, что обработку объектов данных с помощью этих конструкций можно начинать тогда, когда полностью определены и ссылки, и значения.

1.3.2. Типы данных

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

╔══════════════════╗ ╔═════╗

║ │ ║─────>║ ║

╚══════════════════╝ ╚═════╝

Ссылка Значение

а)

┌───┐ ╔══════════════════╗

│ │─────> ║ │ 0 ║

└───┘ ╚══════════════════╝

ИМЯ Ссылка

(не создан объект данных)

б)

┌───┐ ╔══════════════════╗ ╔═════╗

│ │─────> ║ 0 │ ║─────>║ 0 ║

└───┘ ╚══════════════════╝ ╚═════╝

ИМЯ Ссылка Значение

(не определен тип объекта данных

и, следовательно, его значение)

в)

Рис. 1. 7

объектам данных могут присваиваться логически некорректные значения, так, если объект данных используется для подсчета числа появления некоторого события, то присваивание этому объекту отрицательного значения будет некорректным;

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

Ошибки этих классов могут возникнуть в результате ошибок человека при печати, небрежности или логических ошибок, допущенных при разработке программы.

В языке должна быть предусмотрена возможность обнаружения большинства этих ошибок либо компилятором, либо во время работы программы. Однако проверка программы при выполнении уменьшает ее эффективность, поэтому, где это возможно, нужно предпочесть проверку при компиляции. Такую проверку обеспечивает ограничение множества значений и операций, допускаемых для каждого объекта данных, до минимального требуемого. Это может быть сделано при оснащении языка подходящей системой типов данных.

Язык программирования кроме высокой надежности должен обеспечить и адекватное области применения множество типов данных. Современные языки имеют множество предопределенных типов данных и один или более механизмов спецификации типов, определяемых пользователем. Обычно имеются предопределенные целые (integer), действительные (real), символьные (character) и логический (boolean) типы. Над данными числовых типов можно выполнять обычные арифметические операции, операции сравнения; символьные данные можно сравнивать друг с другом; над данными логического типа можно выполнять обычные логические операции. Обозначения операций этих типов обычно совпадают с общепринятыми.

──────────────────────

П р и м е р 1. 1. Описание переменных и запись опе-

раций над данными различных типов:

I: integer:=1;

С: character:='1';

В: boolean:= true;

I+1 I<=2 С>'A' B and false B or true

──────────────────────

Символьные и логический типы определяются перечислением возможных значений -- это так называемые перечислимые типы. Кроме предопределенных перечислимых типов современные языки программирования позволяют определять новые перечислимые типы путем явного указания их значений (констант нового типа).

Имена этих констант выбираются самим программистом из соображений удобочитаемости. Значения перечислимого типа можно сравнивать в порядке перечисления их при определении типа.

Все упомянутые выше типы простые. У объектов простого типа нет внутренней структуры. Языки программирования позволяют определять также структурные типы. Они необходимы по двум причинам. Во-первых, для разработки программ методом сверху вниз нужно иметь возможность описывать данные на различных уровнях. Например, в программе, предназначенной для синтаксического анализа текста, в качестве входных данных можно использовать множество предложений. На высшем уровне разработки входные данные рассматривают как единое целое. По мере уточнения проекта внутренняя структура данных все более детализируется. Сначала различают отдельные предложения, затем каждое предложение разбивается на слова, затем в каждом слове выделяются отдельные слоги и буквы. Таким образом, первоначальная структура данных описывается в терминах более простых структур данных, которые, в свою очередь, описываются в терминах еще более простых структур данных до тех пор, пока в конце не получится описание в терминах простых объектов данных, из которых в конечном счете составлена структура. Во вторых, данные должны быть структурированы, чтобы их можно было эффективно выбирать. Без структурирования данных каждому простому объекту данных должно быть поставлено в. соответствие уникальное имя -- единственное средство ссылки на данные. Поэтому, если одно и то же действие должно применяться к набору одинаковых объектов данных, для обработки каждом индивидуального объекта придется написать свой собственный оператор. При группировке объектов в структуры данных и дальнейшей ссылке на каждый объект с помощью индекса можно будет, например, использовать один-единственный оператор в цикле для выполнения требуемых операций.

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

──────────────────

П р и м е р 1. 2. Описание массива из пяти объектов целого типа, записи из трех объектов целого, символьного и логического типов и обращения к четвертому элементу массива и логической компоненте записи:

А: array (1..5) оf integer;

R: record

I: integer;

С: character;

В: boolean;

end record;

А(4) R.В

Можно считать, что операция выбора элемента массива или записи в качестве результата имеет ссылку на этот элемент (рис. 1. 8). Это пример использования безымянных объектов.

──────────────────────────

Важным частным случаем массивов является массив символов, называемый строкой. Для него обычно вводятся специальные более короткие обозначения, а также специальные обозначения для констант. Например, константа СТРОКА представляет строку из 6 символов. Обычно со строками можно выполнять операцию сцепления (т.е. соединения двух строк в одну).

Механизм массивов и записей предоставляет средства для структурирования данных в пространстве, а механизм объединения -- для структурирования данных во времени,т.е. позволяет обрабатывать разные объекты данных с помощью одной переменной.

┌─────┐ ╦════════════════════╗ ╔═══════════╗

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ║ ║int │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ║ ║int │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ A ├────────>║ ║int │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ┌──>║ ║int │ ║───║──────║──>║ ║ ║

│ │ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ │ ║ ║int │ ║───║──────║──>║ ║ ║

│ │A(4)─┘ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ │ ║ ║ ║

└─────┘ ╚════════════════════╝ ╚═══════════╝

┌─────┐ ╦════════════════════╗ ╔═══════════╗

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ║ ║int │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ R ├────────>║ ║char │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ┌──>║ ║bool │ ║───║──────║──>║ ║ ║

│ │R.B ─┘ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ │ ║ ║ ║

└─────┘ ╚════════════════════╝ ╚═══════════╝

Рис. 1. 8

Это пример динамических структур данных, которые меняют свою форму при выполнении программы.

──────────────────

П р и м е р 1. 3. Описание объединения объектов целого, символьного и логического типов:

U: union

integer;

character;

boolean;

end union;

╔═════╗

║ 0 ║

┌───┐ ╔══════════════════╗ ╔═════╗══╝

│ U │─────> ║ 0 │ ║────────>║ 0 ║

└───┘ ╚══════════════════╝ ╔═════╗══╝

║ 0 ║

╚═════╝

a)

╔═════╗

║ 0 ║

┌───┐ ╔══════════════════╗ ╔═════╗══╝

│ U │─────> ║ char │ ║─────────>║ 'A' ║

└───┘ ╚══════════════════╝ ╔═════╗══╝

║ 0 ║

╚═════╝

б)

Рис. 1. 9

В каждый момент времени переменная, конечно, имеет один вполне определенный (причем из перечисленных в описании) тип, поэтому выбор одного из объектов здесь не нужен.

При создании переменной U тип ее не определен (рис. 1. 9, а), поэтому, чтобы начать обрабатывать U, необходимо задать ее тип и значение. Это можно сделать, присвоив ей значение одном из указанных при описании переменной типа, например символ ' А'. При этом тип переменной U станет символьным (рис. 1. 9, б).

────────────────────

Элементы массивов, записей, объединений можно обрабатывать совершенно так же, как переменные соответствующих простых типов. На тип элементов не накладывается никаких ограничений, поэтому механизмы массивов, записей, объединений можно комбинировать при построении структур данных произвольной сложности.

1.3.3. Выражения и операторы

При разработке языков главным обоснованием для выбора вводимых в него средств описания данных является необходимость спецификации данных на различных уровнях, чтобы данные можно было разрабатывать сверху вниз, уточняя их на каждом уровне. Такие же соображения применимы и к средствам описания действий. Для разработки программы методом последовательного уточнения требуется, чтобы программа сначала специфицировалась в терминах небольшого числа действий высокого уровня. Каждое действие высокого уровня уточняется затем специфицированием его в терминах действий более низкого уровня. Процесс уточнения продолжается до тех пор, пока вся программа не становится определенной настолько подробно, что она выражается непосредственно на используемом языке программирования.

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

Последовательности операторов, которые описывают единичные действия высокого уровня, должны структурироваться на логически самостоятельные единицы. Эти единицы могут реализовываться как процедуры, функции или блоки в зависимости от той роли, которую исполняет данная единица в программе. На чуть более низких уровнях должны иметься конструкции для спецификации последовательности выполнения действий в программе. Это реализуется операторами управления, которые дают возможность условного выполнения операторов действия. Операторы действия непосредственно задают те действия, которые должна выполнить программа. Наконец, самыми элементарными конструкциями, задающими последовательность выполнения операций над объектами данных, являются выражения. Использование перечисленных средств описания действий позволяет написать программу таким способом, который ясно отображает весь процесс разработки программы сверху вниз.

Требования к средствам описания действий аналогичны тем, которые предъявляются к средствам описания данных.

Программные конструкции должны быть надежны; их смысл должен быть

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

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

────────────────────

П р и м е р 1. 4. Описание переменных и запись выражений с ними:

I.J: integer;

PI: constant real:=3.14159285;

B: boolean;

A: array (1..5) of real;

R: record

K: integer;

d: character;

end record;

.............

I:=I+J*2;

J:=3*(I-J) +R.K;

B:=B and (A(3) < PI) and (R.D='A');

A(5):=PI**2+A(5);

────────────────────

В примере 1. 4 кроме выражений используется также самый широко используемый оператор действия -- оператор присваивания:=. Слева от знака оператора указывается тот объект данных, которому в качестве значения присваивается значение стоящего справа выражения. В общем случае операторы действия в противоположность выражениям -- это элементы языка, специально предназначенные для изменения среды программы (т.е. всех ее объектов данных), а также для выполнения некоторых вспомогательных действий.

Обычно операторы выполняются последовательно; для этого они записываются в том порядке, в котором должны выполняться. Однако в некоторых языках есть средства, явно задающие последовательность выполнения операторов. Изменение такого порядка осуществляется специальными операторами управления,. Условное выполнение операторов обеспечивается оператором if, который проверяет некоторое условие (или условия) и в зависимости от истинности или ложности его выполняет те или иные операторы. Повторное (циклическое) выполнение операторов возможно с помощью оператора while. Действие этого оператора заключается в повторном выполнении заданных в нем операторов до тех пор, пока истинно заданное условие, при чем условие проверяется перед выполнением операторов.

1.3.4. Блоки и подпрограммы

Используя перечисленные выше средства, уже можно составлять реальные программы. Однако программы решения практических задач обычно довольно велики, и рассмотренные простые языковые средства неадекватно их отражают. В'о-первых, в программе с простой структурой никак не отмечаются отдельные логические единицы, введенные в процессе ее разработки. Поэтому для программ, которые были разработаны с модульной структурой, первоначальная структура теряется в конечном монолитном программном тексте, что делает ее трудной для понимания и сопровождения. Во-вторых, постоянное хранение всех переменных, используемых в программе, неоправданно увеличивает потребности в памяти. Как правило, не все обьекты данных должны быть активными в каждый момент времени работы программы: одни используются в одной части программы, другие -- в другой; поэтому некоторые переменные могли бы быть размещены в одном и том же месте памяти. В-третьих, так как все объекты данных имеют одну и ту же область действия, т.е. они известны во всей программе, им всем должны быть даны различные имена. Поэтому программист вынужден выбирать неестественные имена, затемняя этим смысл программы. В-четвертых, описания объектов данных могут быть текстуально удалены от операторов, которые их обрабатывают, что затрудняет чтение программного текста. И наконец, в тех программах, где сложное действие нужно выполнять в нескольких различных точках, реализующая это действие последовательность операторов должна выписываться заново в каждой точке. При этом напрасно тратятся как место в памяти, так и усилия программиста, это также не способствует повышению ясности программы.

Эти проблемы решаются введением в язык понятий подпрограммы и блочной структуры. Рассмотрим понятие блочной структуры на примере блоков.

Блок -- это программная единица, состоящая из двух частей:

описания всех локальных или внутренних объектов данных (т.е. требуемых только внутри этого блока) и глобальных или внешних объектов данных (т.е. обрабатываемых в этом блоке, но описанных в объемлющих этот блок программных единицах);

описания действий, которые должен выполнить блок.

──────────────────────

П р и м е р 1.6. Описание блока, переставляющего

значения глобальных переменных I и J, с помощью локаль-

ной переменной ТЕМР:

block

TEMP: integer;

use I,J: in out integer;

begin

TEMP:=I;

I:=J;

J:=TEMP;

end block;

────────────────────────

Блок из примера 1. 6 должен быть расположен в том месте программы, содержащей описания переменных 1 и где необходимо произвести перестановку их значений. Для этого вводится временная переменная TEMP, которая используется при перестановке и уничтожается при завершении выполнения этом блока. В конструкции use указано, что в этом блоке будут использоваться (in) и изменяться (out) значения глобальных переменных I и J, т.е. они необходимы как для получения значений из внешней среды, так и для возвращения результатов -- модифицируемые глобальные переменные. Слова in и out можно указывать и по отдельности при спецификации глобальных объектов:

если указано in -- входной глобальный объект (исполызуется только для получения значения из внешней среды), если out -- выходной (инициализируется в этом блоке).

Блок может находится в любом месте программы, где может быть размещен оператор, отличается от других операторов действия лишь тем, что задает целую последовательность действий, используя дополнительные внутренние переменные (поэтому иногда блок называют "составным оператором). При входе в блок создаются все описанные внутри блока локальные объекты данных, затем выполняется последовательность операторов, и после их окончания созданные объекты уничтожаются. Внутри блока можно обрабатывать глобальные объекты данных, однако для этого необходимо указать их в конструкции use в начале блока.

Блоки в той или иной степени решают рассмотренные выше проблемы, связанные со структурой программ. Для выполнения однотипных действий в разных местах служат более сложные и важные программные единицы -- подпрограммы: процедуры и функции. Они существенно улучшают и решение других перечисленных проблем.

Естественное обобщение понятия блока состоит в том, чтобы рассматривать его не как описание непосредственно выполняемых в данном месте операторов, а скорее как описание действия, которое лишь необходимо в какой-то момент выполнить. Можно было бы возбудить требуемое действие, указав его имя в тех местах программы, где требуется выполнить само действие.

Такое описание называется процедурой, а ее возбуждение -- вызовом процедуры. Процедуры являются важнейшим элементом любого языка программирования. Первоначально они были введены только для исключения многократного дублирования одинаковых совокупностей команд. В настоящее время им придается еще большее значение в качестве средства структурирования программы. При последовательном уточнении программы каждое действие высоком уровня может быть обозначено в тексте с помощью вызова процедуры. Далее каждый этап уточнения будет состоять из определения процедур, которые вызывались на предыдущем этапе, возможно, в терминах обращения к процедурам более низкого уровня. Таким образом, программа организуется в виде иерархии определений процедур. Каждая процедура может быть выражена в компактном виде, что делает всю программу более понятной и удобной для сопровождения.

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

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

────────────────────

П р и м е р 1.7. Описание процедуры, переставляющей значения глобальных переменных 1 и ~, и ее использование:

block

I,J: integer;

procedure ПЕРЕСТАВИТЬ is -- заголовок

ТЕМР: integer;

begin

ТЕМР:=I;

I:=J;

J:=ТЕМР;

end procedure;

begin

I:=1; J:=2;

-- здесь I=1, J=2

ПЕРЕСТАВИТЬ; -- первый вызов процедуры

-- теперь I=2, J=1

ПЕРЕСТАВИТЬ; -- второй вызов процедуры

-- теперь снова I=1, J=2

end block;

──────────────────

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

Главный недостаток процедуры ПЕРЕСТАВИТЬ заключается в том, что из ее вызова явно не видно, значения каких переменных она переставляет. Чтобы узнать это, надо обращаться к описанию процедуры. Таким образом, процедура ПЕРЕСТАВИТЬ неявно взаимодействует со средой, модифицируя глобальные переменные 1 и 3. Как следствие, эту процедуру нельзя применять для перестановки значений других переменных, что, конечно, было бы желательно. Чтобы исправить этот недостаток, используются специальные конструкции -- параметры.

──────────────────────

П р и м е р 1. 8. Описание и использование процеду-

ры с параметрами:

block

I, J, К: integer;

procedure ПЕРЕСТАВИТЬ (M, N: in out integer) is

ТЕМР: integer;

begin

ТЕМР:=M; M:=N; N:=ТЕМР;

end procedure;

begin

I:=1; J:=2; К:=3;

ПЕРЕСТАВНТЬ(I, J); --- здесь I=2, J=1, К=З

ПЕРЕСТАВИТЬ(J, К); --- здесь I=2, J=3, К=1

ПЕРЕСТАВИТЬ(К, I); --- здесь I=1, J=3, К=2

end block;

────────────────────

Прежде всего нужно объяснить способ спецификации параметров. Перед типом параметров стоят слова in и out, которые указывают, что эти параметры используются как для получения значения из внешней среды, так и для возвращения результатов в среду, откуда произошло обращение -- модифицируемые параметры. Эти слова можно указывать и отдельно при описании параметров: если указано in -- параметр входной, если out -- выходной.

Как работает механизм параметров? При вызове процедуры с каждым параметром связывается соответствующий аргумент, указанный в операторе вызова. В примере 1. 8 при первом вызове процедуры ПЕРЕСТАВИТЬ с параметром М связывается переменная I, а с параметром N -- переменная J Дальнейшая обработка идет так, как будто вместо параметров стоят соответствующие аргументы. При окончании работы процедуры связь параметров с аргументами разрывается.

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

──────────────────────

П р и м е р 1.9. Использование процедуры для вы-

числения единственного значения:

block

I, J, К: integer;

ТЕMР1, ТЕMР2, MAX2: integer;

procedure MAX;

(PAR1,PAR2: in integer; REZ out integer) is

begin

if PAR1>PAR2 then

REZ:=PAR1;

else

REZ:=PAR2;

end if;

end procedure;

begin

........

MAX(I, J, TEMP1);

MAX(К, TEMP1, TEMP2);

MAX2:=2*TEMP2;

end block;

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

──────────────────────

Чтобы упростить запись подобных программ, базовый механизм процедур расширяется введением специальной конструкции -- функции. Функция -- это специальная форма процедуры, предназначенная для вычисления одного значения. Для вызова функции, в отличие от процедуры, ее имя нужно записать в виде операнда выражения. Вычисленное функцией значение связывается с именем самой функции, что позволяет обходиться без промежуточных переменных для сохранения выходном значения.

──────────────────────────

П р и м е р 1. 10. Описание и использование функции:

block

I, J, К: integer;

MAX2: integer;

function MAX (PAR1,PAR2: in integer)

return (REZ: out integer) is

begin

if PAR1 > PAR2 then

REZ:=PAR1;

else

REZ:=PAR2;

end if;

end function;

begin

............

MAX2:= 2*MAX(K,MAX(I,J));

............

end block;

──────────────────────────────

Отличие функции в примере 1. 10 от процедуры из примера 1.9 чисто синтаксическое. Так как функция предназначена для вычисления одного значения (т.е. не допускает использования параметров вида out и in out, кроме одного, особо выделенного параметра вида out), то слова in и out в описании параметров можно опускать. Далее будем везде, кроме выходном параметра функций, полагать, что пропуск слов in, out, in out означает описание входного параметра (или входного глобального объекта в блоке), т.е. по умолчанию принимается in.

Часто различные программы связаны между собой: они либо выполняют набор дополняющих друг друга операций, либо обрабатывают одни и те же данные. Поэтому в современных языках программирования введено специальное средство для представления совокупности логически связанных вычислительных ресурсов -- пакеты. Пакеты могут объединять как подпрограммы, так и объекты данных и даже типы данных. Чтобы получить возможность использовать в программе пакет, достаточно указать его имя при описании программы.

1.3.5. Абстрактные типы данных

Чтобы метод последовательном уточнения программ был применим к разработке как структур данных, так и программных структур, для выражения этих структур выбираются соответствующие формы языковых конструкций. Например, компоненты записи могут быть произвольного типа, что позволяет уточнять сложные структуры данных на различных уровнях. Процедуры можно определять в терминах других вложенных процедур, что также позволяет уточнять сложные действия на нескольких уровнях. Такие средства структурирования данных, как записи, массивы, объединения, являются в некоторой степени средствами абстрагирования при описании данных, а процедуры, функции, пакеты -- средствами абстрагирования при описании действий.

При разработке программном обеспечения усиливается тенденция унифицировать, объединять эти два пути последовательного уточнения программ -- уточнение данных и уточнение действий -- с помощью проектирования программ с использованием абстрактных типов данных. Абстрактный тип данных представляет собой множество значений и набор операций, с помощью которых (и только с их помощью можно обрабатывать эти значения. В этом случае проектирование программ, по существу, сводится к спецификации проекта программы на некотором уровне уточнения в терминах множества абстрактных типов данных и связанных с ними операций. Затем на следующем уровне разработки будут уточняться абстрактные типы предыдущем уровня и определяться операции над ними в терминах следующих (чуть менее) абстрактных типов данных. И так далее.

1.3.6. Дополнительные возможности

Кроме основных возможностей, которые непременно должны входить в универсальные языки программирования, есть ряд дополнительных средств, которые либо пока не получили широком распространения среди пользователей, либо связаны в большей степени с внеязыковыми особенностями.

Программа, которая никак не взаимодействует с внешним миром, бесполезна: мы не можем узнать результатов ее работы. Необходимы средства для вывода результатов, например, на печать. Для этого есть специальная процедура PUT, которая печатает значения своих параметров.

Кроме возможности вывода данных программа должна уметь их вводить, чтобы можно было менять исходные данные задачи, которую решает программа. Для этом используется процедура GET, которая вводит некоторые значения и присваивает их своим параметрам.

────────────────────

П р и м е р 1. 11. Ввод и вывод значений перемен-

ных:

I: integer;

F: real;

........

GET(I,F);

PUT(I, F);

────────────────────────

Процедуры PUT и GET, а также другие средства ввода-вывода могут быть собраны в специальном пакете ТЕХТ_IO.

В момент очередном выполнения процедуры GET вводимые значения могли уже кончиться (предыдущие операции ввода ввели все эти значения). В этом случае, конечно, не следует выполнять GET. Чтобы узнать, есть ли еще не введенные значения, используется функция END_OF_FILE, возвращающая значение логическом типа: оно истинно, если значений для ввода уже нет.

На русский язык END_OF_FILE переводится как "конец файла". Что такое файл? Ввод-вывод -- это передача последовательностей значений данных между программой и какими-либо внешними источниками или потребителями. В принципе можно вводить (выводить) несколько независимых последовательностей. Такие последовательности и называются файлами. Мы уже знаем два файла: стандартные файлы ввода (тот, который обрабатывается процедурой GET) и вывода (тот, который обрабатывается процедурой PUT). Эти два файла предопределены -- их не надо описывать в программе. В общем же случае файлы рассматриваются как еще один тип данных и объекты файлового типа описываются так же, как и другие объекты данных. Они также имеют набор атрибутов, с помощью которых конкретизируется их структура и способы обработки. Кроме указанных выше двух назначений файлов они используются для сохранения данных между прогонами программы (например, на магнитном диске) и даже для передачи данных между различными программами, а также при нехватке оперативной памяти как ее расширение.

Предположим, что при выполнении вызова процедуры GET все же обнаружилось, что значений больше нет. Что произойдет в этом случае? Возникнет исключение с именем END_ERROR -- ошибка конца файла. При этом нормальное выполнение программы прекращается, производится некоторая заданная в языке обработка исключения (например, печать сообщения о нем), и после этого программа прекращает работу. Однако программист может задать свою собственную обработку исключения. Для этого в конце программной единицы записывается последовательность операторов, выполняющих необходимую обработку.

────────────────────────

П р и м е р 1. 12. Описание обработчика исключения

END_ERROR:

block

use TEXT_IO: package; -- пакет, содержащий

процедуры ввода-вывода

I: integer;

begin

..........

GET(I);

..........

exception -- начало описания обработчика исключения

END_ERROR: операторы обработки

end block;

────────────────────

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

Существуют и другие предопределенные исключения: ошибки при вычислениях, преобразованиях и др. Кроме этого, программист может описывать свои собственные исключения и обрабатывать их.

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

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

2. СРЕДСТВА ОПИСАНИЯ ДАННЫХ

Средства описания и использования данных -- одна из важнейших составных частей языков программирования. На развитие средств описания данных большое влияние оказали языки ПЛ/1, Паскаль, Ада. Особую значимость имеют вопросы типизации языков [31, 50]. Конкретные типы данных, их использование рассматриваются в [3, 5, 31, 36, 39, 49, 51 -- 55].

2.1. ТИПИЗАЦИЯ ЯЗЫКА

Понятие типа появилось в первых же языках программирования и развивалось вместе с самими языками. Сначала описание типа объекта данных в программе осуществлялось лишь для того, чтобы предоставить возможность компилятору выбрать достаточно эффективное машинное представление для значений этом объекта. С машинной точки зрения тип объекта -- это форма представления его значений в памяти и определяемый этой формой способ доступа х объекту и его части. Чтобы повысить эффективность представления, в языки программирования вводят иногда специальные средства для указания, например, размера области памяти, необходимости упаковки значений.

В современных языках программирования эффектив-

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

2.1.1. Определение типа

До недавнего времени тип определялся как множество значений, которые могут принимать объекты данных этого типа. Такое определение недостаточно точно -- не дает однозначного пути построения типов. Например, следует ли считать различными типы

array(1..10) of integer и array(1..11) of integer

Для языка Паскаль ответ на этот вопрос положительный, а для ПЛ/1 -- отрицательный. В языке Паскаль при вызове некоторой процедуры, у которой есть параметр-массив, этому параметру может соответствовать аргумент лишь одного из двух указанных типов данных, в языке ПЛ/1 эту процедуру можно вызвать с аргументом как первого, так и второго типа. Этот пример свидетельствует о важности определения типа с точки зрения практического использования языка.

Определяя типы просто как множества значений, мы не имеем критерия для предпочтения какой-нибудь конкретной интерпретации пространства значений, допустимых в языке. Любой механизм, позволяющий как-нибудь разбить пространство значений, каким бы тонким или грубым не было разбиение, является допустимым средством определения типов. Поэтому исследователи в области языков программирования отошли от такого определения понятия типа и сосредоточились на поведении объектов данных относительно некоторых операций, понимая под типом множество значений и набор операций, выполняемых над этими значениями и обладающих некоторыми свойствами. Однако и при таком подходе проблема однозначности построения не решается полностью. Здесь также не ясно, насколько детально типы должны разбивать пространство поведений. Различны или нет, например, типы двух списков, если их определения налагают разные ограничения на максимальное число элементов, которое они могут содержать? Удовлетворительного решения проблемы однозначности в настоящее время время не предложено.

Далее мы будем понимать тип данных как множество с операциями (алгебру), учитывая моменты, вытекающие из семантической роли типов в императивных языках если дан новый тип, то можно описывать и инициализировать переменные этого типа;

если дана переменная некоторого типа, то можно определить и изменить ее текущее значение;

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

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

Если два типа отличаются с точки зрения перечисленных моментов, то будем считать их различными. Таким образом, мы небудем считать одинаковыми приведенные выше типы, так как невозможно определить операцию сравнения на равенство, удовлетворяющую общепринятым свойствам (например, транзитивности, инвариантности относительно функциональных преобразований x=y => f(x)=f(y) и т.д.). Этот подход существенно упростит ответы на ряд вопросов, возникающих при изучении семантики языков программирования.

Определение нового типа будем записывать следующим образом:

type имя_типа is описание_типа;

Как конкретно описываются различные типы, рассмотрим позднее.

2.1.2. Способы контроля типов

Одной из основных функций типов является обеспечение как можно более полной и легкой проверки правильности программ (в том числе и с помощью компилятора). Эта проверка заключается в определении типов выражений и их согласованности с типами, которые требуются по правилам языка в данном контексте программы (например, согласованности типов аргументов и параметров процедур). Такая проверка называется контролем типов.

Введем понятия, которые нам понадобятся для классификации способов контроля типов.

Программа называется синтаксически правильной, если она удовлетворяет правилам синтаксиса языка, т.е. не содержит синтаксических ошибок. Определение синтаксической правильности программ производится на этапе компиляции. Обозначим множество программ этого класса через Ls.

Программа называется типово-правильной, если она удовлетворяет правилам типизации языка, к которым относятся приписывание типов переменным и константам, определение типов выражений по типам их частей, согласование типов частей языковых конструкций (например, операторов присваивания) и т.п.

Например, правила типизации большинства языков программирования требуют, чтобы при описании массива были указаны типы его компонент и индексов. Определение типовой правильности программ также производится на этапе компиляции. Обозначим множество программ этого класса через Lt. Конечно, Lt -- подмножество Ls. Правила типизации для некоторого языка могут быть не определены. Такой язык называется нетипизированным (для него не определено множество Lt); в противном случае язык типизированный. Типизированные языки имеют несомненные преимущества перед нетипизированными с точки зрения уменьшения ошибок при программировании. Все современные универсальные языки программирования типизированные, поэтому далее мы будем рассматривать только такие языки.

Программа называется программой без типовой ошибки, если при ее выполнении не возникает типовой ошибки несоответствия типа текущего значения переменной (константы, параметра и т.д.) типу, требуемому операцией, процедурой или другой языковой конструкцией, в которой находится эта переменная (константа, параметр и т.д.). Например, если текущее значение переменной I в операции А(I) выходит за границы изменения индекса массива А, то это типовая ошибка, если границы входят в понятие типа массива (как в Паскале), и не типовая ошибка в противном случае (как в ПЛ/1). Обозначим множество программ этого класса через Le. Ясно, что Le входит в Lt.

Программа называется программой с выловленными типовыми ошибками, если все возникающие при ее выполнении типовые ошибки обнаруживаются при контроле типов. Обозначим множество программ этого класса через Ld: Ld <= lt \ Le

Приведем теперь классификацию языков по способу контроля типов.

Если Lt =Le, т.е. типово-правильные программы не могут содержать типовых ошибок, то язык называется языком с полным статическим контролем типов.

Если Ls =Lt, т.е. правила типизации языка очень слабые или их нет совсем (все синтаксически правильные программы являются типово-правильными), и, следовательно, вся работа по контролю типов производится во время выполнения программ, то язык называется языком с динамическим контролем типов, под которым подразумевается проверка типов объектов данных в процессе выполнения языковых конструкций и выдача сообщений о возможных типовых ошибках. Если при этом Ld =Lt \ Le, т.е. все типовые ошибки обнаруживаются при динамическом контроле типов, то язык называется языком с полным динамическим контролем типов.

Если Le < Lt < Ls, т.е. не все синтаксически правильные программы являются типово-правильными и типовоправильные программы могут содержать типовые ошибки, то язык называется языком со смешанным контролем типов. Если при этом Ld= Lt\ Le, то язык называется языком с полным смешанным контролем типов.

Все практические языки программирования -- это языки со смешанным контролем типов, т.е. контроль выполняется на этапе и компиляции, и выполнения. Конечно, для повышения эффективности выполнения программ было бы желательно количество проверок типа во время выполнения программы (т.е. мощность множества Lt \ Le) уменьшить до нуля.

Однако пока это удается сделать лишь за счет существенной потери мощности языка, поэтому реальной целью является минимизация множества Lt \ Le при сохранении мощности и выполнении условия
Ld=Lt \ Le.

2.1.3. Виды и уровни типизации

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

Если семантика каждой языковой конструкции (например, операций) определяется по тексту программы, а не во время ее выполнения, т.е. статически, язык называется статически типизированным, в противном случае -- динамически типизированным. Не надо путать статическую и динамическую типизацию со статическим и динамическим контролем типов:

статически типизированные языки чаще всем являются языками со смешанным контролем типов (ПЛ/1, Паскаль, Ада).

Однако чем меньше язык использует динамическую типизацию (т.е. чем он более статически типиз

Дата добавления: 2015-07-10