Delphi vs C++ vs C# , ну и Java немножко, где-то ближе к старшему байту номеров страниц

Цитата --Ins-- @ 21.03.12, 12:40

Надеюсь что нет

А я то думал, что нет языка, хуже плюсов приспособленного для создания DSL'ей. Аоновононочо!

Цитата korvin @ 13.03.12, 15:50

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

Подробно я так и не посмотрел. Но, как собственно и написано тут:

Цитата

An advantage over some OOP languages is that methods in Haskell are completely type-safe: any attempt to apply a method to a value whose type is not in the required class will be detected at compile time instead of at runtime. In other words, methods are not "looked up" at runtime but are simply passed as higher-order functions.

И

Цитата

C++ and Java attach identifying information (such as a VTable) to the runtime representation of an object. In Haskell, such information is attached logically instead of physically to values, through the type system.

А для "рекурсивных" инстансов(вроде инстанса ScalarProduct для Cons), он "сохранит" "следующий" инстанс(при передаче в функцию, требующую значение типа, удовлетворяющего тайпклассу - в нашем случае при очередном вызове main'). По крайней мере(насколько я понял) так делает ghc(смотрел по ghc -c), но у них не такая простая реализация абстрактной машины + ленивость, по сему уверен не до конца. Так что никаких идентификаторов типов.

Сообщение отредактировано: D_KEY - 21.03.12, 13:06

Цитата D_KEY @ 21.03.12, 13:05

Цитата

An advantage over some OOP languages is that methods in Haskell are completely type-safe: any attempt to apply a method to a value whose type is not in the required class will be detected at compile time instead of at runtime.

Я и не говорил, что тайп-чек происходит в рантайме. Кстати, статический ООЯП тебе также не даст вызвать метод, если в классе или одном из суперклассов объекта нет такого метода. Так что в этой фразе:

Цитата

methods are not "looked up" at runtime but are simply passed as higher-order functions

наверное подразумевается не совсем то, что ты думаешь. Думаю, тут имеется в виду, что в рантайме не происходит проверка на наличие метода вообще, но выбор реализации как-то должен происходить.

Добавлено 21.03.12, 13:44

Цитата D_KEY @ 21.03.12, 13:05

А для "рекурсивных" инстансов(вроде инстанса ScalarProduct для Cons), он "сохранит" "следующий" инстанс(при передаче в функцию, требующую значение типа, удовлетворяющего тайпклассу - в нашем случае при очередном вызове main'). По крайней мере(насколько я понял) так делает ghc(смотрел по ghc -c), но у них не такая простая реализация абстрактной машины + ленивость, по сему уверен не до конца. Так что никаких идентификаторов типов.

Как он узнает какой инстанс следующий?

Цитата korvin @ 21.03.12, 13:42

но выбор реализации как-то должен происходить.

Какой выбор? Методы(конкретного инстанса нужного тайпкласса) фактически передаются как функции высших порядков. И судя по реализации так и есть.

Добавлено 21.03.12, 13:51

Цитата korvin @ 21.03.12, 13:42

Как он узнает какой инстанс следующий?

Он его вычисляет при передачи в очередной вызов main'

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)  -- Вот тут

Для такого вызова формируются не только значения (Cons (2*i+1) as) и (Cons (i^2) bs), но и нужные методы соответствующего им инстанса(т.к. тип main' этого требует).

Цитата D_KEY @ 21.03.12, 13:44

Какой выбор? Методы(конкретного инстанса нужного тайпкласса) фактически передаются как функции высших порядков. И судя по реализации так и есть.

Да, я пока шел домой, думал об этом, хотя это все равно рантайм и не факт, что более эффективное решение.

Т.е. если переводить на плюсы примерно то, что делает(или мог бы делать) haskell для данного примера(о типобезопасности пока забудем ):

#include <functional>
 
typedef void * generic;
 
struct Nil{};
struct Cons {int data; generic tail; Cons(int d, generic nxt) : data(d), tail(nxt) {} };
 
struct ScalarProductInstance
{
    typedef std::function<int (generic, generic)> instance_t;
 
    ScalarProductInstance(instance_t scalarProductImpl)
        : scalarProduct(scalarProductImpl)
    {
    }
 
    std::function<int (generic a, generic b)> scalarProduct;
};
 
int scalar_product_nil(generic a, generic b)
{
    return 0;
}
 
ScalarProductInstance *ScalarProductNil(new ScalarProductInstance(scalar_product_nil));
 
ScalarProductInstance *ScalarProductCons(ScalarProductInstance *nxt)
{
    return new ScalarProductInstance(
        [=](generic ga, generic gb) -> int
        {
            Cons *a = static_cast<Cons*>(ga);
            Cons *b = static_cast<Cons*>(gb);
 
            return a->data * b->data + nxt->scalarProduct(a->tail, b->tail);
        });
}
 
int f(ScalarProductInstance *disp, int n, int i, generic as, generic bs)
{
    if (n == 0)
    {
        return disp->scalarProduct(as, bs);
    }
    return f(ScalarProductCons(disp), n-1, i+1, new Cons(2*i+1, as), new Cons(i*i, bs));
}
 
int main()
{
    int n;
    std::cin >> n;
    std::cout << f(ScalarProductNil, n, 0, new Nil(), new Nil()) << std::endl;
}

Добавлено 21.03.12, 14:38

Цитата korvin @ 21.03.12, 14:19

хотя это все равно рантайм

Этот рантайм, по сути, никуда деться не может. У тебя в любом случае будут разные вызовы и прямая рекурсия для инстанса Cons невозможна. Тут же ты явно избегаешь диспетчеризации в рантайме(ты всегда знаешь, что конкретно нужно вызвать). Ну а все проверки только в статике.

Сообщение отредактировано: D_KEY - 21.03.12, 14:38

Цитата D_KEY @ 21.03.12, 14:32

Тут же ты явно избегаешь диспетчеризации в рантайме(ты всегда знаешь, что конкретно нужно вызвать). Ну а все проверки только в статике.

И чем этого помогает? В моей версии реализации все проверки тоже в статике, диспетчеризация в случае Хаскелла может происходить за почти константное время, если использовать только конструкторы (а они вроде и так сохраняются для работы паттерн-матчинга, хотя может там такой же механизм используется с передачей функций), а если еще и типы, то за константное, субтипирования-то нет.

Цитата korvin @ 21.03.12, 14:43

И чем этого помогает? В моей версии реализации все проверки тоже в статике, диспетчеризация в случае Хаскелла может происходить за почти константное время, если использовать только конструкторы (а они вроде и так сохраняются для работы паттерн-матчинга, хотя может там такой же механизм используется с передачей функций), а если еще и типы, то за константное, субтипирования-то нет.

Поясни... Вообще в том же С++ виртуальный вызов стоит столько же, сколько вызов функции по указателю. Но там к объекту прикрепляется ссылка на vtbl класса, тут же так сделать нельзя - тайпклассы и инстансы разделены с типами и объектами.

Сообщение отредактировано: D_KEY - 21.03.12, 14:50

Цитата D_KEY @ 21.03.12, 14:49

Поясни... Вообще в том же С++ виртуальный вызов стоит столько же, сколько вызов функции по указателю. Но там к объекту прикрепляется ссылка на vtbl класса, тут же так сделать нельзя - тайпклассы и инстансы разделены с типами и объектами.

Ну может в C++ vtable класса хранит указатели на все непереопределенные функции всех предков, но во многих языках она хранит только функции непосредственного класса объекта, а так же в классе хранится ссылка на ближайщего предка, т.е. алгоритм поиска такой:

dispatch object message:
  dispatch (class of object) message:
    let method = get (class of object) message
      if method:
        then return method
        else return dispatch (superclass of (class of object))

Т.е. время поиска прямопропорционально количеству суперклассов класса объекта. Но раз в C++ не так, то ты сам ответил на свой вопрос =).

В хаскелле к "объекту" "прикрепляется" метка конструктора, чтобы мог работать ПМ:

data Foo
  = Bar Int        — Bar — первый конструктор
  | Baz Double Int — Baz — второй конструктор
 
f :: Foo → String
f foo = case foo of — паттерн-матчинг работает в рантайме
  (Bar i)   → show x
  (Baz d i) → show (roundTo d i)

соответственно метка конструктора может иметь ссылку на тип, а тот, в свою очередь, на таблицу инстансов тайпклассов, инстанциированных для этого типа (считай vtable). Ну или без типа, сразу ссылку на "vtable".

Сообщение отредактировано: korvin - 21.03.12, 15:52

Цитата korvin @ 21.03.12, 15:08

Ну может в C++ vtable класса хранит указатели на все непереопределенные функции всех предков

Грубо говоря, так и есть. Т.е. если виртуальные метод не переопределили, то указатель в vtbl будет указывать на функцию предка. Потому никаких поисков - просто заранее известное смещение по vtbl и вызов функции по лежащему там указателю.
Но надо заметить, что в стандарте этого нет(за что некоторые сишники не любят С++).

Цитата

В хаскелле к "объекту" "прикрепляется" метка конструктора
...
соответственно метка конструктора может иметь ссылку на тип

Может. Но сильно подозреваю, что это банальный enum.
Т.е.

struct Foo
{
    enum
    {
        BAR_TAG,
        BAZ_TAG,
    } tag__;
 
    struct Bar
    {
        int a;
    };
 
    struct Baz
    {
        int a;
        double b;
    };
 
    union
    {
        Bar bar;
        Baz baz;
    } data__;
};

Цитата

а тот, в свою очередь, на таблицу инстансов тайпклассов, инстанциированных для этого типа (считай vtable). Ну или без типа, сразу ссылку на "vtable".

Но ведь тайпклассов может быть много, они могут быть определены в разных модулях и пр. и пр.
И вообще, ИМХО, идеологически для хаскеля не подходят всякого рода ссылки на тип в рантайме. Хотя тут тебе виднее

Добавлено 21.03.12, 15:31
Опять сообщения глючат?

Блин, что за фигня с сообщениями?

Добавлено 21.03.12, 16:00

Цитата D_KEY @ 21.03.12, 15:22

Может. Но сильно подозреваю, что это банальный enum.

Ну ты делал ghc -c. Надо тоже попробовать =)

Цитата D_KEY @ 21.03.12, 15:22

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

Ну и что? А создавать сотни "цепочек функций" лучше? В моем-то случае объем оверхеда хоть более-менее можно прогнозировать при написании программы.

Цитата D_KEY @ 21.03.12, 15:22

И вообще, ИМХО, идеологически для хаскеля не подходят всякого рода ссылки на тип в рантайме. Хотя тут тебе виднее

Идеологически Хаскелл не заботит, как оно реализовано в рантайме =)
Так что, кстати, возможно, что некоторые реализации и используют «мой» подход.

Цитата korvin @ 21.03.12, 15:53

Ну ты делал ghc -c. Надо тоже попробовать =)

Там не все так просто Рантайм у ghc не такой уж легкий и прозрачный

Цитата

Цитата D_KEY @ 21.03.12, 15:22

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

Ну и что?

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

Цитата D_KEY @ 21.03.12, 16:12

Там не все так просто Рантайм у ghc не такой уж легкий и прозрачный

Гы да, уже посмотрел, «треш, угар и содомия». Однако похоже, что все-таки какая-то инфа сохраняется:

static char cjt_str[] = "main:Main.Bar";
 
StgWord Main_Bar_con_info[] = {
((W_)&cjt_str+0), 0x1UL, 0x2UL
};
 
FN_(Main_Bar_con_entry) {
FB_
R1.w = R1.w+1;
JMP_(*Sp);
FE_
}
 
static char cjy_str[] = "main:Main.Bar";
 
StgWord Main_Bar_static_info[] = {
((W_)&cjy_str+0), 0x1UL, 0x7UL
};
 
FN_(Main_Bar_static_entry) {
FB_
R1.w = R1.w+1;
JMP_(*Sp);
FE_
}

Хотя мне сложно что либо судить об этом

Добавлено 21.03.12, 16:22

Цитата D_KEY @ 21.03.12, 16:12

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

Во что-то типа такого:

scalarProduct (x, y):
  dTag = getContructorTag(x)
  inst = getInstance ( ScalarProduct, dTag )
  inst (x, y)

Добавлено 21.03.12, 16:28

Цитата korvin @ 21.03.12, 16:15

Однако похоже, что все-таки какая-то инфа сохраняется:

Впрочем, я думаю, это скорее для компоновки C-модулей.

Цитата korvin @ 21.03.12, 16:15

Во что-то типа такого:

scalarProduct (x, y):
  dTag = getContructorTag(x)
  inst = getInstance ( ScalarProduct, dTag )
  inst (x, y)

Требую подробностей
Т.е. ты таки будешь использовать поиск нужного инстанса? Какие тогда могут быть разговоры о константном времени вызова?

Цитата D_KEY @ 21.03.12, 17:03

Требую подробностей
Т.е. ты таки будешь использовать поиск нужного инстанса? Какие тогда могут быть разговоры о константном времени вызова?

Ты ничего не слышал про хеш-таблицы? o_O'

Добавлено 22.03.12, 04:09
Да и вообще

getInstance (scalarProduct, dTag) = dTag.ScalarProduct.scalarProduct

Даже хеш не нужен. Все то же самое, что и в C++.