Что такое зависимая набор?

StackOverflow https://stackoverflow.com/questions/9338709

Вопрос

Может ли кто -нибудь объяснить мне иждивенную набор? У меня мало опыта в Haskell, Cayenne, Epigram или других функциональных языках, поэтому, чем проще вы можете использовать, тем больше я буду ценить это!

Это было полезно?

Решение

Рассмотрим это: во всех приличных языках программирования вы можете написать функции, например,

def f(arg) = result

Здесь, f берет ценность arg и вычисляет значение result. Анкет Это функция от значений до значений.

Теперь некоторые языки позволяют вам определить полиморфные (aka generic) значения:

def empty<T> = new List<T>()

Здесь, empty принимает тип T и вычисляет значение. Это функция от типов до значений.

Обычно вы также можете иметь определения общего типа:

type Matrix<T> = List<List<T>>

Это определение принимает тип, и оно возвращает тип. Его можно рассматривать как функцию от типов до типов.

Так много для того, что предлагают обычные языки. Язык называется зависимо напечатанным, если он также предлагает 4 -ю возможность, а именно определение функций от значений до типов. Или, другими словами, параметризация определения типа по значению:

type BoundedInt(n) = {i:Int | i<=n}

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

def min(i : Int, j : Int) : BoundedInt(j) =
  if i < j then i else j

Здесь тип результата функции зависит от На фактическом значении аргумента j, таким образом, терминология.

Другие советы

Если вы узнаете C ++, легко дать мотивирующий пример:

Допустим, у нас есть тип контейнера и два экземпляра

typedef std::map<int,int> IIMap;
IIMap foo;
IIMap bar;

и рассмотрим этот фрагмент кода (вы можете предположить, что Foo не пустые):

IIMap::iterator i = foo.begin();
bar.erase(i);

Это очевидный мусор (и, вероятно, повреждает структуры данных), но он будет хорошо проверять, так как «Итератор в Foo» и «Итератор в бар»-это тот же тип,-это один и тот же тип. IIMap::iterator, хотя они совершенно несовместимы семантически.

Проблема в том, что тип итератора не должен зависеть только от контейнера тип Но на самом деле в контейнере объект, т.е. это должен быть «нестатический тип члена»:

foo.iterator i = foo.begin();
bar.erase(i);  // ERROR: bar.iterator argument expected

Такая особенность, способность выражать тип (foo.iterator), которая зависит от термина (Foo), - это именно то, что означает зависимое печатание.

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

Зависимые типы позволяют большему набору логические ошибки быть исключенным в Время компиляции. Анкет Чтобы проиллюстрировать это, рассмотрим следующую спецификацию по функции f:

Функция f должен взять только даже целые числа в качестве входных данных.

Без зависимых типов вы можете сделать что -то вроде этого:

def f(n: Integer) := {
  if  n mod 2 != 0 then 
    throw RuntimeException
  else
    // do something with n
}

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

f(1)    // compiles OK despite being a logic error!

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

Теперь зависимые типы позволяют вам быть намного более выразительными и позволили бы вам написать что -то подобное:

def f(n: {n: Integer | n mod 2 == 0}) := {
  // do something with n
}

Здесь n имеет зависимый тип {n: Integer | n mod 2 == 0}. Анкет Это может помочь прочитать это вслух как

n является членом набора целых чисел, так что каждое целое число делится на 2.

В этом случае компилятор обнаружит во время компиляции логическую ошибку, когда вы передали нечетное число f и предотвратит выполнение программы в первую очередь:

f(1)    // compiler error

Вот иллюстративный пример с использованием Scala зависящие от пути типы о том, как мы могли бы попытаться реализовать функцию f удовлетворение такого требования:

case class Integer(v: Int) {
  object IsEven { require(v % 2 == 0) }
  object IsOdd { require(v % 2 != 0) }
}

def f(n: Integer)(implicit proof: n.IsEven.type) =  { 
  // do something with n safe in the knowledge it is even
}

val `42` = Integer(42)
implicit val proof42IsEven = `42`.IsEven

val `1` = Integer(1)
implicit val proof1IsOdd = `1`.IsOdd

f(`42`) // OK
f(`1`)  // compile-time error

Ключ - заметить, как значение n появляется в типе значения proof а именно n.IsEven.type:

def f(n: Integer)(implicit proof: n.IsEven.type)
      ^                           ^
      |                           |
    value                       value

Мы говорим тип n.IsEven.type зависит от ценность n Отсюда и термин зависимые типы.

Цитирование типов книг и языков программирования (30,5):

Большая часть этой книги была связана с формализацией механизмов абстракции различных видов. В просто напечатанном лямбда-калькулус мы формализовали операцию по сбору термина и абстрагируют SUBERM, давая функцию, которая впоследствии может быть создана путем применения его к разным терминам. В системеF, Мы рассмотрели операцию по сбору термина и абстрагируют тип, давая термин, который может быть создан путем применения его к различным типам. Вλω, Мы повторили механизмы простого типичного Lambda-Calculus «на один уровень вверх», выводя тип и абстрагируя субэкспрессию, чтобы получить оператора типа, который впоследствии можно создать путем применения к различным типам. Удобный способ мышления обо всех этих формах абстракции связан с семьями выражений, индексируемых другими выражениями. Обычная абстракция лямбда λx:T1.t2 Семья терминов [x -> s]t1 Индексируется по терминам s. Анкет Точно так же типовая абстракция λX::K1.t2 Семейство терминов, индексируемые типами, а оператор типа - это семейство типов, индексированных типами.

  • λx:T1.t2 Семейство терминов, индексированные терминами

  • λX::K1.t2 Семейство терминов, индексированные типами

  • λX::K1.T2 Семейство типов, индексированных типами

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top