Языки программирования, 28 лекция (от 14 декабря)

Материал из eSyr's wiki.

Версия от 10:55, 14 января 2013; 79.165.47.85 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

С++
Ада
С# c 2004
Java c 2005

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

Содержание

[править] п.1. Родовые модули языки Ада

Ада-83 – принцип РОРИ пронизывает весь этот язык. Получился очень мощный и одновременно эффективный механизм. Порождение нового пакета порождало новый экземпляр данного типа.

package Stack – два параметра – тип элемента размер стека:

generic
	type T is private;
size: integer;
package Stack is
	Push
	Pop
end Stack;

Можно ли так запрограммировать процедуры, чтобы они эффективно работали для любого размера стека? Конечно, да!

Конкретизация:

package IStack is new Stack(integer, 128);

Тривиальная реализация – простая макроподстановка integer и 128. Плюс – крайняя простота. Минус – очень сильное разбухание кода – сколько объявлений, столько и различных процедур. Ада-83 требовала отдельной компиляции спецификации и реализации.

Теперь представим себе другую ситуацию, например пусть у нас есть родовая процедура сортировки:

generic
	type ElType is private;
	type Index is range <>;
	type Arr is array (Index) of ElType;
	with function <(x, y : T) return Boolean (<>);
procedure G_SORT(A: in out Arr; L,R : Index);

Как написать спецификацию той же шаблонной функции на С++, считая, что уже имеется Vector <T>? Вот так:

template <class T, class Index>
void Sort(Vector <T>&V, Index L,R);

В процедуре Sort обязательно встретится нечто вроде:

if (v[i]<v[j])

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

В Аде большое разнообразие типов формальных параметров родового модуля. Формальные параметры родовых модулей:

параметр-переменная <=> любое константное выражение
type T is private <=> любой тип с операцией присваивания
type T is range <=> любой дискретный тип с упорядоченностью и функциями «следующий» и «предыдущий»
type T is delta <=> любое плавающее выражение
< > <=> при конкретизации процедуры мы можем не указывать этот вариант (параметр по умолчанию).

Пусть у нас есть:

procedure StrSort is new G_SORT(String, Integer, TARR);

C помощью < > компилятор находит функцию < для строк и подставляет как параметр по умолчанию. Родовые сегменты – абсолютно необходимая в Аде конструкция, потому что там нет передачи процедур и функций по параметру. Как по-другому реализовать функцию, скажем, вычисляющую интеграл? Мы должны передавать вещественный тип-параметр и саму подынтегральную функцию. Допустим, мы вводим новый вид чисел, например комплексный, то есть запись. Мы должны описать тип чисел как приватный и передавать как сравнение, так и всю арифметику. Хотя много всего, но зато будет одна процедура и для вещественных, и для комплексных чисел, и для кватернионов. Компилятор должен видеть не только спецификацию данной абстракции, но и тело. Гибкость повышается, но тело родовой абстракции должно быть доступно в любой момент конкретизации. За в этой жизни надо платить! Либо мы повышаем гибкость, либо производительность. В Аде-83 механизм родовых модулей – единственный, который поддерживал ОО. Как вы думаете, что самое главное, что появилось в Аде-95? Правильно, класс – тегированная запись:

type T is tagged

Какова была основная цель введения дженериков в C# и Java? Для коллекций. Если мы почитаем определение языка C#, то первый шаблон, который мы найдём, это реализация стека:

Elem Stack {}

Раньше же мы видели Object []body; Дальше приведение типа, и если мы пропускаем проверку, получим ошибку времени выполнения. В основном коллекции являются не гетерогенными, и, используя шаблоны, можно сильно увеличить производительность. Самый мощный механизм – шаблоны в С++. Почему же они более мощны и гораздо более сложны, чем в других языках?

Шаблоны в С++:
1) Функции
2) Классы

а) Параметр-класс <=> Любой тип
б) Параметр-переменная <=> Константное выражение

template <class T, int size> class Stack {...}

T – тип данных, size может быть везде, где фигурирует целая константа. Конкретизация происходит явным образом. Stack <int, 256> может появляться везде, где может появляться имя типа. После Stack <int, 256>, увидев Stack <int, 2*128>, компилятор ничего не сгенерирует, т.к. уже один раз сгенерировал. А вот Stack <int, 64> порождает новый класс, хотя в общем-то Push и Pop в этом случае делают одно и то же, что и в случае Stack <int, 256>. Но компилятор мужественно породит новый кусок кода…

Stack <int, 64> S; Вот здесь начинается генерация кода. Но в С++ у нас раздельная трансляция. Шаблоны – очень мощная вещь, но неграмотное их использование неопытным программистом ведет к разбуханию кода… Если одинаковые шаблоны сгенерированы в разных модулях, некоторые компиляторы борются с этим, используя PCH, хотя это делает трансляцию зависимой.

Для функций то же самое, но конкретизация не обязательна. Рассмотрим:

template <class T> void Sort (Vector <T>&V);

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

Представим, что у нас в программе есть:

Vector <string> X;
Sort(X);

В Sort должен явно встречаться код:

if (v[i]<v[j])

Компилятор опять же ничего проверить не может. Эта проверка происходит только в момент конкретизации. В Аде-95 и С++ ситуация одинаковая и не такая, как в Аде-83. В момент конкретизации компилятору надо дать полную информацию обо всём шаблоне, и ни о каком принципе РОРИ речи идти не может. Этим С++ не ограничивается. Пока что было очень похоже на Аду-95. Какой недостаток?

В первых версиях шаблонов в С++ было невозможно:

template <class T>
T f() {…}

В новых версиях можно:

Sort <int>(a);

Но это не всё. В С++ есть механизм частичной специализации.

[править] п.2. Шаблоны в С++

Vector <const char *>a;
Sort(a);

Будет подставлена функция < для указателей, и ошибки в программе не будет, но работать она будет неправильно.

template <class T> bool less (T& x, T& y) {
  return x<y;
}

Это описание шаблонной функции. Хорошая функция сортировки должна работать через шаблонную функцию сравнения. Но проблема со * остаётся. Что делать? А вот что.

Пишем:

template <> bool less <const char *> (const char *p1, const char *p2) {
   return strcmp(p1,p2);
}

template <> class Vector <void *>;

Подставь вместе T void * и сгенерируй код. (?)

Для векторов возможны такие реализации:

1) template <class T> class Vector {…}
2) template <> class Vector <T*>;</br>

Vector <long > V;
Vector <int> V1;

Оба по первой реализации и разные.

Vector <const char *> v2;
Vector <int *>v3;

Оба по второй и одинаковые.

Будет также эффективно, как и встроенный в язык вектор. Механизм частичной специализации очень эффективен. Физики очень не любили использовать язык С. Компиляторы с ФОРТРАНА были, как ни странно, эффективнее компиляторов с С. С-шные функции требуют слишком много проверок, пример: memcpy (проверяет перекрытие областей памяти и много-много чего прочего). С появлением шаблонов ситуация изменилась. Многие математические библиотеки, такие как Boost, Loki – это именно библиотеки шаблонов – очень производительны. Читай у Александреску про его библиотеку шаблонов Loki. У STL много недостатков, но написана она исключительно производительно в смысле эффективности.

Вспомним:

Find(It first, It last, …)

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

  • I == X (?)

Можно передавать третьим параметром compare, и вызывать но это неэффективно, так как это срывает работу конвейера. Выход – функтор. Перекрываем операцию ( ):

сlass Finder {
  public:
    bool operator ()(T&x, …) {
      …
   }
}

[править] п.3. C#, Java – обобщенные классы

У них очень простой синтаксис и похожая идея:

class Stack <T> {…}
interface IComparable <T> {…}

Параметризовать можно как классы, так и интерфейсы и методы:

public void add <T> (T x) {…}

Слово class просто синтаксически не нужно. Компилятор производит первичный синтаксический анализ и перевод в MIL/Байт-код. Конкретизация же происходит при выполнении кода. Код генерируется оптимальным образом.

В Java в качестве параметризованных типов только классы. Вместо Stack <int> S надо Stack <Integer> S

В C# на такое пойтить не могли. Там же есть структуры! Если аргумент – класс или интерфейс, код разный. Для ссылок одинаковый.

В Java: if (Stack<Integer>.getClass==Stack<String>.getClass()) даст true

В C#:

сlass Dictionary <K, V> {
}

K – тип ключа, V – тип значения.

Явно при реализации должно быть нечто вроде:

public void Add( K Key, V Value) {
  …
  if (K<K1) …
  …
}

На это будет выдана ошибка. Потому что функции < может не быть.

Надо:

if ((IComparable)K<K1)

Вместо этого можно:

class Dictionary <K, V> where K:Icomparable

Можно теперь ошибки не бояться. Возвращаемся к старой доброй Аде-83.

«Я когда-то за счет изменения нескольких функций выиграл в производительности 30%. Это, извините меня, о-го-го!»

Кстати, по поводу С++. В С++, в отличие от Ады, есть механизм подстановки параметров по умолчанию. new delete

В итоге концепция шаблонов пронизывает все современные языки. Наиболее мощная концепция в С++, но за счёт сложности можно писать очень неэффективные программы. В Java и C# достигнут между производительностью и гибкостью. На этом закончим лекцию и вместе с ней весь курс.

[править] Схема проведения экзамена по Языкам Программирования:

1) Экзамен письменный, длится одну пару

2) Можно пользоваться печатными материалами, если это не типографская продукция

3) Всего восемь задач, максимум за каждую - 6 баллов

4) when баллы>=36 => 5, when 24<=баллы<36 => 4, when 12<=M<25 => 3, default => 2

Задачи досрочного экзамена (19 декабря):

1-ый вариант.

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

Ада, Модула-2, Оберон, Оберон-2, С, С++, Java, C#

2) Объяснить, что означает оператор foreach языка C#. Какие условия накладываются на класс-коллекцию, чтобы он мог использоваться в данном операторе?

3) Объяснить все смыслы ключевого слова final в языке Java.

4) Перечислите способы передачи параметров в языках программирования. Какие из них реализованы в языках Ада-95 и Оберон?

5) Что будет выдано в стандартный канал вывода при вызове функции F()?

class X {
public:
	void g() { cout << 1 << ' '; }
	virtual void f() { g(); }
};

class Y: public X {
public:
	void g() { cout << 2 << ' ';}
	void f() { g(); }
};

class Z: public Y {
public:
	void g() { cout << 3 << ' '; }
	void f() { g(); }
};

X x; Y y; Z z; 
X *px = &x; Y *py = &y; Z *pz = &z;

void out() {
	px->f(); px->g(); py->f(); py-> g(); 
        cout << '\n';
}

void F() {

      out(); px = py;
      out(); py = pz; 
      out();
}

6) В каких из перечисленных ниже языков программирования нет перечислимого типа?

Ада, Паскаль, Модула-2, Оберон, Оберон-2, С, С++, C#

7) Написать спецификацию родового (generic) класса в языке Java, который будет реализовывать очередь. Тела методов писать не нужно.

8) В каких из перечисленных ниже языков есть возможность раздельной трансляции вложенных модулей? Привести пример на одном из таких языков.

Ада, Паскаль, Модула-2, Оберон, Оберон-2, С, С++, Java, C#


Языки Программирования


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28


Календарь

чт вт чт вт чт вт чт вт чт вт
Сентябрь
  05 07 12 14 19 21 26 28
Октябрь
  03 05 10 12 17 19 24 26 31
Ноябрь
02 14 16 21 23 28 30
Декабрь
05 07 12 14

Материалы к экзамену
Сравнение языков программирования


Эта статья является конспектом лекции.
Личные инструменты
Разделы