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-12 11:27 am (UTC)Код не компилируется: видны плюсистские привычки. В жабе нужно писать не .size(), а .length; и Вам уже как минимум 2 (два) человека (я и Алеф) сказали, что в жабе нельзя инстанцировать параметризованный тип, а Вы пытаетесь это сделать. К тому же Вы зачем-то заменили связанный список на массив (вероятно, это хаскельные привычки).
После устранения этих ошибок код все равно получается практически бесполезный. Во-первых, вместо 1 сишной функции объявлены 2 класса и 2 функции. Во-вторых, складывать он может только те элементы, которые унаследованы от Plus. То есть с "примитивными" типами он не работает. Надо для каждого примитивного типа и любого другого, который нам понадобится складывать, завести класс-оболочку. То есть количество копипасты получается одинаковым: вместо нескольких функций Sum программист будет копипастить оболочки. В ряде случаев можно унаследоваться от целевого класса, а если он объявлен final (как например string?) -- то придется делать аггрегацию и копипастить объявления конструкторов и прочих методов. И полученный класс нельзя будет передавать в методы, которые требуют string.
>Если смотреть из того места, где находится Haskell, то C++, Java и C# почти неразличимы.
Что думает сам Haskell-master, лучше спросить у него самого. Общее между Haskell и C++, например, то, что есть полиморфизм времени компиляции и нет принудительного ООП.
no subject
Date: 2010-02-12 11:35 am (UTC)Да, вы правы. Для идеи это, впрочем, не важно.
> код все равно получается практически бесполезный
Продакшен я вам тут писать не собираюсь.
> К тому же Вы зачем-то заменили связанный список на массив (вероятно, это хаскельные привычки).
Да пофигу, что там брать.
> Во-вторых, складывать он может только те элементы, которые унаследованы от Plus. То есть с "примитивными" типами он не работает.
Ну, оберните их. Проблем-то. И, кстати, не "унаследованы от", а "реализуют".
> То есть количество копипасты получается одинаковым: вместо нескольких функций Sum программист будет копипастить оболочки.
Отнюдь. Или вы считаете, что суммирование массива - единственное возможное приложение подобного интерфейса? Не говоря уж о том, что реальный интерфейс в продакшене будет, конечно, побольше.
> Что думает сам Haskell-master, лучше спросить у него самого.
Ну, спрашивайте, я вообще не знаю, кто это такой.
> Общее между Haskell и C++, например, то, что есть полиморфизм времени компиляции и нет принудительного ООП.
А ещё оба пишутся в виде текстовых файлов. И компилируются в код для платформы x86, да. По сравнению с этим то, что в Haskell есть все три вида полиморфизма (параметрический, статический ad-hoc и динамический ad-hoc), а в плюсах - только два ad-hoc-а, а также то, что в С++ можно работать без ООП, а в Haskell объектной системы вообще нет - это так, мелочи жизни.
no subject
Date: 2010-02-12 11:58 am (UTC)>Да пофигу, что там брать.
Как я (или другие читатели fprog) могут сравнить два языка по реализации разных алгоритмов? Сравнивать яблоки с апельсинами?
>Ну, оберните их.
Зачем я должен оборачивать их, только потому что предлагается писать на убогом языке? Сишный код работает со string без оборачивания. Его эквивалента Вы не дали.
>И, кстати, не "унаследованы от", а "реализуют".
Это синонимы, равно как "extends" и "inherits".
>Отнюдь. Или вы считаете, что суммирование массива - единственное возможное приложение подобного интерфейса?
Типов может быть много.
Например комплексные числа (можно умножать, делить, складывать и вычитать, есть операция модуля, нет операции порядка).
Есть кольцо вычетов целых чисел по модулю простого числа -- нету модуля.
Кольцо вычетов целых чисел по модулю составного числа -- нету деления.
Кольцо вычетов вещественных чисел -- складывать свободно, а умножать и делить только на целое.
Ну вот, потребуется на каждый чих вводить интерфейс и функцию. Переложить эту работу на плечи компилятора нельзя.
no subject
Date: 2010-02-12 12:04 pm (UTC)Ой, а вы считаете, что как только связный список заменили на массив - алгоритм стал резко другим, да?
> Зачем я должен оборачивать их, только потому что предлагается писать на убогом языке?
Кому предлагается?
> Сишный код работает со string без оборачивания. Его эквивалента Вы не дали.
Знаете, я думал, мы про алгоритмы говорим, а не про подобную фигню. Ну, возьмите шарп, если хотите использовать базовые типы в дженериках.
> Ну вот, потребуется на каждый чих вводить интерфейс и функцию.
Ещё раз: вы считаете, что один интерфейс будет использоваться ТОЛЬКО в одном месте?
no subject
Date: 2010-02-12 12:11 pm (UTC)>Кому предлагается?
Вы предложили мне дописать недостающие обертки к вашему коду на Java, который якобы эквивалентен сишному коду из статьи.
>Ой, а вы считаете, что как только связный список заменили на массив - алгоритм стал резко другим, да?
Да, для сортировки списков, с одной стороны, и массивов, с другой, используются совершенно разные алгоритмы.
>Ещё раз: вы считаете, что один интерфейс будет использоваться ТОЛЬКО в одном месте?
Заранее этого сказать нельзя. Очень может быть, что и в одном.
no subject
Date: 2010-02-12 12:15 pm (UTC)Я вам не предлагал писать на жабе. Я предложил, если вы ХОТИТЕ писать на Java, написать недостающие обёртки.
> Да, для сортировки списков, с одной стороны, и массивов, с другой, используются совершенно разные алгоритмы.
При чём тут сортировка вообще?
> Заранее этого сказать нельзя. Очень может быть, что и в одном.
То есть, в худшем случае мы, по вашим словам, меняем шило на мыло. Во всех остальных случаях становится лучше. В чём проблема-то?
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)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2010-02-14 03:48 am (UTC)>Знаете, я думал, мы про алгоритмы говорим, а не про подобную фигню.
Алгоритмы? А в соседнем комменте
>> Угу, так случайно получим O(N^2) вместо O(N).
>Глубоко по барабану. Речь о полиморфизме.
>Ну, возьмите шарп, если хотите использовать базовые типы в дженериках.
Чем тут шарп лучше? Можно складывать строки плюсиком, но интерфейса нет, а от string не унаследуешься -- как и в жабе, пишите обертку на три листа, Шура, пишите.
no subject
Date: 2010-02-14 09:13 am (UTC)Именно. Более конкретно - о полиморфизме. А вы считаете, он нужен для чего-то, кроме реализации алгоритмов?
> Чем тут шарп лучше?
Вы тупой? Сами же цитируете: в нём можно использовать базовые типы в дженериках.
> как и в жабе, пишите обертку на три листа
Хотя я согласен, что и шарп, и жаба весьма многословны, но ваши "три листа" - явный перебор.
no subject
Date: 2010-02-16 05:47 am (UTC)>Именно. Более конкретно - о полиморфизме. А вы считаете, он нужен для чего-то, кроме реализации алгоритмов?
Как минимум еще одно применение: для троллинга на ЛОРе.
>> как и в жабе, пишите обертку на три листа
>Хотя я согласен, что и шарп, и жаба весьма многословны, но ваши "три листа" - явный перебор.
Ну так загляните в документацию, сколько у string конструкторов и методов.
http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html
no subject
Date: 2010-02-16 07:31 am (UTC)И вам в вашей задаче нужно оборачивать просто-таки все.
no subject
Date: 2010-02-18 10:15 am (UTC)А что, я не имею права написать
char q = summ(strings).replace(s1,s2).charAt(5); ?
no subject
Date: 2010-02-14 09:51 am (UTC)no subject
Date: 2010-02-16 05:56 am (UTC)Да, правда к Java этот язык имеет такое же отношение как тезис "а если бы у бабушки были яйца".
no subject
Date: 2010-02-16 07:30 am (UTC)