Я изо всех сил пытаюсь понять цель универсального и экзистенциального количественного определения типов. Я играю с написанием игрушечного языка, основанного на исчислении конструкций . Я читал о Морте и Хенке, чтобы помочь мне лучше понять.
Я не понимаю, почему у CoC есть и лямбда, и полная абстракция.
( Λ х : . Б )
( ∀ х : . Б )
Мне кажется, что лямбда входит в систему, где типы передаются вручную. Другими словами, что следующее
( ∀ x : ∗ . Λ a : x . A )
Может быть заменено на
( λ x : ∗ . λ a : x . a )
Если это было впервые применено к используемому типу.
Что мне не хватает? Какие газеты, блоги или статьи можно прочитать, которые могут мне помочь?
Это помогает помнить, что (или как вы иногда видите) является типом. Это обобщает . Поэтому, хотя и имеет смысл сказать , не имеет смысла говорить потому что - это просто тип. Вы бы не сказали потому не для вычислений как таковых, а для классификации лямбда-терминов, которые могут применяться следующим образом .П → ( λ х : . М ) N ( ∀ х : . М ) N ∀ . , , ( A → B ) N →∀Π→( Λ х : . М) N( ∀ х : . М) N∀ . , ,( A → B ) N→
Это было то, что сбило меня с толку, но именно так определяется исчисление конструкций (как и любой другой зависимой типизированной системы).
Две программы, которые вы написали, имеют очень разные намерения, и первая из них имеет неверный тип. Не имеет смысла говорить потому что требует оба аргумента по типам, что означает, что если должен быть хорошо типизирован, мы должны есть . Тем не менее, не является типом, ему может быть назначен только тип формы , никогда . Второй один с другой стороны, почти (я думаю , что вы имели в виду , чтобы вернуть не ) является функцией и задается тип , используя два s.∀ ∀ х : . B B : ∗ λ x . х ∀ х : . B ∗ a x ∀∀ х : . λ x . Икс∀∀ х : . ВB : ∗λ x . Икс∀х : . В*aИкс∀
Не совсем. Я все еще немного смущен. Возможно, мне придется больше думать об этом. Я изменил как пример программу для возвращения вместо й , так как я пытался реализовать я d . :)aИкся д
oconnor0
Я думаю, что на каком-то уровне я хотел сделать термины и типы одинаковыми. Между вашим ответом и cs.stackexchange.com/questions/49531/… Я думаю, что вижу, где я ошибся. Я хочу сделать это в сильно нормализующей системе.
oconnor0
5
Имейте в виду, что экзистенциальные и универсальные типы довольно различны. Это конструктивная логика, а не классическая логика и в конструктивной логике и ∃ не так связаны, как в классической логике.∀∃
- это тип программ, которые получают объект типа A и возвращают объект типа B ( x ) . Здесь важно то, что тип B ( x ) зависитот x и не одинаков для всех x . Это может варьироваться в зависимости от того, что х . Для одного ввода x мы можем вывести целое число. Для другого мы могли бы вывести реальное число. Для еще одного мы могли бы вывести функцию над действительными числами. Если B ( х )∀ х : . Б ( х )AБ ( х )Б ( х )ИксИксИксИксБ ( х )не изменяется с , то вы можете использовать A → B в месте , которое является типом функций от А до B .ИксA → BAВ
являетсязависимойверсией (конструктивной) дизъюнкции. Вы можете думать о конструктивной дизъюнкции A ∨ B двух типов A и B , как несвязное объединение A и B .
∃ х : . В ( х ) является объединением непересекающихся коллекции типов B ( х ) ,
индексированного х : . Дело в том, что типа Б (∃ х : . Б ( х )A ∨ BAВAВ∃ х : . Б ( х )Б ( х )х : А van изменяется в зависимости от значения x : A
делает его зависимым типом. Сравнение со случаемкогда Б не зависит от х : А : ∃ х : А . B . Мы принимаем одну копию того же B для каждого х : А . Это изоморфно × B .Б ( х )х : АВх : А∃ х : .ВВх : АA × B
Теперь вы можете спросить, зачем нам нужны зависимые продукты и типы сумм? Потому что они дают нам больше выразительной силы. Теперь мы можем полностью игнорировать типы и иметь нетипизированную теорию типов / функциональное программирование. Но это устраняет преимущества наличия типов во-первых, например, вы не будете знать, будут ли все программы завершаться всегда (строгая нормализация). См. Лямбда-куб и
Зависимый тип . Я думаю, что хороший способ хорошо понять зависимые типы - это посмотреть на правила для введения и устранения зависимых типов в теории типов Мартина-Лофа .
Суть зависимых типов заключается в следующем: мы хотим оставаться в хорошей типизированной теории по разным причинам (например, избегать ошибок, автоматического доказательства завершения и т. Д.). Мы не хотим переходить к чему-то вроде нетипизированного лямбда-исчисления, где мы можем сделать выражения, подобные тем, которые вы заявили, и гораздо более мощные вещи. Можно сказать, что зависимые типы были изобретены, чтобы позволить выражать больше вещей, оставаясь при этом в хорошей теории типов.
Имейте в виду, что экзистенциальные и универсальные типы довольно различны. Это конструктивная логика, а не классическая логика и в конструктивной логике и ∃ не так связаны, как в классической логике.∀ ∃
- это тип программ, которые получают объект типа A и возвращают объект типа B ( x ) . Здесь важно то, что тип B ( x ) зависитот x и не одинаков для всех x . Это может варьироваться в зависимости от того, что х . Для одного ввода x мы можем вывести целое число. Для другого мы могли бы вывести реальное число. Для еще одного мы могли бы вывести функцию над действительными числами. Если B ( х )∀ х : . Б ( х ) A Б ( х ) Б ( х ) Икс Икс Икс Икс Б ( х ) не изменяется с , то вы можете использовать A → B в месте , которое является типом функций от А до B .Икс A → B A В
являетсязависимойверсией (конструктивной) дизъюнкции. Вы можете думать о конструктивной дизъюнкции A ∨ B двух типов A и B , как несвязное объединение A и B . ∃ х : . В ( х ) является объединением непересекающихся коллекции типов B ( х ) , индексированного х : . Дело в том, что типа Б (∃ х : . Б ( х ) A ∨ B A В A В ∃ х : . Б ( х ) Б ( х ) х : А van изменяется в зависимости от значения x : A
делает его зависимым типом. Сравнение со случаемкогда Б не зависит от х : А : ∃ х : А . B . Мы принимаем одну копию того же B для каждого х : А . Это изоморфно × B .Б ( х ) х : А В х : А ∃ х : .В В х : А A × B
Теперь вы можете спросить, зачем нам нужны зависимые продукты и типы сумм? Потому что они дают нам больше выразительной силы. Теперь мы можем полностью игнорировать типы и иметь нетипизированную теорию типов / функциональное программирование. Но это устраняет преимущества наличия типов во-первых, например, вы не будете знать, будут ли все программы завершаться всегда (строгая нормализация). См. Лямбда-куб и Зависимый тип . Я думаю, что хороший способ хорошо понять зависимые типы - это посмотреть на правила для введения и устранения зависимых типов в теории типов Мартина-Лофа .
Суть зависимых типов заключается в следующем: мы хотим оставаться в хорошей типизированной теории по разным причинам (например, избегать ошибок, автоматического доказательства завершения и т. Д.). Мы не хотим переходить к чему-то вроде нетипизированного лямбда-исчисления, где мы можем сделать выражения, подобные тем, которые вы заявили, и гораздо более мощные вещи. Можно сказать, что зависимые типы были изобретены, чтобы позволить выражать больше вещей, оставаясь при этом в хорошей теории типов.
источник