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 поэтому и беда-беда...

[antilamer.livejournal.com]

Кстати давно хотел померить, тормозит ли в C# полиморфная рекурсия из-за проверки "есть ли уже такой инстанс метода" в рантайме.

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

Как раз на mono и проверял, ессна.

[antilamer.livejournal.com]

Давно ставил? Проверь вот на этом http://bugzilla.novell.com/show_bug.cgi?id=557606 ?

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

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

Просто я некоторое время верил, что шаблоны таки дают параметрический полиморфизм. Ну да, в невидимых единорогов я верить уже перестал, а в это - нет.

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

А там не как в жабе сделано? Я о внутренностях шарпа вообще нифига не знаю.

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

У GHC тоже нет, но повторить там подобную штуку - нет проблем. И да, там тоже один тип остаётся.

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

Cегодня.

Проверил. Зависло. Damn.

[mr-aleph.livejournal.com]

> шаблоны таки дают параметрический полиморфизм

Ну, а они его и дают. Просто не надо хотеть всяких извращений =)

Ну не умеют С++-компиляторы просекать типы с одинаковым "представлением" и использовать для них один и тот же шаблон...

Что ж поделать...

> А там не как в жабе сделано?

Вроде там честное инстанциирование и можно делать new T(), чего в Java делать нельзя. Могу наврать впрочем...

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

> Ну, а они его и дают.

Если бы давали - оно бы работало. Они дают иллюзию параметрического полиморфизма.

> Ну не умеют С++-компиляторы просекать типы с одинаковым "представлением"

Если бы был параметрический полиморфизм, то был бы одни тип.

> Вроде там честное инстанциирование и можно делать new T(), чего в Java делать нельзя. Могу наврать впрочем...

А можно чуть подробнее? А то я в жабе ламер...

[mr-aleph.livejournal.com]

> А можно чуть подробнее? А то я в жабе ламер...

Ну в Жабе нельзя написать метод вида:

 T allocator () {
  return new T();
}

Поскольку на этапе выполнения никакого T не остаётся, компилятор порождает код манипулирующий Object и кое-где runtime касты

[mr-aleph.livejournal.com]

c Haskell фишка такая --- ты там используешь type-classes, тем самым избегая создания реальных типов...

попробуй сделать чисто на data.

[mr-aleph.livejournal.com]

ничего, что я на ТЫ как-то внезапно перешёл? меня иногда клинит...

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

А, теперь понял.

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

Нивапрос.

module Test where 
data Nil = Nil 
data Cons a = Cons Integer a 
newtype ScalarProduct a = ScalarProduct {scalarProduct :: a -> a -> Integer}
nilSP :: ScalarProduct Nil
nilSP = ScalarProduct {scalarProduct = \Nil Nil -> 0}
consSP :: ScalarProduct a -> ScalarProduct (Cons a)
consSP sp = ScalarProduct {scalarProduct = \(Cons n1 a1) (Cons n2 a2) -> n1 * n2 + scalarProduct sp a1 a2}
main :: Integer -> Integer 
main n = main' nilSP n 0 Nil Nil where 
  main' :: ScalarProduct a -> Integer -> Integer -> a -> a -> Integer 
  main' sp 0 _ as bs = scalarProduct sp as bs 
  main' sp n i as bs = main' (consSP sp) (n-1) (i+1) (Cons (2*i+1) as) (Cons (i^2) bs) 

Никаких классов.

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

А я вообще не помню, мы на ты или на вы. Да и важно ли это?

[mr-aleph.livejournal.com]

да, мой слив защитан... Cons a все имеют одинаковое представление, можно всё статически скомпилировать без порождения новых "реальных типов"...

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

У меня mono из портов, версия 2.4.2.3

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

Дык классы - это те же типы, вид в профиль. Разница - а) есть только одно значение данного типа, б) это одно значение компилятор передаёт как неявный параметр. И всё.

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

Оригинально предыдущий код выглядел так:

module Test where 
data Nil = Nil 
data Cons a = Cons Integer a 
class ScalarProduct a where scalarProduct :: a -> a -> Integer
instance ScalarProduct Nil where scalarProduct Nil Nil = 0
instance ScalarProduct a => ScalarProduct (Cons a) where scalarProduct (Cons n1 a1) (Cons n2 a2) = n1 * n2 + scalarProduct a1 a2
main :: Integer -> Integer 
main n = main' n 0 Nil Nil where 
  main' :: ScalarProduct a => Integer -> Integer -> a -> a -> Integer 
  main' 0 _ as bs = scalarProduct as bs 
  main' n i as bs = main' (n-1) (i+1) (Cons (2*i+1) as) (Cons (i^2) bs) 

[nponeccop.livejournal.com]

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

[udpn.livejournal.com]

Даже несмотря на то, что я полностью согласен с вами... Должен реквестировать доказательство, что параметрический полиморфизм невозможно точно определить.

Похоже, очень даже можно, причем несколькими методами. Каждый из них вполне точный и дает свой особый ППМ.

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

Во-1, порядок был обратный (сначала была написана плюсовая версия, потом жабская, потом шарповая).

Во-2, да, пост рассчитан на то, что понимание понятия "параметрический полиморфизм" у читателей совпадает с моим. Если ваше - не совпадает, то предьявить собственное определение должны ВЫ.

В-3, покажите мне хоть один ЖЖ-пост, где определены все используемые понятия.

[nponeccop.livejournal.com]

> В-3, покажите мне хоть один ЖЖ-пост, где определены все используемые понятия.

Это ж мой главный аргумент - что все эти тёрки в ЖЖ о том, чей полиморфизм круче, не имеют научного смысла, т.к. за неимением общепринятого определения отсутствует предмет обсуждения.

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

И только-то? Вы могли не трудиться, излагая подобный трюизм. Я не считаю ЖЖ научным журналом и не считаю себя обязанным соблюдать научную строгость при публикации.

[nponeccop.livejournal.com]

> Если ваше - не совпадает, то предьявить собственное определение должны ВЫ.

Вообще-то никто никому ничего не должен. Я не говорил, что вы мне что-то должны.

Во-первых, как я могу понять, что моё определение не совпадает с вашим? Хорошо, если размышляя, используя свое определение, я приду к противоречию, и пойму, что что-то не так. А если не приду? Тогда возникнет тихое недопонимание, и я, возможно, заражусь от вас ложными убеждениями.

Соответственно, упоминание используемых определений полезно скажется на качестве вашего ЖЖ. Разумеется, по умолчанию подразумевается, что вы используете общепринятые термины, и ничего пояснять не надо. Но в данном конкретном случае общепринятого определения нет, и пояснения были бы полезны.

Во-вторых, почему это я вообще должен что-то фантазировать, прочитав у вас слово "параметрический полиморфизм". Попросить ссылку для прояснения непонятных мест - вполне нормальная реакция, гораздо лучше занятий фантазиями.

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