Make your own free website on Tripod.com

ע. ברנדס וצוותה. עיצוב תכנה. ספר לתלמיד, 1997

А. Брандес и др. Программный дизайн(оформление программы). Книга ученика.

Шалом учителям и ученикам.

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

 

Глава 1. Введение

1.1. Проектирование от общего к частному

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

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

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

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

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

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

 

1.2. Системы программного обеспечения

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

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

 

1.2.1. Требования качества

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

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

Устойчивость(robustness). Когда мы задействуем систему программного обеспечения, не исключены неположенные ситуации, с ними система обязана также справляться. Обслуживание таких (нештатных) ситуаций, не включенных в спецификацию, и называется устойчивостью. Например, предполагается, что системе нужен экран определенного типа. Что произойдет, если к компьютеру будет подключен экран не того типа ? Система рухнет, или напечатает соответствующее

сообщение пользователю, или выполнит работу частично ? Как должен вести себя обработчик текстов, способный обрабатывать документы до определенного размера, когда пользователь упорствует и пытается обработать с его помощью книгу Война и мир? Как поведет себя телефонная станция, предназначенная обслуживать до 1000 разговоров одновременно, если в определенный момент времени решат побеседовать по телефону как раз 1001 абонент?

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

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

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

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

 

1.2.2. Техническое обслуживание (сопровождение)

Система программного обеспечения, подобно любому другому сложному изделию,

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

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

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

 

1.2.3. Проектирование систем программного обеспечения

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

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

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

 

1.3. Разделение интерфейса и реализации - принцип сокрытия информации

Сказано вам : Позвоните тете Блюме и передайте ей горячий привет. И вы сразу поняли, что от вас требуется. Подобное указание в более детальной форме может прозвучать так : Найдите номер телефона тети Блюмы в телефонной книжке, поднимите телефонную трубку, подождите сигнала, разрешающего набор, наберите цифры телефона тети Блюмы из телефонной книжки, подождите ответа, скажите ей Мама передает горячий привет и разъединитесь.

Когда вас попросили позвонить тете Блюме, то подразумевалось, что вы способны перевести указание позвонить Х на последовательность действий : Найдите номер телефона Х в телефонной книге, поднимите телефонную трубку .... Логично предположить, что действие позвонить Х переводится вами на более сложную последовательность действий. Предположим, что телефона Х нет в семейной телефонной книжке, тогда надо искать его в общей телефонной книге; возможно, что после набора номера Х, будет получен сигнал, что телефон занят, тогда надо будет повторить набор. Вам надлежит знать, что делать в каждом возможном случае. Наша жизнь очень упрощается от того, что всякий раз, когда мы звоним тете Блюме, нет нужды детализировать последовательность действий.

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

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

Печать_массива (А, n)

{ Подпрограмма печати n первых элементов массива А согласно их порядку в массиве. Предположение : n меньше числа элементов массива или равно ему. }

Документация (documentation) это неотделимая часть интерфейса подпрограммы. Ее назначение состоит в описании подпрограммы, передаваемых ей параметров и ограничений на их значения.

После того, как мы определили интерфейс, следует написать реализацию (implementation) подпрограммы, т.е. алгоритм, который подпрограмма осуществляет. В простом случае подпрограммы Печать_массива реализация выглядит так :

(1) Для i от 1 до n :

(1.1) печатай А[i].

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

Понятия спецификация, интерфейс и реализация не принадлежат исключительно

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

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

Действие

Способ приведения в действие

Перевод станций

Нажатие на одну из кнопок постоянных станций или вращение переключателя - для настройки на частоту передачи

Изменение мощности звучания

Вращение регулятора мощности налево или направо соответственно - для ослабления мощности звучания или его усиления.

Выбор способа записи AM/FM

Нажатие на клавишу двух положений AM/FM

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

 

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

Вернемся к стерео-системе, которую мы обсуждали в предыдущем параграфе. Если мы захотим приобрести такую систему, то можем пожелать сочетания блоков, созданных разными производителями. Можно купить усилитель одной фирмы, подключить его к приемнику , произведенному на другой фабрике, и к громкоговорителям, сделанным в третьем месте. Какой аппарат позволяет нам собирать стерео-систему из блоков разных фирм ? Основная идея заключается в том, что интерфейс между блоками, т.е. способы соединения блоков, согласованы производителями элементов стерео-систем. Звуковой выход магнитофона идентичен для любого из них, даже если они устроены по-разному. Итак мы знаем, что если вдруг сломается купленный нами магнитофон, или мы захотим поменять его на лучший магнитофон, мы можем просто отсоединить провода , соединяющие его с остальными блоками системы и заменить на новое устройство.

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

Как решается вопрос о том, какие модули должны быть включены в новую систему? Это не простой вопрос. Не существует ясного рецепта, который позволит нам однозначно установить, что какая-то определенная часть системы удостаивается статуса отдельного модуля, но в ходе проектирования (программирования) нами руководит один важный принцип - принцип модульности(modularity principle). Единицы(блоки) построения систем программного обеспечения, модули, должны быть удобными для подсоединения и замены, подобно тому как в стерео-системе подключение нового блока или его замена осуществляются относительно легко. Как правило, когда делят систему на модули, стремятся к тому, чтобы зависимость между различными модулями,

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

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

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

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

1.5. Резюме

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

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

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

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

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

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

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

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

Понятия и ключевые слова (согласно еврейского алфавита)

software engineering

Инженерия программного обеспечения

הנדסת תכנה

information hiding

Сокрытие информации

הסתרת מידע

module

Модуль

מודול

modularity

Модульность

מודולריות

implementation

Реализация

מימוש

interface

Интерфейс

ממשק

user interface

Интерфейс пользователя

ממשק למשתמש

software system

Система программного обеспечения

מערכת תכנה

system specification

Спецификация системы

מפרט מערכת

correctness

Корректность

נכונות

robustness

Устойчивость

עמידות

upgrade

Повышение

שדרוג

code reuse

Повторное использование

שימוש חוזר

maintenance

Обслуживание(сопровождение)

תחזוקה

documentation

Документация

תיעוד

top-down design

Проектирование от общего к частному

תכנון מהכלל אל הפרט

 

Глава 2. Библиотечный модуль в Турбо Паскале

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

Использование библиотек Паскаля не является для вас новым. Разумеется вы пользовались в прошлом командой uses crt; , которая помещалась в начале программы. Команда разрешала использование модуля crt , подключенного к пакету программ Турбо Паскаля. Среди прочего этот модуль содержит несколько действий, связанных с экраном, вроде его очистки (clrscr), переход к определенному месту на экране (gotoxy) и т.д. Пользователь не знает, как реализованы эти подпрограммы, но интерфейс модуля включает точные указания для обращения к ним. Интерфейс можно найти в документации Турбо Паскаля или посредством команды help в меню среды программирования.

? Попытайтесь проверить, какие дополнительные программы определены в интерфейсе библиотечного модуля crt . Знаете ли вы другие библиотечные модули ? Какова их функция ?

2.1. Структура библиотечного модуля

Файл библиотечного модуля выглядит как обычный файл, содержащий программу Паскаля (и расширение его имени также .pas), но две важные вещи отличают его от обычной программы : первое - у файла модуля специальная структура, и второе - после компиляции модуля получается не программа, готовая к прогону, а файл с расширением имени .tpu (начальные буквы Turbo Pascal Unit). Этим файлом могут пользоваться другие программы Паскаля.

unit my_unit;

interface

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

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

implementation

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

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

begin

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

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

end.

Рис. 2.1. Структура библиотечного модуля в Турбо Паскале

На рис. 2.1 в схематической форме представлена структура файла библиотечного модуля. Файл начинается с зарезервированного слова unit , за которым следует

имя модуля (имя это должно быть тождественно основной части имени файла). Файл содержит три основных части : интерфейс, который начинается с зарезервированного слова interface; реализацию, которая начинается с зарезервированного слова implementation; инициализацию, которая появляется в конце файла между словами begin и end. Программа , обращающаяся к библиотечному модулю, может пользоваться функциями, процедурами, переменными, постоянными или типами, которые декларированы в его интерфейсной части. В разделе реализации находится вся информация, спрятанная от пользователя. Реализация функций и процедур, провозглашенных в интерфейсе, должна находится в этой части, и можно добавить в нее дополнительные функции и процедуры, которыми мы можем пользоваться, не раскрывая их пользователю. И переменными, постоянными, типами, провозглашенными в реализации, нельзя пользоваться за пределами библиотечного модуля.

(Программа 2.1 - библиотечный модуль grade)

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

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

Постоянная : grade_subject_num - число дисцилин в экзаменах на багрут.

Типы : grade_type - запись, включающая отметку и число единиц обучения по отдельной дисцилине.

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

Подпрограммы : grade_init - процедура, обнуляющая все поля массива оценок.

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

grade_average - функция, вычисляющая взвешенную оценку с бонусом и без него.

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

2.2. Документация библиотечного модуля

Библиотечный модуль grade

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

-----------------------------------------------------------------------------------------------------------------------

Постоянные :

1. grade_subject_num - постоянная, определяющая число дисцилин .

-----------------------------------------------------------------------------------------------------------------------

Типы :

1.Запись, включающая число единиц обучения(points) и отметку(grade).

grade_type = record

points : integer;

grade : real;

end;

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

2. Массив, используемый для хранения багрутных оценок . Индекс элемента массива есть номер дисциплины.

grade_array = array[1.. grade_subject_num] of grade_type;

---------------------------------------------------------------------------------------------------------------------- Подпрограммы :

1. Процедура, обнуляющая все поля массива оценок grades .

procedure grade_init(var grades : grade_array);

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

2. Процедура, добавляющая в массив отметок grades оценку grade по дисциплине номер subject_num, изучавшейся на points единиц обучения.

procedure grade_enter(var grades : grade_array; subject_num, points : integer;

grade : real);

Внимание! Число дисциплин subject_num должно быть от 1 до grade_subject_num.

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

3. Функция, возвращающая среднюю взвешенную массива оценок grades. Если add_bonus есть TRUE, то к оценке добавляется бонус в 20% на 5 единиц обучения, и 10% - на 4 единицы обучения.

function grade_average(grades : grade_array; add_bonus : boolean) : real;

 

Рис. 2.2. Документация библиотечного модуля grade

 

Когда пользователь получает библиотечный модуль, написанный заранее другим программистом, он не обязательно заинтересован в расмотрении библиотечного файла на языке Паскаль . А когда модуль поступает к нему после компиляции в виде файла .tpu, он просто не может сделать это. Поэтому следует сопровождать файл .tpu документацией модуля. Документация позволит пользователю узнать в точности , что это за библиотека и из чего она состоит, чтобы он смог подключить этот модуль к коду своей программы. Рис. 2.2 представляет документацию библиотечного модуля grade .

 

2.3. Подключение библиотечного модуля к программе на Паскале

Рассмотрим (Программа 2.2. Использование библиотечного модуля grade), использующую модуль grade. Когда мы желаем в своей программе прибегнуть к услугам какого-либо библиотечного модуля, мы пишем в ее начале команду uses и затем имя необходимого модуля. И действительно, в программе test_grade появляются постоянные, типы и подпрограммы, определенные в интерфейсе модуля grade . Но если бы мы захотели , к примеру, обратиться к функции grade_add_bonus из нашей программы, компилятор объявил бы об ошибке компиляции, поскольку эта подпрограмма не объявлена в интерфейсной части модуля. Важно подчеркнуть, что и в библиотечные модули можно включать декларацию uses. Например, если в интерфейсе модуля А появляется декларация uses В;, то внутри А можно использовать определения из интерфейса В.

 

2.4. Внутренние переменные в библиотечном модуле

Если внимательно посмотреть на программу 2, то увидим, что массив the_grade используется исключительно подпрограммами , определенными в модуле grade . Этот факт подсказывает, что можно определить этот массив как внутреннюю составляющую модуля. Подобно определению внутренних переменных в подрограмме, используемых только ею, можно определять внутренние переменные в разделе реализации библиотечного модуля, и эти переменные не открыты пользователям модуля. Рассмотрим программу 3, которая представляет собой немного измененную версию модуля grade .

(Программа 3. Вторая версия модуля grade)

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

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

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

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

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

 

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

 

2.5. Резюме

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

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

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

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

В разделе реализации можно определять внутренние переменные.

Рис. 2.3 резюмирует процесс построения модуля и способ его использования в Турбо Паскале. (Рис. 2.3. Библиотечный модуль в Турбо Паскале)

Понятия и ключевые слова (согласно еврейского алфавита)

initialization

Инициализация

אתחול

library unit

библиотечный(-ая) модуль(единица)

יחידת ספרייה

implementation

Реализация

מימוש

interface

Интерфейс

ממשק

internal variable

внутренняя переменная

משתנה פנימי

internal routine

внутренняя подпрограмма

שגרה פנימית

 

Задачи

1. Перед тобой библиотечный модуль по имени mystery1 :

unit mystery1;

interface

uses crt ;

var a,b : real ;

procedure one(x , y : real);

procedure three(x , y : real);

procedure two(g : real) : boolean;

implementation

var i , j : integer ;

procedure one(x , y : real);

begin

.......

end ; (* one *)

procedure four(var c , d : real);

var k : integer ;

begin

.......

end ; (* four *)

procedure three(z , t : real);

begin

.......

end ; (* tree *)

procedure two(g : real) : boolean;

 

begin

.......

end ; (* two *)

begin

end.

a). Мы хотим написать программу, которая будет использовать модуль mystery1. Что требуется для связи библиотеки и программы ?

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

Имя подпрограммы/переменной

Главная программа

one

two

three

four

one

 

 

 

 

 

two

 

 

 

 

 

three

 

 

 

 

 

four

 

 

 

 

 

crt

 

 

 

 

 

a

 

 

 

 

 

b

 

 

 

 

 

I

 

 

 

 

 

j

 

 

 

 

 

k

 

 

 

 

 

2. Даны модули alpha , beta , gamma . Ниже приведены их интерфейсы :

unit alpha;

interface

function alpha_one : boolean;

function alpha_two : real;

 

unit beta;

uses alpha , gamma;

interface

function beta_one : integer;

function beta_two : real;

function beta_tree;

 

unit gamma;

uses alpha;

interface

function gamma_one;

function gamma_two : integer;

 

В некоей главной программе написано : uses beta , gamma;

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

Имя подпрограммы

Главная программа

alpha

beta

gamma

alpha_one

 

 

 

 

alpha_two

 

 

 

 

beta_one

 

 

 

 

beta_two

 

 

 

 

beta_three

 

 

 

 

gamma_one

 

 

 

 

gamma_two

 

 

 

 

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

Инициализация часов

Подпрограмма, которая устанавливает(обнуляет) секундомер и приступает к подсчету времени.

Фиксация времени

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

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

a). Напишите интерфейс соответствующего библиотечного модуля.

 

b). Реализуйте библиотечный модуль.

с). Задокументируйте модуль.

d). Напишите программу, которая проверяет работу модуля.

4. Мы хотим построить библиотечный модуль по имени math_utl , обслуживающий различные математические функции. Модуль должен включать следующие опреции :

power - вычисляет х в степени у.

factorial - вычисляет х! .

is_prime - проверяет, является ли х простым числом.

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

Положим, что все параметры подпрограмм есть целые числа.

a). Напишите интерфейс соответствующего библиотечного модуля.

b). Реализуйте библиотечный модуль.

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

d). Напишите программу, которая проверяет работу модуля.

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

список действий , которые должны войти в этот модуль :

Операция принимает измерение температуры в градусах Цельсия и переводит его в градусы Фаренгейта, и операция, обратная описанной.

Операция принимает измерение расстояния в метрах и возвращает его в футах(feet), и операция, обратная описанной.

Операция принимает измерение объема в литрах и возвращает его в пинтах(pint), и операция, обратная описанной.

Операция принимает измерение веса в граммах и возвращает его в унциях(ounce), и операция, обратная описанной.

Действуйте согласно следующих правил перевода .

Из градусов Цельсия в градусы Фаренгейта : 9с.5 + 32.

1 метр = 3.281 футов. 1 литр = 2.11 пинт. 1 грамм = 0.0353 унций.

a). Напишите интерфейс соответствующего библиотечного модуля.

b). Реализуйте библиотечный модуль.

с). Напишите полную документацию модуля.

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

 

Глава 3. Типы данных

Многие алгоритмы в той или иной форме занимаются числами, словами, текстами и даже странными предметами вроде мест в кинотеатре. Принято называть разнообразные предметы, которые обрабатывают алгоритмы, данными (data). Множество целых чисел (..., -2, -1, 0, 1, 2, ...) есть определенный вид данных, которые могут обрабатываться алгоритмами. Над целыми числами определены арифметические действия умножения, деления, сложения и вычитания, а также действия сравнения - равно, не равно, больше, меньше, больше или равно, меньше или равно, образованные из отношений целых чисел(помним, что между двумя целыми числами а и b могут существовать только три вида отношений : а больше b, а меньше b, а равно b ). Алгоритмы, работающие с целыми числами, пользуются набором действий, определенных над этими числами.

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

Абстрактный тип данных (abstract data type или сокращенно ADT) есть множество значений некоторого типа и набор действий, определенных над этими значениями. В соответствие с тем, что мы уже видели, тип абстрактных данных - целые числа - включает множество значений ..., -2, -1, 0, 1, 2, ... , а действия, которые определены над ними, есть арифметические действия и действия сравнения. Важно обратить внимание на то, что существуют действия, которые не определены, когда их пытаются задействовать над частью значений этого типа. У каждого действия есть область определения (domain of definition), которая представляет из себя набор значений, над которыми его можно осуществлять. Например, область определения действия деления над типом данных целых чисел не может включать делитель, равный 0. Когда описывают абстрактный тип данных, следует оценивать для каждого действия область его определения.

Еще один пример типа абстрактных данных это слова. Определим слово как последовательность из нуля или большего числа исключительно букв a - z (без пробелов и заглавных букв). Например, abcdefgh есть слово длиной 8 букв, qwertyuio есть слово из 9 букв, и даже w есть слово длиной в одну букву. Существует также особое слово - пустое , которое не содержит букв, и его длина равна 0. Обратите внимание на то, что согласно нашему определению , слово не обязано иметь смысл на английском языке. Часть возможных действий над типом данных - словами - есть : изменение буквы в определенном месте слова (изменение третьей буквы в слове abcdefgh на u производит слово abudefgh), добавление буквы следом за последней буквой в слове( добавление f к слову we порождает слово wef ), представление слова в обратном порядке ( обращение слова waef порождает слово feaw) и склеивание двух слов (склеивание слов riz и raz порождает слово rizraz) . Можно также определить действие, которое возвращает длину слова (длина слова rytrewqfdertyp равняется 14). Что еще можно сказать об определении этих действий? Нет смысла в изменении пятой буквы слова длиной в 3 буквы, поэтому область определения действия изменения буквы , находящейся на позиции n, ограничено словами, длина которых не меньше n .

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

3.2. Представление в компьютере типов данных

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

3.2.1. Определенные заранее(предопределенные) типы данных

Язык Паскаль включает в себя определенные заранее(предопределенные) типы данных (built-in data types), которые делают возможным представление в компьютере распространеннных типов данных. Один из них тип данных integer , который позволяет помещать в компьютер целые числа и выполнять над ними определенные действия. Чтобы мы могли пользоваться предопределенным типом данных, нам необходимо знать пути обозначения этого типа в компьютере и способы осуществления действий над ним. Чтобы обозначить число 482 в компьютере, набери на клавиатуре 482. Иногда можно представлять значения не единственным способом. В вещественном типе данных real можно обозначить число так : 0.25 или 25Е-2 или 0.00025Е3. Тип данных обретает смысловую полноту только в сочетании с действиями, определенными над ним. Арифметические действия, определенные над типом данных integer, выполняются в компьютере с помощью символов +, -, * и команд mod и div , а действия сравнения осуществляются с помощью символов =, <>, >, <, >=, <= . Хранение значений в компьютере осуществляется с помощью переменных. Переменная есть имя ячейки памяти, в которой можно хранить значения определенного типа. Объявление в Паскале переменной х типа integer приводит к выделению ячейки памяти, способной содержать произвольное значение этого типа, и связывает с ячейкой имя х. Занесение значений в переменную осуществляется с помощью действия присвоения, которое обзначается в Паскале символом := .

Способ использования данных, т.е. форма оценки значений, через совершение действий и их смысл есть интерфейс обслуживания данных. Он напоминает программный модуль, который включает минимальную информацию требуемого интерфейса для использования модуля и скрывает информацию, в которой нет необходимости для его задействования. Так и интерфейс типа данных скрывает информацию о способе хранения значений и пути реализации действий . Знаем ли мы как хранится целое число в компьютере ? Известно ли нам , как осуществляется действие сложения двух целых чисел ? Логично предположить, что мы не знаем в точности на уровне битов , как все это выглядит в компьютере. Но чтобы пользоваться этим типом данных у нас и нет нужды в этой информации. В стандартном Паскале существуют и другие предопределенные типы данных : real - тип вещественных чисел, boolean - тип логических(булевых) значений и char - символьный тип.

? Тип данных boolean есть представление значений истинности. Каковы значения этого типа данных? Какие действия можно осуществлять над ними?

3.2.2. Ограничения в представлении значений

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

? Как с помощью программы можно выяснить, чему равняется значение MAXINT ? Есть ли гарантия, что это значение будет тем же для любого компилятора ?

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

 

3.3. Пути построения новых типов данных в Паскале

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

3.3.1. Порядковый тип данных

Значения типа данных не обязательно являются числовыми. Мы уже видели, что в типе данных слово его значения есть последовательности букв a - z . Во многих случаях мы склонны представлять в компьютере наборы нечисловых данных с помощью чисел. Так , например, дни недели - воскресенье, понедельник, .... , суббота(по еврейскому календарю) принято обозначать числами 1, 2, ... , 7 соответственно. Но известно, что во многих странах понедельник является первым днем недели, поэтому логично выглядит представление дней недели с помощью их наименований. Язык Паскаль дает нам возможность построить порядковый тип (enumerated type). Значения этого типа есть имена, устанавливаемые программистом. Во время определения такого типа указываются все его значения по порядку. Этот порядок определяет для каждого значения, кроме последнего, следующее значение и для каждого значения, кроме первого, предыдущее значение. Для каждого элемента определяется место, равное его номеру в списке элементов(при том, что место первого элемента равно 0).

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

type

HebrewMonths = (Tishrey,Heshvan,Kislev,Tevet,Shvat,Adar,Nissan,Iyar,Sivan,Tamuz,Av,Elul);

program months;

type hebrew_months =

(Tishrey,Heshvan,Kislev,Tevet,Shvat,Adar,Nissan,Iyar,Sivan,Tamuz,Av,Elul);

var month : hebrew_months;

procedure month_displey(month : hebrew_months);

begin

case month of

Tishrey : writeln('Tishrey'); Heshvan : writeln('Heshvan'); Kislev : writeln('Kislev');

Tevet : writeln('Tevet'); Shvat : writeln('Shvat'); Adar : writeln('Adar');

Nissan : writeln('Nissan'); Iyar : writeln('Iyar'); Sivan : writeln('Sivan');

Tamuz : writeln('Tamuz'); Av : writeln('Av'); Elul : writeln('Elul');

end

end;

begin

month := succ(Heshvan); {of course, Kislev}

month_displey(month);

end.

Программа 1. Пример использования порядкового типа данных

Опишем интерфейс к порядковому типу данных в Паскале. Действия определения предыдущего и последующего значений выполняются с помощью функций pred и succ. Функция pred(х) возвращает значение, предшествующее значению х в списке, а функция succ(x) возвращает следующее за ним значение. Действие определения места значения выполняется функцией ord , которая возвращает число, обозначающее место заданного элемента. Например, ord(Av) вернет значение 10.

? Каковы области определения функций pred и succ ?

Программа 1 есть простой пример определения порядкового типа данных и его

использования. Обратите внимание на то, что команда вроде writeln(Tishrey); послужит причиной ошибки компиляции. Для того, чтобы напечатать значения этого типа, надо воспользоваться процедурой mont_display.

 

3.3.2. Типы данных - массив и запись

Тип массив объединяет постоянное число ячеек для запоминания значений определенного типа. В массиве можно осуществлять действия доступа к ячейке для запоминания в ней значения и извлечения значения из нее. Язык Паскаль обеспечивает удобный способ осуществления таких действий : когда мы определяем переменную типа массив, действие доступа к ячейкам выполняется посредством указания имени переменной и следом за ним в квадратных скобках номера ячейки. К примеру, пусть arr есть переменная типа массив целых чисел с индексами 1..100 ; доступ к ячейке 24 осуществляется так : arr[24] . Это обращение к ячейке возможно как для запоминания в ней некоторого значения (arr[24] := 5;) , так и для извлечения значения из ячейки (writeln(arr[24];).

? Какова область определения действия доступа к элементу массива ?

Запись позволяет объединять вместе некоторое число ячеек для запоминания значений, которые не обязательно принадлежат одному типу, и обращаться к каждой из них по имени записи. Ячейки запоминания в записи называются полями. Над записью определено действие доступа к полю, осуществляемое с помощью имени записи, имени поля и точки между ними. К примеру, если р есть запись, составленная из двух полей - num типа real и let типа char , - то доступ к полю let выполняется так: p.let. И в записи доступ к полю может выполняться для запоминания значения в поле и извлечения значения из него.

3.4. Этапы определения и представления абстрактного типа данных

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

3.4.1. Прямые прямоугольники

У прямых прямоугольников стороны параллельны осям координат. В противоположность прямоугольникам испорченым, у которых стороны не параллельны осям координат, прямые прямоугольники есть консервативное и упорядоченное подмножество множества прямоугольников.

(Рис. 3.1. Прямые и испорченные прямоугольники)

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

(Рис. 3.2. Действия разбухания и объединения)

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

3.4.2. Проектирование интерфейса к абстрактному типу данных

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

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

центр_прямоугольник(rect)

Возвращает центр прямоугольника rect

левый_верхний_прямоугольник(rect)

Возвращает левый верхний угол rect

левый_нижний_прямоугольник(rect)

Возвращает левый нижний угол rect

правый_верхний_прямоугольник(rect)

Возвращает правый верхний угол rect

правый_нижний_прямоугольник(rect)

Возвращает правый нижний угол rect

длина_прямоугольник(rect)

Возвращает длину прямоугольника rect

ширина_прямоугольник(rect)

Возвращает ширину прямоугольника rect

сдвиг_прямоугольник(rect,dx,dy)

Операция сдвигает прямоугольник rect на dx единиц по х и на dy единиц по у

раздувание_прямоугольник(rect, c)

Операция раздувает прямоугольник rect в с раз в предположении, что c > 0.

объединение_прямоугольники(rect1, rect2)

Возвращает прямоугольник - объединение прямоугольников rect1 и rect2

Таблица 3.1.Черновик интерфейса типа данных - прямые прямоугольники

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

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

3.4.3. Выбор способа представления значений типа данных

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

? Достаточны ли верхний левый угол и левый нижний угол для представления прямого прямоугольника?

Какой из указанных способов представления предпочтительней? На первый взгляд

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

Способ представления с помощью центра, длины и ширины (далее центр_длина_ширина) будет представлять прямоугольник посредством четырех величин : (center_x, center_y), length, width . Здесь length есть длина прямоугольника по оси у и width его ширина по оси х.

Метод представления с помощью левого верхнего и правого нижнего углов (далее способ представления углами) будут представлять прямоугольник посредством четырех величин: (left_top_x, left_top_y), (right_bottom_x, right_bottom_y) .

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

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

(left_top_x, left_top_y) = (center_x - width/2, center_y + length/2).

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

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

? Как вычисляются значения, возвращаемые операциями центр_прямоугольник, левый_нижний_прямоугольник, длина_прямоугольник и ширина_прямоугольник, когда прямоугольник представлен методом углов.

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

Рассмотрим еще три операции и выясним, как они реализуются в этих двух представлениях. сдвиг_прямоугольник(rect,dx,dy) перемещает прямоугольник rect на dx единиц по оси х и на dy единиц по оси у. В представлении посредством углов все , что нам надлежит сделать, это сдвинуть left_top_x на dx единиц и left_top_y на dy единиц. Таким же образом надо изменить значения нижней правой точки - и новый прямоугольник нами установлен. А что происходит, если наше представление есть центр_длина_ширина? Значения center изменяются точно также, но length и width не изменяются.

раздувание_прямоугольник(rect, c) раздувает прямоугольник rect в с > 0 раз. Т.е. нужно умножить на с длину и ширину прямоугольника. (Обратите внимание, что действие раздувания обращается в сжатие, если 0 < c < 1).

? Что происходит в операции раздувания с точкой центра прямоугольника ?

Реализация действия раздувание_прямоугольник очень простая, когда прямоугольник представляется посредством центр_длина_ширина. А в методе представления углами раздувание реализуется не так уж просто. Ширина исходного прямоугольника согласно этого представления

width = right_bottom_x - left_top_x .

Ширина нового прямоугодльника равна сwidth. Чтобы сохранить местоположение центра прямоугольника, надо уменьшить left_top_x на половину разницы между новой шириной прямоугольника и его исходной шириной, т.е.

left_top_xnew = left_top_xold - (сwidth - width)/2 = left_top_xold - (с - 1)width/2

? Как определяются остальные значения прямоугольника left_top_y, right_bottom_x и right_bottom_у ?

объединение_прямоугольники(rect1, rect2) возвращает наименьший из прямоугольников, содержащих в себе два заданных (см. рис. 3.2). Это действие очень простое для реализации в методе представления углами. Для , к примеру , левой верхней точки, формулы выглядят так :

left_top_xобъед = minimum(left_top_xrect1, left_top_xrect2)

left_top_yобъед = maximum(left_top_yrect1, left_top_yrect2)

Тем же способом можно найти и правый нижний угол объединенного

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

представления центр_длина_ширина является более сложным.

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

3.4.4. Инициализация абстрактного типа данных

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

инициализация_прямоугольник(left_top_x, left_top_y, right_bottom_x, right_bottom_y) .

Например, инициализация_прямоугольник(0, 1, 2, 0) rect возвращает прямоугольник rect, левый верхний угол которого (0, 1), а правый нижний (2, 0).

? Будет ли необходимость изменить передаваемые этой инициализации параметры, если избран способ представления центр_длина_ширина?

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

3.4.5. Контроль исправности данных

Рассмотрим операцию инициализация_прямоугольник(1,0,0,1) rect . В этой операции сделана ошибка: значения верхнего левого угла поменялись местами со значениями правого нижнего угла. И rect не есть законное значенние типа данных.

Каким условиям должны удовлетворять избранные нами значения, чтобы прямоугольник получился законным ? На рис. 3.3 показан прямой прямоугольник. Из рисунка следует, что должны выполняться два условия : left_top_x < right_bottom_x , right_bottom_y < left_top_y . (Рис. 3.3. Представление с помощью левой верхней вершины и правой нижней вершины и отношения между ними).

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

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

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

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

3.4.6. Полный интерфейс на русском для абстрактного типа данных

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

инициализация_прямоугольник

(lt_x, lt_y,rb_x,rb_y)

Возвращает прямоугольник, левый верхний угол которого (lt_x,lt_y), а правый нижний - (rb_x,rb_t). Допущение: углы действительно представляют исправный прямоугольник.

центр_прямоугольник(rect)

Возвращает центр прямоугольника rect.