С ЭТОЙ ТОЧКИ Зрения очевидно значение языков программирования. Язык программирования описывает некоторую абстрактную вычислительную машину, понимающую термины этого языка, что соответствует какому-то уровню абстракции от объектов, используемых реальной ЭВМ. Следовательно, работая с таким языком высокого уровня , программист освобождается (и отстраняется) от вопросов представления чисел, если число - элементарный объект этого языка.

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

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

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

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

1.2. Концепция типа для данных .17

ользуется в данной книге [1.3, 1.5]. Этот язык был успешно еализован на нескольких ЭВМ, и было показано, что он остаточно близок к реальным машинам, а его свойства и их еализация довольно понятны. Кроме того, этот язык близок к другим языкам, особенно к Алголу-60, поэтому наши выводы можно использовать также применительно и к этим языкам.

1.2. концепция типа для данных

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

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

Таким образом, рассматриваемая здесь концепция типа, которая включена в язык программирования Паскаль, имеет следующие основные свойства [1.2]:

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

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

3. Каждая операция или функция требует аргументов фикси-рованного типа и выдает результат фиксированного типа. Если операция допускает аргументы нескольких типов (например, -{- используется для сложения как целых, так и вещественных чисел), то тип результата можно определить по специальным правилам языка.

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

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

Число различных значений, принадлежащих типу Г, называется кардинальным числом Т. Кардинальное число определяет размер памяти, нужной для размещения переменнойх типа Т. Этот факт обозначается так - х: Т.

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