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: 2009-12-06 02:40 pm (UTC)Просто я некоторое время верил, что шаблоны таки дают параметрический полиморфизм. Ну да, в невидимых единорогов я верить уже перестал, а в это - нет.
> в C# я думаю типы-инстансы плодяться во время исполнения --- потому и работает...
А там не как в жабе сделано? Я о внутренностях шарпа вообще нифига не знаю.
> у С++ нету VM поэтому и беда-беда...
У GHC тоже нет, но повторить там подобную штуку - нет проблем. И да, там тоже один тип остаётся.
no subject
Date: 2009-12-06 02:55 pm (UTC)Ну, а они его и дают. Просто не надо хотеть всяких извращений =)
Ну не умеют С++-компиляторы просекать типы с одинаковым "представлением" и использовать для них один и тот же шаблон...
Что ж поделать...
> А там не как в жабе сделано?
Вроде там честное инстанциирование и можно делать new T(), чего в Java делать нельзя. Могу наврать впрочем...
no subject
Date: 2009-12-06 03:01 pm (UTC)Если бы давали - оно бы работало. Они дают иллюзию параметрического полиморфизма.
> Ну не умеют С++-компиляторы просекать типы с одинаковым "представлением"
Если бы был параметрический полиморфизм, то был бы одни тип.
> Вроде там честное инстанциирование и можно делать new T(), чего в Java делать нельзя. Могу наврать впрочем...
А можно чуть подробнее? А то я в жабе ламер...
no subject
Date: 2009-12-06 03:03 pm (UTC)Ну в Жабе нельзя написать метод вида:
T allocator () { return new T(); }Поскольку на этапе выполнения никакого T не остаётся, компилятор порождает код манипулирующий Object и кое-где runtime касты
no subject
Date: 2009-12-06 03:17 pm (UTC)no subject
Date: 2009-12-06 03:12 pm (UTC)попробуй сделать чисто на data.
no subject
Date: 2009-12-06 03:22 pm (UTC)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)Никаких классов.
no subject
Date: 2009-12-06 03:24 pm (UTC)no subject
Date: 2009-12-06 03:29 pm (UTC)no subject
Date: 2009-12-06 03:32 pm (UTC)no subject
Date: 2009-12-06 03:13 pm (UTC)no subject
Date: 2009-12-06 03:22 pm (UTC)