Информация об изменениях

Сообщение Re[28]: «Собаку съел» от 14.02.2017 7:35

Изменено 14.02.2017 8:02 vdimas

Старый текст
Новый текст
Разница

Re[28]: «Собаку съел»

Здравствуйте, samius, Вы писали:

S>>>верно. Но цитата из Пирса однозначно отсылает к механике выполнения в рантайме.
V>>Не ведись на это. ))
V>>Хороший теоретик не обязан быть хорошим инженером, и обратное тоже верно.
S>Т.е у хороших инженеров свой полиморфизм и определения?

Почему бы и нет?
На сегодня существует несколько конкурирующих м/у собой классификаций параметрического полиморфизма, где каждый автор гнёт что-то своё, и?

В любом случае, отсылка к механике выполнения в рантайм при обсуждении системы типов является грубой ошибкой, независимо от степени "теоретической" грамотности автора или его прежних заслуг.

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

ИМХО, во всём этом множестве сценариев, важны лишь следующие координаты:
— монотип или полиморфный тип;
— типизированный полиморфизм или нетипизированный;
— статический матчинг типов к ф-иям (методам) или динамический.

"Типизированный полиморфизм" — это тот самый параметрический полиморфизм в ограничениях (привет обычному ООП-полиморфизму).

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

V>>Хороший оптимизатор в итоге и должен сводить подавляющее большинство сценариев к ad hoc.

V>>Но это, повторюсь, лишь подробности реализации компилятора, которые могут быть несколько ортогональны "внешним" возможностям ЯП.
S>Зачем сводить к ad hoc то, что не ad hoc?

Потому что это эффективней — работать напрямую с монотипами вместо абстракций.

Абстракции, проникающие в рантайм, не бесплатны — почти всегда работа одного и того же машинного кода с разными абстракциями означает работу с "боксированными" значениями, то бишь со ссылочными типами (потому что физический размер ссылки одинаков, независимо от типа, на который ссылка указывает), т.е. везде имеем +1 к косвенности, если машинный код один и тот же.

Например, чтобы заслужить виртуальный вызов в С++, компилятор должен "видеть" ссылочный тип, т.е. видеть не полностью определённый тип (не монотип), а лишь базовый класс (эдакое "ограничение"). Иначе компилятор будет фигачить прямой вызов, вместо виртуального. В Объектном Паскале, Джаве, C# аналогично.

Вот почему с т.з. инженера, а не "голого теоретика" — это грубая ошибка, ссылаться на способ реализации.

Рядом давал уже примеры, когда оптимизатор С++ способен проследить историю возникновения текущего контекста достаточно далеко и зафигачить прямой вызов даже там, где, казалось бы, он совершенно не ожидается. И сразу же появляется возможность порождать ДРУГОЙ машинный код для каждого уникального места, где вызывается одна и та же полиморфная ф-ия.

V>>Это всё параметрический полимофизм тоже. ))
S>Ты не читал и не согласен, или читал но не согласен,

Я-то читал и даже понимал. ))

S>т.к. вики хаскеля писали сантехники для домработниц, а не инженеры?

Вполне может быть так, что ты невнимательно прочел по собственной ссылке.

Например, цитата:

In Haskell, this is achieved via the system of type classes and class instances.

Каждый инстанс класса — это ad hoc.
"Инстанс класса" — это объявление перегрузок методов под этот класс.

Но использование техники ограничений на классах типов — это признак (главный и основной) именно т.н. "типизированного параметрического полиморфизма".

Хотя ты, несомненно, из приведенной ниже цитаты сделал ровно противоположный вывод. ))
Спутав, очевидно, сам инстанс со сценарием его использования. Потому что если инстансов меньше двух, то никакого ad hoc нет принципиально, бо нет перегрузки сигнатур.

Далее.
Даже когда мы имеем "одинаковый машинный код" для тех самых боксированных (или ссылочных для ООП) типов, то рано или поздно для вызова специфических для типа действий совершается ad hoc, т.е. матчинг конкретного метода/ф-ии на конкретный тип.

Так вот. Такой матчинг бывает статическим или динамическим. Ввиду того, что в конечном бинарном образе программы на Хаскель система типов всегда является "закрытой" (в отличие от возможностей ООП-полиморфзма, расписанного на базовых абстрактных/полиморфных типах), компилятор способен увидеть, где там происходит выбор перегрузок переопределений для классов типов, а где нет, т.к. банально эта "перегрузка" единственная. В таких случаях, даже если в исходнике у нас использовалась и техника параметрического полиморфизма, и техника ad hoc-специализаций — пофиг, вообще никакого полиморфизма (в отсутствии таких вариаций) в генерируемом коде нет. Ну и плюс оптимизация сводит к похожим сценариям даже те случаи, где перегрузки объективно имеются, но в данном конкретном месте невозможны, т.е. можно считать, что их нет вовсе.

S>Давай я тебе процитирую, что бы ты не пропустил.
S>

S>You can recognise the presence of ad-hoc polymorphism by looking for constrained type variables: that is, variables that appear to the left of =>, like in elem :: (Eq a) => a -> [a] -> Bool. Note that lookup :: (Eq a) => a -> [(a,b)] -> Maybe b exhibits both parametric (in b) and ad-hoc (in a) polymorphism.

S>Это по ссылке выше, если что.

ЧТД, недопонимание.
"you can" говорит о возможности, но не обязательности.

Ad hoc — это перегрузка сигнатур. Да, чаще всего мы можем увидеть ad hoc, когда на аргументы накладываются ограничения.
Почему?
Да потому что тогда и только тогда перегрузка и возможна.

Что касается "механики", повторюсь, вызов же elem для параметрически полиморфного аргумента a в общем случае зависит от контекста — может быть разресолвлено статически или динамически.

Вот точный аналог этого примера для C#:

class SomeUtils {
    public bool Elem(List<a> list) where a : IEquatable<a> {...}
}

Это ad hoc или параметрический полиморфизм? ))
Правильный ответ: параметрический.

А так?

class SomeUtils {
    public bool Elem<a>(IList<a> l) where a : IEquatable<a> {...}

    public bool Elem<a, b>(IDictionary<a, b> d) where a : IEquatable<a> {...}
}

Правильный ответ: оба совместно.

Не знаю как тут можно было заплутать...
Ну вот рядом мы как раз обсуждали сценарий "where T : IEquatable<T>" как сценарий параметрического полиморфизма в C#, не?

Еще вопрос — а что ты сможешь сделать затем с b из Maybe b?
Опять точный аналог для C#:

class SomeUtils {
    public Nullable<b> Lookup<a, b>(List<KeyValuePair<a,  b>> list) where a : IEquatable<T> {...}
}

... если до этого в вызывающем контексте вычислений не подал ограничения на b или не указал для на него конкретный тип?
Аж ничего. Не хочешь в этом месте помедитировать?

Собственно, в скипнутом тобой суть вещей раскрыта — про "концепт".
Любой современный типизированный полиморфизм от этого концепта пляшет.

В общем, когда ты начинаешь вызывать одни ф-ии из других, то начинают совместно работать ограничения на полиморфные типы (т.е. классы типов) и/или монотипы + конкурирующие инстансы ф-ий для них (ad doc).

Haskell even allows class instances to be defined for types which are themselves polymorphic (either ad-hoc or parametrically).

Это по ссылке выше, если что.

S>То есть, в моем понимании, если ты делаешь в интерпретаторе :t foo и тебе пишут (Eq a) =>, то foo ad hoc полиморфна по типу a.

При том, что сам тип a объявлен в этой сигнатуре как параметрически полиморфный?

S>Просто, не правда ли?

Не обманывай себя. ))
Я уже говорил — разные виды полиморфизма работают совместно или даже являются одним и тем же в конкретной ситуации.

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

V>>А тут:
V>>

V>>equal_to :: (Eq a) => a -> a -> Bool
V>>equal_to a b = (a == b)
V>>

V>>?
S>см выше. Ad hoc.

А тут:

 struct GenericEqualityComparer<T> : IEqualityComparer<T> where T : IEquatable<T>
 {
     public bool Equals(T x, T y)
     {
         if (x != null)
         {
             if (y != null) return x.Equals(y);
             return false;
         }
         if (y != null) return false;
         return true;
     }
 }

V>>Ну вот я против таких заморачиваний и выступал в прошлом сообщении, что это всё условности. Ты можешь считать так, что моё определение equal_to для Хаскеля — это всегда параметрический полиморфизм. Такой подход можно назвать "строгим", теоретикам навроде Пирса нравится. А тот факт, что Хаскель способен в 99% случаев привести его к ad hoс через оптимизацию и/или вывод типов в конкретном контексте — лишь приятный бонус, эдакий побочный эффект. ))
S>да не, я как раз считаю что твое определение equal_to для Хаскеля — это ad hoc.

Даже когда оно одно? ))
Ведь не всегда ограничения вводятся для отличий перегрузок, они часто вводятся для доступа к операциям над "концептом".

Например, аналогичный случай в С++ зовется "частичной специализацией шаблонов", когда на тип можно подать ограничения:

Пример частичной специализации в ограничениях

// Инфраструктура
using namespace std;

class NotImplemented {};

template<typename T1, typename T2>
struct where
{
    typedef typename enable_if<is_base_of<T2, T1>::value, NotImplemented>::type type;
};

// Использование
template<typename T, typename = NotImplemented>
class List;

template<typename T>
struct IEquatable {
    virtual bool isEqual(const T & other) const = 0;
};

// Определяем List только для наследников IEquatable<T>
template<typename T>
class List<T, typename where<T, IEquatable<T>>::type> {
public:
    void add(T item) {
        list_.push_back(item);
    }

    bool elem(const T & item) const {
        for(auto const & element : list_) {
            if(element.isEqual(item))
                return true;
        }

        return false;
    }

private:
    vector<T> list_;
};

// Пример наследника IEquatable<T>
template<typename T>
struct Box : IEquatable<Box<T>> {
    bool isEqual(const Box<T> & other) const {
        return value == other.value;
    }

    Box(const T & v = T()) : value(v) {}

    T value;
};

// Проверяем
void main() {
    //List<int> list;    // error C2079: 'list2' uses undefined class 'List<int,NotImplemented>'
    List<Box<int>> list; // ok

    list.add(42);
    bool elem = list.elem(42);

    cout << elem << endl;
}

Хаскель позволяет трюки подобного рода. C# — нет.

S>И этого не спрятать 10ю обертками equal_to_10 над equal_to_N. Можно попытаться сотней, но я не уверен что получится.

Наоборот, спрятать ad hoc получится с помощью единственной "специализации".

Еще раз. Медленно.
Аргумент в приведенной специализации — параметрически полиморфный.
Несколько конкурирующих специализаций (перегрузок) ф-ии с одним и тем же именем — ad hoc.

Блин, очевидно же, что нельзя создать несколько перегрузок некоей ф-ии (для примера, с одним аргументом), не указав РАЗНЫЕ ограничения на полиморфные типы её аргумента или просто конкретные типы аргументов.

Т.е., если у нас в области видимости есть только одно определение equal_to, то никакого ad hoc не возникает прямо по-определению, потому что для ad hoc-полиморфзма надо минимум две отличающиеся перегрузки одной ф-ии в области видимости.

Но да, наличие специализации для полиморфного аргумента ПОЗВОЛИТ добавлять "конкурирующие" сигнатуры. Тут главное не путать "потенциальную возможность" и "фактическое наличие", как в "you can" по ссылке.

Вот чуть более подробная статья на Хабре:
https://habrahabr.ru/post/166353/

Для объяснения сути ad hoc-полиморфизма был взят пример специализации оператора `+` для разных типов, классов типов и даже списков.
Должно стать чуть понятнее.