Коллизии идентификаторов.

В большинстве случаев не требуется дополнительных определений, чтобы использовать программное исчисление с процедурами с параметрами в CF Pascal. Локальные переменные появляются внутри < блока>, текст которого присоединяется как значение к идентификатору процедуры в состоянии выполнения. Значение процедурного оператора получается из значения идентификатора применением бокс-функции к тексту процедуры. Локальные переменные через функцию VAR … помещаются в состояние выполнения и удаляются с помощью функции VAR …^T аналогично переменным, объявленным в главном блоке.

Рассмотрим для примера программу.

PROGRAM NoCon(INPUT, OUTPUT);

VAR

Global: CHAR;

PROCEDURE HasLocal;

VAR

Local: CHAR;

BEGIN {HasLocal}

Local: = ‘L’

END; {HasLocal}

BEGIN {NoCon}

Global: = ‘G’;

HasLocal

END. {NoCon}

Состояние выполнения перед выполнением процедурного оператора будет

s = {INPUT ·< x, ††, R>, OUTPUT ·< ††, ††, W>, Global·G}

где x – входная строка

Значение процедурного оператора HasLocal для состояния S:

HasLocal (S) = S(HasLocal) (S) = VAR Local: CHAR; BEGIN Local: = ‘L’ END (S)

= VAR Local: CHAR; ^T(Local: = ‘L’(VAR Local: CHAR; (S)))

= VAR Local: CHAR; ^T(Local: = ‘L’({INPUT·< x, ††, R>, OUTPUT·< ††, ††, W>, Global·G, Local·? }))

= VAR Local: CHAR; ^T({INPUT·< x, ††, R>, OUTPUT·< ††, ††, W>, Global·G, Local·L})

= {INPUT·< x, ††, R>, OUTPUT·< ††, ††, W>, Global·G }

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

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

PROGRAM Confuse(INPUT, OUTPUT);

VAR

MixedUp: CHAR;

PROCEDURE HasLocal;

VAR

MixedUp: CHAR;

BEGIN {HasLocal}

MixedUp: = ‘L’

END; {HasLocal}

BEGIN {Confuse}

MixedUp: = ‘G’;

HasLocal

END. {Confuse}

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

< MixedUp·G>

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

И должна быть добавлена пара

< MixedUp·L>

для локальной переменной.

Имеем смешение идентификаторов, которые должны храниться отдельно.

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

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

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

Формальное определение функции частного значения процедурного оператора для объявления

PROCEDURE P (VAR X: CHAR); VAR Z: CHAR; BEGIN … END

будет

P (Y) (s) = s (P) _{X< -Y, Z< -Z’} (s)

где Z Î domain(s), a Z’ – новый идентификатор

Для примера выше, используя схему добавления символа N для создания нового идентификатора, получим

HasLocal(S) = S(HasLocal) (S) = VAR MixedUpN: CHAR; BEGIN MixedUpN: = ‘L’ END (S)

и здесь все работает так, как должно быть.

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

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

PROGRAM WhichWhich (INPUT, OUTPUT);

VAR

Which: CHAR;

PROCEDURE Zap

BEGIN {Zap}

Which: = ‘Z’ {Прибъем ее, пока не известно, какую именно? }

END; {Zap}

PROCEDURE Invoke

VAR

Which: CHAR;

BEGIN {Invoke}

Which: = ‘B’;

Zap;

WRITE(Which)

END; {Invoke}

BEGIN {WhichWhich}

Which: = ‘A’;

Invoke;

WRITELN (Which)

END. {WhichWhich}

Здесь ясно, какие переменные используются в выражениях WRITE: локальная переменная, объявленная в Invoke, используется в операторе WRITE и глобальная в WRITELN. Однако, между присвоения и операторами WRITE одна из переменных оказывается прибита (Zapped). Если прибивается локальная переменная, тогда значение программы будет функцией с постоянным значением

W = < †ZA†>

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

W = < †BZ†>

В трудных случаях, таких как этот, существует способ определить значение без вычисления функции значения программы. Представим, что мы изменили описанным выше способом один из идентификаторов Which. Если меняется локальный, программа продолжает оставаться синтаксически корректной и ее OUTPUT будет †BZ†. Если меняется глобальный идентификатор Which, программа не будет синтаксически корректной, поскольку в Zap будет использоваться необъявленная переменная Which. Следовательно, в Zap используется глобальная переменная Which, которая «прибивается» в нашем случае.

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

S = {INPUT ·< x, ††, R>, OUTPUT ·< ††, ††, W>, Which·A}, которое существует при вызове процедуры Invoke

Invoke (S) = S(Invoke) (S) = VAR WhichN: CHAR; BEGIN WhichN: = ‘B’; … END (S)

= VAR WhichN: CHAR^T (BEGIN WhichN: = ‘B’; … END (VAR WhichN: CHAR (S)))

= VAR WhichN: CHAR^T (BEGIN WhichN: = ‘B’; … END

({INPUT ·< x, ††, R>, OUTPUT ·< ††, ††, W>, Which·A, WhichN·? }))

= VAR WhichN: CHAR^T (WhichN: = ‘B’; Zap; WRITE(WhichN)

({INPUT ·< x, ††, R>, OUTPUT ·< ††, ††, W>, Which·A, WhichN·? }))

= VAR WhichN: CHAR^T (Zap; WRITE(WhichN)

({INPUT ·< x, ††, R>, OUTPUT ·< ††, ††, W>, Which·A, WhichN·B}))

= VAR WhichN: CHAR^T (WRITE(WhichN)

({INPUT ·< x, ††, R>, OUTPUT ·< ††, ††, W>, Which·Z, WhichN·B}))

= VAR WhichN: CHAR^T ({INPUT ·< x, ††, R>, OUTPUT ·< †B†, ††, W>, Which·Z, WhichN·B})

={INPUT ·< x, ††, R>, OUTPUT ·< †B†, ††, W>, Which·Z}

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

W = < †BZ†>

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