Вопрос по types, existential-type, haskell, quantifiers, type-systems – Какова теоретическая основа для экзистенциальных типов?

66

Haskell Wiki хорошо объясняет, как использовать экзистенциальные типы, но я не совсем понимаю теорию, стоящую за ними.

Рассмотрим пример экзистенциального типа:

data S = forall a. Show a => S a      -- (1)

определить оболочку типа для вещей, которые мы можем преобразовать вString, В вики упоминается, что мыreally хочу определить тип как

data S = S (exists a. Show a => a)    -- (2)

то есть истинное "экзистенциальное" типа - слабо я думаю об этом как о "конструкторе данных"S принимает любой тип, для которогоShow примерexists и оборачивает это ". На самом деле, вы могли бы написать GADT следующим образом:

data S where                          -- (3)
    S :: Show a => a -> S

Я не пытался скомпилировать это, но похоже, что оно должно работать. Для меня GADT, очевидно, эквивалентен коду (2), который мы хотели бы написать.

Однако для меня совершенно не очевидно, почему (1) эквивалентно (2). Почему перемещение конструктора данных наружу превращаетforall вexists?

Самая близкая вещь, о которой я могу думать,Законы де Моргана в логике, где смена порядка отрицания и квантификатора превращает экзистенциальные квантификаторы в универсальные квантификаторы, и наоборот:

¬(∀x. px) ⇔ ∃x. ¬(px)

но конструкторы данных кажутся совершенно отличным от оператора отрицания.

Какая теория лежит в основе способности определять экзистенциальные типы, используяforall вместо несуществующегоexists?

Ваш Ответ

3   ответа
6

на которую вы ссылаетесь. Я заимствую некоторые строки кода и комментарии из него и попытаюсь объяснить.

data T = forall a. MkT a

Здесь у вас есть типT с конструктором типаMkT :: forall a. a -> T, право?MkT является (примерно) функцией, поэтому для каждого возможного типаa, функцияMkT иметь типa -> T. So, we agree that by using that constructor we may build values like [MkT 1, MkT 'c', MkT "hello"]все они типаT.

foo (MkT x) = ... -- what is the type of x?

Но что происходит, когда вы пытаетесь извлечь (например, путем сопоставления с шаблоном) значение, заключенное вT? Его тип аннотации говорит толькоTбез какой-либо ссылки на тип значения, фактически содержащегося в нем. Мы можем только согласиться с тем фактом, что, что бы это ни было, оно будет иметь один (и только один) тип; как мы можем заявить об этом в Хаскеле?

x :: exists a. a

Это просто говорит о том, что существует типa которомуx принадлежит. На этом этапе должно быть ясно, что, удаливforall a отMkTопределение и путем явного указания типа переносимого значения (то естьexists a. a), мы можем достичь того же результата.

data T = MkT (exists a. a)

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

10

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

Mitchell, John C.; Plotkin, Gordon D.; Abstract Types Have Existential Type, ACM Transactions on Programming Languages and Systems, Vol. 10, No. 3, July 1988, pp. 470–502

На высоком уровне,

Abstract data type declarations appear in typed programming languages like Ada, Alphard, CLU and ML. This form of declaration binds a list of identifiers to a type with associated operations, a composite “value” we call a data algebra. We use a second-order typed lambda calculus SOL to show how data algebras may be given types, passed as parameters, and returned as results of function calls. In the process, we discuss the semantics of abstract data type declarations and review a connection between typed programming languages and constructive logic.

ссылка на PDF:theory.stanford.edu/~jcm/papers/mitch-plotkin-88.pdf
53

взгляните на «переписку Карри Ховарда». в котором говорится, что типы в компьютерной программе соответствуют формулам в интуиционистской логике. Интуиционистская логика похожа на «обычную» логику, которую вы выучили в школе, но без закона исключения из среднего или двойного отрицания:

Not an axiom: P ⇔ ¬¬P (but P ⇒ ¬¬P is fine)

Not an axiom: P ∨ ¬P

Laws of logic

Вы находитесь на правильном пути с законами DeMorgan, но сначала мы собираемся использовать их, чтобы получить некоторые новые. Соответствующая версия законов DeMorgan:

∀x. P(x) = ¬∃x. ¬P(x) ∃x. P(x) = ¬∀x. ¬P(x)

Мы можем получить (& # x2200; x. P & # x21D2; Q (x)) & # xA0; = & # xA0; P & # x21D2; (& # x2200; x. Q (x)):

(∀x. P ⇒ Q(x)) (∀x. ¬P ∨ Q(x)) ¬P ∨ (∀x. Q(x)) P ⇒ (∀x. Q)

И (& # x2200; x. Q (x) & # x21D2; P) & # xA0; = & # xA0; (& # x2203; x. Q (x)) & # x21D2; P (этот используется ниже):

(∀x. Q(x) ⇒ P) (∀x. ¬Q(x) ∨ P) (¬¬∀x. ¬Q(x)) ∨ P (¬∃x. Q(x)) ∨ P (∃x. Q(x)) ⇒ P

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

Simple Types

С простейшими типами легко работать. Например:

data T = Con Int | Nil

Конструкторы и методы доступа имеют следующие сигнатуры типов:

Con :: Int -> T
Nil :: T

unCon :: T -> Int
unCon (Con x) = x
Type Constructors

Теперь давайте рассмотрим конструкторы типов. Возьмите следующее определение данных:

data T a = Con a | Nil

Это создает два конструктора,

Con :: a -> T a
Nil :: T a

Конечно, в Haskell переменные типа неявно универсально определены количественно, так что это действительно:

Con :: ∀a. a -> T a
Nil :: ∀a. T a

И доступ так же прост:

unCon :: ∀a. T a -> a
unCon (Con x) = x
Quantified types

Давайте добавим экзистенциальный квантификатор & # x2203; к нашему исходному типу (первый, без конструктора типа). Вместо того, чтобы вводить его в определение типа, которое не похоже на логику, введите его в определения конструктора / средства доступа, которые выглядят как логика. Мы исправим определение данных позже, чтобы соответствовать.

ВместоIntтеперь будем использовать∃x. t, Вот,t это какое-то выражение типа.

Con :: (∃x. t) -> T
unCon :: T -> (∃x. t)

Основываясь на правилах логики (второе правило выше), мы можем переписать типCon чтобы:

Con :: ∀x. t -> T

Когда мы переместили экзистенциальный квантификатор наружу (форма prenex), он превратился в универсальный квантификатор.

Таким образом, следующие теоретически эквивалентны:

data T = Con (exists x. t) | Nil
data T = forall x. Con t | Nil

За исключением того, что нет синтаксиса дляexists в Хаскеле.

В неинтуиционистской логике допустимо выводить следующее из типаunCon:

unCon :: ∃ T -> t -- invalid!

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

Sources

«Полиморфизм первого класса с выводом типа», Марк П. Джонс, Труды 24-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования (Web)

Совершенно верно, исправлено. Относительно легко получить противоречие из & quot; P & # x2227; & # xAC; P & quot ;, поскольку & quot; P & # x2227; & # XAC; Р & Quot; обычно используется в качестве определения самого противоречия.
Я считаю, что вы должны заявитьNot a theorem: P ⇔ ¬¬P и т.д. Это действительно не имеет значения, аксиома это или нет, важно то, что это не теорема интуиционистской логики.
Приветствия. И, если можно, исключение двойного отрицания и исключенное среднее эквивалентны, поэтому аксиомы классической логики упоминают только одну из них. Строго говоря, они также эквивалентны закону Пирса, который имеет смысл использовать только логическое следствие (закон таков: ((P & # x21D2; Q) & # x21D2; P) & # x21D2; P ). Закон Пирса соответствует СНcall/cc.
Мне было трудно неформально разобраться∀x. (Q(x) ⇒ P)  & # X21D4;∃x. Q(x) ⇒ P, Я бы перевел это так:For all x: if x is a red cat, then Hans is scared. & # X21D4;If there exists at least one red cat, then Hans is scared, ТакQ(x) = x is a red cat? а такжеP = Hans is scared, Это сделало это очевидным для меня. Не уверен, если это поможет кому-то еще.
@DietrichEpp: Зависимые пары кодируют экзистенциальную квантификацию по CH. Например, (& # x2203; n) n + 1 = 2 будет закодировано какΣ[ n ∶ ℕ ] (n + 1 ≡ 2)тогда доказательство состоит из свидетеля и доказательства того, что свидетель удовлетворяет предложению, например(1 , refl) (ты можешь читатьrefl как "следует из определения"). Сравните это с зависимыми функциями, которые кодируют универсальное количественное определение. Функция типа(n : ℕ) → n ≡ 0 + n превращает произвольное натуральное число в доказательство того, чтоn = 0 + n.

Похожие вопросы