Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

7.4. АС-ПРЕДСТАВЛЕНИЕ ЦИКЛОВ

355

пример, фрагмент программы 7.7:

ﬂoat (*cp)[25][10];

cp = new ﬂoat[10][25][10];

(7.7)

и функция

New(Pointer)

Pascal

. Динамические значения почти наверняка

будут создаваться, если вы пользуетесь аппаратом ООП.

Конечно же, в технологиях и методиках програмирования дается масса

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

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

ся картина контекстов приобретает вид, изображенный на рис. 7.5. Даже в

…

Рис. 7.5. Идеальная ситуация с контекстами

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

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

все созданные в нем динамические значения, которые, в свою очередь, могли

создать другие значения.

Но в реальности либо в Вашей программе, либо в используемых ею па-

кетах и модулях почти всегда есть нарушения требований технологии и хо-

рошего тона в программировании. В этом случае ситуация приобретает еще

356

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

более унылый вид (рис. 7.6) и задача освобождения памяти становится тяже-

…

Рис. 7.6. Реальная ситуация с контекстами

лой. Появляются две типичные ошибки:

• Освобождается и уничтожается значение, на которое уже ссылаются из

объемлющего, сохраняющегося контекста. Тогда, как говорят, некото-

рые ссылки “повисают”.

• Забывают удалить ненужное значение, и возникает ситуация, извест-

ная программистам под названием утечка памяти (memory leak), един-

ственным лекарством от которой чаще всего является перезагрузка си-

стемы. Эта ситуация показана на рис. 7.6 на примере изолированного

объекта, к которому нет доступа.

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

(garbage collection). Для нее разработано множество алгоритмов, но все они

либо ограничены по области применимости, либо не могут предотвратить

7.4. АС-ПРЕДСТАВЛЕНИЕ ЦИКЛОВ

357

утечки памяти и (чаще всего) появления висячих ссылок.

Поэтому удале-

ние еще нужных динамических объектов практически целиком остается на

совести программиста и является одним из источников мистических ошибок

в используемых программах.

Еще более трудной становится ситуация, если у нас вычисления суще-

ственно совместные, распределенные либо параллельные. Тогда структура

контекстов может стать деревом (см. рис. 7.7), где у многих приостановлен-

Рис. 7.7. Дерево контекстов

ных контекстов есть несколько подчиненных им активных либо приостано-

вленных контекстов.

Как уже говорилось, это — типичная ситуация при практическом решении теоретически

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

А дублирование памяти практически редко используется.

358

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

7.4.3. Исключения

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

полнив его до конца,является возникновение исключительной ситуации.Для

обработки исключительных ситуаций, начиная с языка

Ada

, вводятся специ-

альные средства. Рассмотрим их на примере

C++

try

<Оператор try>

catch (<Имя исключения>)

<Оператор catch>

(7.8)

Конструкция

catch

может повторяться несколько раз. Внутри <Оператора

try

> может использоваться конструкция

throw <Имя исключения>;

Эта конструкция возбуждает исключение с соответствующим именем.

Кроме того,

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

раторов внутри <

Оператора try

>, также вызывают исключения со стандарт-

ными именами. В частности, такие (обычно вылавливаемые лишь по непри-

ятностям, возникающим впоследствии) ошибки, как переполнение диапазо-

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

исключения. При возникновении исключения:

1) уничтожаются все возникшие внутри <Оператора

try

> локальные объек-

ты,

2) ищется соответствующий имени исключения обработчик исключения,т.е.

catch

3) если обработчик найден, то

исполняется найденный обработчик;

4) если обработчик не найден, то

управление передается оператору

try-catch

, находящемуся в объемлю-

щем контексте, который обрабатывает исключение по тем же правилам;

В стандарте языка

С++

это оговорено явно, но в

VisualC

это работает, лишь если включена

соответствующая директива периода трансляции.

7.4. АС-ПРЕДСТАВЛЕНИЕ ЦИКЛОВ

359

5) если обработчик исключений не найден и объемлющего оператора

try-

catch

нет в контексте программы, то

вызывается функция завершения работы программы;

6) завершается оператор (7.8).

Возникает вопрос: что считается объемлющим контекстом? Тот контекст, в

который вложен оператор

try-catch

в тексте самой программы или контекст

подпрограммы, вызвавшей другую подпрограмму, в тексте которой находит-

ся данный оператор? И здесь мы естественно переходим к следующей главе

курса, в которой подробно разбираются процедуры и аспекты работы про-

грамм, связанные с их вызовами.

Но перед завершением главы нужно упомянуть о еще одной возможно-

сти. В языках

Java

Object Pascal

оператор

try

может завершаться опера-

тором

ﬁnally

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

вершении, и при структурном выходе, и при ошибке. В языке

C++

можно

добиться почти такого же эффекта, использовав

catch(...)

, но нормальный

выход в этом случае остается неотработанным.

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

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

не заботясь о том, как должна реагировать программа на ситуации, когда

нарушается естественная логическая последовательность действий. Описа-

ние необходимых в этих ситуациях действий в таких случаях выносится из

основной «канвы повествования» программы в специальные разделы, четко

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

примеру, вы пишите серьезную вычислительную программу, которая может

работать с некорректными данными, вызывающими деление на ноль. Учет

этого в алгоритме потребовал бы реализовать соответствующие проверки,

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

делать, когда такое происходит, помогает, в частности, при организации стан-

дартного реагирования на данную ситуацию.

Как уже отмечалось (см. § 3.5), оперирование с исключительными си-

туациями можно рассматривать как один из вариантов программирования в

событийно-ориентированном стиле. Здесь события — возникновение ситуа-

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

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

ния, логически не очень сложен, то использование средств поддержки опе-

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

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

360

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

том, с какими событиями-исключениями можно иметь дело, какими спосо-

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

Есть еще одна методическая трудность работы с исключениями: что де-

лать после отработки реакции? Как правило (и это зафиксировано в при-

веденном выше описании действий абстрактного вычислителя) реакция за-

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

туации (конструкция

try

). Если не считать тривиального (и совершенно не-

гибкого) прекращения вычислений программы после отработки реакции, то

принципиально возможны еще два решения: возврат в точку выполнения, в

которой произошел вызов реакции (это трактуется как исправление ошибки

при выполнении реакции), и завершение блока, в котором определено пред-

писание о реагировании на ситуацию (это трактуется как невозможность ис-

правления ошибки и, как следствие, невозможность выполнения указанно-

го блока). Второе решение легко моделируется с помощью описанного выше

механизма. Что касается трактовки исключения как исправления ошибки, то,

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

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

ного программирования

Prolog

называется backtracking. Такой вид возвратов

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

с другими стилями, кроме сентенциального, и поэтому такой трактовки ис-

ключения стараются избегать. Заметим, что указанный нами частный случай

синтаксического анализа как раз и относится к числу задач, где естественней

всего сентенциальное программирование.

Задания для самопроверки

1. Какие типовые приемы из перечисленных выше использованы в про-

граммах из таблицы 7.5?

2. Составить программу, аналогичную 7.2.2, в которой не требуется ни

переменная

Prime

, ни двойная проверка ее значения.

3. Изменить програму 7.2.5 таким образом, чтобы файл не перезаписы-

вался, если в этом нет нужды.

4. Изменить програму 7.2.5таким образом,чтобы файл использовался как

словарь ранее сосчитанных простых чисел, пополняемый в тех случа-

ях, когда в нем не удается найти нужного элемента.

7.4. АС-ПРЕДСТАВЛЕНИЕ ЦИКЛОВ

361

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

выделения параметров цикла в языке, которым Вы пользуетесь?

6. Каковы логические причины концептуального противоречия между со-

вместными циклами и потоками?

7. Разработать абстрактно-синтаксическое представление и алгоритм его

вычисления для оператора цикла

for

8. Разработать абстрактно-синтаксическое представление и алгоритм его

вычисления для оператора

try-catch

9. Объясните, почему в фрагменте программы 7.7 переменная

имеет

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

указывать

после исполнения данного фрагмента?

10. Разработать алгоритм вычисления цикла

for

для случая структурных

завершений.

Глава 8

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

Формирование понятия подпрограммы является одним из наиболее зна-

чительных достижений в области информатики. Необходимость использо-

вания подпрограмм осознавалась еще на самом раннем этапе применения

вычислительной техники. В течение всего периода существования програм-

мирования это понятие постоянно развивалось.

Первоначально подпрограммы понимались исключительно как средство

сокращения записи алгоритмов путем ‘вынесения за скобки’ их общих ча-

стей. Очень быстро оформилось понятие подпрограммы как библиотечного

средства, — такой программной единицы, которая может (и должна) быть

использована в различных программах, в том числе и в программах различ-

ных разработчиков.Как только было осознано,что конструирование сколько-

нибудь серьезной программы немыслимо без разбиения ее на относительно

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

дули, роль подпрограмм существенно возросла: их начали рассматривать в

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

программы на относительно независимые части, допускающие независимые

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

но.

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

FORTRAN

подпрограм-

мы использовались прежде всего как средство модуляризации, и в этом от-

ношении

FORTRAN

по меньшей мере на 25 лет опередил другие языки про-

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

языка

FORTRAN

были совсем не теми, для которых она актуальна сейчас:

независимое, абстрактное рассмотрение подпрограмм. В данном языке мо-

дульность — это, в первую очередь, одно из средств раздельной компиля-

362

363

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

нения программных единиц, хранимых на внешних носителях. Что касает-

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

модульность на уровне компиляции вполне может применяться и для этих

целей. И этим стали активно пользоваться.

Мы видим, что есть два вида модуляризации:

• технологическая модуляризация, предназначенная для поддержки не-

зависимой разработки подпрограмм на уровне декомпозиции програм-

мы, и

• модуляризация для сегментации,поддерживающая независимую транс-

ляцию и исполнение программных единиц, называемых обычно загру-

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

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

виях дефицита памяти; она не противоречит технологической модуляриза-

ции, а потому, следуя

FORTRAN

овской традиции, два вида модуляризации

очень часто смешиваются. Но это разные задачи, которые нужно решать в

такой последовательности: сначала определяется логическая декомпозиция,

а после того, как она построена, строится декомпозиция на сегменты.

Две стороны подпрограмм — использование для выделения общих ча-

стей алгоритмов и для декомпозиции сложных программ — по сей день явля-

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

поддержки обоих аспектов подпрограмм, постоянно развиваются и данный

раздел курса программирования нельзя считать полностью устоявшимся. Ви-

Если происходит их смешивание, а такое можно встретить сплошь и рядом, то в первую

очередь страдает сегментация. К примеру, на логическом уровне вполне естественно груп-

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

инициализацию, обработку и уничтожение. Более того, именно такая организация модулей

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

на уровне сегментной декомпозиции ситуация меняется: инициализация и уничтожение —

разовые действия, отнесение которых к одному сегменту с обработкой приводит к ничем

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

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

язык

ЯРМО

, где возможности приписывания фрагментов кода к разным загрузочным сег-

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

подобного разделения, еще и сегодня общераспространенные системы программирования

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

программные единицы, которые можно подключать к сегментам, есть логические модули.

364

ГЛАВА 8. ПОДПРОГРАММЫ

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

дения и изменения.

Если раньше понятие подпрограммы связывалось исключительно с от-

дельными алгоритмами, которые ими реализуются, то в современных языках

понятие подпрограммы в большей мере соотносится с совместным опреде-

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

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

нее понятие библиотеки — это просто набор реализаций тематически связан-

ных алгоритмов, то нынешние библиотеки объединяют подпрограммы во-

круг данных, над которыми они оперируют, и тем самым помогают модуля-

ризации. Это развитие отражает потребности технологии конструирования

программ.

Что же касается сегментной декомпозиции, то ее задачи в условиях по-

стоянного снижения стоимости памяти сегодня ушли на второй план. Как

следствие, сейчас не появляются новые или уствершенствованные средства

ее поддержки. Однако было бы опрометчиво полагать, что проблемы сегмен-

тирования уже никогда не станут вновь актуальными.

§ 8.1. ВИДЫ ПОДПРОГРАММ

Проще всего рассматривать подпрограмму как на операционную едини-

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

ма). Часто принято различать два вида операционных подпрограмм:

a) функции, выполнение которых порождает значение, передаваемое в точку

их вызова, (вызов функции есть элемент выражения) и

b) процедуры, выполнение которые используются лишь для преобразования

данных, доступных в контексте вызова, и которых не порождает значений

(вызов процедуры — это оператор).

Эти два понятия естественно объединяются путем формального расширения

множества всех мыслимых значений всех типов специальным значением ни-

что (void). Считается, что процедура есть функция, которая вырабатывает

такое значение. Данный прием принят во многих развитых языках програм-

мирования, начиная с

Алгола-68

, в частности, в

C++

Java

. Поэтому в

перечисленных языках понятие подпрограммы не вводится. Есть лишь по-

нятие функции.