Самитов Р.К.

Прошу сообщать об ошибках, несуразностях, неясностях в изложении...

Абстрактные типы данных, модули и классы.

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

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

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

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

Пример 2. Банковский счет. С этим понятием программист работает при решении задач о расчетно-денежных операциях в банке.

Значение типа «Банковский счет» может содержать, например, следующие сведения: номер счета, текущий остаток денежных средств на счете, владелец счета, даты открытия и закрытия счета...

Операции со значениями типа «Банковский счет»: открыть счет, закрыть счет, положить сумму на счет (увеличив этим остаток счета), снять сумму со счета, получить сведения о текущем остатке, о владельце счета...

Пример 3. Region (Word).

Стеки и очереди.

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

Пусть нас интересует процесс, который преобразует входной поток данных в выходной поток.

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

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

Собственно преобразования нас не будут интересовать, поэтому мы будем считать, что входные данные просто передаются на выход. Больше нас будут интересовать возможности управлять формированием выходного потока, которые возникают благодаря наличию памяти^(*). Возможности эти зависят от объема памяти и от способа доступа к её компонентам.

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

Способ доступа к компонентам памяти. В этом случае тоже, ограничимся лишь качественной классификацией способов доступа с точки зрения поставленного вопроса. Будем различать - прямой и последовательный доступ. Прямой доступ: Обозначение компонента  Значение компонента. Обозначение компонента - «имя» (например, в случае простой переменной), «имя, уточненное селектором компонента» (указатель поля в записи, переменная с индексами)... Последовательный доступ - разновидности случаев, когда механизм доступа по сути задается средствами перечисления компонентов в некоей последовательности.

Важно осознавать, что по сути базовым является именно последовательный доступ, поскольку прямой подразумевает, что известно «обозначение компонента», например вычислимы индексы интересующего нас компонента массива... В задаче «Проверить имеется ли в массиве x[1..n] компонент x[i]=a» возможность прямого доступа к любому x[j] фактически не может быть использована по существу, нужна лишь возможность последовательно перечислить все компоненты... Если массив x[1..n] упорядочен, то возможность прямого доступа уже может играть важную роль, например в «дихотомическом поиске», но не решает проблему полностью, поскольку остается необходимость последовательного перечисления компонентов (пусть и не всех, пусть и в «нетиповом» порядке, отличном от порядка индексации компонентов). Если значения, хранимые в упорядоченном массиве, сгруппировать не в «массив», а в подходящее «поисковое дерево» с последовательным доступом к компонентам, то и при отсутствии прямого доступа можно сохранить применимость модифицированного варианта «дихотомического поиска».

Файлы, стеки и очереди можно трактовать как модели динамической памяти с последовательным доступом к компонентам, специфическим в каждом из этих трех случаев^(*).

Стек - динамическая память с последовательным доступом типа «последние события вспоминаем в первую очередь» (LIFO - Last Input First Output - последний пришел первый ушел)^(**).

Стек как абстрактный тип данных:

• множество возможных значений - (конечные) последовательности компонентов одинакового типа;

• набор операций:

• создать пустой стек - с семантикой, тождественной семантике оператора ReWrite;

• проверить стек на пустоту - на условие быть пустой последовательностью;

• добавить (компонент в конец последовательности), положить в стек - с семантикой, тождественной семантике оператора Write;

• удалить (последний компонент последовательности), вытолкнуть из стека - с семантикой, удовлетворяющей двум требованиям:

• операция допустима  стек непустой,

• последовательность операций «добавить;удалить» не изменяет значения стека:

;

• посмотреть - возвращает значение последнего компонента последовательности (вершина стека), операция применима только к непустому стеку.

Очередь - динамическая память с последовательным доступом типа «события вспоминаем в порядке их поступления, но с задержкой» (FIFO - First Input First Output - первый пришел первый ушел). Такая память ещё известна, как «окно просмотра» («угол-поле зрения»).

^(**)

Очередь как абстрактный тип данных:

• множество возможных значений - (конечные) последовательности компонентов одинакового типа;

• набор операций:

• создать пустую очередь - с семантикой, тождественной семантике оператора ReWrite;

• проверить очередь на пустоту - на условие быть пустой последовательностью;

• добавить (компонент в конец последовательности) в очередь - с семантикой, тождественной семантике оператора Write;

• удалить (первый компонент последовательности) из очереди - с семантикой, удовлетворяющей двум требованиям:

• операция допустима  очередь непустая,

• «добавить(a);удалить»=«удалить;добавить(a)» при условии, что исходная очередь была непустая, т.е. обе последовательности операций дают одинаковый результат (при оговоренном условии):

;

• посмотреть - возвращает значение первого компонента последовательности (фронт очереди), операция применима только к непустой очереди.

Модули и многомодульные программы.

Что даёт программисту аппарат модулей, как этим пользоваться и зачем...

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

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

• Аппарат модулей предоставляет средства для организации межмодульной связи.

• Аппарат модулей предоставляет механизм защиты своих инструментов от некорректного внешнего вмешательства в их функционирование.

При разработке программной системы (ПС) часть задач предметной области (часть функционала ПС) вполне возможно будет вынесена на уровень инструментов.

Нормальная бытовая ситуация в группе разработчиков ПС – один занимается решением конкретной прикладной задачи а в реализации использует программу, написанную другим, и включённую в библиотеку инструментов. Первый утверждает, что его правильная программа даёт неправильные результаты, потому что неправильно работает использованный инструмент. А второй утверждает, что его инструмент работает правильно, а тот первый неправильно использует инструмент и потому имеет последствия... Защита инструментов позволяет чётче разделять ответственность...

• Оборотная сторона защищённости инструментов модуля – (относительная) независимость программы решения задачи от способа реализации использованных инструментов.

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

• Модуль – отдельно транслируемый компонент программы.

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

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

Оформление модуля в Object Pascal 2.

UNIT ИмяМодуля ;

INTERFACE // Интерфейсная секция модуля

// В этой секции описывается взаимодействие

// данного модуля с другими пользовательскими и

// стандартными модулями, а также

// с главной программой. Другими словами –

// взаимодействие модуля с «внешней средой».

USES ИмяДругогоМодуля , … ; // Список импорта

// Здесь объявляются модули, инструменты которых

// используются в секциях описываемого модуля.

CONST // Список экспорта. Содержит

TYPE // традиционные разделы Паскаль-программы,

VAR // в которых определяются константы и

PROCEDURE // типы, а также описываются переменные и

FUNCTION // заголовки (прототипы) процедур и функций,

// которые таким образом объявляются

// инструментами модуля,

// доступными из внешней среды.

IMPLEMENTATION // Секция реализации

// В этой секции описываются данные и действия

// модуля, не видимые извне, в частности,

// реализация процедур и функций, объявленных в

// интерфейсной секции.

USES ИмяДругогоМодуля , … ; // Список импорта

// Здесь объявляются модули, инструменты которых

// используются только в секции реализации

// описываемого модуля.

LABEL // Разделы объявления, определения и

CONST // описания внутренних для секции

TYPE // реализации данных и действий.

VAR // Содержит традиционные разделы Паскаль-

PROCEDURE // программы в их традиционном синтаксисе

FUNCTION // и семантике. Заголовки процедур и

// функций, объявленных в интерфейсной

// секции, здесь можно указать без списка

// параметров.

INITIALIZATION // Секция инициализации – необязательная

// В эту секцию включаются действия,

// которые выполняются перед выполнением

// раздела операторов программы, в которой

// этот модуль объявлен предложением USES.

FINALIZATION // Секция завершения – необязательная

// В эту секцию включаются действия,

// которые выполняются по окончании

// выполнения раздела операторов

// программы, в которой этот модуль

// объявлен предложением USES.

END.

Использование модуля в Object Pascal 2.

• В оформлении программы (!!! но не описаний процедур и функций) появился новый раздел – список импортируемых модулей:

USES ИмяМодуля , … ;

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

• Имена инструментов (типов, переменных, процедур...) модуля, доступные внешней среде, вне модуля можно использовать с уточнением: ИмяМодуля.Имя

Подведем первые итоги.

• Синтаксически конструкция описания модуля похожа на конструкцию описания процедуры. Но семантика – существенно отличается:

• у модуля нет раздела операторов, который (тело процедуры!!!) играет фундаментальную роль в описании процедуры; секции инициализации и завершения в модуле играют весьма специальную роль подготовки к работе и «чистки рабочего места» по окончании работы;

• инструменты, которые модуль предоставляет другим – это константы, типы данных, переменные (для хранения данных), процедуры и функции (для преобразования данных), которые описаны в интерфейсной секции модуля; в традиционной системе понятий эти переменные, процедуры и т.д. оказались бы локальными и были бы недоступны извне!!!

• Таким образом, интерфейсная секция модуля является принципиально новым понятием, которое «вклинивается» между традиционными понятиями локальные и глобальные инструменты.

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

• Поскольку у модуля нет параметров и концепция глобальных объектов «плохо совмещается» с понятием модуль, возникает вопрос о способах организации информационной связи с модулем и между ними. Как можно организовать использование двумя модулями общих данных и действий? – через интерфейсную секцию! В частности, можно определить третий модуль, объявив в его интерфейсной секции (доступной «всем желающим») требуемые общие переменные, процедуры и функции, и включить этот модуль в списки импорта в тех модулях, которые «заинтересованы» в этих общих инструментах.

Реализация стеков и использование модулей (для этих целей).

Понятие стек (почти) не зависит от типа его компонентов. Поэтому оформим отдельный модуль инструментов для работы со значениями компонентов.

UNIT UVal;

INTERFACE TYPE TVal= CHAR;

PROCEDURE WriteElement(xPrm:TVal);

CONST CMaxL=1000 {статическая реализация - размер стека

изначально ограничен};

IMPLEMENTATION

PROCEDURE WriteElement(xPrm:TVal); BEGIN WRITE(xPrm)

END;

END.

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

• Вариант 1. ObjectPascal2. Статическая реализация стека.

UNIT UStack; INTERFACE USES UVal;

PROCEDURE MakeNull {Создать пустой стек};

FUNCTION Empty:BOOLEAN {Проверить на пустоту};

PROCEDURE Push(xPrm:UVal.TVal){Добавить, положить в стек};

PROCEDURE Pop {Удалить, вытолкнуть из стека};

FUNCTION Top:UVal.TVal {Посмотреть вершину};

PROCEDURE WriteAll {Вывести все элементы стека};

VAR ErrStack:INTEGER {Код ошибки};