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-14 03:44 am (UTC)Понятно, значит те примеры, которые приводил Душкин, легко перенести с хаскеля на си++, но перенести их на жабу вы не умеете. Правильно, значит пишут в http://www.rsdn.ru/article/java/genericsinjava.xml:
В целом, generic-и в Java получились проще, чем шаблоны в С++, но обладают гораздо меньшими возможностями.
>> Заранее этого сказать нельзя. Очень может быть, что и в одном.
>То есть, в худшем случае мы, по вашим словам, меняем шило на мыло. Во всех остальных случаях становится лучше. В чём проблема-то?
Нет, это в лучшем случае мы меняем шило на мыло, а в худшем: вместо N простых функций требуется написать 1 генерик-функцию, K интерфейсов, N классов-оберток, N*K оберток методов для интерфейсов и обертки того, что наследуется от оборачиваемых классов. Кроме того, оборачиваемые типы -- разные и велик риск наделать ошибок (так, навскидку, сколько строк займет обёртка для string?). Потребление памяти при этом растёт катастрофически -- до уровня настоящего объектного языка. И что главное, генерики тут не причём: что с ними, что без них, нужно написать N*K методов-обёрток. А квадратичный рост быстрее линейного... Введение генериков выполнило ту же функцию, что и введение прототипов функций в процедурном Си: ошибки ловить стало проще, но в программе поменялся только синтаксис, а структура программ остается прежней. Это даже меньшее изменение, чем возможность использовать класс без forward-declaration (чего нет в С/С++).
no subject
Date: 2010-02-14 09:23 am (UTC)Идею перевода я вам показал.
> 1 генерик-функцию, K интерфейсов, N классов-оберток, N*K оберток методов для интерфейсов
Откуда взялось K?
> так, навскидку, сколько строк займет обёртка для string?
Зависит от стиля написания. При более-менее стандартном стиле - строчек пять, две из них - "}", правильность ещё одной контролируется статической типизацией.
> генерики тут не причём: что с ними, что без них, нужно написать N методов-обёрток.
Опять же - в худшем случае, то есть, когда интерфейс для КАЖДОГО типа используется один раз.
> Это даже меньшее изменение,
Появился параметрический полиморфизм. Это ОЧЕНЬ крупное изменение.
no subject
Date: 2010-02-16 05:54 am (UTC)>Идею перевода я вам показал.
Оно мало того, что еще и не работает, не является эквивалентом.
>> Это даже меньшее изменение,
>Появился параметрический полиморфизм. Это ОЧЕНЬ крупное изменение.
А раньше какой был полиморфизм?
HashSet m = new HashSet();
m.add(1);
m.add(2);
m.add("Hello");
System.out.println(m);
один интерфейс -- одна реализация на все типы -- или это параметрический полиморфизм, либо в вашем определении чего-то не хватает.
в любом случае, такое "крупное" изменение не привело к существенному изменению библиотек. В С++ с введение темплейтов структура библиотек изменилась очень сильно, ранние библиотеки с STL практически не имеют ничего общего.
no subject
Date: 2010-02-16 07:35 am (UTC)Не работает реализация, которую я писал без компилятора под рукой.
Какая эквивалентность имеется в виду?
> m.add(1);
Вообще неполимофная операция, работает с одним типом Object. Плюс ad-hoc-полиморфизм в виде объектной иерархии, позволяющей кастовать что угодно к Object.
> в любом случае, такое "крупное" изменение не привело к существенному изменению библиотек.
Вы хотите мне ещё раз доказать, что жаба - далеко не идеал и делали её, скажем так, не гении? Спасибо, знаю.
no subject
Date: 2010-02-18 10:13 am (UTC)Ну если бы там были простые опечатки, то это ничего. А вот как new T() заменить -- выбор нетривиальный.
А главное -- еще можно без проблем переписать без генериков, и будет работать так же.
>Какая эквивалентность имеется в виду?
Чтобы можно было использовать функцию с любым типом. Примеры на хаскале, которые привел Душкин, можно использовать с любыми типами. Приведенный дальше код С++ отличается главным образом синтаксисом, и туда тоже можно поместить в качестве аргумента списки строк или чисел. Я ему напишу с вопросом -- есть ли у него присланные читателями примеры.
>Вообще неполимофная операция, работает с одним типом Object.
Что же, в жабе совсем полиморфизма не было? А как же один из столпов ООП?
>Плюс ad-hoc-полиморфизм в виде объектной иерархии, позволяющей кастовать что угодно к Object.
Почему ad-hoc? Класс HashSet и его метод add определен один раз.
>Вы хотите мне ещё раз доказать, что жаба - далеко не идеал и делали её, скажем так, не гении? Спасибо, знаю.
Вы говорите, что в жабе есть "настоящий ПП". Может быть, объясните, какой дизайн библиотек более соответствует языку с настоящим ПП? (вы сделали одно отличие - разделить HashSet и TreeSet, но это не имеет отношения к ПП).
no subject
Date: 2010-02-18 10:49 am (UTC)Почему, было. Только функция HashSet.add неполиморфная.
> Почему ad-hoc?
Потому что наследование.
> Может быть, объясните, какой дизайн библиотек более соответствует языку с настоящим ПП? (вы сделали одно отличие - разделить HashSet и TreeSet, но это не имеет отношения к ПП).
interface Hashable { int hashCode(); } interface Set { void add(C obj); } class HashSet implements Set { void add(C obj) { ... int h = obj.hashCode(); ... } }no subject
Date: 2010-02-20 05:02 am (UTC)Почему это она не полиморфная? Она работает с объектами разного типа, используя (перегруженные через наследование) функции-методы equals, hashCode. У TreeSet.add() аргумент должен быть также унаследован от Comparable.
>> Почему ad-hoc?
>Потому что наследование.
Так и после введения генериков наследование в жабе обязательно.
В вашем примере, как компилятор (или интерпретатор) узнает, что у аргумента add есть метод hashCode?
no subject
Date: 2010-02-20 09:14 am (UTC)Выглядеть должно, конечно, так:
interface Hashable { int hashCode(); } interface Set<C implements Hashable> { void add(C obj); } class HashSet<C implements Hashable> implements Set<C> { void add(C obj) { ... int h = obj.hashCode(); ... } }А наследование обязательно именно потому, что библиотеки устаревшие. По нормальному достаточно реализации интерфейсов+дженерики.
no subject
Date: 2010-02-22 07:52 am (UTC)abstract class Moo implements Comparable {}, а реализовать методы где-нибудь в классах-потомках. И вообще разница в жабе между интерфейсами и классами эфемерная, и в ряде языков ее нет вообще -- если конечно, словом "интерфейс" не называется совсем другая сущность.
Comparable c = new Double(5);
System.out.println(c); // очевидно, Comparable неявно является потомком Object
То, что вы поменяли наследование от абстрактного класса (как оно сейчас есть в жабьем HashSet) на наследование от интерфейса, пользователь даже не заметит. А где собственно, TreeSet, вы полагаете, что он не нужен?
no subject
Date: 2010-02-22 08:38 am (UTC)Не понял эту фразу.
> Можно напиcать abstract class Moo implements Comparable {}, а реализовать методы где-нибудь в классах-потомках.
Можно, но не надо.
> И вообще разница в жабе между интерфейсами и классами эфемерная
Что не говорит в пользу жабы.
> То, что вы поменяли наследование от абстрактного класса (как оно сейчас есть в жабьем HashSet) на наследование от интерфейса, пользователь даже не заметит.
Пользователь заметит, что тип множества теперь несёт информацию о типе содержимого (как и должно быть). В частности, операция извлечения объекта из множества становится совершенно безопасной.
> А где собственно, TreeSet, вы полагаете, что он не нужен?
Почему вы так решили?
no subject
Date: 2010-02-22 10:19 am (UTC)>Не понял эту фразу.
В жабе интерфейс -- особый тип класса, введенный для устранения некоторых проблем множественного наследования. Когда пишем "Moo implements Comparable" -- унаследовались, когда определили тело "compareTo" -- реализовали. Если нету наследования (нельзя тайпкастить Moo к Comparable), то и интерфейс является нереализованным несмотря на наличие/отсутствие там compareTo.
>> И вообще разница в жабе между интерфейсами и классами эфемерная
>Что не говорит в пользу жабы.
Это говорит о том, что подчеркивание разницы в жабе между implements и extends является лексическим онанизмом.
>Пользователь заметит, что тип множества теперь несёт информацию о типе содержимого (как и должно быть). В частности, операция извлечения объекта из множества становится совершенно безопасной.
В некотором роде это уже пять лет как существует в жабе, если не рассматривать legacy code опять же.
>> А где собственно, TreeSet, вы полагаете, что он не нужен?
>Почему вы так решили?
Ваш код не расширяется на TreeSet, какого-то вида полиморфизма не хватает. Возможно, это легко делается в хаскеле, но в жабе явно проблемы.
no subject
Date: 2010-02-22 10:22 am (UTC)> Это говорит о том, что подчеркивание разницы в жабе между implements и extends является лексическим онанизмом.
Да подчёркивайте сколько угодно.
> В некотором роде это уже пять лет как существует в жабе
В каком роде?
> Ваш код не расширяется на TreeSet
Почему, что плохо?
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)
From: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, то всё работает.