М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 22
Текст из файла (страница 22)
end Proc_2;
begin – Main
…
end Main;
Глубина вложения
Принципиальных ограничений на глубину вложения нет, но ее может произвольно ограничивать компилятор. Область действия и видимость определяются правилами, данными выше: область действия переменной — от точки ее объявления до конца блока, а видимость — такая же, если только не скрыта внутренним объявлением. Например:
procedure Main is
| Ada |
procedure Level_1 is
Local: Integer; -- Внешнее объявление Local
procedure Level_2 is
Local: Integer; --Внутреннее объявление Local
begin -- Level_2
Local := Global; -- Внутренняя Local скрывает внешнюю Local
end Level_2;
begin -- Level_1
Local := Global; -- Только внешняя Local в области действия
Level_2:
end Level_1;
begin -- Main
Level_1;
Level_2; -- Ошибка, процедура вне области действия
end Main;
Область действия переменной Local, определенной в процедуре Level_1, простирается до конца процедуры, но она скрыта внутри процедуры Level_2 объявлением того же самого имени.
Считается, что сами объявления процедуры имеют область действия и видимость, подобную объявлениям переменных. Таким образом, область действия Level_2 распространяется от ее объявления в Level_1 до конца Level_1. Это означает, что Level_1 может вызывать Level_2, даже если она не может обращаться к переменным внутри Level_2. С другой стороны, Main не может непосредственно вызывать Level_2, так как она не может обращаться к объявлениям, которые являются локальными для Level_1.
Обратите внимание на возможность запутаться из-за того, что обращение к переменной Local в теле процедуры Level_1 отстоит от объявления этой переменной дальше по тексту программы, чем объявление Local, заключенной внутри процедуры Level_2. В случае многочисленных локальных процедур найти правильное объявление бывает трудно. Чтобы избежать путаницы, лучше всего ограничить глубину вложения двумя или тремя уровнями от уровня главной программы.
Преимущества и недостатки блочной структуры
Преимущество блочной структуры в том, что она обеспечивает простой и эффективный метод декомпозиции процедуры. Если вы избегаете чрезмерной вложенности и скрытых переменных, блочную структуру можно использовать для написания надежных программ, так как связанные локальные процедуры можно хранить и обслуживать вместе. Особенно важно блочное структурирование при выполнении сложных вычислений:
procedure Proc(...) is
-- Большое количество объявлений
begin
-- Длинное вычисление 1
| Ada |
-- Длинное вычисление 2, вариант 1
elsif N = 0 then
-- Длинное вычисление 2, вариант 2
else
-- Длинное вычисление 2, вариант 3
end if;
-- Длинное вычисление 3
end Proc;
В этом примере мы хотели бы не записывать три раза Длинное вычисление 2, а оформить его как дополнительную процедуру с одним параметром:
procedure Proc(...) is
-- Большое количество объявлений
procedure Long_2(l: in Integer) is
begin
-- Здесь действуют объявления Proc
| Ada |
begin
-- Длинное вычисление 1
if N<0thenl_ong_2(1);
elsif N = 0 then Long_2(2);
else Long_2(3);
end if;
-- Длинное вычисление З
end Proc;
Однако было бы чрезвычайно трудно сделать Long_2 независимой процедурой, потому что пришлось бы передавать десятки параметров, чтобы она могла обращаться к локальным переменным. Если Long_2 — вложенная процедура, то нужен только один параметр, а к другим объявлениям можно непосредственно обращаться в соответствии с обычными правилами для области действия и видимости.
Недостатки блочной структуры становятся очевидными, когда вы пытаетесь запрограммировать большую систему на таком языке, как стандарт Pascal, в котором нет других средств декомпозиции программы.
• Небольшие процедуры получают чрезмерную «поддержку». Предположим, что процедура, преобразующая десятичные цифры в шестнадцате-ричные, используется во многих глубоко вложенных процедурах. Такаясервисная процедура должна быть определена в некотором общем предшествующем элементе. На практике в больших программах с блочной структурой проявляется тенденция появления большого числа небольших сервисных процедур, описанных на самом высоком уровне объявлений. Это делает текст программы неудобным для работы, потому что нужную программу бывает просто трудно разыскать.
• Защита данных скомпрометирована. Любая процедура, даже та, объявление которой в структуре глубоко вложено, может иметь доступ к глобальным переменным. В большой программе, разрабатываемой группой программистов, это приводит к тому, что ошибки, сделанные младшим членом группы, могут привести к скрытым ошибкам. Эту ситуацию можно сравнить с компанией, где каждый служащий может свободно обследовать сейф в офисе начальника, а начальник не имеет права проверять картотеки младших служащих!
Эти проблемы настолько серьезны, что каждая коммерческая реализация Pascal определяет (нестандартную) структуру модуля, чтобы иметь возможность создавать большие проекты. В главе 13 мы подробно обсудим конструкции, которые применяются для декомпозиции программы в таких современных языках, как Ada и C++. Однако блочная структура остается важным инструментом детализированного программирования отдельных модулей.
Понимать блочную структуру важно также и потому, что языки программирования реализованы с использованием стековой архитектуры, которая непосредственно поддерживает блочную структуру (см. раздел 7.6).
7.5. Рекурсия
Чаще всего (процедурное) программирование использует итерации, то есть циклы; однако рекурсия — описание объекта или вычисления в терминах самого себя — является более простым математическим понятием, а также мощной, но мало используемой техникой программирования. Здесь мы рассмотрим, как программировать рекурсивные подпрограммы.
Наиболее простой пример рекурсии — функция, вычисляющая факториал. Математически она определяется как:
0! = 1
n! = п х (п - 1)!
Это определение сразу же переводится в программу, которая использует рекурсивную функцию:
int factorial(int n)
| C |
if (n == 0) return 1 ;
else return n * factorial(n - 1);
}
Какие свойства необходимы для поддержки рекурсии?
• Компилятор должен выдавать чистый код. Так как при каждом обращении к функции factorial используется одна и та же последовательность машинных команд, код не должен изменять сам себя.
• Должна существовать возможность выделять во время выполнения произвольное число ячеек памяти для параметров и локальных переменных.
Первое требование выполняется всеми современными компиляторами. Самоизменяющийся код — наследие более старых стилей программирования и используется редко. Обратите внимание, что если программа предназначена для размещения в постоянной памяти (ROM), то она не может изменяться по определению.
Второе требование определяется временем жизни локальных переменных. В примере время жизни формального параметра n — с момента, когда процедура вызвана, до ее завершения. Но до завершения процедуры делается еще один вызов, и этот вызов требует, чтобы была выделена память для нового формального параметра. Чтобы вычислять factorial(4), выделяется память для 4, затем 3 и т. д., всего пять ячеек. Нельзя выделить память перед выполнением, потому что ее количество зависит от параметра функции во время выполнения. В разделе 7.6 показано, как это требование выделения памяти непосредственно поддерживается стековой архитектурой.
Большинство программистов обратит внимание, что функцию, вычисляющую факториал, можно написать так же легко и намного эффективнее с помощью итерации:
int factorial(int n)
{
| C |
result = 1;
while (i != 0) {
result = result * i;
i--;
}
return result;
}
Так почему же используют рекурсию? Дело в том, что многие алгоритмы можно изящно и надежно написать с помощью рекурсии, в то время как итерационное решение трудно запрограммировать и легко сделать ошибки. Примером служат алгоритм быстрой сортировки и алгоритмы обработки древовидных структур данных. Языковые понятия, рассматриваемые в гл. 16 и 17 (функциональное и логическое программирование), опираются исключительно на рекурсию, а не на итерацию. Даже для обычных языков типа С и Ada рекурсию, вероятно, следует использовать более часто, чем это делается, из-за краткости и ясности программ, которые получаются в результате.
7.6. Стековая архитектура
Стек — это структура данных, которая принимает и выдает данные в порядке LIFO — Last-In, First-Out (последним пришел, первым вышел). Конструкции LIFO существуют в реальном мире, например стопка тарелок в кафетерии или пачка газет в магазине. Стек может быть реализован с помощью массива или списка (см. рис. 7.5). Преимущество списка в том, что он не имеет границ, а его размер ограничен только общим объемом доступной памяти. Массивы же намного эффективнее и неявно используются при реализации языков программирования.
Кроме массива (или списка) в состав стека входит еще один элемент — указатель вершины стека (top-of-stack pointer). Это индекс первой доступной пустой позиции в стеке. Вначале переменная top будет указывать на первую позицию в стеке. На стеке допустимы две операции — push (поместить в стек) и pop (извлечь из стека), push — это процедура, получающая элемент как параметр, который она помещает в вершину стека, увеличивая указатель вершины стека top. pop — это функция, которая возвращает верхний элемент стека, уменьшая top, чтобы указать, что эта позиция стала новой пустой позицией.
Следующая программа на языке С реализует стек целых чисел, используя массив:
| C |
int stack[Stack_Size];
int top = 0;
void push(int element)
{
if (top == Stack_Size) /* Переполнение стека, предпримите
что-нибудь! * I
else stack[top++] = element;
}
int pop(void)
{
if (top == 0) /* Выход за нижнюю границу стека,
предпримите то-нибудь! */
else return stack[--top];
}
Выход за нижнюю границу стека произойдет, когда мы попытаемся извлечь элемент из пустого стека, а переполнение стека возникнет при попытке поместить элемент в полный стек. Выход за нижнюю границу стека всегда вызывается ошибкой программирования, поскольку вы сохраняете что-нибудь в стеке тогда и только тогда, когда предполагаете извлечь это позднее. Переполнение может происходить даже в правильной программе, если объем памяти недостаточен для вычисления.
Выделение памяти в стеке
Как используется стек при реализации языка программирования? Стек нужен для хранения информации, касающейся вызова процедуры, включая локальные переменные и параметры, для которых память автоматически выделяется после входа в процедуру и освобождается после выхода. Стек является подходящей структурой данных потому, что входы и выходы в процедуры делаются в порядке LIFO, а все нужные данные принадлежат процедуре, которая в цепочке вызовов встречается раньше.
Рассмотрим программу с локальными процедурами:
procedure Main is
G: Integer;
| Ada |
L1: Integer;
begin ... end Proc_1 ;
procedure Proc_2 is
L2: Integer;
begin... end Proc_2;
begin
Proc_1;
Proc_2;
end Main;
Когда начинает выполняться Main, должна быть выделена память для G. Когда вызывается Ргос_1, должна быть выделена дополнительная память для L1 без освобождения памяти для G (см. рис. 7.6а). Память для L1 освобождается перед выделением памяти для L2, так как Ргос_1 завершается до вызова Ргос_2 (см. рис. 7.66). Вообще, независимо оттого, каким образом процедуры вызывают друг друга, первый элемент памяти, который освобождается, является последним занятым элементом, поэтому память для переменных и параметров может отводиться в стеке.
Рассмотрим теперь вложенные процедуры:
procedure Main is
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
