Концепция действий в языке Паскаль

Размещено на http://www.allbest.ru/

Министерство образования и науки Украины

Национальный технический университет Украины "КПИ"

Факультет Информатики и вычислительной техники

Курсовая робота

Концепция действий в языке Паскаль

Киев 2011

1. Блочная организация программ

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

Такая форма организации вычислений не противоречит принципу Неймана. Действительно, естественный порядок выборки очередной команды программы с помощью наращивания значения СЧАК или PI с шагом, равным единице, может быть изменен при условии, что для этого в системе команд предусмотрены соответствующие инструкции. Такой инструкцией может служить так называемая команда безусловного перехода, предписывающая занесение в СЧАК (PI) нового значения (аналог - оператор goto). Это значение обычно находится в ячейке памяти, адрес которой указывается в адресной части соответствующей команды, и для каждой подпрограммы всегда однозначно определено.

При этом нужно "побеспокоиться" о возврате в основную программу. Возврат может быть обеспечен с помощью той же команды безусловного перехода, которая вернет в СЧАК (PI) его прежнее значение, увеличенное на единцу. Это значение, называемое адресом возврата, необходимо перед уходом на подпрограмму предварительно ей "передать", поскольку подпрограмма может вызываться из различных мест основной программы и возвращаться нужно не в одно и то же место. Для этого можно использовать инструкцию, которая позволяет записать адрес возврата в адресную часть команды безусловного перехода.

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

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

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

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

возможность разработки программ методом последовательных уточнений (stepwise refInement);

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

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

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

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

Динамическое распределения памяти

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

Для реализации динамического распределения памяти используется механизм блочной или модульной организации программ. Под блоком понимается выделенная определенным образом часть программы, в которой содержится описание переменных и констант, необходимых для ее выполнения. Такие переменные и константы называются локальными и существуют в оперативной памяти только при выполнении действий, связанных с блоком. Естественно, что такой блок при блочной организации программы не может существовать "сам по себе" и должен быть описан внутри некоторого другого блока. Исключение составляет самый внешний блок. Так как блоки могут вкладываться один в другой, то каждому из них можно приписывать некоторый уровень вложенности. Если самый внешний блок относится к уровню 0, то блок, определенный внутри этого блока, должен относиться к уровню 1 и т. д.). Вложенность блоков, в общем случае, не ограничена.

Переменные, описанные в блоке называются глобальными по отношению к внутренним блокам. Вложенность блоков и понятия глобальной и локальной переменной иллюстрируются рис 4.2.



На рисунке изображены четыре блока. Внешний или блок нулевого уровня не заполнен тенью. Пусть во внешнем блоке описаны переменные a и b. Переменные являются глобальными по отношению ко всем вложенным блокам и "доступны" в этих блоках. Во вложенных блоках первого уровня описаны переменные c,d и e,f, которые недоступны во внешнем блоке и по отношению к нему считаются локальными. Переменные g и h доступны только в блоке второго уровня вложенности, относительно которого c и d могут рассматриваться как глобальные. После выхода из блока память, распределенная под локальные переменные, считается свободной и на их месте могут размещаться локальные переменные следующего блока.

При выполнении такой программы в оперативной памяти будут сначала располагаться только переменные a и b, затем при входе в блоки и после выхода из них в соответственна с рисунком a,b,c,d, a,b,c,d,g,h, a,b, a,b,e,f и снова a,b, т.е. память распределяется динамически в процессе выполнения программы. Эта концепция впервые была четко сформулирована Э. Дейкстрой и реализована в языке Алгол 60. С тех пор она в различных вариантах реализуется в большинстве современных языков программирования. В языке Паскаль концепция блочной структуры программы организуется с помощью аппарата процедур. Кроме того, аппарат процедур в этом языке позволяет реализовать все перечисленные ранее возможности, свойственные структурированию вычислений процесса с выделением подпрограмм.

2. Процедуры

Определение процедуры в языке Паскаль позволяет выделить подзадачу как явную подпрограмму. Правила, определяющие конструкцию <процедура> - это те же правила, которые определяют конструкцию программы. Исключение составляет зарезервированное слово procedure, используемое вместо program в заголовке и отсутствие точки после блока.

<процедура> ::= <заголовок процедуры>;

<блок>

<заголовок процедуры> ::= procedure <имя процедуры>

procedure <имя процедуры>

(<список формальных параметров>)

<блок> ::= <список разделов описаний>:

<раздел операторов>

<список разделов описаний> ::= < раздел >

<список разделов описаний>:

< раздел >

< раздел > ::= < раздел меток >

< раздел констант >

< раздел типов>

< раздел переменных>

< раздел процедур и функций >

<раздел операторов> ::= begin<список операторов> end

<список операторов> ::= <оператор>

<список операторов>;<оператор>

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

Раздел процедур и функций не именуется отдельным зарезервированным словом и определяется конструкцией списка:

< раздел процедур и функций > ::= < процедура или функция >

<раздел процедур и функций > ;

< процедура или функция >

< процедура или функция > ::= < процедура>

< функция >

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

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

< оператор процедуры> ::= <имя процедуры>

<имя процедуры>

(<список фактических параметров>

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

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

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

В качестве примера программы с процедурой без параметров, рассматривается программа, позволяющая определить минимальное (mIn) значение и его индекс в последовательности целых чисел W₁, ..., W_n, при условии, что к ним добавляются приращения j₁, ..., j_n и затем вновь отыскивается mIn.

program Prim4_1;

type

Index =1 .. 10;

Vector=array [Index] of Integer;

var

I,N : Index;

W, Change : Vector;

procedure SearchMin; {описание процедуры SearchMIn}

var

I,K : Index;

Min : Integer;

begin

MIn :=W[1];

K :=1;

for I :=2 to N do

if W[I] < Min then

begin

MIn :=W[I];

K :=I

end;

WriteLn (`Значение компоненты вектора с индексом `,I,

'равно `,min)

end;{SearchMin}

procedure Modification; {описание процедуры ModifIcation}

var

I : Index;

begin

Write (`Введите `,n,' компонент вектора-модификатора ');

for I :=1 to N do

Read (Change[I]);

WriteLn;

for I := 1 to N do

W[I] := W[I]+Change[I];

end; { Modification }

begin {начало блока программы}

Write (`Введите размерность вектора `);

ReadLn (N);

WriteLn (`Введите ',n,' компонент вектора');

for I :=1 to N do

Read (W[I]);

WriteLn;

SearchMin; {оператор процедуры SearchMin }

Modification; {оператор процедуры Modification }

SearchMin {повторный вызов процедуры SearchMin;}

end. {Prim4_1}

Несмотря на простоту программы, в качестве комментария к ней можно отметить, что:

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

глобальными являются переменные I, N, а также векторы W и change; на переменную N и на компоненты векторов можно ссылаться в программе повсюду (например, присваивание MIn :=W[1] в блоке процедуры SearchMin или W[I] := W[I]+Change[I] в Modification);

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

При этом можно отметить, что в таком переопределении в примере не было необходимости. Однако, "хороший стиль" программирования требует строгой локализации переменных в процедуре, если на них нет ссылок вне процедуры. Выполнение такого требования позволяет ясно очертить данные, "принадлежащие" именно этой процедуре, и обеспечивает дополнительную безопасность по отношению к возможным ошибкам. Например, в рассматриваемой программе I можно было бы оставить глобальной переменной. Но тогда расширение программы (иллюстрация - program Prim4_2) для случая нескольких модификаций вектора W, где к процедуре SearchMin пришлось бы обращаются из цикла с параметром I, приведет к нарушению ее нормального выполнения.

program Prim4_2;

type

Index=1 .. 10;

Vector=array [Index] of Integer;

var

J,N : Index;

I,M : Integer;

W, Change : Vector;

procedure SearchMin;

var

I,K : Index;

Min : Integer;

begin

Write (`Введите размерность вектора `);

Readlyn (n);

WriteLn (`Введите ',n,' компонент вектора ');

for J :=1 to N do

Read (W[I]);

WriteLn;

Min := W[1];

K :=1;

for I:=2 to N do

if W[I] < Min then

begin

Min := W[I];

K :=I

end;

WriteLn (`Минимальное значение компоненты равно `,mIn)

end; { SearchMin }

procedure ModifIcation;

var

I : Index;

begin

Write (`Введите `,n,' компонент вектора-модификатора ');

for I := 1 to n do

read (Change[I]);

Writen;

for I :=1 to N do

W[I] :=W[I]+Change[I];

end; {ModificatIon}

begin

Write (`Введите колчество повторений ');

Realm (M);

for I :=1 to M do

begin

SearchMin;

Modification

end

end. {Prim4_2}

В программе переопределен тип глобальной переменной I и введены переменные J и M. Это обусловлено тем, что переменная I теперь обозначает текущий номер повтора, а M - количество повторов и обе не обязательно принадлежат типу Index. Кроме того, имя параметра циклов, которые обеспечивают ввод W и Change, а также модификацию W, не должно конфликтовать с именем параметра цикла, задающего повторы. Здесь же можно отметить, что при использовании вместо I для одной из переменных (локальной или глобальной) другого имени устранило бы необходимость обсуждения области их действия.

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

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

Небольшое и, на первый взгляд, несущественное усложнение рассматриваемой задачи, связанное с необходимостью поиска минимального значения в нескольких векторах с разными именами, (например, W1, W2, W3), вызовет затруднениям при попытке использовать для этих целей процедуру без параметров. В этом случае придется вводить дополнительный вектор, с которым будут "работать" процедуры SearchMin и Modification, предварительно пересылая в этот вектор значения W1, W2 или W3.

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

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

<список формальных параметров> ::= < формальный параметр>

<список формальных параметров>;

<формальный параметр>

<формальный параметр> ::= <параметр-переменная>

<параметр-значение>

<параметр-процедура>

<параметр-функция>

<параметр-переменная> ::= var <список имен>:<тип>

<параметр-значение> ::= <список имен>:<тип>

<параметр-процедура> ::= procedure<имя процедуры>

<параметр-функция> ::= function<имя функции>:<тип>

<список имен> ::= <имя переменной>

<список имен>,

<имя переменной>

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

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

Различия между параметрами-переменными и параметрами-значениями хорошо видны на таком примере:

program Prim4_3;

var

A,D : Integer

procedure DemoPar (var X : Integer; Y : Integer);

begiIn

X :=X + 1;

Y :=Y + 1;

Writen (A, A)

end; {DemoPar}

begin

A := 0;

D := 0;

DemoPar (A, B);

WriteLn (A, B)

end. {Prim4_3}

Результатами вывода будут пары чисел ??? и ???, поскольку параметр X - параметр-переменная и оператор присваивания X:=X+1 в блоке процедуры эквивалентен оператору A:=A+1 после замены X фактическим параметром A при вызове процедуры. Значение фактического параметра B было "скопировано" в процедуру при ее вызове (он описан как параметр-значение) и поэтому изменялась только его копия, а значение самой глобальной переменной осталась прежним.

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

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

program Prim4_4;

type

Index=1 .. 10;

Vector= array [Index] of Integer;

var

N1,N2,N3 : Index;

W1,W2,W3 : Vector;

procedure SearchMin (N : Index; W : Vector;);

var

I : Index;

Min: Integer;

begin

Min :=W[1];

for I:=2 to N do

if W[I] < Min then

Min := W[I];

WriteLn (`Минимальное значение компоненты равно `,mIn)

end; {SearchMin}

procedure MyInput (var N : Index; var W : Vector);

var

I : Index;

begin

WrIte (`Введите размерность вектора `);

Realm (N);

Written (`Введите ',n,' компонент вектора');

for j :=1 to n do

read (W[I]);

WriteLn

end; {MyInput}

begin

MyInput (N1, W1);

SearchMin(N1, W1);

MyInput (N2, W2);

SearchMin(N2, W2);

MyInput (N3, W3);

SearchMin(N3, W3;)

end. {PrIm4_4}

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

Параметры процедуры SearchMin - это параметры-значения. Соответ-ствующие им фактические параметры являются для этой процедуры исходными данными. Их не yogi сохранять lineal выхода eke SearchMin, а результат выполнения этой процедуры непосредственно выводится air зкран.

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

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

3. Функции

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

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

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

<заголовок функции > ::= function <имя>: <тип результата>

function <имя>

(<список формальных параметров>):

<тип результата>

<тип результата> ::= <простой тип><ссылочный тип>

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

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

В следующем ниже примере описание funkion Epod, предназначенной для вычисления S=b^y, для -n y n, т.е. степенной функции вещественного аргумента для произвольного целого показателя степени.

program PrIm4_5;

var

P : Reel;

q : Integer;

funkion Epod(X : Reel; Y : Iinteger) : Reel;

var

I : Intoegerm;

begin

if y<0 then

begin

X := 1/X;

Y :=-Y

end;

Epod :=1;

for I:=1 to Y do

Epod := Epod *X

end: {Epod}

begin

WriteLn (`Введите аргумент степенной функции х. ');

ReadLn(P);

WriteLn (`Введите показатель степени y=');

ReadLn(Q);

WriteLn (x,' в степени `,y,' равно `,Epod(P,Q)

end. {Prim4_5}

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

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

program prim_22;

var

A, B, Eps : Reel; {[A,B]- интервал, Eps -погрешность}

function zero (funkion F : Reel; X, Y : Reel) : Reel;

var

u,z : real;

S : Boolean;

begin

S := F(X)<0;

repeat

U :=(X+Y)/2;

Z := F(U);

if (Z<0) = S

then

X :=U

else

Y :=U

until Abs (X-Y) < Eps;

Zero :=U

end; {Zero}

begin

Write (`Введите значения границ интервала ');

ReadLn (a,b);

Write (`Введите допустимую погрешность ');

ReadLn (Eps);

WriteLn (Zero (SIn,A,B));

WriteLn (Zero (Cso,A,B))

end. {Prim4_6}

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

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

program Prm4_6;

var

A,Z : Integer;

funkion SidTest (X : Integer) : Integer;

begin

Z :=Z - X; {побочное воздействие на Z}

SidTest :=X * X

end; {SidTest}

begin

Z :=10;

A :=SidTest(Z);

WrieLn (A,Z); {результат вывода : 100 и 0 }

Z :=10;

A :=SidTest (10) * SidTest (Z);

WriteLn (A,Z); {результат вывода : 0 и 0 }

Z :=10;

A :=SidTest (Z) * SidTest (10);

WriteLn (a,z) {результат вывода : 10000 и -10 }

end. {Prim4_6}

Для исключения ошибок, связанных с побочным эффектом, желательно:

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

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

4. Рекурсия

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

Так конструкция <список операторов> в бэкусовой нормальной форме имеет вид:

<список операторов> ::= <оператор><список операторов>;

<оператор>.

Натуральное число рекурсивно определяется следующим образом:

единица есть натуральное число;

целое число, следующее за натуральным, есть натуральное число.

Функция n! для неотрицательных целых чисел определяется как :

0! = 1

если n > 0, то n! = n*(n-1)!.

Мощность рекурсии обусловлена тем, что она позволяет задать бесконечное множество объектов с помощью конечного высказывания. Точно так же бесконечные вычисления можно описать с помощью конечной рекурсивной программы, даже если эта программа не содержит явных циклов. В общем случае рекурсивную программу Р можно изобразить как композицию операторов S_I , не содержащих Р, и самой Р, т.е. Р [S_I , P].

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

Рассматривая рекурсию важно отметить, что она является только средством описания некоторого объекта, но не задает механизмов реализации вычислений. Например, при вычислении n! для n=4 можно использовать механизм, изображенный на рис х.х, который представляет собой "спуск" с запоминанием выражений функции до тех пор, пока значение выражения не может быть вычислено, а затем "подъем" с вычислением промежуточных значений вплоть до искомого.

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

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

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

P=if B then P[S_I , P] или P=P[S_I , if B then P]

Надежный способ обеспечить окончание процедуры аналогичен способу, применяемому для тех же целей у операторов цикла. Он заключается в определении некоторой, например, монотонно убывающей функции f(x) (x - множество переменных процедуры), такой, что f(x)=0 удовлетворяет условию окончания процедуры. Чаще всего это связанный с Р параметр (пусть - n), который при рекурсивном вызове Р уменьшается на единицу. Тогда замена условия В на n > 0 гарантирует окончание процедуры. Это можно изобразить следующими схемами:

P(n)=if n > 0 then P[SI, P(n - 1)] или P(n)=P[SI, if n > 0 then P(n - 1)].

Так, например, вычисление факториала по его рекурсивному описанию сводится к тому, что "граничное значение" определяется явным образом как f(0)=1, а последующие числа обычно определяются рекурсивно, т.е. с помощью предшествующего значения: f(I+1)=f(I)*(I+1). Эта формула предполагает использование рекурсивного алгоритма для вычисления n-го факториального числа с применением процедуры, соответствующей схеме P = if B then P[S_I , P] или P = P[S_I , if B then P].

На языке Паскаль это выражается программой:

program prIm4_7;

var

F,I,N : Integer;

procedure P;

begIn

if I < N then

begIn

I := I+1;

F :=I*F;

P

end

end;

begIn

WrIteLn( `Введите n');

ReadLn (N);

I :=1;

f :=1;

P;

WrIten( `n! равно ', f)

end. {Prim4_7}

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

program Prim4_8;

var

N : Integer;

funkion F (N : Integer) : Integer;

begin

If N> 0

then

F := N*F(N - 1)

else

F:= 1

end; {F}

begin

WriteLn( `Введите n');

ReadLn (n);

WriteLn( `n! равно ', F(N))

end. {Prim4_8}

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

I:= 0;

f :=1;

whale I< N do

begin

I :=I+1;

f :=I*F

end ;

Здесь схема P=If В then P[S_I ,P] преобразована к виду P=(x:=x₀; whale B do S), где x:=x₀ соответствует "граничим условиям" в рекурсивном определении (граничные условия таким образом превращаются в "начальные").

Другим примером целесообразности такой замены, может служить вычисление чисел Фибоначчи, определяемых с помощью рекуррентного соотношения fIb_n+1 = fIb_n + fIb_n-1 для n > 0 и fIb₁ = 1, fIb₀ = 0.

Используя рекурсивную схему, можно написать функцию

funkion Fib(N: Integer): Integer;

begin

if N=0 then

Fib :=0

else

If N=1 then

Fib :=1

else

Fib := Fib(N-1) + Fib(N-2)

end;

При вычислении fIb_n обращение к функции Fib(N) приводит к ее очередной активации дважды, т.е. общее число обращений растет экспоненциально (см. Рис.4.3). Такая программа потребует достаточно большого количества свободной памяти для реализации рекурсивных вычислений.

Однако числа Фибоначчи можно вычислять и по итеративной схеме, при которой использование вспомогательных переменных X=FIb_is и Y=FIb_is-1 позволяет избежать повторного вычисления одних и тех же значений:

I := 1;

X :=1;

Y :=0;

whale I < N do

begin

X :=X+Y;

y:=X - Y;

I := I+1

end;

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

В качестве примера задачи, итеративное решение которой затруднительно, часто рассматривается задача-игрушка "Ханойские башни", Рис.4.4. Цель игры - перенести башню, состоящую из n колец, с иглы а на иглу с по следующим правилам:

перемещать можно только одно кольцо;

при переносе можно использовать любую иглу как вспомогательную;

нельзя класть большее кольцо на меньшее.

При таких правилах основное внимание следует обратить на нижнее кольцо иглы A, поскольку перенос его с иглы A на иглу C является ключом к решению всей задачи, позволяя уменьшить ее размерность до n-1. Это можно осуществить, переместив башню , состоящую из n-1 колец с иглы A на иглу B (в качестве вспомогательной используется игла C). Теперь нижнее кольцо можно переносить на иглу C, а затем переместить туда мотавшуюся часть башни, используя в качестве вспомогательной иглу A. Описанные действия имеют смысл при истинном условии "высота перемещаемой башни больше нуля" или, что то же самое, при n 1.

Таким образом, решение задачи переноса башни из n колец с иглы a на иглу c может быть приведено к схеме P = if n0 then P[S_i, P(n-1)] и описано как:

перенести башню из N-1 колец с иглы A на иглу B, используя в качестве вспомогательной иглу C, или MoweTower (N-1, A,B,C);

перенести кольцо с иглы A на иглу C, или MoweRing (A,C);

перенести башню из n-1 колец с иглы B на иглу C, используя в качестве вспомогательной иглу A, или MoweTower(N-1, B,C,A);

ничего не делать если N 1.

Соответствующая этой схеме действий программа имеет вид:

program Prim4_9;

var

NRIngo : Integer;

procedure MoweTowerr(N,A,C,B: Integer);

procedure MoweRinag(Out_,In_ : Integer);

begin

Writen (Out_,'-->',In_)

end; {MoweRinag}

begin

if n>0 then

begin

MoweTowerr(N-1,A,B,C);

MoweRinag (A,C);

MoweTowerr(N-1,B,C,A)

end

end; {MoweTowerr}

begin

Written (`Введите количество колец в acacia');

Realm (NRing);

Written(`Рекомендуемая последовательность перемещения колец:');

MoweTowerr(NRIngo,1,3,2)

end. {Prim4_9}

В качестве дополнительного комментария к программе следует отметить, что процедура MoweRinag позволяет вывести на экран номер иглы, с которой снимается и на которую переносится очередное кольцо (игле A соответствует 1, B - 2, C - 3). Кроме того, программа весьма чувствительна к объему свободной памяти, т.е. задача может быть решена только для небольших значений N.

Опережающее описание процедур и функций

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

procedure P (X : T); forwarid;

procedure Q (Y : T1);

begin

P(A)

end;

procedure P; {описание параметров не повторяется}

begin

Q(B)

end;

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

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

5. Модули

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

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

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

funkion Seach(var W: We; Т: Integer; Item: Reel): Integer;

var

I: Index;

begin

I := 0;

repeat

I:= I+1

until W[I]=Item;

if I <> n+1

then

Seach:=I

else

Seach:=0

end { Seach};

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

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

funkion Seach(var W: We; Т: Integer; Item: Reel): Integer;

var

I: Index;

begin

I :=N+1;

repeat

I:= I-1

until W[I]=Item;

if I <>0

then

Seach:=I

else

Search:=0

end { Search};

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

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

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

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

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

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

для использования процедур или функций, входящих в состав модуля, достаточно только "подключить" модуль к своей программе, что достигается с помощью специальной инструкции uses (предложения использования);

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

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

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

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

В состав библиотеки модулей Borland Pascal, ориентированных на платформу DOS, входят модули System, Dos, Crt, PrInter, Graf, Graf3, Overlay и Turbo3, которые достаточно хорошо описаны в документации. Там же необходимо знакомиться с характеристикой библиотеки модулей, входящих в версии, которые ориентированы на платформу WIndows.

Синтаксическая конструкция, соответствующая определению модуля имеет вид:

<модуль > ::= <заголовок модуля >

<интерфейсная секция>

< секция реализации>

< секция инициализации >

<заголовок модуля> ::= unit¦ <имя модуля >

<имя модуля > ::= <идентификатор>

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

< предложение использования > ::= uses<список имен модулей>

<список имен модулей> ::= <имя модуля>

<список имен модулей>,

<имя модуля>

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

<интерфейсная секция> ::= Interfaсe <список разделов>

Interfaceсe

< предложение использования >

<список разделов>

<список разделов> ::= <раздел >

<список разделов>;<раздел>

<раздел> ::= <раздел констант>

<раздел типов >

<раздел переменных>

<раздел заголовков>

<раздел заголовков> ::= <заголовок>

<раздел заголовков>;<заголовок>

<заголовок> ::= <заголовок процедуры>

<заголовок функции>

Описание процедур и функций в интерфейсной секции аналогично опережающему описанию (директива forwarid не указывается или игнорируется).

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

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

Синтаксис секции реализации практически во всем соответствует синтаксису раздела описаний программы , определенному стандартом языка. Заголовок секции включает зарезервированное имя Implementation и, возможно, предложение использования. Последнее относится также к уточнению конструкции <заголовок программы>, если в программе используются какие-либо модули, кроме модуля System, который подключается к программе по умолчанию.

<Секция реализации> ::= Implementation

<список разделов описаний>

Implementation

<предложение использования>

<список разделов описаний>

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

<секция инициализации> ::= end