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

K>>Вот только имя конструктора — тег в размеченном объединении — это не тип. Точно так же как 3 не тип и "hello" — не тип. Это значение.

V>Я упомянул теорию групп, потому как в Хаскеле присутствует типобезопасное размеченное объединение, для описания св-в которого как раз наиболее подходит теория групп. Поэтому я называю группу сущностей, объединяемых в размеченном объединении, типами (они же — сорта). Имею полное право.

Называть то вы можете, но это так экстравагантно, что все остальные вас имеют право не понять.

V>Конкретно в Хаскеле в размеченное объединение можно заворачивать только туплы и ничего кроме туплов. Для вырожденных случаев тупл пустой или состоит из одного элемента. Далее. Имя конструктора размеченного объединения используется так же как синоним значения разметки этого объединения в паттерн-матчинге. Эта дуальность — следствие минималистичности синтаксиса Хаскеля. Один и тот же идентификатор обозначает в разных ситуациях разные сущности: один из конструкторов АлгТД или же символьный алиас метки типа. То бишь выступает идентификатором соответствующего типа упакованного тупла (во втором случае).

Это разные идентификаторы. Они в разных пространствах имен и могут поэтому совпадать.

V>>>, примерно точно так же, как dynamic_cast проверяет токен типа (на который ссылается экземпляр типа через указатель на vtable), а удачная ветка матчинга затем предоставляет доступ к значению упакованного в АлгТД типа.

K>>Еще раз, типы в АлгТД не упаковываются. Вы путаете сабтайпинг и АлгТД. Они не родственники и даже не однофамильцы.

V>Еще раз — курить Алгебраические типы

Курим:

Алгебраический тип данных — в теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа.

Т.е. все как я и сказал. Никакие типы в АлгТД не упаковываются. Упаковываются значения.
Ну, может и можно сказать, что конструктор типа "упаковывает" типа по аналогии с тем, как конструктор "упаковывает" значение. Вот только конструкторы типов в рантайме не матчатся (в рантайме их нет). А "матчатся" в компайл-тайме инстансами классов типов и семействами типов.

V>Похоже, та специфика минималистичности Хаскеля, что одновременно с объявлением АлгТД объявляется (вводится) мн-во оборачиваемых им типов-туплов, совершенно сбивает тебя с толку.

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

V>И я догадываюсь — почему. Наверно от того, что в Хаскеле нет возможности дать символьный алиас типу некоего тупла для других остальных сценариев. Ну это проблемы Хаскеля право, а не сути вещей или системы типов. Дело в том, что размеченное объединение — это объединение уникальных типов. Даже если оборачиваемые типы имеют одинаковую структуру, их необходимо рассматривать как уникальные типы. Прямо как в С++, когда два разных класса имеют одинаковую структуру — они всё-равно являются разными типами. В этом плане boost::variant, например, не дотягивает до полноценных размеченных объединений, т.к. не в состоянии отличить при матчинге одинаковые типы, которые входят в variant.

Ну так boost::variant это не сумма, а объединение — чего вы от него хотите. variant< int, bool > это int или bool. С суммами все иначе: Either Int Bool не является ни Int ни Bool.
Поэтому variant не "недотягивает" до АлгТД — это вовсем другая штука со своими достоинствами и недостатками и слабопересекающейся с АлгТД областью применения.

Одно непонятно: зачем так фиксироваться на суммах? В описываемом примере они вовсе не используются. Тайплевел вычисления делаются на Nil и Cons, первый — единица с тегом, второй — произведение с тегом.

K>>Еще раз повторяю, если речь идет о типах. Типы в памяти ничего из себя не представляют (в рантайме). Их просто нет. А для значений да, все это верно (с оговорками). Вот только никакой интерпретации структуры типов в рантайме тут нет.
V>Такие вещи придется обосновать, бо любая модель типов предполагает некоторую технику реализации.

Реализация (в компиляторе) требуется. место в памяти в рантайме — нет. В рантайме нет типов.

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

Да ни в одной существующей реализации ПП нет никакого "бесконечного инстанцирования". Параметрический тип — не шаблон. Код-то один для всей (потенциальной) бесконечности типов. Всякие исключения с оптимизацией — не рассматриваем. Потому я и говорю, что для реализации ПП реализация шаблонов не подходит. И наоборот: шаблоны таким способом не реализовать в общем случае. Ничего удивительного в этом нет, потому что шаблоны и ПП вещи разные. Это и их типизации касается, и семантики компайл-тайм вычислений на них, и реализации.

K>>Ну правильно. Я тут так и писал. Код используется повторно ценой боксинга, такую цену за повторное использование сгенерированного кода C++ платить не может. Но мне справедливо напомнили, что я увлекаюсь деталями реализации. Ну а теперь вы увлекаетесь. Разница-то в системе типов.

V>Бесплатно что-ле всё? Я не спорил с работоспособностью примера, а лишь указал, какую цену мы за это платим.

Ну так я прямо говорю, что не бесплатно. Вы мои ответы вообще читаете? см. выделеное.

V>ИМХО, система типов — это не цель ни разу, а ср-во. Инструмент. Инструмент должен непротиворечиво работать. Программист обязан знать, как работает инструмент и сколько он за него платит, остальное — лирика. Я всего-навсего утверждаю, что для общего случая для самой возможности оперировать рекурсивными типами произвольной мощности (неизвестной в compile-time) требуется обязательное боксирование значений из-за необходимости сохранения однородной разметки в памяти.

Отлично. Т.е. вы объясняете мне то, что я сам использовал как главный аргумент против того, что шаблоны — параметрический полиморфизм, пока samius не одернул меня, указав что я концентрируюсь на реализации.

V>Всё-таки дотнет более чем убедительно показал, что статическая типизация и статическая компиляция — вовсе не одно и то же.

Я разве с этим спорю?

V>А ты неаккуратно используешь одно вместо другого, почему я и напомнил, что для Хаскеля вовсю используется сплошная динамическая типизация во время операций распаковки значений АлгТД через ПМ. Т.е. чуть ли не в каждой второй строчке среднестатистической программы.

Еще раз. Динамической типизации тут нет. a == 3 динамическая типизация? Нет, 3 не тип.

V> Ведь в приведенном примере работоспособность только от того, что два списка формируются параллельно:
V>main' n i as bs = main' (n-1) (i+1) (Cons (2*i+1) as) (Cons (i^2) bs)

Совершенно верно. Это масимум того, что можно получить от ML-like полиморфизма. Для большего нужны зависимые типы.

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

От того. Без поддержки ПП это не заработает.

V>Ну и в С++ вызов ф-ии — это ф-ии времени компиляции, а в Хаскеле — это обращение к группе ф-ий и выбор конкретной через паттерн-матчинг:
V>main' 0 _ as bs = scalarProduct as bs
V>main' n i as bs = main' (n-1) (i+1) (Cons (2*i+1) as) (Cons (i^2) bs)

Это не верно. Никакой группы функций нет. Вот так:

test' :: ScalarProduct a => Integer -> Integer -> a -> a -> Integer
test' n i as bs | n == 0    = scalarProduct as bs
                | otherwise = test' (n-1) (i+1) (Cons (2*i+1) as) (Cons (i^2) bs)

тоже сработает. Классы типов тут тоже ничего в рантайме не диспетчеризуют (для ранг-2 полиморфизма будут, но это здесь не используется).

V>В сухом остатке: хотя имеем статическую типизацию (проверку соответствий типов), конкретные типы проверяются в рантайм,

Не верно, все типы проверяются в компайл-тайм. Иначе как ошибка появилась бы при компиляции?

V> конкретные ф-ии тоже выбираются в рантайм

Не верно. Все функции выбираются в компайл-тайм.

V> и только затем вызываются.

Вызываются и впрямь в рантайме.

V>Куда ни плюнь — сплошная динамика... В общем, чудес, увы, не бывает.

Ага вся динамика n == 0. Но 0 не тип, так что эта динамика — не динамическая типизация. scalarProduct тоже ничего в динамике не проверяет. Cons не сумма, а произведение, так что значения просто выбираются по известным смещениям. Выбор между двумя видами scalarProduct происходит на этапе компиляции, классы типов без расширений в рантайме не работают.

V>В общем, если для С++ боксирование проэмулировать, то работать будет, но потеряем compile-time проверку одинаковых по длине списков.

Но весь смысл этого куска кода в compile-time проверке!

V>Проблема в С++ не в самой системе типов ни разу (если обсуждать приведенный пример), это ошибочное мнение. Проблема как раз в низлежащей технике реализации, т.е. в предоставляемых возможностях помимо системы типов. Получившая система типов — это следствие, а не причина.

Ну да. Я так и говорил: C++ не может себе позволить параметрический полиморфизм.

V>Попробую пояснить.

V>Единственным способом рантайм-полиморизма для С++ является диспетчеризация на таблице виртуальных ф-ий.

А в хаскеле без расширений, на котором код и написан рантайм-полиморфизма вообще нет.

V>Для сравнения, Хаскель сначала требует через ПМ распаковать содержимое АлгТД, т.е. уменьшить мощность (или "логическую косвенность") для нашего сценария рекурсивного типа

Сюрприз: в обсуждаемом коде на хаскеле 0 (ноль) рекурсивных типов.

V>, т.е. позволяет оперировать непосредственными полями только на одном уровне. Но если надо продвинуться дальше — опять требуется распаковка содержимого и т.д. пока не Nil. Итого, любая операция над АлгТД в Хаскеле сопровождается обслуживанием полиморфизма.

Вы опять рассуждаете так, как будто у нас сумма, да еще и рекурсивная:

data List = Cons Integer (List a) | Nil

а в коде-то — смотрите-ка:

data Nil = Nil

data Cons a = Cons Integer a

Никаких рекурсивных типов. Никаких сумм.

V>Аналог в технике С++ требовал бы обращение к любым полям через акцессоры — виртуальные ф-ии, которые вполне мог бы генерить компилятор, автоматически превращая поля в пару акцессоров (почему так? вспомни про предложение нарисовать карту памяти для небоксированного сценария)... Но сие малость неэфективно, если каждый чих будет полиморфным, а ведь С++ претендует на нишу самой эффективной на сегодня работы с памятью.

Вывод вы делаете правильный, а посылка — неверная. В случае хаскелевой реализации эти "аксессоры" не виртуальные, без рантайм диспетчеризации для произведений и с рантайм диспетчерезацией для сумм. Т.е проверки не везде — как в наследовании, а только там, где действительно по смыслу программы придется писать if, хоть в C++, хоть где. Но боксинг и лишняя косвенность и так дорого обходится, C++ такого позволить себе не может.

V>Единственно что мы можем сделать, это встроить в С++ полный аналог АлгТД из Хаскеля

Для описываемого фокуса вообще не нужен полный аналог АлгТД. Это тест на параметрический полиморфизм, а не на полность аналогии АлгТД,

V>Он знает только после распаковки содержимого и только в области видимости соответствующей ветки ПМ.

В подавляющем большинстве случаев у ПМ 1 (одна) ветка и все смещения нам уже извстны.

V>Чтобы распаковать полученное рекурсивное поле — надо опять делать ему ПМ и так до бесконечности в цикле (см код ф-ии scalarProduct). А ПМ как раз проверяет теги типов, т.е. это банальная рантайм-проверка типов.

Хаскель — не лисп. Тегов типов в нем нет. В обсуждаемом коде и теги конструкторов не проверяются — проверяется число на равенство 0.

V>Не путаю. Дескриминатор-то типа проверяется в рантайм.

Дескриминаторов типа в Хаскеле просто не существует (если вы не сделаете для типа инстансы Data/Typeable, обеспечив RTTI и не используете Data.Dynamic для всего того, что вы сейчас рассказываете. В обсуждаемом примере это не используется)

V>Получаем двухтактную схему — сначала проверка тега типа

Да не типа, а значения.

V>и выбор ветки алгоритма для этого запакованного типа, затем операция a == 3, где a — переменная шаблона ПМ. Ты ведь привел простой тип, а мы обсуждали алгебраический.

Integer — алгебраический тип (и по стандарту, а 3 — его конструктор) и в реализации. Не забудьте еще алгебраический тип Bool. True и False, кстати, тоже типы по-вашему?

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

Да. Там где проверять не нужно — там вы не будете проверять ни в хаскеле, ни в C++. Там где без этого не обойтись (например, это указатель на следующий элемент списка или на null) — вы будете проверять в рантайме и там и там.

V>У Хаскеля тоже своё ограничение: боксирование — это жутко неэффективная техника на классических архитектурах с плоской (неасоциативной) памятью. Я по характеру своей работы стараюсь избавляться от лишней косвенности, досигая порой прирост вдвое-четверо лишь только за счет вдвое меньшей коссвености. А тут буквально всё косвенно нафик...

О чем я и говорю — параметрический полиморфизм C++ не по карману.