Зависимые типы для проверки структурированных данных

Question

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

Но мой вопрос касается зависимых типов данных, а не программ, как или мы можем использовать их для проверки структурированных данных?То есть, как json или xml или структурированные данные любого типа, можно ли их эффективно проверить с помощью некоторой системы зависимых типов?

Редактировать:

Я имел в виду под зависимыми типами наиболее широкое определение «тип, зависящий от значения», и не нужно, чтобы те, кто проверял теорему, и сотрудники CoC.Я не знаю их, и я не хочу идти по этому пути, я не верю, что это единственный и «окончательный» способ получить достойных зависимых типов.В FP кодеры пишут свою самую сложную логику каждый день очень элегантно, конструктивно, со всей простотой и без проблем.Я верю, что у них будет их окончательная «элегантная» зависимая печать.

Однако мой вопрос был о чистых данных, в отличие от кода, когда большая часть проверок может быть просто ненужной и может просто скрываться в потоке программы и логике, даже динамическая типизация может нормально работать таким образом.В данных это не тот случай, когда вы хотите проверить правильность некоторых документов и дать четкие сообщения об ошибках.С другой стороны, у данных нет проблемы сложности, когда вам приходится иметь дело с «функциями» в очень экстремальной системе зависимых типов (семейства CoC).

Answer 1

Возможно, вам будет интересна эта статья: Следующие 700 языков описания данных (PDF) , Кэтлин Фишер, Ицхак Мандельбаум и Дэвид Уокер, 2006.

Основная цель этой статьи - начать понимать семью специальные языки обработки данных. Мы делаем это, как сделал Ландин, разработка семантической структуры для определения, сравнения и контрастные языки в нашем домене. Эта семантическая структура вращается вокруг определения исчисления описания данных (DDC ^ α). это исчисление использует типы из теории зависимых типов для описания различных формы специальных данных: базовые типы для описания атомарных фрагментов данных и конструкторы типов для описания более богатых структур. Мы показываем, как дать денотационная семантика к DDC ^ α путем интерпретации типов как синтаксического анализа функции, которые отображают внешние представления (биты) в структуры данных в типизированном лямбда-исчислении. Точнее, эти парсеры производят оба внутренние представления внешних данных и дескрипторы разбора которые точно указывают на ошибки в оригинальном источнике.

Короче говоря: да, зависимые типы необходимы, если вы хотите статически кодировать детализированные инварианты ваших данных. Будучи более выразительными, чем алгебраические типы данных и GADT, они также позволяют выражать их и связанные с ними конструкции (например, комбинацию без тега объединения и маркированного продукта), имея возможность быть в некотором роде языком ассемблера описания данных, даже если пользовательская спецификация не раскрывает зависимости терминов напрямую.

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

(На дополнительном фронте относительно вашего введения в тролль: пожалуйста, идите вперед и играйте с ATS , Guru или Agda , они предназначены для относительно практического программирования Если вы хотите пойти по пути Франкенштейна, есть также SHE ; Coq , не предназначенный для того, чтобы быть «практичным для разработки программного обеспечения», но, как известно, злоупотребляли таким образом - Я бы не советовал это для зависимого типа программирования , но это хорошо для не очень зависимого программирования плюс сопроводительные доказательства корректности - и если вы хотите продать свою душу, есть также F * скоро.)

Answer 2

Я полагаю, что главная проблема с зависимыми типами в языке - это делает проверку типов (не говоря уже о выводе типов) неразрешимой проблемой. Это означает, что для некоторых программ компилятор будет вынужден войти в бесконечный цикл, просто оценивая типы, прежде чем он даже попадет в компиляцию.

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

Однако, что бы это эффективно добавило, это «слой времени компиляции» в вашем программировании, выполняющий полные вычисления по Тьюрингу в совершенно ином режиме, чем обычная программа. Я верю, что это уже можно сделать на некоторых языках; Я полагаю, что метапрограммирование шаблонов C ++ является полным по Тьюрингу, и система типов Scala может кодировать исчисление SKI в соответствии с блогом, который я однажды прочитал.

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

Лично я жду, будет ли разработан язык, который попытается решить все эти проблемы удобным для использования способом. Однако я совсем не удивляюсь, почему таких вещей уже не существует; это чертовски сложно решить проблемы!