DM>Кажется, ты все время срываешься с обсуждения ЯП в целом и существующих ЯП на обсуждение гипотетического языка твоей мечты, эдакого мегаС++. Который должен уметь то и предоставлять это.
обсуждение ЯП в целом включает в себя задачу: как меняются ЯП от прошлого к настоящему и куда эти изменения будут двигаться дальше.
DM>А мне пофиг на долю, мы говорим о теории ЯП и систем типов, а не о рынке браузеров. Нет в спецификации языка — значит нет в языке.
ты сейчас имеешь ввиду спецификацию де юре, а большая часть мира работает по спецификации де факто.
DM>Ты только что сузил спектр обсуждаемых языков до ассемблера. Ни в каком другом языке ты не можешь всем этим управлять с нужной точностью.
в c/c++ сложно, но можно, чем все обычно и занимаются
DM>Я лишь опроверг твой тезис о том, что то определение типа диктует его определенное представление. Представление может быть и другим, но необязательно таким, какое ты просишь дальше.
в реальном коде, кроме определения типа будут еще использованы функции по его созданию, а вот эти функции уже не отмапишь на массив (тем более неявно компилятором)
Здравствуйте, DarkGray, Вы писали:
DG>в chrome входит, в IE — хз. и это означает, что код для FF и chrome будет работать быстро, а IE — медленно, и доля IE сократится еще в два раза. DG>и пофигу что там говорит стандарт.
Ну если уж даже на стандарт пофигу, то нам вас точно не переубедить
DG>>ты сейчас имеешь ввиду спецификацию де юре, а большая часть мира работает по спецификации де факто.
VE>Хотел бы я с вами не системы типов, а, например, теорию категорий пообсуждать. Мне кажется, и там бы вы нашли способ обсуждать практику, а не теорию.
система типов и есть частный случай теории категорий и ее практической применение
DG>>система типов и есть частный случай теории категорий и ее практической применение
VE>То-то и оно. Оказывается, категория, это не класс объектов и морфизмы, а ещё и маппинги объектов на их расположение в памяти.
DG>>>система типов и есть частный случай теории категорий и ее практической применение
VE>>То-то и оно. Оказывается, категория, это не класс объектов и морфизмы, а ещё и маппинги объектов на их расположение в памяти.
DG>для кого оказывается?
Видимо, для того, кто упорно это приплетает в обсуждение системы типов.
Здравствуйте, vdimas, Вы писали:
M>>Вот тут, например, что является уточнёнными типами? M>>[haskell] M>>data T = A A1 A2 ... M>> | B B1 B2 ...
V>Tuple(A1, A2) и Tuple(B1, B2).
Т.е. тип значения A a1 a2 ... — Tuple(A1,A2,..), так что ли?
Здравствуйте, mima, Вы писали:
M>Т.е. тип значения A a1 a2 ... — Tuple(A1,A2,..), так что ли?
Хаскельный алгебраик — это сумма (копроизведение) произведений. Так что формально T — это сумма Tuple(A1, A2, ...) и Tuple(B1, B2, ...). Каждый из них — отдельный тип, их сумма — третий тип, отличный от обоих.
Здравствуйте, VoidEx, Вы писали:
VE>У нас тут оверхед, потому что на деле нужен только один элемент из массива (остальные всё равно средствами самого Haskell не получить из-за свойств языка), но вот такова реализация. Зато память интерпретируется достоверно.
Это она где-то в середине операции интерпретируется достоверно. А до начала операции достоверно ничего неизвестно.
И да, это очередная эмуляция механики происходящего в Хаскель, поздравляю.
VE>Это я для простоты нарисовал массив, на деле-то можно сгенерировать структурку с типизированными указателями.
Это ничего не изменит, так же как в твоей реализации union на "типизированной" структуре их 2-х указателей. Все равно до проверки указателей неизвестно, по какому из них лежит целевое значение, т.е. неизвестно, как интерпретировать содержимое АлгТД-обертки.
VE>2. Давай реализуем АлгТД как: функция, принимающая кортеж обработчиков, и вызывающая ровно один из них при каждом case of.
VE>
VE>// Either a b
VE>typedef std::function<void (ptr)> onData;
VE>typedef std::function<void (onData, onData)> either;
VE>// foo e = case e of
VE>// Left x -> expr1
VE>// Right y -> expr2
VE>void foo(either const & e)
VE>{
VE> e([] (ptr x) { expr1 }, [] (ptr y) { expr2 });
VE>}
VE>
VE>Теперь АДТ — функция.
А что поменялось? Кто-то должен будет сделать диспетчеризацию, т.е. выбрать саму ф-ию в любом случае.
Даже это было необязательно. Бо ты здесь ограничен примитивами С++, а компилятор может сделать простой jump/call по косвенной адресации. При нормальном кодировании метки типа ветвление можно сделать за O(1) на таблице независимо от числа вариантов. Здравствуй ООП-like полиморфизм.
VE>Что такое "интерпретация памяти"? Когда мы compile-time знаем, какого типа данные лежат в памяти? Ну вот знаем теперь, и что?
Если уйдут парные операции запаковки/распаковки — то то. Избавишься от лишних затрат, связанных с динамической распаковкой. Я кстате постоянно критикую увлечение подражательством этой технике на других языках — на дотнете/C#, например, где эту технику непосредственно вручную эмулируют. Мне возражают — это удобства ради. Т.е. это выходит такой способ группировки операций через объединение данных. ИМХО, почти всегда можно обойтись без группировки данных, проведя преобразования кода, которые ты предлагал. Ну, кроме случая зафиксированности таких данных во внешнем контракте, который будет открыт для реализации извне.
V>>Далее. Должен существовать оператор динамической проверки и приведения типа, где на входе этого оператора будет неуточненный тип выражения, а на выходе — уточненный. Заметь, приведение к объемлющему типу происходит "бесплатно": для С++ в худшем случае константное смещение указателя/ссылки, если база не первая в списке, а для Хаскеля — это безусловное конструирование АлгТД. Зато переход от объемлющего типа к уточненному требует или dynamic_cast в С++, или динамическое приведение в яве/дотнете, или ПМ в Хаскеле/Немерле. Т.е. первая операция выполняется за O(1), то вторая за O(n), где n — общее кол-во тестируемых уточненных типов.
VE>Т.е. ПМ в Haskell выполняется за O(n), да?
ХЗ. Мне недавно сказали, что в GHC кодирует не последовательные константы для юзверских АлгТД, а некую ссылку на описатель. Выходит, прямая табличная диспетчеризация недоступна при ветвлении по метке конструктора.
VE>Давайте разбираться.
VE>На вход мы даём выражение одного типа, на выходе (возможно) получаем другое выражение другого типа, так ещё и с другим адресом. VE>Под эти свойства подходит даже взятие элемента массива или доступ к полю объекта. Или разыменование указателя.
И что? Ты ведь сам показал в своих преобразованиях, что почти всегда этого можно НЕ делать. Т.е. если решать задачу таким же образом как в Хаскеле — то да, придется эмулировать работу АлгТД, никто не спорит. Но ведь можно не складывать типы в мешок, можно ведь протаскивать не данные в некий контракт, а наоборот, применить DI и затребовать типизированный обработчик-визитор (твой кортеж типизированных ф-ий). Классика жанра, однако.
VE>Я тут пытался описать свойства такой функции. VE>Так вот на мой взгляд эти свойства выглядит так: VE>
VE>-- каст туда-обратно гарантированно возвращает то же выражение
VE>dynamicCast (cast x) = Just x
VE>-- если каст успешен, то исходное выражение было получено кастом в обратную сторону
VE>(dynamicCast e = Just v) -> (e = cast v)
VE>
VE>Если будешь дополнять, то лучше псевдокодом, а не словами.
Не буду. Я многократно соглашался, что от dynamic_cast убежать более чем легко. Ты мне предлагаешь убежать не через пересмотр всего решения, а через техники-заменители, которые ни разу не изменяют исходное решение. Смысл? Количество if-ов, как ты правильно заметил, в этом случае НЕ изменится. Т.е. то ли ты проверяемый признак загонишь в систему типов, то ли в поле объекта, но если ты не сумел сделать перетащить этот признак из данных в поведение, то кол-во телодвижений будет одинаковое, с точностью до несущественных деталей.
VE>Но вот беда, для моего случая как динамика подходит указатель. int мы можем преобразовать в int*, а обратно — если указатель не равен 0.
Для случая maybe аналогично. Можно поинтересоваться, ты хотел что-то показать этим, или просто вслух рассуждаешь?
VE>Хуже того, int мы можем преобразовать в std::pair<bool, std::pair<int, float> >, а обратно — second.first или second.second в зависимости от флага. Перечисленным выше свойствам это удовлетворяет. VE>Я догадываюсь, какое свойство ты захочешь ввести, но попробуй его формализовать, и наверняка всплывут двойные трактовки. "Интуитивное" понимание меня волнует мало.
Зато я не догадываюсь, о чем догадываешься ты.
Поясни. Как системщик по образованию и призванию, я не делаю принципиальное различие м/у способами кодирования данных. Угу. Потому что при смене кодирования, пространство состояний (как минимум валидных состояний, т.е. интересующих нас), остается неизменно. Удачное кодирование данных может упростить схему, т.е. удешевить каждую/некоторую операцию в отдельности, но не изменить кол-во самих операций в координатах выбранного пространства состояний. Ты же пока упорно ставишь эксперименты в области кодирования этого пространства, доказывая (якобы доказывая), что кол-во операций при этом не изменится... Блин, но я это и так уже почти 20 лет прекрасно знаю. Вот что мне тебе на это отвечать? Давай уж тогда перейдем к вопросам оптимального кодирования состояний, коль оно тебя так волнует... будет чуть поинтересней... бо, скажем прямо, обсуждение maybe на указателях и прочий детсад малость потребляет терпение...
V>>Дык, а чего предлагать? В Хаскеле ты требуемый признак вложил в систему типов программы (Maybe), а в С++ этот признак искуственный, проверяется вручную.
VE>Правильно. Но какая разница, вручную или нет, это ведь останется динамической типизацией. То, что в Хаскеле закладывается в систему типов (Maybe, Either, any other ADT), в C++ придётся реализовать искусственно, а значит от "телодвижений в рантайм" никуда не деться.
Еще как деться. Ты же сам недавно показал неплохие преобразования. Кол-во операций ИЗМЕНЯЕТСЯ, потому что изменяется кол-во состояний. В твоем примере преобразования изчезало промежуточное состояние Either, т.е. изчезали все накладные расходы,связанные с его обслуживанием.
VE>По поводу реинтерпретации памяти. Мне не нравится это интуитивное понятие, потому что на самом нижнем уровне типов уже нет. У нас указатели и вызовы функций, принимающие указатели. Тот же Either a b можно представить как просто флаг и указатель void*.
Здравствуйте, D. Mon, Вы писали:
V>>Почему попытку разобраться в реализации всё время пытаются объявить "смешиванием"?
DM>Я согласен, что представлять, во что превращаются данные в памяти, нередко полезно и иногда даже необходимо. Но это просто знание подробностей компилятора. Хорошее, полезное знание. Просто не надо эту информацию толкать обратно в язык и говорить, что "на самом деле" там типы такие и такие. Нет, "на самом деле" компиляторов может быть много, и определение языка от них не должно зависеть.
Это малость не так. Например, даже в этом обсуждении была обнаружена как минимум пара ограничений на реализацию обсуждаемой системы типов. Т.е. такие ограничения можно вывести вообще без знания о реализации конкретного компилятора.
DM>Если вбить себе в голову, что такой-то тип представлен именно так, а не иначе, это может привести к проблемам, когда оптимизатор вдруг возьмет и сделает по-другому. Это даже в Си ежедневно случается, что уж говорить о более сложных языках.
И в современных оптимизаторах (т.е. суперкомпиляторах, по-сути) тоже никакой магии.
На сегодняшний день глубина просмотра вложеностей лидеров оптимизирующих компиляторов (а это С++ и ничего кроме С++) — порядка десяти уровней. Для того, чтобы скомипилять далеко не самые большие проги с полной оптимизацией, даже на линуксах уже требуются 2 гига оперативки под консолью. А каждый +1 к уровню просмотра оптимизации — это +1 к степени по фиг его знает какому основанию (сколько там ветвлений в средней процедуре?).
Т.е. даже возможности оптимизации современных компиляторов тоже надо предствлять себе, бо эти возможности ограничиваются объективными вещами — характеристиками сегодняшнего ходового железа.
Здравствуйте, vdimas, Вы писали:
DM>>Если вбить себе в голову, что такой-то тип представлен именно так, а не иначе, это может привести к проблемам, когда оптимизатор вдруг возьмет и сделает по-другому. Это даже в Си ежедневно случается, что уж говорить о более сложных языках.
V>На сегодняшний день глубина просмотра вложеностей лидеров оптимизирующих компиляторов (а это С++ и ничего кроме С++) — порядка десяти уровней.
Ну причем тут это. Вон, в хаскеле оптимизатор умеет какие-то промежуточные списки вообще выкидывать, используя fusion и rewriting rules. Видишь в коде список, думаешь, что знаешь как он устроен в памяти, а его на деле вообще может там не оказаться. Или даже проще — тупл. Ты можешь знать, как обычно туплы представлены в памяти, но в конкретном коде при передаче тупла из функции его компоненты могут быть переданы через стек без выделения памяти в куче. И т.д. Вряд ли найдется человек, четко представляющий все-все-все трюки GHC или современных С++ компиляторов.
Здравствуйте, D. Mon, Вы писали:
M>>Т.е. тип значения A a1 a2 ... — Tuple(A1,A2,..), так что ли? DM>Хаскельный алгебраик — это сумма (копроизведение) произведений. Так что формально T — это сумма Tuple(A1, A2, ...) и Tuple(B1, B2, ...). Каждый из них — отдельный тип, их сумма — третий тип, отличный от обоих.
Вопрос был вполне конкретный.
Ок, с другой стороны зайду. Понятие типа включает в себя операции над ним? Если да, то есть операции над типом Tuple(A1, A2...)? Есть. Можно ли их использовать для значений A a1 a2? Нет. И наоборот — операций над "типом" A не бывает. Только над общим типом T. Даже A -> Tuple не может быть операции. Только T -> Maybe Tuple.
Например, в Scala это не так, а в Haskell так: A — не тип. Мы можем использовать его как тапл только через разбор, например, катаморфизм.
В общем-то это и хотелось узнать: понятие типа для vdimas включает или нет операции над ним?
Ну, в хаскеле все еще прозрачней. В данном примере А — это функция, она принимает набор значений типов (A1, A2, ...) и возвращает значение типа T. Соответственно, какие-то операции мы можем делать с ее аргументами, это один тип, какие-то другие — с получаемым значением, это другой тип (T), а с самой А мы можем делать то, что позволительно делать с функциями, это третий набор операций.
"А a1 a2 ..." имеет тип Т, для него применимы операции с Т. "(a1, a2,...)" имеет другой тип, там другие операции доступны.
Тут есть еще тонкость тупл там или просто несколько аргументов, но с учетом карринга будем считать это несущественным.
А вот входят ли операции над типом в его определение — вопрос сложный и неоднозначный. Некоторые говорят, что входят. Мое мнение — не входят. Эти операции сами имеют свои типы, определяемые через типы аргументов, так что тип аргументов уже должен быть определен к моменту описания операций.
Здравствуйте, D. Mon, Вы писали:
DM>Ну, в хаскеле все еще прозрачней. В данном примере А — это функция, она принимает набор значений типов (A1, A2, ...) и возвращает значение типа T. Соответственно, какие-то операции мы можем делать с ее аргументами, это один тип, какие-то другие — с получаемым значением, это другой тип (T), а с самой А мы можем делать то, что позволительно делать с функциями, это третий набор операций.
Это не имеет отношения к вопросу.
DM>"А a1 a2 ..." имеет тип Т, для него применимы операции с Т. "(a1, a2,...)" имеет другой тип, там другие операции доступны.
Да. Обратите внимание, что по vdimas у A a1 a2 уточнённый тип (A1, A2)
DM>Тут есть еще тонкость тупл там или просто несколько аргументов, но с учетом карринга будем считать это несущественным.
Это всё неважно.
DM>А вот входят ли операции над типом в его определение — вопрос сложный и неоднозначный. Некоторые говорят, что входят. Мое мнение — не входят. Эти операции сами имеют свои типы, определяемые через типы аргументов, так что тип аргументов уже должен быть определен к моменту описания операций.
Давайте попробуем как-то с понятием разобраться. data T = A ... | B ... У значений A ... и B ... — один тип или разный? У выражений if flag then A ... else B ... и if not flag then A ... else B ... — один тип или разный?
Здравствуйте, vdimas, Вы писали:
VE>>Правильно. Но какая разница, вручную или нет, это ведь останется динамической типизацией. То, что в Хаскеле закладывается в систему типов (Maybe, Either, any other ADT), в C++ придётся реализовать искусственно, а значит от "телодвижений в рантайм" никуда не деться.
V>Еще как деться. Ты же сам недавно показал неплохие преобразования. Кол-во операций ИЗМЕНЯЕТСЯ, потому что изменяется кол-во состояний.
Странно, система типов одна, код один, а кол-во операций меняется. А динамическая типизация при этом убирается?
V>В твоем примере преобразования изчезало промежуточное состояние Either, т.е. изчезали все накладные расходы,связанные с его обслуживанием.
Spineless Tagless G-machine.
Только эти преобразования могут быть целиком на совести компилятора.
Здравствуйте, mima, Вы писали:
M>Давайте попробуем как-то с понятием разобраться. data T = A ... | B ... У значений A ... и B ... — один тип или разный? У выражений if flag then A ... else B ... и if not flag then A ... else B ... — один тип или разный?
Здравствуйте, D. Mon, Вы писали:
DM>Ну причем тут это. Вон, в хаскеле оптимизатор умеет какие-то промежуточные списки вообще выкидывать, используя fusion и rewriting rules. Видишь в коде список, думаешь, что знаешь как он устроен в памяти, а его на деле вообще может там не оказаться. Или даже проще — тупл. Ты можешь знать, как обычно туплы представлены в памяти, но в конкретном коде при передаче тупла из функции его компоненты могут быть переданы через стек без выделения памяти в куче. И т.д. Вряд ли найдется человек, четко представляющий все-все-все трюки GHC или современных С++ компиляторов.
Я удивляюсь, как можно одновременно ставить во главу угла представление типа в памяти и одновременно плевать на то, как значение типа будет (и будет ли вообще) представлено в программе.
