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

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

Я предыдущее скипнул, бо оно подводит именно к этой фразе.

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

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


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

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

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


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

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

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


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

Вот те раз? А Дед Мороз тоже существует?
Бесплатно что-ле всё? Я не спорил с работоспособностью примера, а лишь указал, какую цену мы за это платим.

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

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


K>И в гипотетической реализации C++ где скомпилированный код повторно используется (это только для частных случаев можно будет сделать) и все забоксено — этот код или не будет работать все равно, или это будет не C++. Речь то о системе типов и семантике языка.

Ну... если бы не куча прочитанных недостойных ярлыков здесь, я бы и не влез. Назвать систему шаблонов С++ макросами на стероидах можно только при очень поверхностном знакомстве. Ведь в приведенном примере работоспособность только от того, что два списка формируются параллельно:
main' n i as bs = main' (n-1) (i+1) (Cons (2*i+1) as) (Cons (i^2) bs)
а не от того, что полностью поддерживается параметрический полиморфизм в том смысле, как нам пытаются показать в примере. Сформируй два списка одинаковой длины независимо и попробуй подать на scalarProduct. Увидишь, что это такие же макросы на стероидах (С) как и в С++.

Ну и в С++ вызов ф-ии — это ф-ии времени компиляции, а в Хаскеле — это обращение к группе ф-ий и выбор конкретной через паттерн-матчинг:
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)

В сухом остатке: хотя имеем статическую типизацию (проверку соответствий типов), конкретные типы проверяются в рантайм, конкретные ф-ии тоже выбираются в рантайм и только затем вызываются. Куда ни плюнь — сплошная динамика... В общем, чудес, увы, не бывает.

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

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

Единственным способом рантайм-полиморизма для С++ является диспетчеризация на таблице виртуальных ф-ий. Так вот, в случае боксирования будет возможна техника, аналогичная АлгТД, только вместо тега размеченного объединения может быть использована vtable. Итого детали реализации меняются — суть нет, т.е. поведение системы типов для рассматриваемого сценария могли быть быть идентичными, останется только реализовать открывшиеся возможности аналогичного ПП... Так вот, эта гипотетическая реализация была бы НЕПРОТИВОРЕЧИВОЙ, тогда и только тогда, когда в С++ не было такой вещи, как прямой доступ к полям типов. Именно в момент этого доступа возникает противоречие с придуманной системой типов для нашего нового гипотетического С++ с ПП. Для сравнения, Хаскель сначала требует через ПМ распаковать содержимое АлгТД, т.е. уменьшить мощность (или "логическую косвенность") для нашего сценария рекурсивного типа, т.е. позволяет оперировать непосредственными полями только на одном уровне. Но если надо продвинуться дальше — опять требуется распаковка содержимого и т.д. пока не Nil. Итого, любая операция над АлгТД в Хаскеле сопровождается обслуживанием полиморфизма. Аналог в технике С++ требовал бы обращение к любым полям через акцессоры — виртуальные ф-ии, которые вполне мог бы генерить компилятор, автоматически превращая поля в пару акцессоров (почему так? вспомни про предложение нарисовать карту памяти для небоксированного сценария)... Но сие малость неэфективно, если каждый чих будет полиморфным, а ведь С++ претендует на нишу самой эффективной на сегодня работы с памятью. Поэтому аппарат типов он использует лишь как ср-во разметки этой памяти для своих нужд. Поэтому-то в С+ run-time полиморфизм скорее опциональный инструмент, чем целевой. Вот и получается, что система типов, помимо своего класса принадлежности в теории типов, так же ограничивается желаемыми характеристиками языка. Хотим неполиморфно обращаться к памяти — закрыли себе часть св-в типов by design. Ругать получившуюся систему типов можно будет затем лишь от непонимания причинно-следственных связей характеристик языка и подходящей под эти характеристики системы типов.

Единственно что мы можем сделать, это встроить в С++ полный аналог АлгТД из Хаскеля, и тогда на такой разновидности полиморфизма можно будет делать аналогичные фокусы. Вроде как-то уже обсуждалось, что это было бы возможно и интероперабельно с другими типами С++, т.е. такие типы можно было бы вкладывать в другие типы, а те, в свою очередь, в АлгТД. Ну и платить ровно такую же цену в итоге.

K>Ну так он и в хаскеле знает смещения и расположения в памяти. Теги "типов" как в динамике он в рантайме не проверяет.

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


V>>Мн-во допустимых типов значений АлгТД проверяется статически, конкретный тип из множества — динамически. Какие проблемы-то?

K>Ну так динамически проверяются значения, а не типы. точно так же, как и в C++. В чем динамическая типизация-то?
K>Вот a == 3 — проверка динамическая, а типизация — сатическая, потому, что и код сравнения и структура для хранения 3 в памяти известна на этапе компиляции. Вы как-то систематически типы и значения путаете.

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

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

K>Для самой рекурсивной структуры данных — да. Точно так же, как и в C++.

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


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

K>Ну да, безопасность размеченных объединений по сравнению с неразмеченными достигается рантайм проверкой. Точно так же как и с доступом по индексу в массиве, например. Но какое это отношение имеет к типизации? В C++ аналогично и то и другое либо опасно, либо безовасно за счет рантайм проверки. Но тип у массива любой длины — одинаковый. И у любого конструктора АлгТД — одинаковый. Ну так при чем тут динамическая типизация-то?

Для случая рекурсивных типов — причем. Для С++ была предложена для сравнения техника, когда рекурсивный тип должен был быть воплощен без боксирования. А в этом случае в С++ никакой динамической типизации для доступа к след. уровню рекурсии не требовалось. Вот и выходит, что с одной стороны это эффективней, с другой стороны — ограничение.

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