On Vox: Поигрался тут
Dec. 6th, 2009 04:28 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
migmitКто-то (увы, не помню кто - напомните?) не так давно предлагал вопрос для интервью соискателям: где в C++ находится параметрический полиморфизм? Правильный ответ был "в районе шаблонов". Соответственно, я бы предложил следующий вопрос: а почему шаблоны таки не являются параметрическим полиморфизмом? Правильный ответ: потому что это всего лишь макросы на стероидах. Реализация метапрограммирования. А метапрограммирование ничего не может сделать, если под ним находится слишком слабенькая система.
Вот в чём сие выражается. Я запостил на ЛОР задачку (сопроводив её кодом на Хаскеле): подсчитать скалярное произведение двух векторов, статически гарантировав, что они имеют одинаковую длину. Мне не интересно сейчас снова демонстрировать, как это делается на Хаскеле (очень просто), но даже на C# вот такой код вполне работает:
Однако, переписав этот код почти один в один на C++ (с шаблонами вместо дженериков), получаем... нерабочий код:
using System;
interface ScalarProduct<A> {
int scalarProduct(A second);
}
class Nil : ScalarProduct<Nil> {
public Nil(){}
public int scalarProduct(Nil second) {
return 0;
}
}
class Cons<A> : ScalarProduct<Cons<A>> where A : ScalarProduct<A> {
public int value;
public A tail;
public Cons(int _value, A _tail) {
value = _value;
tail = _tail;
}
public int scalarProduct(Cons<A> second){
return value * second.value + tail.scalarProduct(second.tail);
}
}
class _Test{
public static int main(int n){
return _main(n, 0, new Nil(), new Nil());
}
public static int _main<A>(int n, int i, A first, A second) where A : ScalarProduct<A> {
if (n == 0) {
return first.scalarProduct(second);
} else {
return _main(n-1, i+1, new Cons<A>(2*i+1,first), new Cons<A>(i*i, second)); // Works
//return _main(n-1, i+1, first, new Cons<A>(i*i, second)); // Doesn't work
}
}
}
public class Test{
public static void Main(){
Console.Write("Enter a number: ");
int val = Convert.ToInt32(Console.ReadLine());
Console.WriteLine(_Test.main(val));
}
}
Бесконечное развёртывание шаблонов.
#include <iostream>
template <class A> class ScalarProduct {
public:
virtual int scalarProduct(const A &second) const = 0;
};
class Nil : public ScalarProduct<Nil> {
public:
Nil(){}
virtual int scalarProduct(const Nil &second) const {
return 0;
}
};
template <class A> class Cons : public ScalarProduct<Cons<A> > {
public:
int value;
const A &tail;
Cons(int _value, const A &_tail) : value(_value), tail(_tail) {}
virtual int scalarProduct(const Cons<A> &second) const {
return value * second.value + tail.scalarProduct(second.tail);
}
};
class _Test {
public:
static int main(int n){
return _main<Nil>(n, 0, Nil(), Nil());
}
template <class A> static int _main(int n, int i, const A &first, const A &second){
if (n == 0) {
return first.scalarProduct(second);
} else {
return _main(n-1, i+1, Cons<A>(2*i+1,first), Cons<A>(i*i, second)); // Doesn't work
//return _main(n-1, i+1, Cons<Nil>(2*i+1, Nil()), Cons<Nil>(i*i, Nil())); // Works, but isn't what we want
}
}
};
int main(int argc, char* argv[]){
std::cout << "Enter a number: ";
int val;
std::cin >> val;
std::cout << _Test::main(val) << std::endl;
return 0;
}
Джавский вариант тоже, разумеется, работает.
Originally posted on migmit.vox.com
no subject
Date: 2010-02-22 10:33 am (UTC)>Да подчёркивайте сколько угодно.
Я, напротив, говорю что это одно и то же.
>>Теперь понял. Что ж, как я уже говорил - вариант жабы с реализацией интерфейсов, но без наследования был бы полезен сам по себе.
>> Ваш код не расширяется на TreeSet
>Почему, что плохо?
Потому что в описании Set заложено требование Hashable, которое не имеет смысла для TreeSet. Для TreeSet нужно Comparable (compareTo). Собственно, даже для HashSet нужно equals (т.к. хэш-коллизии неибежны) -- тоже отдельный интерфейс создавать будем?
no subject
Date: 2010-02-22 11:57 am (UTC)Не имеет значения.
> Для TreeSet нужно Comparable (compareTo). Собственно, даже для HashSet нужно equals (т.к. хэш-коллизии неибежны) -- тоже отдельный интерфейс создавать будем?
Можно, скажем, унаследовать Hashable от Eq, чтобы не писать лишнего.
Да, насчёт TreeSet хорошее замечание. Имеет смысл убрать Hashable из интерфейса Set.
no subject
Date: 2010-02-22 12:11 pm (UTC)О том, чтобы написать функцию, которая может складывать Complex с Complex лучше и не думать.
С темплэйтами ни то ни другое не является проблемой. А генерики сами по себе не дают ничего. Кстати в C++/CLI есть генерики и темплэйты. Генерики собственно в Managed C++ появились еще до темплэйтов.
no subject
Date: 2010-02-22 12:23 pm (UTC)Почему же нельзя? Вполне можно, для этого и Set заведён.
Почему же нельзя? Вполне можно, для этого и Set заведён.
<pre>
public<S extends Set<MyCoolType>> void addToSet(S set, MyCoolType item){
set.add(item);
}
</pre>
> О том, чтобы написать функцию, которая может складывать Complex с Complex лучше и не думать.
Ну, не думайте, если боитесь. Мы не боимся.
> А генерики сами по себе не дают ничего.
Они дают параметрический полиморфизм, которого без них не было. Позволяют убрать лажу с тайпкастами. Делают код безопаснее.
no subject
Date: 2010-02-25 04:48 am (UTC)У TreeSet и HashSet разные ограничения на типы, которые можно помещать в контейнер, поэтому можно выбрать что-то одно: либо иметь возможность использовать TreeSet и HashSet взаимозаменяемо, либо безопасно. И Sun правильно сделали это в библиотеке, лучше -- при таком полиформизме как в жабе, не получится.
>Ну, не думайте, если боитесь. Мы не боимся.
Ну и как же там надо написать, чтобы можно было: (Возьмите уж сишарп, если жаба настолько убога).
complex<double> sum;
complex<float> foo(int) { /*...*/ }
for(/*...*/) sum+=foo(/*...*/);
И параметром complex может быть не double и float, но и любой тип, который заранее неизвестен.
>Они дают параметрический полиморфизм, которого без них не было. Позволяют убрать лажу с тайпкастами. Делают код безопаснее.
В тривиальных случаях -- да. Но даже в TreeSet & HashSet тайпкаст остался.
no subject
Date: 2010-02-25 05:36 am (UTC)Нет. Пусть компилятор следит за правильностью использования типов, см. addToSet выше.
> Ну и как же там надо написать, чтобы можно было:
Обернуть double и float, чтобы поддерживали нужный интерфейс.
В Хаскеле и этого не потребовалось бы.
> Но даже в TreeSet & HashSet тайпкаст остался.
Потому что реализовали их без дженериков. Ни одна технология ничего не даст, если ею не пользоваться.
no subject
Date: 2010-02-25 06:42 am (UTC)Вопрос -- что надо сделать, чтобы компилятор уследил за использованием типов в этом случае?
Set<Object> s = new TreeSet<Object>();
s.add(new Object());
s.add(new Object());
Object нельзя использовать в TreeSet, т.к. он не унаследован от Comparable, а компилятор пропускает. В вашем примере с Hashable еще хуже: т.к. мы должны унаследовать TreeSet от Set, то компилятор будет требовать наследование Hashable (что бессмысленно для объектов в сбалансированном дереве).
>Обернуть double и float, чтобы поддерживали нужный интерфейс.
Вы не поняли. Складывать не complex<double>+complex<double> и complex<float>+complex<float>
а
complex<double>+complex<float>
Ну положим можно эмулировать multi-dispatch на виртуальных функциях. Но только если мы заранее знаем все типы.
>Потому что реализовали их без дженериков.
Ваша неправда. Мой пример относится к жабе 1.6 (после дженериков).
no subject
Date: 2010-02-25 06:50 am (UTC)На этом месте должно падать, если делать, как я показал.
> мы должны унаследовать TreeSet от Set, то компилятор будет требовать наследование Hashable
Я же сказал: да, из Set нужно требование Hashable убрать. И только оттуда.
> complex<double>+complex<float>
Источник невнятных багов. Не надо так делать, серьёзно.
> Ваша неправда. Мой пример относится к жабе 1.6
Моя правда. Ибо если дженерики есть в языке, это не значит, что их используют в любой библиотеке.
no subject
Date: 2010-02-26 04:51 pm (UTC)>Источник невнятных багов. Не надо так делать, серьёзно.
Обычное дело, когда сумматор/умножатель имеет более широкий тип, чем слагаемые/множители.
Или приведение float к double тоже надо запретить, как источник багов?
no subject
Date: 2010-02-26 05:36 pm (UTC)Сабтайпинг - зло.
> Или приведение float к double тоже надо запретить, как источник багов?
Если у вас много приведений float к double - вы что-то делаете не так.
Если их немного - написать в нужном месте float2double() не сложно.
Если float->double будет единственным возможным кастом - язык будет неконсистентен. Если возможных (ап-)кастов будет много - это очень плохо.
no subject
Date: 2010-03-01 06:34 am (UTC)Например, память экономлю. Да, бывают и такие программы, что массивы чисел занимают основную часть памяти.
>Если их немного - написать в нужном месте float2double() не сложно.
А если тип поменялся -- то потом убирать. Источник ошибок.
Некоторый момент с вашим TreeMap заключается еще в том, что жабий TreeMap поддерживает задание внешнего компаратора (задается в конструкторе TreeMap), который позволяет сравнивать объекты, не унаследованные от Comparable. В других языках есть аналоги. Как быть с этим?
no subject
Date: 2010-03-01 09:02 am (UTC)Ути-пути. Тогда, если сделано по уму, будет чёткая граница между местами, где хранятся флоаты, и местами, где используются даблы. И на этой границе будут находится все касты. Коих будет немного.
> А если тип поменялся -- то потом убирать. Источник ошибок.
Если неявные касты запрещены, то такие "ошибки" поймает компилятор. Что есть хорошо.
> жабий TreeMap поддерживает задание внешнего компаратора
Снова, пишу без компилятора под рукой:
interface Comparator<C> { boolean isGreater (C first, C second); } class DefComp<C extends Comparable<C>> implements Comparator<C> { public boolean isGreater (C first, C second) { return first.greater(second); } } class TreeSet<C> implements Set<C> { Comparator<C> comparator; public TreeSet(Comparator<C> _comparator) { comparator = _comparator; } public void add(C item) { ... if (comparator.isGreater(item, ...)) {...} ... } } class TreeSetFactory<C extends Comparable<C>> { public static TreeSet<C> getTreeSet() { return new TreeSet<C>(new DefComp<C>); } }no subject
Date: 2010-03-01 12:02 pm (UTC)interface Comparable<C> { boolean greater(C other); } interface Comparator<C> { boolean isGreater(C first, C second); } class DefComp<C extends Comparable<C>> implements Comparator<C> { public boolean isGreater(C first, C second) { return first.greater(second); } } interface Set<C> { void add(C item); } class TreeSet<C> implements Set<C> { Comparator<C> comparator; TreeSet(Comparator<C> _comparator) { comparator = _comparator; } public void add(C item) { if (comparator.isGreater(item, item)){ return; } else { return; } } } class TreeSetFactory{ public static <C extends Comparable<C>> TreeSet<C> getTreeSet() { return new TreeSet<C>(new DefComp<C>()); } } class TestComp implements Comparable<TestComp> { public boolean greater(TestComp other) { return true; } } class Test { void test() { TreeSet<TestComp> treeSet = TreeSetFactory.<TestComp>getTreeSet(); return; } }no subject
Date: 2010-02-25 06:56 am (UTC)interface Hashable { int hashCode(); } interface Comparable<C> { boolean greater(C other); } interface Set<C> { void add(C item); } class HashSet<C extends Hashable> implements Set<C> { public void add(C item){ return; } } class TreeSet<C extends Comparable<C>> implements Set<C> { public void add(C item) { return; } } public class Test { void test() { Set<Object> a = new TreeSet<Object>(); //здесь падает по type parameter is not within its bound } }Если закомментировать строчку с new TreeSet, то всё работает.