Re[9]: Мифический Haskell - Декларативное программирование

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

K>Ага, классы типов — это такой недопролог, который интерпретируется, правда во время компиляции.

При чем тут классы типов и паттерн-матчинг алгебраических типов? Классы типов — это лишь проверяемые в compile-time ограничения, то бишь контракты. В данном случае класс типов дает знать, что для типа существует scalarProduct, который можно безопасно вызывать. Я обратил внимание на то, что сама реализация контракта была описана для разных значений дескриминатора АлгТД. Т.е. это такая фишка Хаскеля — при объявлении ф-ий доступен урезанный паттерн матчинг по дискриминаторам АлгТД, где конкретная ф-ия выбирается в рантайм по результатам матчинга.

V>>В отличие от Haskel, подобное преобразование типов (распаковка) для кода Tonal- выполняется в compile-time.

K>Это в хаскеле — во время компиляции. А в C++ такой код не написать.

Никогда в Хаскеле распаковка АлгТД не происходит во время компиляции.

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

K>Не понимаю, что за запакованный тип.

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

K>Для АлгТД статически проверяется множество населяющих его значений — как и у любого другого типа.

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

K>Типы, ни "запакованные", ни какие АлгТД не населяют, они населяют кайнд. Кайнды, конечно, тоже бывают алгебраическими.

Вид, сорт, тип — это синонимы в теории групп.

V>>Конкретный тип распаковывается исключительно в рантайм, а сама техника распаковки тождественна технике dynamic_cast (с точностью до деталей, то бишь с точностью до способа кодирования/представления токена типа для целей рантайма).

K>Каст преобразует тип значения. Матчинг АлгТД никаким преобразованием типов не занимается.

Опять неверно, dynamic_cast НЕ изменяет само значение, переданное по ссылке (это обязательно, использовать dynamic_cast можно только через ссылку или указатель), оно тестирует тип поданного значения и преобразует тип ссылки, а не само значение, предоставляя доступ затем к мемберам типа по ссылке. Матчинг АлгТД в Хаскеле аналогично проверяет в рантайм дискриминатор объединения, то бишь запакованный тип, примерно точно так же, как dynamic_cast проверяет токен типа (на который ссылается экземпляр типа через указатель на vtable), а удачная ветка матчинга затем предоставляет доступ к значению упакованного в АлгТД типа.

V>>Там, где ML-яык работает с боксированными значениями в рантайм

K>Какая разница, боксированы значения или нет, если речь идет о типах?

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

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

То бишь боксированность нам гарантирует одинаковый размер полей, т.е. одинаковую карту размещения для любого инстанса такого типа. Возвращаясь к примеру: в итоге, код ф-ии scalarProduct будет одинаков для всех узлов рекурсивного типа Cons int a.

K>Будут значения боксированными или нет — это вообще детали реализации, на статичность/динамичность системы типов не влияющие.

Угу, именно на это твое непонимание и обратил внимание. Статическая система типов хапрактерна не тлько статической проверкой контрактов. Упоминание эффективности статики как само собой разумеющееся (и даже ты тут отметился не раз в этой ветке, напоминая про статику) — это следствие того, что статически порожденный код ЗНАЕТ, как расположено в памяти значение оперируемого типа, и обращается к полям значения непосредственно, то бишь через фиксированные смещения в памяти, а не через дескрипторы/акцессоры.

V>>там мы имеем классическую эмуляцию динамики/интерпретации, хоть и со статическими проверками допустимости

K>Так динамика или стат. проверки? Тут одно из двух.

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

V>>мн-ва АлгТД в момент компиляции.

K>Что за "множество АлгТД"?

ОМГ

V>>инстанциировать типы целиком

K>А это что значит?

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

V>>Они не нужны только для боксированной реализации рекурсивных типов и прочей динамической типизации.

K>Типы не бывают "боксированными" — такими бывают значения. И к динамике это не имеет отношения. Динамика — это когда нет стат. типов, есть рантайм проверки. Типы в рантайме в хаскеле вообще не проверяются. В рантайме их нет — они уже стерты.

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

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

K>Ну и где тут (потенциальная) бесконечность типов? Верхняя граница тут явно задоается.

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

K>>>В C++ же кол-во типов всегда конечно, поэтому полиморфизм там только ad-hoc.

V>>Обычно для показанной техники делают adhoc только для BigN=0, но и это необязательно. Точнее сформулируем так: можно использовать только те типы, которые выводимы во время компиляции, т.е. независимы от данных. И тогда мн-во реально задействованных в программе типов ес-но будет конечным, но это могут быть любые типы из почти бесконечного объвленного мн-ва:

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

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

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

K>Нет. Ad-hoc это соседний класс. Никакого "чистого полиморфизма" не бывает. Бывают такие виды порлиморфизма: параметрический полиморфизм (дженерики), ad-hoc (перегрузка/специализация) и сабтайпинг (полиморфизм через наследование) + возможные сочетания.

Разве? Параметрический — это ортогонально чистому, бо может быть еще разновидность полиморфизма через утиную типизацию. Чистый полиморфизм — это который "одинаковый для всех случаев". ИМХО, в любом случае параметрический или любой другой вид полиморфизма превращается в ad-hoc в конечной точке, т.е. во время исполнения, коль используемые типы-параметры имеют различную структуру в памяти. Например, для генериков дотнета мы в ограничениях определяем контракт (напр. интерфейс), а затем вызываем методы интерфейса в коде. И, хотя код одинаков для всех типов с виду, но в момент вызова доступных из ограничений методов интерфейсов происходит runtime-ad-hoc через таблицу методов интерфейсов (перегрузка методов для конкретных this).

Отличие шаблонов С++ в том, что там так же доступен compile-time ad-hoc, который недоступен в генериках. Это из-за того, что для боксированных типов JIT генерит идентичный код, поэтому увеличивать мощность рекурсивных типов в рантайм в дотнете можно относительно дешево (это в плане приведенного примера). Если же имеем специализацию генерика небоксированным типом... то можно из двух строчек описания рекурсивного типа породить десятки мегабайт кода в compile-time.

Или же еще больше нагрузить JIT в рантайм, т.к. будет каждый раз генерироваться новый код.

Кстати, из-за последнего момента когда-то много лет назад я уже высказывал идею, что вполне можно было бы в генерики добавить compile-time ad-hoc, коль они для релиза 2-го дотнета разработали технику уникальной генерации методов для небоксированных типов. Т.е. раз такая техника есть, почему бы ее не использовать?

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

V>При чем тут классы типов и паттерн-матчинг алгебраических типов?

Понятия не имею. Это вы вдруг про паттерн-матчинг АлгТД заговорили.

V>Классы типов — это лишь проверяемые в compile-time ограничения, то бишь контракты.

Не только.

V>Я обратил внимание на то, что сама реализация контракта была описана для разных значений дескриминатора АлгТД.

Что такое "разные значения дескриминатора АлгТД"? Разные конструкторы?

V>Я обратил внимание на то, что сама реализация контракта была описана для разных значений дескриминатора АлгТД.

Если "декскриминаторы" — конструкторы, то нет. Кмплементации класса нельзя писать для разных конструкторов. Только для типов. Так в этом примере и сделано.

V>Никогда в Хаскеле распаковка АлгТД не происходит во время компиляции.

Если под "распаковкой" подразумевается паттерн-матчинг, то да, не происходит. Но в данном случае это и не нужно. Вычисления то тайплевелные — матчатся типы Nil и Cons. Они, естественно, матчатся в компайл-тайме, потому что в рантайме их просто нет.

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

Но у всех значений один и тот же тип — именно что АлгТД.

K>>Для АлгТД статически проверяется множество населяющих его значений — как и у любого другого типа.

V>Неверно, статически проверяется мн-во ТИПОВ населяющих его значений, но не сами значения

Откуда всялось множество типов? Проверяется принадлежность значения к множеству значений — типу.

V>Хаскель, в отличии от С++ НЕ умеет статически реагировать на сами значения (С++ умеет на целочисленные, в т.ч. на указатели).

Хаскель этого, понятное дело, не умеет. Зависимых типов в хаскеле нет. Точно так же и C++ не умеет. Статически "реагирует" он не нацелочисленные значения, а на целочисленные типы — типы кайнда Nat.

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

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

V>Вид, сорт, тип — это синонимы в теории групп.

А в теории типов — нет. Вид (кайнд) — это тип типа, а сорт — тип кайнда.

K>>Каст преобразует тип значения. Матчинг АлгТД никаким преобразованием типов не занимается.
V>Опять неверно, dynamic_cast НЕ изменяет само значение

Я и не говорю, что меняет значение — меняет тип.

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

Аналог dynamic_cast в Хаскеле — Data.Dynamic. Там действительно есть проверка типа в рантайме.

V>Матчинг АлгТД в Хаскеле аналогично проверяет в рантайм дискриминатор объединения,

Ну разумеется.

V> то бишь запакованный тип

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

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

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

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

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

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

V>То бишь боксированность нам гарантирует одинаковый размер полей, т.е. одинаковую карту размещения для любого инстанса такого типа. Возвращаясь к примеру: в итоге, код ф-ии scalarProduct будет одинаков для всех узлов рекурсивного типа Cons int a.

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

K>>Будут значения боксированными или нет — это вообще детали реализации, на статичность/динамичность системы типов не влияющие.

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

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

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

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

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

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

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

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

... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>

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

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

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

V>Дело не в шаблонах, а в переносе части типизации из статики в динамику для случая Хаскеля.

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

V>Рядом ответил подробнее, предлагаю обсуждать там.

ОК.

... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>

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

K>>Нет. Ad-hoc это соседний класс. Никакого "чистого полиморфизма" не бывает. Бывают такие виды порлиморфизма: параметрический полиморфизм (дженерики), ad-hoc (перегрузка/специализация) и сабтайпинг (полиморфизм через наследование) + возможные сочетания.

V>Разве? Параметрический — это ортогонально чистому, бо может быть еще разновидность полиморфизма через утиную типизацию.

Утиная типизация — это структурный сабтайпинг. разновидность сабтайпинга.

V> Чистый полиморфизм — это который "одинаковый для всех случаев".

Такой результат — однородный код — достигается разными видами полиморфизма.

V> ИМХО, в любом случае параметрический или любой другой вид полиморфизма превращается в ad-hoc в конечной точке, т.е. во время исполнения, коль используемые типы-параметры имеют различную структуру в памяти. Например, для генериков дотнета мы в ограничениях определяем контракт (напр. интерфейс), а затем вызываем методы интерфейса в коде. И, хотя код одинаков для всех типов с виду, но в момент вызова доступных из ограничений методов интерфейсов происходит runtime-ad-hoc через таблицу методов интерфейсов (перегрузка методов для конкретных this).

Интерфейсы в качестве констрейнтов дженериков — это, разумеется, ad-hoc полиморфизм, просто он тут взаимодействует с параметрическим полиморфизмом дженериков и сабтайпингом интерфейсов. И да, в чистом виде параметрический полиморфизм нигде не существует. Разве что в SML (с некоторыми оговорками вроде типов с проверкой на эквивалентность и перегрузки мат. операций). В подавляющем большинстве языков сложно взаимодействуют 2-3 разновидности полиморфизма. В случае C++ просто среди этих 2-х разновидностей параметрического не оказалось.
Что касается конечной точки то да, в большинстве реализаций параметрического полиморфизма, (и в C# и в Хаскеле и т.д.) предпринимаются действия для того, чтоб избавляться от боксинга, где это возможно, генерировать специализированный код и т.д. Но это детали реализации, тут обсуждается начальная точка.

V>Отличие шаблонов С++ в том, что там так же доступен compile-time ad-hoc, который недоступен в генериках. Это из-за того, что для боксированных типов JIT генерит идентичный код, поэтому увеличивать мощность рекурсивных типов в рантайм в дотнете можно относительно дешево (это в плане приведенного примера). Если же имеем специализацию генерика небоксированным типом... то можно из двух строчек описания рекурсивного типа породить десятки мегабайт кода в compile-time.

Или же еще больше нагрузить JIT в рантайм, т.к. будет каждый раз генерироваться новый код.

Compile-time ad-hoc в дженериках доступен в виде констрейнтов. Издержки реализации — понятны и обсуждались.

V>Кстати, из-за последнего момента когда-то много лет назад я уже высказывал идею, что вполне можно было бы в генерики добавить compile-time ad-hoc, коль они для релиза 2-го дотнета разработали технику уникальной генерации методов для небоксированных типов. Т.е. раз такая техника есть, почему бы ее не использовать?

... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>

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

_>Вообще из всех декларативных языков у меня настоящую симпатию вызвал только Пролог.

Тогда попробуй Меркури. Это типизированный аналог пролога. Хотя Прологу он тоже уступает по удобству.

Но пролог — это такая же игрушка как Хаскель. Даже Хаскель намного практичнее. По сути интересного в прологе только унификация и поиск с откатами. А это можно и в библиотеке воплотить. Уж в ДСЛ-е точно.

В коде вывода типов Немерла как раз используется специализированный язык унификации. Для своей задачи он очень удобен.

_>Все функциональные языки (считаем подвидом декларативных) как-то особых прелестей не показали, а недостатков кучи. Жаль что он всё же не подходит для наших реальных дел — тут точно только "фан".

Во-первых, прелесть у ФЯ достаточно, если сравнивать с С++, а не с Прлогом. При этом производительность полученного кода как раз можно сравнивать с С++, а не с Прологом (для которого она стремится к нулю).

_>Для дела же мне сейчас больше всего нравятся императивные языки с возможностями функциональности, метапрограммирования и т.п. Типа C++11, а лучше D и т.п.

_>Немерле посмотрю. ) Хотя пока не понял его ориентированность.

Дык в нем как раз ФП — это так, приятная мелочь. А главное в нем это как раз метапрограммирование (МП). Немерл — это язык с расширяемым синтаксисом и средствами МП позволяющими делать ДСЛ-и и автоматизировать работу.

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

_>Т.е. понятно что везде можно извернуться, но допустим на Питоне мы пишем скрипты (внутренние и серверные), но не большие проекты. А на C++ скрипты не пишем, хотя это возможно в теории.. Вот для чего Немерле лучше?

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

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

Это естественно не серебряная пуля и тем более не передовой край науки. Но посмотреть его будет интересно — это точно.

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

_>Остались ещё требования: быстродействие (в разумных пределах), доступ к системным функциям, возможность подключения (или наличие большого числа биндингов как у Питона) к C/C++ библиотекам.

В этом плане Немерл является практически полной копией C#-а. Быстродействие практически стакое же. Лучшим компиляторам С++ он конечно проиграет, но не порядки, а в лучшем случае разы. Но в общем, будет на уровне.

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

К С-библиотекам подключение идет теми же средствами.

С С++ по сложнее. У него нет внятного бинарного протокола. Но и тут есть выход. Есть C++CLI. С его помощью можно очень легко сделать обертку над любой С++-но библиотеку и уже эту обертку из любого дотнетного языка.

Скорость вызова методов из С ниже чем родных, но не так уж что бы это было критично. Скажем на работе с GDI разницу не заметить.

Кроме того в дотенете есть море библиотек на все случаи жизни. Они в сто раз удобнее чем использование сишных аналогов.

_>.Net в моих глазах — это недостаток. Для дела естественно, a для "фана" пофиг. Но вроде бы же говорят что планируется Немерле для нейтива.

Нет недостаток кода нужно вести разработку не под винду. Но и тут есть выход — можно.

В будущем мы планируем сделать бэкэнды для других платформ (в том числе и нативную). Но до этого еще далеко. Года три, точно.

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

V>>Кстати, из-за последнего момента когда-то много лет назад я уже высказывал идею, что вполне можно было бы в генерики добавить compile-time ad-hoc, коль они для релиза 2-го дотнета разработали технику уникальной генерации методов для небоксированных типов. Т.е. раз такая техника есть, почему бы ее не использовать?

Напомню, в бете второго дотнета для небоксированных типов для случая генериков происходило боксирование, а потом они добавили этот мощный инструмент, который превращает генерики в runtime ad-hoc для случая небоксированных типов.

K>1) Про ситуацию с бетой CLR 2 я тут уже писал.

А что писал?

K>2) В том и дело, что не рантайм, а компайл-тайм.

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

Здравствуйте, 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++ аналогично и то и другое либо опасно, либо безовасно за счет рантайм проверки. Но тип у массива любой длины — одинаковый. И у любого конструктора АлгТД — одинаковый. Ну так при чем тут динамическая типизация-то?

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

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

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

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

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

K>Мешает вид полиморфизма в C++
Не мешает. В компайл-тайме можно применить еще один Succ<T> и превзойти любую оценку, данную заранее.

S>>Но мы обсуждаем ПП, фичу языка, а не конкретную программу. Причем тут конкретная программа — непонятно.

K>При том, что фича языка позволяет писать определенный класс конкретных программ. А ее отсутствие — не позволяет.
Фича ПП позволяет ровно то, что написано в определении. А использовать ПП на бесконечном количестве типов — это уже другая фича.

K>Рассуждать про n программ, которые в сумме что-то реализуют — это софистика. Ну, как говорить, что (int,+,*) это не кольцо вычетов, а кольцо целых чисел, складывая модули кольца вычетов во всех возможных программах.
Угу, потому как нигде не написано что бесконечность типов при использовании ПП должна достигаться в одной программе.

K>>>Из определения парам. полиморфизма следует, что у нас есть, по крайней мере, один мономорфный тип () и один полиморфный forall a. Succ a с этим вы согласны?
S>>Нет. Из определения ПП следует лишь то, что такие типы полиморфным кодом должны обрабатываться единым образом.

K>Вы берете удобную для себя половину определения, которое я тут привел полностью.
По ссылке вы во второй части привели не часть определения, а описание формы ПП (согласно TAPL).

K>Одна только однородность кода не является каким-то характеристическим признаком параметрического полиморфизма. Сабтайпинг, например, тоже позволяет писать однородный код. Собственно, компилятор Java и переписывает однородный код на языке с параметрическим полиморфизмом в однородный код с использованием сабтайпинга на языке, в котором ПП нет вовсе.
Что и куда переписывается и чем исполняется — не суть важно. ПП в Java имеется. А вот

template <class T> struct Succ{};

Вполне удовлетворяет и "вторую часть" вашего определения по ссылке.

S>> А то что они должны существовать, да еще и в какой-то конкретной программе, да еще и потенциальной бесконечностью — увы, не следует.

K>А неудобную для вас вторую часть определения, о том, как однородный код типизируется вовсе отбрасываете. Из второй части определения следует, что они должны существовать.
Это не вторая часть определения, это форма. Бывает еще и предикативный ПП. Но из нее опять не следует бесконечность, а следует лишь возможность подстановки.
K>В C++ они, разумеется, не существуют. Шаблонный код на C++ вообще не может быть типизирован (отсюда и вся мощность шаблонов) и не типизируется. В некоторых реализациях вроде gcc проверяются кайнды (* или Nat), в некоторых, вроде, макрософтовской — даже кайнды не проверяются (ну или не проверялись раньше). Типизируется только инстанциация, результат применения. В языках с ПП типизируется и однородный код и само применение.
Мало что понял, но в C++ ПП импредикативный.

S>>что мешает сконструитьвать еще один тип в программе на C++? Разумеется, явно в коде, или в компайл-тайме.

K>Отсутствие в системе типов C++ типа forall a. Succ a.
Не мешает. Обычный такой

template <class T> struct Succ{};

Позволяет написать еще один тип.
Ну и конечно же, в системе типов C# тоже нет типа forall a. Succ a.

S>>Если обсуждаются примеры из http://migmit.livejournal.com/32688.html, то С# там их применяет в рантайме.

K>Покажите применение в рантайме из того кода.
см. _main<A>

S>>Тогда вопрос. Откуда C# в компайл тайм знает что надо применить как минимум 1000 типов? Для 1000 код работает, мог бы работать и для большего числа, если бы не StackOverflow.

K>Еще раз, параметрический код не требует для проверки знания числа типов. Ну, как типизация функции + над int не требует построения и типизации таблицы констант для всего декартова произведения двух множеств значений int.
Это не ответ. Ответ здесь в том, что С# конкретизирует такие типы в рантайме (точнее, в момент JIT компиляции, которую он вызовет для каждой конкретизации _main<A> по мере востребования). C++ так не умеет, потому ему нужно конкретизировать все в момент компиляции.

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

K>>Мешает вид полиморфизма в C++
S>Не мешает. В компайл-тайме можно применить еще один Succ<T> и превзойти любую оценку, данную заранее.

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

S>Фича ПП позволяет ровно то, что написано в определении. А использовать ПП на бесконечном количестве типов — это уже другая фича.

Приведенное мной док-во того, что вторая фича следует из первой вы, разумеется, игнорируете. Как же так?

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

Т.е. и 32-битный int — это тоже самое настоящее целое число?

S>По ссылке вы во второй части привели не часть определения, а описание формы ПП (согласно TAPL).

Что за описание формы? В первой части требование к коду, во второй к типам. Друг без друга они смысла не имеют.

S>Что и куда переписывается и чем исполняется — не суть важно. ПП в Java имеется. А вот
S>

S>template <class T> struct Succ{};
S>

S>Вполне удовлетворяет и "вторую часть" вашего определения по ссылке.

Нет, это не описание типа и не код, который можно типизировать в рамках системы типов C++. Это шаблон порождающий код, который только после этого будет типизирован.

K>>В C++ они, разумеется, не существуют. Шаблонный код на C++ вообще не может быть типизирован (отсюда и вся мощность шаблонов) и не типизируется. В некоторых реализациях вроде gcc проверяются кайнды (* или Nat), в некоторых, вроде, макрософтовской — даже кайнды не проверяются (ну или не проверялись раньше). Типизируется только инстанциация, результат применения. В языках с ПП типизируется и однородный код и само применение.
S>Мало что понял, но в C++ ПП импредикативный.

Если что-то непонятно, задайте конкретные вопросы. Импредикативность тут вообще не обсуждвется.

S>Позволяет написать еще один тип.

Вот и MigMit думал, что позволяет. Попробовал — не позволило. А вы в упор смотрите на пример где не позволяет и говорите "позволяет!".

S>Ну и конечно же, в системе типов C# тоже нет типа forall a. Succ a.

В системе типов C# 2 и выше — есть.

S>>>Если обсуждаются примеры из http://migmit.livejournal.com/32688.html, то С# там их применяет в рантайме.

K>>Покажите применение в рантайме из того кода.
S>см. _main<A>
Смотрим:

  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)); 
    }
  }

Видим 0 (ноль) применений в рантайме. Зачем же вы обманываете?

S>Это не ответ. Ответ здесь в том, что С# конкретизирует такие типы в рантайме

Это неверный ответ.

S> (точнее, в момент JIT компиляции, которую он вызовет для каждой конкретизации _main<A> по мере востребования).

JIT-компилятора для C# не существует в природе. Допустим, что мы обсуждаем JIT-компиляцию CIL. Вы утверждаете, что в link-time, ngen-ом этот код полностью не скомпилировать?
И как быть с Java у которой в байт-коде нет ПП и, следовательно, нет смысла о JIT говорить? Как быть с хаскелем?
Главный вопрос: как мы получаем ошибку компиляции C# за долго до того, как полиморфный код якобы скомпилируется в рантайме.

S>C++ так не умеет, потому ему нужно конкретизировать все в момент компиляции.

Нужно конкретизировать все до момента тайпчека, вы хотели сказать?

... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>

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

K>>1) Про ситуацию с бетой CLR 2 я тут уже писал.

V>А что писал?

Писал что никаких специализаций для value-типов JIT в бете не генерировал: 9-я строка с конца.

K>>2) В том и дело, что не рантайм, а компайл-тайм.

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

Почему рантайм-то? Берете ngen и компилируете в link-time. Точно так же и Хаскель, если может сгенерировать специализированный код при межмодульном анализе — специализирует и даже от боксинга избавится, где это возможно.

... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>

Здравствуйте, 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++ не по карману.

... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>

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

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

K>>>Мешает вид полиморфизма в C++
S>>Не мешает. В компайл-тайме можно применить еще один Succ<T> и превзойти любую оценку, данную заранее.

K>Вот вы говорите можно, а из обсуждаемого здесь опыта известно, что нельзя. Как же так?
Здесь обсуждается другой опыт. А опыт написать Succ<Succ<Succ<...>>> сколько ума хватит раз не обсуждается.

S>>Фича ПП позволяет ровно то, что написано в определении. А использовать ПП на бесконечном количестве типов — это уже другая фича.

K>Приведенное мной док-во того, что вторая фича следует из первой вы, разумеется, игнорируете. Как же так?
Вторая фича тут — это импредикативность, верно? Вы доказывали что-то другое, причем я ответил по этому доказательству.

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

K>Т.е. и 32-битный int — это тоже самое настоящее целое число?
Нет. Я же согласился что это софистика.

S>>По ссылке вы во второй части привели не часть определения, а описание формы ПП (согласно TAPL).

K>Что за описание формы? В первой части требование к коду, во второй к типам. Друг без друга они смысла не имеют.
Предикативный и импредикативный — это формы, а не определение ПП.

S>>Вполне удовлетворяет и "вторую часть" вашего определения по ссылке.

K>Нет, это не описание типа и не код, который можно типизировать в рамках системы типов C++. Это шаблон порождающий код, который только после этого будет типизирован.

Succ<Succ<int> > v;

Так пойдет?

K>Если что-то непонятно, задайте конкретные вопросы. Импредикативность тут вообще не обсуждвется.
Вы дали ссылку и по ссылке вторым пунктом импредикативность. Что же вы обсуждаете, если не импредикативность?

S>>Позволяет написать еще один тип.

K>Вот и MigMit думал, что позволяет. Попробовал — не позволило. А вы в упор смотрите на пример где не позволяет и говорите "позволяет!".
У него не получилось кое-что другое, о чем я не говорю. А вот написать наперед заданное число раз Cons<Cons<... он не попробовал. А это помогло бы

S>>Ну и конечно же, в системе типов C# тоже нет типа forall a. Succ a.

K>В системе типов C# 2 и выше — есть.
Аналога explicit forall в C# нет. Если бы был, можно было бы описать абстракцию функтора/монады и не пришлось бы жарить уток как в Query expression pattern.

S>>см. _main<A>
K>Смотрим:
K>

K>  public static int _main<A>(int n, int i, A first, A second) where A : ScalarProduct<A> {
K>    if (n == 0) {
K>      return first.scalarProduct(second);
K>    } else {
K>      return _main(n-1, i+1, new Cons<A>(2*i+1,first), new Cons<A>(i*i, second)); 
K>    }
K>  }
K>

K>Видим 0 (ноль) применений в рантайме. Зачем же вы обманываете?
Мало ли что мы тут видим. Типы применяются во время выполнения, для каждого рекурсивного вызова _main выполняется докомпиляция JIT-ом.

S>>Это не ответ. Ответ здесь в том, что С# конкретизирует такие типы в рантайме

K>Это неверный ответ.
Аргументы?

S>> (точнее, в момент JIT компиляции, которую он вызовет для каждой конкретизации _main<A> по мере востребования).

K>JIT-компилятора для C# не существует в природе. Допустим, что мы обсуждаем JIT-компиляцию CIL. Вы утверждаете, что в link-time, ngen-ом этот код полностью не скомпилировать?
Не так. в один проход мы его скомпилируем, но по мере необходимости рекурсивных вызовов он будет докомпиляться.
А где-нибудь в сингулярити, где JIT-а нет, такой код работать не будет и мы получим ситуацию в точности как с C++.

K>И как быть с Java у которой в байт-коде нет ПП и, следовательно, нет смысла о JIT говорить? Как быть с хаскелем?
А никак не надо быть, мы ведь обсуждаем ПП ЯВУ а не байт-кода.

K>Главный вопрос: как мы получаем ошибку компиляции C# за долго до того, как полиморфный код якобы скомпилируется в рантайме.
О какой конкретно ошибке речь? Вообще-говоря, С# проверяет ограничения при компиляции в IL и получает гарантии что они не будут нарушены в рантайме. Если такая проверка обламывается, мы получаем ошибку времени компиляции в IL. Если нет — то в JIT все будет как по рельсам.

S>>C++ так не умеет, потому ему нужно конкретизировать все в момент компиляции.

K>Нужно конкретизировать все до момента тайпчека, вы хотели сказать?
наверное

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

K>>Вот вы говорите можно, а из обсуждаемого здесь опыта известно, что нельзя. Как же так?
S>Здесь обсуждается другой опыт. А опыт написать Succ<Succ<Succ<...>>> сколько ума хватит раз не обсуждается.

Да не написать Succ<Succ<Succ<...>>> а получить еще один из готового. Как тут:

instance ScalarProduct a => ScalarProduct (Cons a)

S>Вторая фича тут — это импредикативность, верно?

Нет, не верно.

S>Вы доказывали что-то другое, причем я ответил по этому доказательству.

Вы по доказательству ответили, что оно не считается и все тут.

K>>Т.е. и 32-битный int — это тоже самое настоящее целое число?
S>Нет. Я же согласился что это софистика.

И чем, по-вашему, это обоснование через "все возможные" программы отличается от вашего?

S>Предикативный и импредикативный — это формы, а не определение ПП.

Точно. И что? Импредикативного никто и не требует.

S>Вы дали ссылку и по ссылке вторым пунктом импредикативность. Что же вы обсуждаете, если не импредикативность?

Ок. Выкинте упоминание об импредикативности — оно там "для справки".
1) Возможность написать однородный (работающий одинаково для любого типа) код
2) Типизировать этот код обобщенным типом, содержащим переменные, которые конкретизируются применением обобщенного типа к конкретному.

Типизировать шаблонный код в C++ нельзя вообще никак.

S>У него не получилось кое-что другое, о чем я не говорю. А вот написать наперед заданное число раз Cons<Cons<... он не попробовал. А это помогло бы

Нда. Кто decl читал — тот в цирке не смеется.

K>>В системе типов C# 2 и выше — есть.
S>Аналога explicit forall в C# нет. Если бы был, можно было бы описать абстракцию функтора/монады и не пришлось бы жарить уток как в Query expression pattern.

1)explicit forall не обязателен для такого простого типа. Он тут для понятности. explicit forall, кстати, в Хаскеле без расширений нет.
2)В C# он наоборот есть — программист просто обязан писать его в сигнатуре:

T foo<T>(Bar<T> a)

что то же самое, что

foo :: forall t. Bar t -> t

В хаскеле же писать его не обязательно, там где он очевиден — это просто сахар.

S>Мало ли что мы тут видим.

Видим все что надо

S>Типы применяются во время выполнения

Нет, не применяются. Как выглядит применение во время выполнения в C# мы уже обсудили.

S>, для каждого рекурсивного вызова _main выполняется докомпиляция JIT-ом.

Зачем его докомпилировать? Это же ссылочные типы, для них никакие специализации не нужны!

S>Аргументы?

Аргументы ниже.

K>>JIT-компилятора для C# не существует в природе. Допустим, что мы обсуждаем JIT-компиляцию CIL. Вы утверждаете, что в link-time, ngen-ом этот код полностью не скомпилировать?
S>Не так. в один проход мы его скомпилируем, но по мере необходимости рекурсивных вызовов он будет докомпиляться.
S>А где-нибудь в сингулярити, где JIT-а нет, такой код работать не будет

Докажите, что он не будет там работать.

K>>И как быть с Java у которой в байт-коде нет ПП и, следовательно, нет смысла о JIT говорить? Как быть с хаскелем?
S>А никак не надо быть, мы ведь обсуждаем ПП ЯВУ а не байт-кода.

Так и я о том же. По вашему параметрические типы должны применятся в рантайме. Поэтому вы и обсуждаете компиляцию байткода в котором ПП есть. И только рантаймовую — возможность линктаймовой компиляции вы полностью игнорируете. В случае с C# лично для меня ситуация с рантаймом понятна, но вокруг нее столько всяких недопониманий и суеверий, что я просто сразу предлагаю: обсуждаем случаи, в которых никаких двусмысленностей нет: в Java и Haskell параметрические типы не могут применятся в рантайме в принципе потому, что в рантайме они не существуют.

K>>Главный вопрос: как мы получаем ошибку компиляции C# за долго до того, как полиморфный код якобы скомпилируется в рантайме.
S>О какой конкретно ошибке речь?

Об ошибке, когда код генерирует неравные списки. Она возникает в компайл-тайм.

S>Вообще-говоря, С# проверяет ограничения при компиляции в IL и получает гарантии что они не будут нарушены в рантайме. Если такая проверка обламывается, мы получаем ошибку времени компиляции в IL. Если нет — то в JIT все будет как по рельсам.

Т.е. вы хотите сказать, что система типов второго C# unsound, статически проверить безопасность компилятор не может. Спорить с этим сложно, потому что благодаря таким мегафичам как ковариантность массивов и даункасты — так оно, собственно, и есть. С дженериками C# таких проблем, правда, нет, но мне проще обсудить полиморфизм на примере другого языка, чем вас в этом убедить.

K>>Нужно конкретизировать все до момента тайпчека, вы хотели сказать?
S>наверное

Ну, тоесть параметрических типов в C++ нет, а параметрический полиморфизм, по вашему, есть? Оригинально.

... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>

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

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

В каких разных? Продемонстрируй плиз разные пространства имен для конструктора АлгТД и для одноименного идентификатора метки типа в конструкции ПМ некоего значения, созданного с помощью этого конструктора.

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

K>Курим:
K>

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

K>Т.е. все как я и сказал. Никакие типы в АлгТД не упаковываются. Упаковываются значения.

Эээ... колега, а что вообще могло бы означать "упаковка другого типа" для АлгТД? Можно мне поинтересоваться, что другое ты мог подумать? Как ты себе представляешь упаковку самих типов, а не их значений в системе, где описательная информация о типах недоступна?

Вот фраза, вызвавшая сложность в понимании:

Матчинг АлгТД в Хаскеле аналогично проверяет в рантайм дискриминатор объединения, то бишь запакованный тип.

А если так перефразировать:
Матчинг АлгТД в Хаскеле аналогично проверяет в рантайм дискриминатор объединения, то бишь тип запакованного значения.

(По моему ИМХО, одно упоминание АлгТД подразумевает все связанные с этим детали, которые не обязательно повторять в каждом предложении.)

K>Ну, может и можно сказать, что конструктор типа "упаковывает" типа по аналогии с тем, как конструктор "упаковывает" значение. Вот только конструкторы типов в рантайме не матчатся (в рантайме их нет).

А как конструкторы могут матчиться? Ведь конструктор — это ф-ия. Может матчиться лишь некое ID размеченного объединения, то бишь матч всегда идет по ЗНАЧЕНИЮ, в данном случае это значение метки типа. Т.е. можно сказать, что идет матч по типу завернутого значения.

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

Угу, ты повторно налегаешь на подтипирование, хотя я его не упоминал. Я догадываюсь, что ты намекаешь на реализацию наподобие АлгТД в Немерле, но я-то здесь при чем?

Размеченное объединение обязательно хранит метку обернутого в АлгТД типа. Почему именно типа? Потому что согласно определения, размеченное объединение хранит в себе не только сам элемент, но обязательно некий уникальный идентификатор мн-ва, к которому принадлежит хранимый элемент. Мн-во — это тип, элемент мн-ва — это значение типа.

data List a = Nil | Cons a (List a)

Для значения дескриминатора Nil_tag хранится tuple(/*empty*/), для значения Cons_tag хранится tuple(a, List<a>). Оба тупла и есть хранимые значения. Но сии значения-туплы имеют тип, как ни крути. Теперь перечитай ту фразу еще раз:

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

Я теперь более чем уверен, что это именно так.

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

K>Ну так boost::variant это не сумма, а объединение — чего вы от него хотите. variant< int, bool > это int или bool.

Не так, это еще хранимый признак типа, как и положено. Поэтому это или container<0, int> или container<1, bool>. Т.е. в плане хранения — дотягивают. Они недотягивают в момент диспетчеризации по конкретным хранимым типам, бо для одного и того же типа будет вызвана одна и та же ветка диспетчеризации, хотя их контейнер имел разные типы, например для случая variant<int, bool, int> будет вызвана одна и та же ветка диспетчеризации в клиентском коде для container<0, int> и для container<2, int> с аргументом просто int, т.е. эти случаи будут неразличимы. Жаль. Было бы неплохо генерить ошибку компиляции для случая одинаковых типов.

K>С суммами все иначе: Either Int Bool не является ни Int ни Bool.

Как я только что показал — вовсе не иначе. Проблема в сценариях и гарантиях. Хотя, проблему нетипизированного union они решили.

K>Поэтому variant не "недотягивает" до АлгТД — это вовсем другая штука со своими достоинствами и недостатками и слабопересекающейся с АлгТД областью применения.

Ну как раз область применения пересекается нормально. Особенно для случая уникальных типов в варианте. И особенно в случае boost::make_recursive_variant — как раз под такие же сценарии.

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

Да пофиг. Реализация инстансов классов на технике-аналоге vtable ничем по-сути от происхоящего с помощью АлгТД не отличается. Вернее, наоборот, реализация матча по АлгТД во многих сценариев может быть выполнена на таблицах ф-ий.

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

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

Для тега алгТД место в рантайме таки требуется.

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

Повторю, для алгТД есть:

data Box = IntBox int | StringBox string

isThree Box b =
  case b of
    IntBox a -> a == 3
    StringBox a -> a == '3'

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

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

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

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

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

Да неполноценный это ПП ни разу. В любой точке примера используется один и тот же тип для обоих списков, а потом заявляется, что мы якобы проверяем что типы одинаковы. Хотя такими их объявили сами же. Хочется спросить автора — он хорошо себя чувствует?

Нет ничего проще взять тот же самый n, сформировать сначала один список, потом другой, потом попробовать проделать тот же самый фокус. И хотя тип списков будет опять одинаковый, но фокус уже не сработает. Где ты там увидел работающее ПП? В примере показан несложный трюк, основанный на том, что компилятор Хаскеля способен два одинаково объявленных типа в одной области видимости считать одинаковыми. Стоит выйти из области видимости — и всякое ПП исчезает.

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)

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

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

K>тоже сработает.

Угу, как возражение, что при вызове ф-ий используется неявное ПМ привел явную реализацию на ПМ. Поздравляю.

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

Табличная диспетчеризация таки есть.

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

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

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

K>Выбор между двумя видами scalarProduct происходит на этапе компиляции

Каким образом? Чтобы выбор сделать, надо отказаться от боксированного представления, т.е. заранее знать, где конец списка. Если же в compile-time компилятор не знает где конец, то данные надо связывать с кодом, например посредством таблиц ф-ий.

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

Да нет там никакой проверки, не изобретай! Ограничение идет прямо в самой сигнатуре main':
main' :: ScalarProduct a => Integer -> Integer -> a -> a -> Integer

Т.е. в самой сигнатуре main' черным по белому сказано, что a->a. Как можно было потом радоваться, что у нас скомпиллировалась строчка в теле main':
scalarProduct a1 a2
или
scalarProduct (Cons x a1) (Cons y a2)
если a1 и a2 имеют один и тот же тип по опредедению main'?

Это как написать x = 2 * 2 и радоваться, что получилось 4.

Ты мне покажи вот так:
main' :: Integer -> Integer -> a -> b -> Integer

Потом подай на a и b одинаковые типы извне. Вот это и будет настоящий ПП, а не тот, которым вы хотите незаслуженно обозвать систему типов Хаскеля.

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

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

K>data Nil = Nil
K>data Cons a = Cons Integer a
K>

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

Ну коль Cons a параметризируется типом Cons a', то у нас выходит, скажем, де-факто параметрический рекурсивный тип в примере. Дело в том, что в С++ возможны только такого рода рекурсивные типы, если рекурсия объявлена по-значению (через поле или базовый класс), а не по ссылке/указателю. В приведенной неудачной попытке реализации примера на С++ был именно этот вид рекурсии.

И да, как раз случай простого боксирования для обычного рекурсивного типа неинтересен, бо код действительно будет один и тот же на любой глубине рекурсии, т.к. тип один и тот же. Гораздо интереснее вариант такой полиморфной рекурсии, как в примере. Если код main' должен быть одинаковым для каждого шага рекурсии (а он однозначно должен быть одинаковым, коль n может быть сколь угодно большим и неизвестным в compile-time), то должна присутствовать та или иная техника диспетчеризации вызова интерфейсной ф-ии scalarProduct.

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

K>Дескриминаторов типа в Хаскеле просто не существует

True, False, Cons, Nil — вот тебе существующие в рантайм дискриминаторы, хранимые вместе с данными. Для случая True, False, Nil данные представляют из себя пустой тупл.

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

Это конструкторы АлгТД в одном контексте и теги АлгТД, то бишь теги хранимого типа — в другом, например в конструкции ПМ. А что, тебя смущает вырожденный случай размеченного объединения навроде Bool?

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

Это если у нас связанный список боксированных вычислений, то будет так же. А так-то вычисления на подобных шаблонных рекурсивных типов на С++ не то, что не рекурсивны, там даже циклов нет с проверками, есть просто линейный код, повторенный столько раз, сколько глубина рекурсии. Ну и оптимизация в регистрах получается существенная, т.к. помимо ухода затрат на организацию цикла, освобождаются лишние регистры, т.е. кач-во оптимизации выходит получше. Например, для фильтрации нерекурсивным фильтром, эта техника дает увеличение в 1.8-3 раза по сравнению с вариантом двух вложенных циклов... Там же еще играют роль всякие вещи: например, ветвление по выходу из цикла в 100% случаев провоцирует сброс конвейера процессора, а в случае цепочек таких линейных вычислений — никогда. В общем, факт в том, что любой if — тоже дорогая операция, бо может сбросить конвейер. Виртуальные ф-ии в этом плане предпочтительней тега АлгТД, т.к. адрес выбирается безусловно механизмом процессора еще до исполнения инструкции ядром, и плюс компилятор оптимизирует так, что адрес ф-ии достается в начале цикла лишь однажды.

	От:	Klapaucius
	Дата:	22.03.12 10:01
	Оценка:

	От:	vdimas
	Дата:	22.03.12 12:05
	Оценка:	+1

	От:	vdimas
	Дата:	22.03.12 12:18
	Оценка:

	От:	vdimas
	Дата:	22.03.12 12:44
	Оценка:

	От:	Klapaucius
	Дата:	22.03.12 13:09
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	22.03.12 21:54
Оценка:

От:	samius	http://sams-tricks.blogspot.com
Дата:	23.03.12 06:13
Оценка:

	От:	VoidEx
	Дата:	24.03.12 17:18
	Оценка: