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

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

8.2. ИМЕНОВАНИЕ ПРОЦЕДУР

375

Таким образом, требуется хранилище имен, которое необходимо и достаточ-

но для решения задач идентификации и работы со стеком контекстов. В ка-

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

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

содержит секцию стека контекстов, соответствующую комплекту объектов,

описываемых в некоторой конструкции программы. Путь от корня к какой-

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

ний структуру стека контекстов.

В современных языках программирования все чаще появляются проце-

дуры с одним и тем же именем, но обозначающие разные алгоритмы. В этой

связи встает вопрос о том, как трактовать именование таких процедур.

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

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

мый в зависимости от ситуации. Так, в

Pascal

очень много смыслов имеет

служебное слово

end

. Каждый из них распознается при синтаксическом ана-

лизе текста и далее конкретного синтаксиса не распространяется. Различные

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

C/C++

Pascal

и дру-

гих языках знак “+” связан с различными алгоритмами для разных типов ар-

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

больше вариантов смыслов в

C/C++

имеет знак “*”, который обозначает и

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

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

его синтаксическая позиция, так и типы аргументов. Заметим, что разное ис-

пользование символа (например, “+” как знак операции “+” или часть знака

“++”) — не относится к рассматриваемому вопросу, поскольку само понятие

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

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

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

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

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

полиморфными.

Важным видом полиморфизма является полиморфизм имен: один и тот

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

личное: данные, алгоритмы и др. Здесь смысл идентификатора, или, что то

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

нения правил локализации имен (см. следующий параграф). Процедуры с од-

ним и тем же именем, но обозначающие разные алгоритмы, (в

С++

, и др.) —

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

376

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

называемых

сигнатур

— информации о количестве и типах параметров. Это

в точности то же самое, что и полиморфизм операций в выражении, когда

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

При рассуждениях о процедурах удобно рассматривать сигнатуру как часть

имени. И хотя такое рассмотрение несколько противоречит разграничению

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

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

Для чи-

тателей, сведущих в объектно-ориентированном программировании, заме-

тим,что частью имени нельзя считать информацию о том,какая из одноимен-

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

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

ся действующий в данный момент объект, когда понятие именования уже не

рассматривается.

Этот динамический полиморфизм зачастую рассматрива-

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

ничем не мотивированно.

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

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

с клавиатуры квадратной матрицы размера N на N, размещаемой в “объ-

емлющем” двумерном массиве, индексируемом значениями

1:NN

, где

—

константа, (см. Рис. 8.2).

Первая процедура с заголовком

void MyOwnMatr(Matrix M, int SizeM);

не вырабатывает значения, вторая — вырабатывает значение, определяющее

размер массива:

int MyInpMatr(Matrix M);

MyOwnMatr

применима тогда, когда заранее известно значение N,а

MyInpMatr

—

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

тываемое функцией значение есть размер матрицы по каждому из измерений.

Сквозной пример носит иллюстративный характер:понятно,что две функ-

ции по своему назначению альтернативны (нет смысла использовать их в од-

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

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

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

поставлять с сигнатурами описаний процедур. Придумайте алгоритмы, решающие поста-

вленную задачу.

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

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

ектов.

8.3. ЛОКАЛИЗАЦИЯ ИМЕН

377

Неиспользованная часть

массива

Рис. 8.2. Представление матрицы размера

N*N

в массиве размера

ной программе), что предпочтительнее

MyInpMatr

, т. к. функция не связана

с необходимостью предварительного определения N и вообще более авто-

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

и функций ниже

MyOwnInpMatr

MyInpMatr

будут рассмотрены совместно и

в разных вариантах.

§ 8.3. КОНТЕКСТЫ И ОБСТАНОВКИ. ЛОКАЛИЗАЦИЯ ИМЕН

Тело подпрограммы в совокупности с ее локальным контекстом называ-

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

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

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

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

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

котором она применена. Такое использование регламентируется так называ-

емыми правилами локализации имен.

Сосредоточимся сейчас в первую очередь на процедурах. Из сказанного

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

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

ру, возможность рекурсивного вызова). Внешние, перерабатываемые данные

378

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

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

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

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

образом.

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

щие:

• заголовок;

• описания локального контекста;

• тело.

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

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

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

ми.

Глобальный контекст обеих процедур ввода матрицы

MyOwnInpMatr

MyInpMatr

, в соответствии с их назначением, должен содержать:

1. константу

— размер массива по измерениям;

2. переменную

типа

int

— фактический размер матрицы;

3. переменную

Matr

типа двумерный массив размера

на

компонент,

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

ﬂoat

Эти три объекта исчерпывают внешние перерабатываемые процедурами дан-

ные. Кроме перерабатываемых данных, в глобальном контексте представле-

ны два оператора

#include

, задающие внешние библиотечные средства.

Внутренние данные, т. е. локальный контекст, определяются при соста-

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

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

предполагается, что глобальный контекст

MyOwnInpMatr

MyInpMatr

пред-

ставлен следующими описаниями:

8.3. ЛОКАЛИЗАЦИЯ ИМЕН

379

#include <stdio.h>

#include <stdlib.h>

const NN = 100;

typedef ﬂoat Matrix[NN][NN];

Matrix Matr; //

(*)

int N;

(8.1)

Это первый вариант глобального контекста. Когда потребуется оперирование

с несколькими матрицами, вместо строки с (*) в (8.1) используется:

Matrix Matr1,Matr2;

Описание типа

typedef ﬂoat Matrix[NN][NN];

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

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

тры и т. д. одного и того же типа:

Matrix Matr1,Matr2; /**/

void MyOwnInpMatr(Matrix M, int SizeM);

int MyInpMatr(Matrix M);

Рассмотрим теперь соотношение обстановки и контекста. Мы говорили

об обстановке лишь для оператора цикла (см. п. 7.3.5). Для программы и под-

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

текста, в котором она работает: служебные и библиотечные программы и пе-

ременные операционной среды и системы программирования. Кроме того,

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

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

потоки. От обстановки зависит поведение программы.

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

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

ствует.

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

объединение составляющих:

a) контекст описания — то, что описано на том же уровне, что и сама про-

цедура, и на уровнях, статически охватывающих ее описание;

380

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

b) контекст вызова — то, что описано на уровне точки вызова процедуры,

и на уровнях, статически охватывающих ее.

Про обстановку вычислений любого другого фрагмента осмысленно гово-

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

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

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

но, поскольку это заслонило бы содержательную сущность понятия: разгра-

ничение между локализованными во фрагменте элементами вычислений и

внешними по отношению к нему элементами. Такое разграничение — часть

задачи анализа программы.

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

треблять имена, декларированные в этом контексте. В современнных языках

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

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

значены для данной процедуры.

Как правило, в языках программирования контекст вызова (за исключе-

нием той его части, которая попадает в контекст описания), непосредственно

процедуре недоступен. Поэтому необходимо передать процедуре те элемен-

ты контекста вызова,которые должны обрабатываться (использоваться и/или

модифицироваться).

В настоящее время распространены два способа передачи данных кон-

текста вызова во внутренний контекст процедуры.

Определение 8.3.1. Параметризация — часть локальных данных процеду-

ры (называемая совокупностью формальных параметров) объявляется спе-

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

процедуры и контекстом ее вызова. Общие блоки —- некоторый контекст мо-

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

граммы.

Конец определения 8.3.1.

Оба варианта передачи данных изображены на рис. 8.3. Серым цветом обо-

значены данные, совместно используемые тремя процедурами. Они предо-

ставляются четырьмя общими блоками и через передачу параметров. Стрел-

ки отражают фактическое обращение к данным. Из рисунка видно, что при

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

как при параметризации нет этого свойства. Поскольку

вызывается внутри

8.3. ЛОКАЛИЗАЦИЯ ИМЕН

381

main

Общий

блок

Общий

блок

Общий

блок

Общий

блок

параметры

Рис. 8.3. Общие блоки и параметры

, а та внутри

main

, то через формальные параметры

может получать дан-

ные из двух контекстов,

из двух, а главная программа может иметь лишь

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

ных вынуждает программиста думать о взаимоотношении подпрограмм по-

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

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

танности программ.

Остановимся вначале на менее распространенной дисциплине взаимо-

связи вызова процедуры и других фрагментов программы — на общих бло-

ках.

Пример 8.3.2. Общие блоки появились в языке

FORTRAN

. В этом языке

тексты основной программы и подпрограмм полностью разделены. Но мож-

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

COMMON /COORD/ X,Y,Z

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

пользуется переменными

X, Y, Z

как элементами своего внутреннего контек-

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

программе

COMMON /COORD/ A(3)

или даже

382

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

COMMON /COORD/ CHAR STR(10)

Общие блоки в языке

FORTRAN

понимаются лишь с точки зрения общей ма-

шинной памяти, разделяемой подпрограммами.

Конец примера 8.3.2.

В языке

С++

имеется любопытный суррогат общих блоков, лишенный

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

FORTRAN

Если некоторый элемент класса определяется как

static

, то он разделяется

всеми экземплярами данного класса.

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

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

контекстов (правилами локализации, см. определение 7.3.2).

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

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

Pascal

)

употребление имен языковых объектов регламентируется правилами, впер-

вые сформулированными в

Algol 60

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

описаний ее локального контекста, то оно понимается в том смысле, в

котором оно определено в локальном контексте;

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

ди описаний ее локального контекста, то делается попытка найти его в

объемлющем контексте (т. е. в том контексте, в рамках описаний которо-

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

предшествует описанию данной процедуры;

c) если имя, употребляемое в теле процедуры, не удается найти в соответ-

ствии с правилами (a) и (b), то делается попытка найти его в следующем

объемлющем контексте до тех пор, пока контекст поиска имени не ока-

зывается локальным контекстом процедуры. (Для

это правило не дей-

ствует, поскольку нельзя описывать функции внутри функций; в

С++

кон-

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

сматривать как задание уровня вложенности в описания класса).

d) если в результате выполнения действий, указанных в правилах (a), (b) и

использование — некорректным.

Перечисленные правила локализации имен языковых объектов зачастую до-

полняются еще одним соглашением (это сделано, например, в языке

Pascal

8.3. ЛОКАЛИЗАЦИЯ ИМЕН

383

e) поиск использованного в программе или подпрограмме имени осуществля-

ется среди тех описаний (какого-либо контекста), которые текстуально

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

Правило (e) впервые появилось в связи с идеей так называемой однопроход-

ной трансляции (построения объектного кода за один просмотр текста про-

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

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

отошла на второй план.

Правила локализации имен —второе по важности после именования сред-

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

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

цедуры и текста программы.

Для языка

C/С++

, где вложенных процедур нет, все представляется до-

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

нятия.

Программа 8.3.1

#include <stdio.h>

const N = 100,

N1 = 30;

int a, b, c, x, y, z, u, v;

void P1();

void P2();

Контексты программы:

локальный:

const N 100; N1 30;

переменные

a, b, c, x, y, z, u, v

;

процедуры

P1, P2

;

глобальный:то, что предоставляет

<stdio.h>

void main()

{

const N1 = 50;

int x, y, u, v;

Контексты функции

main

локальный:

const N1 50;

переменные x, y, u, v;

384

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

глобальный:

const N 100;

переменные

a, b, c, z

;

процедуры

P1, P2

;

то, что предоставляет

<stdio.h>

Внешние данные

main

: она ничего не принимает и не выдает

} //

конец

main

void P1()

{

const N1 = 40;

int x, z, v;

Контексты функции

локальный:

const N1 40;

переменные

x, z, v

;

глобальный:

const N 100;

переменные

a, b, c, y, u

;

процедуры

P1, P2

;

то, что предоставляет

<stdio.h>

x = N1; //

локальной переменной

присваивается значение

// N1 = 40

— локальной константы

y = x + N; //

переменной

, глобальной для

и локальной для

// main,

присваивается значение суммы переменной

// x

, локальной для

= 100 — глобальной (из

программы) константы

a = b + x + y; //

глобальной переменной

присваивается

сумма глобальных переменных

(из программы)

(из

) и локальной переменной

Внешние данные

переменные

y, a, b

; константа

} //

конец

void P2()

{

Контексты функции

локальный: (пустой)

глобальный:

const N 100; N1 30;

переменные

a, b, c, x, y, z, u, v

;

процедуры

P1, P2

;

то, что предоставляет

<stdio.h>

x = N1;