On Vox: Поигрался тут

[migmit]

Кто-то (увы, не помню кто - напомните?) не так давно предлагал вопрос для интервью соискателям: где в 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));
  }
}

Однако, переписав этот код почти один в один на C++ (с шаблонами вместо дженериков), получаем... нерабочий код:

#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

Comments

[antilamer.livejournal.com]

В Mono, кстати, совсем недавно были баги с инлайнингом полиморфной рекурсии, он тоже пытался все максимально развернуть.

[mr-aleph.livejournal.com]

тут задача с "потенциально бесконечным" числом типов, чего же ты хотел от языка, в котором любая программа должна порождать конечное число типов?

в Java работает, потому что там один тип на самом деле остаётся, случай тут простой и чекер его осиливает...

в C# я думаю типы-инстансы плодяться во время исполнения --- потому и работает...

у С++ нету VM поэтому и беда-беда...

[nponeccop.livejournal.com]

Вы, надеюсь, понимаете, что ввиду отсутствия определения параметрического полиморфизма ваш пост - просто фантазия. Вы написали какой-то код, который якобы, как подсказывает вам ваше образное мышление на основании туманных эмоциональных образов, использует параметрический полиморфизм, а затем переписали этот код на другой язык, где он не заработал. И на этом основании заявляете, что в С++ нету параметрического полиморфизма, а в Java он есть. Как можно обсуждать то, что невозможно точно определить?

[migmit.vox.com (from livejournal.com)]

Отвечаю на вопрос из другого топика:

> Ну и почему же Sun тогда не ввели новые, полностью безопасные generic классы?

Недостаток времени/лень/память подвела/не сообразили - спросите у фирмы Sun.

> Нет, и что? Это возмножно и в языке, в котором типов нет ВООБЩЕ.

Отмотать для вас тред?

>>>>Ага, только в результате не получается вводить полиморфные типы, аргументы которых заранее неизвестны.
>>>Для этого вполне подходит ООП (фабрики классов и т.п.), да и в простом Си это тоже возможно.
>>Нет. Система типов C тем более полиморфных типов не содержит (вообще). И даже имитации нет.
>Нет, и что? Это возмножно и в языке, в котором типов нет ВООБЩЕ.

Может быть, вы мне объясните, с помощью какой магии можно вводить полиморфные типы, если типов нет?

>>Но вы порывались утверждать, что возможности дженериков меньше, чем возможности темплейтов C++.
>"Хозяин" C# -- Микрософт в лице MSDN со мной согласна.

Что вы говорите! А я-то думал, что по приведённой вами ссылке указаны НЕКОТОРЫЕ (но не все) отличия темплейтов от дженериков. Видимо, я где-то не заметил фразу "дженерики имеют меньше возможностей, чем C++".

В любом случае, это неправда - пример приведён.

> Так ваше скалярное произведение и так выглядит достаточно длинно, чтобы придти в ужас. Куда уж длиннее?

Вы спросили про продакшен. Мне лично представляется, что продакшен-код в подавляющем большинстве случаев содержит ОЧЕНЬ много строк.

> А я называл?

Вы писали: "а оказывается лучше дженерики C#/Java (которые на самом деле были введены для того, чтобы убрать приведение типов при доступе к контейнеру)." Поскольку статья, собственно, рассматривает именно вопрос о полиморфизме, то вариантов два: либо вы согласны с тем, что темплейты не дают параметрического полиморфизма (и, значит, фраза из статьи в этом контексте верна), либо нет - тогда вы в очередной раз не видите очевидного.

> Все обсуждаемые языки Тьюринг-полные, поэтому реализовать можно что угодно.

Неверно. Можно реализовать любой алгоритм; это не значит, что можно реализовать любую ИДЕЮ.

> для решения простой задачи понапихали тайпкастов и рефлексий.

Я не понял задачу. Если она имеет отношение к дискуссии, то расшифруйте. Если нет - не надо.

> Вы умнее меня, поэтому уж расскажите, как в Java сделать так, чтобы можно было обощенно использовать complex, complex, а еще complex и complex, и (о ужас, basic_string) -- все это помогает создавать легко читаемый код.

Более подробно можно? Что вы хотите получить в итоге? В чём у вас проблема?

[secondary-tea.livejournal.com]

>Что вы говорите! А я-то думал, что по приведённой вами ссылке указаны НЕКОТОРЫЕ (но не все) отличия темплейтов от дженериков. Видимо, я где-то не заметил фразу "дженерики имеют меньше возможностей, чем C++".
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;
если не будет хватать диапазона значений, легко будет изменить одну строку, а не раскиданные по всему коду.