Исследование обобщённого программирования

Материал из Вики проекта PascalABC.NET
Перейти к: навигация, поиск

Содержание

Java Generics

Особенность Java Generics — стирание типов. Обобщенный класс A<T> транслируется в обычный класс A, где везде вместо типа T используется Object. Если на параметр типа есть ограничение, например, A<T extends Comparable<T> >, то в результирующем коде вместо T стоит Comparable.

Из-за стирания типов возникает неприятное для нас ограничение: параметр шаблона не может реализовывать разные специализации одного интерфейса [*]. Что это и чем оно нам грозит?

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

Convertible<S, U>

который содержит функцию

U convert(S x)

или

U S::convert()

Можем ли мы естественным образом реализовать нечто подобное на Java? У нас ведь есть обобщённые интерфейсы, может это выход?

public interface Convertible<S> {
	public S convert();
}
 
public class A1 {}
 
public class A implements Convertible<A1> {
	public A1 convert() {
		return new A1();
	}
}

Здорово! Но мы хотим, чтобы класс A мог быть преобразован и в какой-нибудь A2.

public interface Convertible<S> {
	public S convert();
}
 
public class A1 {}
public class A2 {}
 
public class A implements Convertible<A1>, Convertible<A2> {
	public A1 convert() {
		return new A1();
	}
	public A2 convert() {
		return new A2();
	}
}

А вот это уже не работает. Причина — ограничение [*], которое даёт стирание типов. Класс A может реализовывать только какой-нибудь один Convertible.

Использование объектов-моделей

Придётся использовать наши любимые объекты-концепты в обобщенном коде и объекты-модели — в конкретном.

public interface EqualityComparable<T, S> {
	public boolean eq(T x, S y);
	public boolean neq(T x, S y);
}
 
public static <T, S> boolean contains(Collection<T> elems, S x, EqualityComparable<T, S> cmp) {
	boolean found = false;
	for (T t : elems) {
		if (cmp.eq(t, x)) {
			found = true;
			break;
		}
	}
	return found;
}
 
public class IntDoubleEqCmp implements EqualityComparable<Integer, Double> {
	public boolean eq(Integer x, Double y) {
		return x.doubleValue() == y;
	}
	public boolean neq(Integer x, Double y) {
		return !eq(x, y);
	}
}
 
public class IntCharEqCmp implements EqualityComparable<Integer, Character> {
	public boolean eq(Integer x, Character y) {
		return Character.getNumericValue(y) == x;
	}
	public boolean neq(Integer x, Character y) {
		return !eq(x, y);
	}
}
 
private static void testEqCmp() {
	ArrayList<Integer> arr = new ArrayList<Integer>();
	// ...
	IntCharEqCmp cmpIC = new IntCharEqCmp();
	//Algos.contains(arr, new Double(3.14), cmpIC);	// ERROR
	IntDoubleEqCmp cmpID = new IntDoubleEqCmp();
	Algos.contains(arr, new Double(3.14), cmpID);
}

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

  1. интерфейс не может содержать реализации методов по умолчанию, поэтому во всех моделях EqualityComparable приходится дублировать реализацию метода neq (Scala traits допускают базовую реализацию).
  2. приходится описывать реализацию модели в конкретном классе, а потом создавать объект данного класса, чтобы передать его в вызов обобщенного алгоритма. В Scala для этой цели удобно использовать объект-наследник концепта (синглтон).
  3. любой концепт, который нам требуется, приходится передавать отдельным параметром. В Scala ситуацию спасают implisits, а здесь нам может потребоваться довольно большое число объектов-моделей, что весьма громоздко.

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

public class EqualityComparableBasic<T, S> {
	public boolean eq(T x, S y) {
		return true;
	}
	public boolean neq(T x, S y) {
		return !eq(x, y);
	}
}
 
public static <T, S> boolean contains(Collection<T> elems, S x, EqualityComparableBasic<T, S> cmp) {
	boolean found = false;
	for (T t : elems) {
		if (cmp.eq(t, x)) {
			found = true;
			break;
		}
	}
	return found;
}
 
public class IntDoubleEqCmpB extends EqualityComparableBasic<Integer, Double> {
	public boolean eq(Integer x, Double y) {
		return x.doubleValue() == y;
	}
}
 
public class IntCharEqCmpB extends EqualityComparableBasic<Integer, Character> {
	public boolean eq(Integer x, Character y) {
		return Character.getNumericValue(y) == x;
	}
}

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

Вторая проблема — concept refinement. Если обобщенный класс-концепт, улучшающий некоторый концепт, описать ещё можно:

public class ComparableBasic<T, S> extends EqualityComparableBasic<T, S> {
	public int cmp(T x, S y) {
		return 0;
	}
}

то как определять модель? У класса может быть только один предок. Поэтому, если мы определяем класс-модель, который наследует наш новый ComparableBasic, придётся переопределять в нём как методы ComparableBasic, так и EqualityComparableBasic.

В случае с интерфейсами этой проблемы нет. Мы можем определить класс IntDoubleCmp — наследник IntDoubleEqCmp (реализует EqualityComparable), который реализует Comparable.

public interface Comparable<T, S> extends EqualityComparable<T, S>{
	public int cmp(T x, S y);
}
 
public class IntDoubleCmp extends IntDoubleEqCmp implements Comparable<Integer, Double> {
	public int cmp(Integer x, Double y) {
		return new Double(x.doubleValue()).compareTo(y);
	}
}

.NET generics

В NET дженерики другие, вот подходящая статья про их компиляцию: статья про компиляцию шаблонов NET на MSDN («Generics in the Run Time (C# Programming Guide)»).

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

Сами дженерики NET компилируются в код Microsoft intermediate language (MSIL), где хранится метаинформация о типовых параметрах.

В NET generics можно указать, что тип реализует несколько специализаций одного обобщенного интерфейса:

public class A : IEqComparable<A1>, IEqComparable<A2> {...

Интерфейс может содержать обобщенный метод:

public interface IEqComparableGen<T>
{
	bool eqGen<S>(S y) where S : T;
}

Можно указывать зависимости между типовыми параметрами:

public static void algo1<T, U, S>(T x, U y, S z)
	where T : IComparable<T>
	where U : T
	where S : GenType<T>
{...

Можно описывать обобщённые делегаты:

public delegate void Delegate3<T>(T x) where T : struct;

Чего нет в сравнении с концептами

  • ассоциированные типы;
  • распространение ограничений;
  • перегрузка на основе ограничений — следующее недопустимо:
public void p<S>(T x, S y) where S : class {...}
public void p<S>(T x, S y) where S : struct {...}
  • в качестве типового параметра не может выступать обобщенный тип (конструктор типа).

Полезные ссылки

Персональные инструменты