Лекция 17 (лекции (2002))

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

При статической параметризации параметрами могут являться:

• объекты данных.

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

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

Статическая параметризация должна обеспечить надежность. Механизм статической параметризации есть только в двух языках, причем не самых современных. Языки, которые появились в последнее время (Delphi, C#, Java) не используют механизм статической параметризации. Основная проблема, по-видимому, связана со сложностью реализации соответствующих понятий. Скажем, в С++ до сих пор большинство компиляторов не соответствуют принятому стандарту языка С++. Причина этого несоответствия – это прежде всего механизм шаблонов. Это самый сложный с точки зрения реализации механизм языка С++. Даже такая известная фирма как Microsoft, которая уже больше 10 лет выпускает соответствующий компилятор С++, постоянно его модифицируя, признает, что их нынешний компилятор (так называемый Visual C++ 7), не смотря на то, что его согласованность со стандартом лучше, полной согласованности со стандартом не имеет.

Механизмы статической параметризации в С++ и в Аде различны. С концептуальной точки в языке Ада статическая параметризация проще.

Ада.

Механизм статической параметризации в языке Ада носит название родовые сегменты. Объектами статической параметризации в Аде являются пакеты и подпрограммы. Синтаксис достаточно простой

generic

[описание аргументов]

спецификация сегмента

generic - ключевое слово.

Простейший пример: стек, реализованный с помощью массива. Соответствующие функции push, pop и т.д. При выполнении операции pop будет происходить что-то вроде

X:= body(top);

top := top-1;

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

generic

package Stack is

procedure Push(X: in T);

procedure Pop(X: out T);

…

end Stack;

Параметров нет. Конкретизация (мы хотим создать новый пакет):

package Stack1 is

new Stack;

Поскольку параметров нет, то никакие фактические параметры тут не передаются. Мы объявили новый пакет Stack1, к которому применимы операции Push, Pop и т.д. Можно написать также

package Stack2 is

new Stack;

Все имена, которые описаны в соответствующей интерфейсной части становятся доступны. Теперь можно написать следующее:

X: T;

Stack1.Pop(X);

Stack2.Push(X);

Здесь мы пользуемся тем, что Stack1, Stack2 – имена конкретных модулей, и мы можем обращаться к именам процедур таким образом. Один пакет внутри себя как бы инкапсулирует одну переменную типа Stack. Заводя новый объект через новую конкретизацию, мы как бы заводим новую переменную этого типа. Обращение к функциям этой переменной выглядит очень похоже на обращение в классических объектно-ориентированных языках программирования. Таким образом, с помощью механизма родовых сегментов, получаем некоторый абстрактный тип данных. Присваивать и сравнивать эти переменные нельзя.

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

generic

type T is private;

size: integer;

package Stack is

Push

Pop

end Stack;

Запись type T is private говорит о том, что в качестве фактического параметра здесь при конкретизации может стоять любой тип данных, для которого определена операция присваивания. Соответствующий тип данных не обязан быть описан как приватный в какой-то другой спецификации. Например это может быть integer. Также мы параметризуем стек объектом данных size. Это размер стека. Теперь конкретизации пакета будут порождать не просто переменные одного типа Stack, а переменные, которые хранят в себе объекты разных типов (каждый стек хранит в себе объекты только одного типа). Конкретизации:

package Int_Stack is new Stack(integer, 256);

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

package Char_Stack is new Stack(Character, 1024);

Теперь мы можем работать аналогично

Int_Stack.Push(1);

Char_Stack.Pop(с);

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

Напишем функцию, которая осуществляет сортировку массива. Прототип функции

procedure Sort(A: in out Arr);

Sort – обычная процедура с динамической параметризацией. Проблема в параметре А. В Аде есть понятие неограниченного массива, поэтому максимум, что мы можем параметризовать в данном случае, это его размер. Arr будет где-то описан так

type Arr is array(INDEX range < >) of T;

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

Требования к механизму родовых сегментов:

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

2. РОРИ – Разделение Определения, Реализации, Использования. Принцип, который проходит через весь язык Ада. Здесь это достигнуто. Для родовых сегментов отдельно объявляется спецификация пакета (т.е. определение), отдельно – тело пакета, которое выглядит так же, как обычное тело пакета, отдельно использование (использование в данном случае – это конкретизация).

3. Раздельная трансляция. Общее требование для родовых сегментов в языке Ада, чтобы они с точки зрения использования ничем не отличались от обычных, неродовых сегментов (принцип РОРИ и раздельная трансляция). В языке Ада можно отдельно написать спецификацию пакета, оттранслировать ее отдельно, отдельно написать тело пакета. Модули, которые использует (т.е. конкретизируют) этот пакет тоже можно транслировать отдельно. Проблема возникает, если, например, у нас есть модуль - клиент, он использует модуль - сервер. Модуль – сервер содержит спецификацию пакета и реализацию пакета (его тело). Использовать пакет можно только при наличии спецификации пакета. Т.е. вся информация, которая необходима компилятору, чтобы выполнить все статические проверки и далее, в лучшем случае, сгенерировать код, находится в спецификации пакета. Это требование оказывается довольно жестким. Механизм конкретизации (клиентский модуль будет содержать, например, is new Stack(…);) должен работать, даже если мы ничего не знаем о теле пакета. Вся информация должна быть сосредоточена в спецификации пакета. При односторонней связи серверный модуль никак не зависит от клиентского модуля. Клиентский модуль о теле пакета вообще ничего не должен знать. Иначе говоря, получается, что контекст конкретизации никак не зависит от контекста реализации (контекста, где определена соответствующая абстракция). Мы конкретизируем родовую процедуру Sort. Компилятор должен оттранслировать тело в данном случае не пакета, а родовой функции Sort независимо от специализации. Компилятор, чтобы один раз оттранслировать тело функции Sort должен знать, что тип данных Т. Если Т – это элемент массива, при сортировке над ним выполняются операции присваивания (все алгоритмы сортировки основаны на том, что алгоритм переставляет) (type is private означает, что над типом определена операция присваивания), сравнения. Чтобы компилятор смог оттранслировать тело пакета, не зная контекста конкретизации, ему нужно передавать явно еще операцию сравнения. Параметры: тип, операция сравнения, сам массив Arr, INDEX. Чтобы транслятор не зависел от контекста конкретизации необходимо передавать 4 параметра. Для операции сортировки необходимо писать следующую абстракцию

generic

type T is private;

type INDEX is range < >;

type Arr is array(INDEX range < >) of T;

with function "<"(A, B: T) return Boolean;

procedure G_SORT(A: in out Arr);

Для стека хватало только type T is private потому, что для того, чтобы сформировать стек нужна только операция присваивания. Для типа INDEX не достаточно написать

type INDEX is private;

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

type INDEX is range < >;

Фактическим аргументом может быть любой дискретный тип данных. Заголовок функции остался прежним. Но кроме этого есть еще 4 параметра. Сортировка – достаточно простой пример. В случае более сложных алгоритмов, мы должны проанализировать какие операции над соответствующими типами данных потребуются для реализации. Получается, что проектируя интерфейс мы сразу должны думать о реализации соответствующей абстракции (т.е. мы заранее должны понимать как мы будем ее реализовывать). Это самая неприятная особенность языка Ада с этой точки зрения. В данном случае у нас будет

procedure Sort1 is

new G_SORT(integer,

integer,

IntArr,

"<");

IntArr должен быть описан где-то выше следующим образом

type IntArr is array(range < >) of integer;

Писать и продумывать нужно достаточно много. В качестве крайнего примера родовой процедуры можно привести функцию MAPLISTS из книги Джехани (это одна из лучших книг о языке Ада 83).Это функция типа функции map в языке LISP. Она берет список и применяет некоторую другую процедуру к каждому элементу, порождая в результате новый список. Для такой достаточно простой операции требуется 8 параметров. Только одним из параметров будет та функция, которую нужно поэлементно применять к списку. Сначала пишется реализация, а потом уже интерфейс с этими 8 параметрами. Тут перевертывается с ног на голову стиль программирования. Т.е. не смотря на то, что механизм добился всех своих целей (он надежен, удовлетворяет правилам, которым удовлетворяют неродовые сегменты), в самом механизме не хватает некоторой концептуальной целостности. Поэтому, например, есть 6 видов соответствующих формальных параметров:

1. Типы.

type T is private;

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

1. Дискретные типы.

type Ind is range < >;

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

1. Плавающие типы. К тикам типам данных можно применять арифметические операции. У них можно параметризовать только точность. Формальный параметр описывается в виде

type T is digits < >

Фактическим параметром может быть любой плавающий тип данных (т.е. тип данных, который конкретизированн количеством цифр).

1. Фиксированные типы данных.

type T is delta < >;