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 07:09 am (UTC)http://msdn.microsoft.com/en-us/library/c6cyy67b(VS.80).aspx
Ну давайте почитаем различия между ними. Первое:
C# generics do not provide the same amount of flexibility as C++ templates.
Дальше идут пять (5) пунктов, начинающихся с C# does not
И еще
At the implementation level, the primary difference is that C# generic type substitutions are performed at runtime
У темплэйтов C++ есть куча недостатков, только они не оказались достаточно значимыми, чтобы быть упомянутыми в статье из MSDN. То, что генерики C# интстанцируются в рантайме -- это круто, но mixed blessing... Это значит, что на очень большом числе архитектур генерики C# работать не будут вообще.
>Может быть, вы мне объясните, с помощью какой магии можно вводить полиморфные типы, если типов нет?
Если типов нет в языке, это не значит, что их нет вообще. Главное, чтобы функция имела общий интерфейс к полиморфному типу, с которым она работает, -- если интерфейса нет, то действительно необходима магия, или хотя бы ЛИСП. Интерфейс может быть любым. Например, qsort из Си может сортировать данные любых типов благодаря указателю на функцию.
В Java генерики не работают с "примитивными" типами. Все остальные типы в Java -- это всегда указатель на объект, в терминах Си -- void * (реже void **). В каждом объекте по фиксированному смещению лежит указатель на дескриптор класса. В дескрипторе класса по фиксированному смещению лежит указатель на таблицу виртуальных функций реализаций (с интерфейсами сложнее, т.к. для них есть множественное наследование). Кстати, конструкторов в этой таблице нет и поэтому нельзя вызвать конструктор для параметризованного типа. Поскольку JIT'ы никогда не хранят скомпилированный код на диске, а только статистики выполнения, проблемы бинарной несовместимости не возникает. Таким образом, генерик-функция работает фактически с одним типом -- void * с пришпиленными таблицами , по которым процессор может найти нужные ООП функции. Это в первом приближении, а во втором JIT-компилятор может создать сколько угодно экземпляров генерик-функции с заинлайненными вызовами и это поведение контролировать на уровне исходного кода нельзя. Следствие -- что генерики в Java бесполезны без ООП. Другое следствие -- если бы не было общего предка (Object), то ситуация была гораздо хуже. В C# "примитивные" типы при подстановке в генерик подвергаются автобоксингу -- и дальше действует схема, похожая на вышеописанную, но с существенными отличиями. Инстанцирование в C# необходимо, т.к. там могут быть значимые типы (которые не являются void*) и таким образом, функция действительно должна работать с другими объектами.
>В любом случае, это неправда - пример приведён.
Имеющий практического смысла меньше, чем ray-tracer в compile-time.
>Вы спросили про продакшен. Мне лично представляется, что продакшен-код в подавляющем большинстве случаев содержит ОЧЕНЬ много строк.
Особенно если это индусский или китайский код.
Как надо: запускаем Maple или если ее нет, идем на http://www.wolframalpha.com/input/
вбиваем sum(i=0..n-1,(2*i+1)*i*i)
После чего пишем в код обширный комментарий, проверку и строку, которая вычисляет нужное за O(1)
if(n<0) throw чего-то там;
return (n-1)*n*(3*n*n-n-1)/6;
если не будет хватать диапазона значений, легко будет изменить одну строку, а не раскиданные по всему коду.
no subject
Date: 2010-02-12 08:57 am (UTC)Ещё раз:
>> по приведённой вами ссылке указаны НЕКОТОРЫЕ (но не все) отличия темплейтов от дженериков.
Поэтому этой статьёй можете хоть обчитаться.
> Это значит, что на очень большом числе архитектур генерики C# работать не будут вообще.
Гм. Учитывая, что C# работает на, по сути, ОДНОЙ архитектуре (.NET)...
> Если типов нет в языке, это не значит, что их нет вообще.
И откуда тогда В ЯЗЫКЕ возьмутся полиморфные типы?
> Кстати, конструкторов в этой таблице нет и поэтому нельзя вызвать конструктор для параметризованного типа.
В шарпе можно.
> Таким образом, генерик-функция работает фактически с одним типом -- void * с пришпиленными таблицами , по которым процессор может найти нужные ООП функции.
Это всё - исключительно детали реализации, которые никого не ебут. Вопрос не в том, что там происходит в бинарнике, вопрос в том, какие возможности у ЯЗЫКА.
> Следствие -- что генерики в Java бесполезны без ООП.
Что вы разумеете под "ООП", в данном случае? На самом деле, я полагаю, что жаба без наследования (но с реализацией интерфейсов) и с дженериками была бы весьма полезной штукой.
> Имеющий практического смысла меньше, чем ray-tracer в compile-time.
А вы что хотели от примера?
>> Вы спросили про продакшен. Мне лично представляется, что продакшен-код в подавляющем большинстве случаев содержит ОЧЕНЬ много строк.
> Особенно если это индусский или китайский код.
Может быть, покажете продакшен-код, умещающийся в один ЖЖ-шный постинг?
> вбиваем sum(i=0..n-1,(2*i+1)*i*i)
> После чего пишем в код обширный комментарий, проверку и строку, которая вычисляет нужное за O(1)
> if(n<0) throw чего-то там;
> return (n-1)*n*(3*n*n-n-1)/6;
Вы, надеюсь, понимаете, что мне не составит абсолютно никакого труда заполнять массив не заранее известными числами, а вводимыми пользователем? И будет при этом то же самое.
no subject
Date: 2010-02-12 11:46 am (UTC)Ссылку в MSDN, где приведены ВСЕ различия, не подскажете?
>Гм. Учитывая, что C# работает на, по сути, ОДНОЙ архитектуре (.NET)...
Вы правы.
>И откуда тогда В ЯЗЫКЕ возьмутся полиморфные типы?
Вам шашечки или ехать? Меня больше интересуют ПРОГРАММЫ, а не языки.
>Это всё - исключительно детали реализации, которые никого не ебут.
Тем не менее Душкина и Вас почему-то занимает вопрос, как обрататывает исходный код компилятор C++. Про кодогенератор GHC почему-то ни слова, Алеф негодует.
>Может быть, покажете продакшен-код, умещающийся в один ЖЖ-шный постинг?
На коммент ограничение 4 тысячи символов, на пост еще больше. Вы хотите сказать что в продашкн коде не бывает модулей менее 4 кб ?
>Что вы разумеете под "ООП", в данном случае? На самом деле, я полагаю, что жаба без наследования (но с реализацией интерфейсов) и с дженериками была бы весьма полезной штукой.
Я читал интервью одного из разработчиков Java, что он так бы и сделал (ссылку, к сожалению, не могу найти). Только вот, между наследованием от интерфейса и наследованием от абстрактного класса семантически нет никакой разницы. ООП = все, что использует виртуальные функции или эквивалент. Страуструп сказал в 80-х: "вам не нужен С++, если вы не используете виртуальные функции". К настоящим объектным языкам я этот критерий не отношу.
>Вы, надеюсь, понимаете, что мне не составит абсолютно никакого труда заполнять массив не заранее известными числами,
Вот ТАМ у Вас как раз не массив, а связный список. Опять путаете.
>а вводимыми пользователем? И будет при этом то же самое.
На хаскеле, с инкапсуляцией ввода в монады?
no subject
Date: 2010-02-12 11:55 am (UTC)Нет, не подскажу.
> Вам шашечки или ехать? Меня больше интересуют ПРОГРАММЫ, а не языки.
Тогда какого хрена вы разговариваете о возможностях ЯЗЫКОВ?
> Тем не менее Душкина и Вас почему-то занимает вопрос, как обрататывает исходный код компилятор C++.
Не занимало бы, если бы не отражалось на возможностях языка.
> На коммент ограничение 4 тысячи символов, на пост еще больше. Вы хотите сказать что в продашкн коде не бывает модулей менее 4 кб ?
Бывают, конечно. Так почему вы так испугались, когда я сказал, что продакшен-код будет больше?
> Я читал интервью одного из разработчиков Java, что он так бы и сделал (ссылку, к сожалению, не могу найти).
Интересно, не знал.
> Только вот, между наследованием от интерфейса и наследованием от абстрактного класса семантически нет никакой разницы.
Да. Если хотите, чтобы я сказал "оставьте наследование только от (полностью) абстрактных классов" - пожалуйста. Правда, тогда проще будет, если обозвать их "интерфейсами".
> Вот ТАМ у Вас как раз не массив, а связный список.
Глубоко по барабану.
> На хаскеле, с инкапсуляцией ввода в монады?
Могу и на хаскеле, да. Так уж получилось, знаете, что интерфейс ввода-вывода в хаскеле монадический.
А могу на жабе, или на шарпе.
no subject
Date: 2010-02-12 12:07 pm (UTC)По возможностям для написания программ, которые на них пишут. Если в языке чего-то нет, но можно сделать так, что получается практически так же, как если бы это было встроено в язык, то это хороший язык.
>> Вот ТАМ у Вас как раз не массив, а связный список.
>Глубоко по барабану.
Угу, так случайно получим O(N^2) вместо O(N). Медленно работает? Босс, докупите серверов. Ой, правда язык распаралелливать не умеет. Но нам пофиг.
>> На хаскеле, с инкапсуляцией ввода в монады?
Ну это на питоне будет просто, а через монады уже требуются некоторые усилия.
no subject
Date: 2010-02-12 12:10 pm (UTC)Во-1, не переводите стрелки. Я спросил "какого хрена", а не "по каким критериям".
Во-2, ну, сделайте мне в C так, чтобы получилось практически также, как если бы в язык были встроены полиморфные типы.
> Угу, так случайно получим O(N^2) вместо O(N).
Глубоко по барабану. Речь о полиморфизме.
> Ой, правда язык распаралелливать не умеет.
Кто именно?
> Ну это на питоне будет просто, а через монады уже требуются некоторые усилия.
Что "это"?
no subject
Date: 2010-02-14 03:44 am (UTC)Хрен имеет отношение к обсуждаемой теме?
>Во-2, ну, сделайте мне в C так, чтобы получилось практически также, как если бы в язык были встроены полиморфные типы.
Не так и сложно. Поскольку С вы видимо знаете лучше чем жабу, то знаете и без меня.
>> Угу, так случайно получим O(N^2) вместо O(N).
>Глубоко по барабану. Речь о полиморфизме.
Если рассуждение о полиморфизме ведется на таком же уровне строгости, ничего человек со стороны воспринять не сможет, увы.
>> Ой, правда язык распаралелливать не умеет.
>Кто именно?
Жаба конечно -- это я о вашем коде на жабе, который суммирует массив. Да и я ж не то что живых, в даже интернете хаскеллистов (промышленных) не встречал. Кстати, мне решающие сложные задачи (численные решения граничных задач) говорят, что в нетривиальных задачах все равно приходится распараллеливать человеку.
no subject
Date: 2010-02-14 09:17 am (UTC)Выражение "какого хрена" в русском языке является заменителем слова "зачем". А не "по каким критериям".
> Не так и сложно. Поскольку С вы видимо знаете лучше чем жабу, то знаете и без меня.
Если бы я знал, я бы вас не спрашивал. Видимо, вы тоже не знаете, а только газифицируете лужи.
> Если рассуждение о полиморфизме ведется на таком же уровне строгости
Уровень строгости имеет какое-то отношение к O(N^2)?
> говорят, что в нетривиальных задачах все равно приходится распараллеливать человеку.
А, то есть вы хотели сказать "автоматически распараллеливать не умеет"? Тогда да, это вообще, кажется, практически никто не умеет. Правда, написать в нужных местах `par` - дело довольно нехитрое.
no subject
Date: 2010-02-16 05:50 am (UTC)Когда перепишите примеры из статьи на Яве, тогда и ответ получите.
>> Если рассуждение о полиморфизме ведется на таком же уровне строгости
>Уровень строгости имеет какое-то отношение к O(N^2)?
Имеет.
>> говорят, что в нетривиальных задачах все равно приходится распараллеливать человеку.
>А, то есть вы хотели сказать "автоматически распараллеливать не умеет"? Тогда да, это вообще, кажется, практически никто не умеет. Правда, написать в нужных местах `par` - дело довольно нехитрое.
Нет, в сложных задачах приходится модифицировать алгоритм и менять структуры данных. Тоже самое приходится делать и для борьбы с численной неустойчивостью. Компиляторы делать этого не умеют, кроме тривиальных случаев.
no subject
Date: 2010-02-16 07:29 am (UTC)Сначала объясните, как одно относится к другому.
> Имеет.
Не имеет.
> Нет, в сложных задачах приходится модифицировать алгоритм и менять структуры данных.
Бывает. Тем не менее, распараллеливание при помощи `par` - техника, позволяющая во многих случаях этого избежать.
no subject
Date: 2010-02-18 10:21 am (UTC)>Сначала объясните, как одно относится к другому.
Спасибо за исправление ошибки.
Во-первых, если у вас одни типы превращаются в другие без всякой причины, то никто вас не поймет и разве что подумает что вы не уважаете собеседника.
Во-вторых, в императивных языках как правило нет встроенной поддержки списков, и для прохода по нему нужно вводить новую сущность -- итератор, а это уже имеет прямое отношение к тому, какие в языке есть виды полиморфизма.