Implementation

TYPE TStack= RECORD Elem: ARRAY[1..CMaxL] OF UVal.TVal;

Top: 0..CMaxL END;

VAR Stack: TStack;

FUNCTION Empty:BOOLEAN; BEGIN Empty:=(Stack.Top=0) END;

PROCEDURE Push(xPrm:UVal.TVal); BEGIN

IF Stack.Top=CMaxL THEN {переполнение} ErrStack:=-1

ELSE BEGIN Stack.Top:=Stack.Top+1;

Stack.Elem[Stack.Top]:=xPrm END END;

PROCEDURE Pop; BEGIN

IF Stack.Top=0 THEN {недопустима} ErrStack:=-2

ELSE Stack.Top:=Stack.Top-1 END;

FUNCTION Top:UVal.TVal; BEGIN

IF Stack.Top=0 THEN {недопустима} ErrStack:=-2

ELSE Top:=Stack.Elem[Stack.Top] END;

PROCEDURE WriteAll; VAR i:INTEGER; BEGIN

FOR i:=1 TO Stack.Top DO WriteElement(Stack.Elem[i])

END;

INITIALIZATION

{Создать пустой стек} Stack.Top:=0; ErrStack:=0

END.

Рассмотрим задачу (использование модуля).

Инфиксная (EZE), префиксная ZEE и постфиксная EEZ записи арифметических выражений, где E - переменная, символ ’a’..’z’ или выражение (в соответствующей записи); Z - знак операции ’+’,’-’,’*’,’/’.

Преобразовать: правильную инфиксную  постфиксную.

(a-(b*(c+(d/e))))  abcde/+*-

((((e/d)+c)*b)-a)  ed/c+b*a-

((a-(b*(c+(d/e))))/((((e/d)+c)*b)-a))abcde/+*-ed/c+b*a-/

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

• задерживать передачу «операций» на выход;

• вспоминать подпоследовательности «операций» в обратном порядке и выталкивать на выход их элементы тоже в обратном порядке.

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

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

• конкретика нашей задачи состоит лишь в управлении процессом «когда запоминать, а когда вспоминать».

program InfixToPostfix;uses UVal, UStack;

VAR Vh,Vih: FILE OF CHAR; x,y: CHAR;

begin RESET(Vh); REWRITE(Vih);

WHILE NOT EOF(Vh) DO BEGIN READ(Vh,x);

CASE x OF

'(': ;

'+','-','*','/': UStack.Push(x);

')': BEGIN y:=UStack.Top; WRITE(Vih,y); UStack.Pop END;

ELSE {'a'..'z'} WRITE(Vih,x);

END END; CloseFile(Vh); CloseFile(Vih) end.

PROGRAM\PRG3A\Project1.dpr

Теперь вернемся к понятию «модуль» и уточним семантику этого понятия.

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

• Модуль вводит в употребление новые средства программирования - механизм инкапсуляции. Инкапсуляция (encapsulation)– «скрытие», защита от внешнего воздействия: извне модуля доступны данные и операции, определенные в модуле (локальные???!!!), но только те, которые объявлены в интерфейсной секции (как видимые). Понятие инкапсуляция вносит существенно новое в дилемму локальные - глобальные.

• Интерфейсные инструменты - описанные в интерфейсной секции:

• интерфейсный тип данных – TVal (в модуле UVal);

• интерфейсная переменная – ErrStack;

• интерфейсные процедуры и функции – Empty, Push, Pop, Top, WriteAll.

Интерфейсные инструменты используются для организации информационной и операционной связи с модулем.

• Инкапсулированные инструменты - описанные в секции реализации:

• инкапсулированные типы данных – TStack;

• инкапсулированные переменные - Stack;

• реализация тел интерфейсных процедур и функций – тоже инкапсулирована.

Инкапсулированные инструменты «скрыты в капсуле», вне модуля на них невозможно ссылаться по их именам. Однако, не являясь глобальными, они не являются и локальными инструментами модуля. Из смысла программы InfixToPostfix ясно, что инкапсулированная в модуле UStack переменная Stack «живет» в течение всего периода выполнения программы InfixToPostfix. Она «непрерывно хранит» элементы стека и положение «его вершины», ее значение изменяется в процессе работы программы со стеком. Манипулировать стеком (переменнной Stack) программа InfixToPostfix может только косвенно с помощью («рук-манипуляторов») Push, Pop.

Кстати, традиционной локальной переменной является i:INTEGER (в процедуре WriteAll). А глобальных для всей многомодульной программы переменных не может быть. Переменные Vh,Vih,x,y можно было бы использовать как глобальные, но только процедурами и функциями в пределах головного модуля InfixToPostfix, вне него они не видны.

• Возможно, используя отмеченные выше инкапсулированные инструменты, некоторые действия в программе InfixToPostfix можно было бы реализовать и эффективнее, чем это сделано в примере, однако

• Инкапсуляция защищает модуль от некорректного внешнего вмешательства в функционирование его инструментов.

• Оборотная сторона защищённости инструментов модуля - независимость программы решения задачи от способа реализации использованных инструментов.

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

Оформление модуля в C/C++.

Для понятия «модуль» в С/С++ нет специальной синтаксической конструкции языка. Но это ни в коей мере не означает, что это понятие не играет важнейшей роли в методологии, методике и практике программирования на С/С++ ^(*):

• Многомодульная программа (проект) оформляется в С/С++ как набор программных файлов.

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

• Для оформления межмодульных связей и защиты инструментов используются средства управления областью видимости и периодом жизни инструментов.

Область видимости и период жизни.

• В одномодульном программировании организация связи между инструментами решения задач базируется на понятии «локальные-глобальные», а для оформления этого понятия используется принцип вложенности программных компонентов:

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

• в С/С++ - возможности вложенного использования оператора блок.

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

Что-то новое появляется в дилемме локальные – глобальные, когда базовое понятие «переменная» расширяется понятием «динамическая переменная», потому как динамические переменные не описываются, а явно создаются и уничтожаются в периоде выполнения программ.

Отметим, что понятие «локальные-глобальные» относительное – локальное для данного программного компонента является глобальным для вложенного в него программного компонента, с другой стороны – каждое глобальное для программного компонента должно быть локализовано в одном из объемлющих его. В программе обычно имеются максимальноглобальные инструменты, локализованные на самом верхнем уровне вложенности, т.е. объявленные вне процедур-функций. Отметим, что сами функции в С/С++ всегда максимальноглобальны.

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

• В многомодульном программировании ситуация усложняется в связи с тем, что:

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

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

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

• Организация межмодульной связи.

Для оформления связей и защиты инструментов модуля в C/C++ используются средства управления областью видимости и периодом жизни инструментов:

• модификаторы класса памяти: static, extern – ключевые слова ставятся в начале объявления переменной или заголовка описания функции;

• прототип функции: заголовок её описания.

Теперь рассмотрим оформление инкапсулированных и интерфейсных инструментов и импорта инструментов. В таблице 2 на следующей странице систематизировано соотношение этих понятий, их областей видимости и периодов жизни, а также способов оформления импорта-экспорта в Object Pascal 2 (OP2) и С/С++.

	Для данного программного компонента: процедуры или функции – в Pascal, блока - в C/C++
	Инструмент – локальный для этого программного компонента	Инструмент - глобальный (нелокальный) для этого программного компонента
		Относительно глобальный	Максимально глобальный
Область видимости	Этот программный компонент (в котором объявлен этот инструмент).	Тот объемлющий программный компонент, в котором этот инструмент локализован.	Вся программа, точнее: program-модуль (или unit-модуль) в Pascal, программный файл в C/C++
Период жизни	Период выполнения этого программного компонента (в котором объявлен этот инструмент), т.е. период выполнения вызова функции или оператора процедуры – в Pascal, блока - в C/C++	Период выполнения того объемлющего программного компонента, в котором этот инструмент локализован.	Период выполнения всей программы. Замечание: если головной модуль программы импортировал инструменты модуля, то этот модуль остаётся в «живом» состоянии весь период выполнения головного модуля программы.

Таблица 1. Организация внутримодульной связи, область видимости и период жизни инструмента.

		Интерфейсные инструменты	Инкапсулированные инструменты	Локальные static-переменные
Импорт  Экпорт	OP2	uses  interface	невозможно  implementation
	C/C++	extern  максимальноглобальный	невозможно  static максимальноглобальный	static ОбъявлениеПеременной
Область видимости		Определяющий (экпортирующий) и импортировавший модули	Определяющий модуль	Блок, в котором эта переменная объявлена
Период жизни		Период выполнения всей многомодульной программы

Таблица 2. Организация межмодульной связи, область видимости и период жизни инструмента.